Comp 372 Study Questions  Dordal  December, 2004

The exam will be open book, just like the midterm: you can use
the Haskell & Lisp books.

The following will NOT be on the exam: python, prolog, haskell IO

The following material may be covered on the exam:

Basic functions in Haskell and Lisp

Lambdas in Haskell and Lisp

General topics:
	Polymorphism
	functional v oo styles

Specific topics:
	Lisp Macros
		variable capture, multiple evaluation
		swap, ntimes
		extensibility of the language
	Lisp closures
	
Haskell types and functions
	Unification of Haskell types
		sum:: Num a => [a]->a
		length:  [a]->int
		What is type of [sum,length]?

Haskell "iteration":
	update: a->a
	pred:	a->bool
	init:	a
	
	looper (init, update, pred)
	   | pred(init) = looper(update(init), update, pred)
	   | otherwise  = init
   
	Getting this to work for a loop to find sum[1..n]
	
Parameters
	value
	result
	value-result
	reference
	aliasing
	const reference
	variable number of parameters
	short-circuit
	name

Evaluation
	Order of evaluation: left-to-right, right-to-left, compiler's-choice
	outer/top-down eval versus inner/bottom-up eval
	Haskell lazy evaluation
	Haskell lazy eval of functions defined with patterns or cases
	Infinite lists
		sumcubes n = sum (map (^3) [1..n]); why list is never built!

OO Lisp
 	defstruct
 	property lists
 		putting functions onto property lists
 	CLOS
 		defclass
 		defmethod
 		(call-next-method) order
 		multiple inheritance
 		double-dispatch rules
 			(ie CLOS generic functions with >=2 parameters)
 		what all this says about OOP: 
 			methods are not necessarily part of objects!
 	game program
 	
 Java
 	Lisp interpreter in Java
 		handling of "free" variables
 			examples of free variables
 		how lambdas work
 		how nlambdas work
 		evaluation strategy in general

==============================================================


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.


(b). Explain why DO* would fix this. (You may need to look up DO* 
in the textbook).


(c). Fix it while leaving it as a DO (not DO*) loop.

NOTE: recall that DO evaluates its variable initializations
and updates in *parallel*; DO* evaluates them strictly sequentially.

==============================================================

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.

==============================================================

3. What are the types of the following Haskell functions?
[CORRECTED]

(a)  rev([], L) = L 
     rev(h:t, L) = rev(t, h:L)

(b)  foo([], [])    = []
     foo(h1:t1, h2:t2) = h1(h2) : foo(t1, t2)

(c)  c x = (\ y -> y*x)

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

(b). As things stand now, what function is applied if r isn't damControlRoom 
but v *is* TURN?

(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?

(d). Explain why the problem of (c) might not be expected
to arise in practice.


==============================================================

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);


(b). what can go wrong with
	int fact(int n) {
	    return my_if(n==1, 1, n*fact(n-1));
	}


==============================================================

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 (on the property list of x with key "keyname") 
if present, with parameter y, and otherwise calls (default_interpret y)

Hint:
	(funcall FN ARG)  calls function FN with argument ARG

==============================================================

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.

[You may have to choose specific a,b to generate different values]
	
==============================================================

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 "~A  ~A  ~A  ~A" x y z u))  // CORRECTED

(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)

(b)  (bar 10 11 12)