I will be in my office late Tuesday.

Comp 372 Study Question ANSWERS
 
> 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. Suppose class Deriv is derived from class Base in C++.
> (a). Suppose we have the following declarations:
> 	Base b;
> 	Deriv d;
> What is the problem with the assignment
> 	b=d;
 
Slicing. Note that this isn't an issue in Java.
However, in C++ any added fields of Deriv are sliced off,
*and* any virtual functions revert to their definitions in Base.

> (b). Suppose we have the declarations
> 	Base ** pp; 
> 	Deriv ** qq;
> Explain the hole in the type system that would be introduced
> if we allowed the assignment pp = qq;
 
We have
	pp --> p --> b

	qq --> q --> b

*Suppose* we now allow pp = qq. This means that pp points to q:

	pp    p --> b
 	  \
           \
            \
	qq --> q --> b

Now we do
	*pp = p;	// *pp and &b are both of type (Base*)

but *pp is now an alias for q; this is the same as q=p,
and this pointer assignment IS IN THE WRONG DIRECTION.
It allows a deriv* pointer to become a base* pointer.

Oops.


This is a serious violation of an essential type rule!
If p is of type Base* then p can point to d, 
but the reverse (ie q pointing to b) is unsafe.

> ==============================================================
> 
> 3. What are the ML types of the following functions?
> 
> (a)  fun rev(nil, L) = L | rev(h::t, L) = rev(t, h::L);
 
('a list) * ('a list) -> 'a list

> (b)  fun foo(nil,    nil)    = nil
>       |  foo(h1::t1, h2::t2) = h1(h2) :: foo(t1, t2);  
 
Foo takes two list parameters. For the moment, assume they are 'a list
and 'b list. THe trick is to realize h1 is of type 'a and h2 is of type 'b,
and h1 is a *function* being applied to h2. Thus, h1 must really be
of type 'b->'c (the domain type is 'b because h2 is of type 'b).

The type of the first list is thus ('b->'c) list, and the entire type is

	('b->'c) list  * 'b list  ->  'c list

> (c)  fun c x = fn y => y*x;
 
THis is curried (and also ambiguous in SML93; I should have added
some indication that int multiplication was at stake). 
The type is
	int -> (int -> int)

That is, c(3) is a function int->int (called the tripling function).

> (d) The function c in (c) above is Curried. 
> Give the type of c(x), and also give an uncurried 
> equivalent uc(x,y).
 
fun uc(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 doues 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".