Comp 372 final exam study guide answers CORRECTED VERSION of Dec 14, 2004 > ============================================================== > > > 1. Consider the following DO loop in lisp: > (defun badfact (n) > (do > ((i 1 (1+ i)) > (prod 1 (* i prod))) > ((equal i n) prod))) ;; exit condition > > It doesn't quite work. > (a). Explain what (badfact 4) returns. The problem is that prod is multiplied by the "old" value of i each time; that is, the value of i before incrementing. When evaluating (badfact 4), the successive values of i at the end of the loop are 2,3,4, but we've multiplied prod by, successively, 1,2,3. The value 6, or 3!, is returned. > (b). Explain why DO* would fix this. (You may need to look up DO* > in the textbook). DO*, if you look this up (and you *won't* have this kind of thing on the real exam; I used this as a sample question for that reason) does the updates in *sequence*; that is, when we update prod to (* i prod) we use the *new* value of i. This fixes the loop. > (c). Fix it while leaving it as a DO (not DO*) loop. We can either update prod to (* (1+ i) prod), or we can change the termination condition to ((> i n) prod), which will continue until i=n+1 and the last factor in prod is n. > ============================================================== > > 2. Use the following Haskell function > looper (init, update, pred) > | pred(init) = looper(update(init), update, pred) > | otherwise = init > to write a call to looper that calculates the sum of 1 to N. The Java-style loop is as follows (where loop body is chosen so that the two assignments can be done in parallel): sum = 0; count = 1; while (count <=n) { sum = sum + count; count = count + 1; } The state is (count,sum). The initial value is (1,0). The predicate is mypred(c,s) = (c<=n) The update is myupdate(c,s) = (c+1, s+c) The call is thus looper ( (1,0), myupdate, mypred ) > ============================================================== > > 3. What are the types of the following Haskell functions? > (a) rev([], L) =L rev(h:t, L) = rev(t, h:L); ([a] , [a] ) -> [a] > (b) foo([], []) = [] > foo(h1:t1, h2:t2) = h1(h2) : foo(t1, t2); The first parameter is a list of functions a->b; the second is a list of values a to which the functions can be applied The function is in unCurried (tuple) form: ( [a->b] , [a] ) -> [b] > (c) c x = (\ y -> y*x) c 3 is the "tripling" function; c 2 is the "doubling" function etc. The type of c is int -> (int -> int) (The parentheses here can be dropped, and any num type is ok) (d) The type of c x is int->int; an uncurried version is c (x, y) = x*y > ============================================================== > 4. In class I gave the following CLOS example. I assumed that > classes Room and Word were defined, and that damControlRoom > was a particular Room. > > (defmethod response((r Room) (v Verb)) ...) ; definition 1 > > Then, to define response in damControlRoom, I defined > > (defmethod response ((r (eql damControlRoom)) (v (eql TURN))) ...) > ;; definition 2: interprets TURN VALVE in damControlRoom > > Finally I defined > (defmethod response ((r room) (v (eql TURN))) ...) > ; definition 3: default interpretation of TURN outside the damcontrolroom. > > (a). What function is applied if r is damControlRoom but v isn't TURN? definition 2 fails because v isn't TURN; so does definition 3. That leaves definition 1, which is not specific to damControlRoom. > (b). As things stand now, what function is applied if r isn't > damControlRoom but v *is* TURN? We would get definition 3, which is *probably* what we want. So far. > (c). Suppose I define swampRoom, and > (defmethod response ((r (eql swampRoom)) (v Verb))...) > Suppose swampRoom has no special interpretation for TURN. > What would happen if I tried to TURN something in swampRoom? We have a choice between the old (defmethod response ((r room) (v (eql TURN))) ...) and the new (defmethod response ((r (eql swampRoom)) (v Verb))...) The first is specific for the verb; the second is specific for the room. Unfortunately, CLOS finds the closest match on the first parameter before looking at the second, and so the second function would be invoked. However, it does *not* have a default interpretation for TURN, and so we'd be back to the I don't understand the verb "TURN" problem; TURN would be completely unrecognized in swampRoom. > (d). Explain why the problem of (c) might not be expected to > arise in practice. The definition of a method for an *arbitrary* verb is basically only used to handle undefined verbs. There would be *no* reason to provide a room-specific method to handle undefined verbs. We would handle TURN generally by (defmethod response ((r Room) (v (eql TURN))) ...) If swamproom offered no special method for TURN, this would then be the function called, as desired. > ============================================================== > 5. Suppose I write a function my_if(a, b, c); a is boolean, > and if it evaluates to true then we return b otherwise c. > However, I'm not too clever, and so my_if always evaluates > all three parameters in full before proceding (that is, > a, b, and c are ordinary value parameters). > > (a). What can go wrong with > my_if (x==0, 0, 1/x); When x==0, we return 0 but also *evaluate* 1/x, which may blow up. Note that this actually depends on hardware and on program-language semantics; for example, the current trend is for 1/0.0 *not* to cause any kind of exception but to simply return NaN ("not a number"). > (b). what can go wrong with > int fact(int n) { > return my_if(n==1, 1, n*fact(n-1)); > } This one is more serious. If n=1, we plan on returning 1, but we also evaluate fact(0) as part of the "then" clause. THis leads to infinite recursion overflow: fact(-1), fact(-2), .... > ============================================================== > 6. Lisp lets you attach essentially *anything* to the property > list of an atom, with > (get x 'key) > (setf (get x 'key) 'value) > Attempting to retrieve the value for an undefined key > simply results in nil. > > Write a function (calldynamic x y keyname default) that invokes > the attached function if present, and otherwise calls > (default_interpret y) (defun calldynamic (x y keyname default) (let ((int-fn (get x keyname))) (cond ((null int-fn) (funcall default y)) (t (funcall int-fn y)))) In other words, retrieve the function from the property list. If it's not there, then int-fn will be NIL and we call "default". > ============================================================== > 7. Parameters example > > Give a function foo(x,y) such that foo(a,b) gives > different values for value-result parameters, > reference parameters, and name parameters. There are lots of possibilities; here is one. Note, though, that you have to break the rules at least a little; reference and name are equivalent in the case that the actual parameters are distinct variables. In order for value-result to differ from referencing, we need ALIASING. Since the actual parameters are given as a,b; that is, two different variables, the example below introduces aliasing some other way. In order for call-by-name to be different, we need some dependency between a and b. foo(x, y) { x+=y; x+=y; a++; return x; } If we invoke a=2; b=3; foo(a,b); then call-by-value-result means x=2+3+3=8 at the end, and this is returned. Call-by-reference means that x==8 at the beginning of a++, but since x is an alias for a here this means a++ leaves us with x==9, which is then returned. If we make the call foo(a,a*a) (where the second parameter can no longer be a reference param), then call-by-name yields a += a*a; // a = 2*2 = 4 now a += a*a; // a = 4*4 = 16 now a++ // a = 17 now > ============================================================== > 8. Suppose Lisp evaluates expressions (as in minilisp) by > * evaluating the arguments > * binding the formal params to the respective arguments > (ie building LocalBindings) > * evaluating the body, evaluating symbols first by looking > for the frontmost entry on LocalBindings, and then by > looking for a global value. > Show the LocalBindings in effect at the point when the body of FOO > is evaluated in the following, and state what is printed: > (defun foo (x y z) (format t "x= ~A y= ~A z=~A" x y z u)) > (defun bar (y z u) (foo x y z)) > (setq x 2) > (setq y 3) > (setq z 4) > (setq u 5) > (a) (foo 10 11 12) We have the local bindings (x=10) (y=11) (z=12) and the output is 10 11 12 5 ;; 5 from global value of u > (b) (bar 10 11 12) We have local bindings (y=10) (z=11) (u=12) as we call (foo x y z); that is, (foo 2 10 11). The call to foo adds the bindings (x=2) (y=10) (z=11) so that the complete LocalBindings would be (note that when we look up a variable we stop at the FIRST match): (x=2) (y=10) (z=11) (y=10) (z=11) (u=12) In this environment, evaluating the body of FOO (ie printing x y z u) gives 2 10 11 12