Comp 372 sample exam/study guide	Dordal	October 20, 1999	

The exam will be Monday, Oct 25, and will be open book (but not notes).
However, you will make the best use of your time if you plan on using
the book only as an occasional reference. A brief ML function example 
(eg the len function) will be provided; you will *not* be expected to
know any ML syntax but basic recursion questions posed in ML as a new
language may be included. 

Here are some Lisp things you should know:
	recursive functions (arithmetic recursion, cdr & car/cdr recursion
	iteration (via DO loops)
	use of MAPCAR, etc, and LAMBDA functions
	macro fundamentals
	variable binding, and closures, and evaluation basics
Here are some ML things you should know:
	*Basic* function definitions (with recursion)
	Basic ML type inference rules for functions
You should also review value, reference, value-result, and function 
parameters.

Here are a few sample problems
1. Define (EQUAL x y) in lisp. Two atoms are EQUAL if they are EQL; 
two lists are EQUAL if the cars and cdrs, respectively, are EQUAL. 
This is car/cdr recursion.

2. Write a function UNIQ in lisp, that takes a list of symbols and 
eliminates duplicates. For example, (uniq '(a b c b a)) could 
return either (a b c) or (c b a). Use a DO loop.

3. Write UNIQ using a lambda function and MAPLIST. 
(MAPLIST fun '(a b c d e)) is like MAPCAR, but fun is applied 
successively not to the *elements* a, b, c, d, e, but instead 
to the successive cdrs: 
((fun '(a b c d e)) (fun '(b c d e)) (fun '(c d e)) (fun '(d e)) (fun '(e)) (fun nil)). 
Here is something to get you started; stick an element onto the 
result when it's *not* in the rest of the list:
   	(defun uniq (lis)
	      (let (result nil)
	            (maplist __________________________________ lis)
	            result))

4. Write a function in ML that takes a list of functions, 
flis = [f1, f2, ....fn], and an x, and returns f1(f2(...(fn(x)...)). 

5. What is the type of the following ML functions:
(a). fun foo (nil) = 0.0 | foo(h::t) = h + foo(t);
(b). fun bar (L) = if null L then 0 else (hd(L))(1) + bar(tl(L));

6. Consider the following function in C++. Rewrite it so that it 
does not use assignment. You may assume that a function readint() 
is available that returns the next integer in the input:
	
main() {
    int n, m =0, i=0;
    cin >> n;
    while (i<n) {
        i++;        m += 2*i+1;
    }
    cout << "The answer is: " << m;
}

7. Suppose we define a swap macro so that (swap X Y) expands into 
(let ((temp X)) (setf X Y) (setf Y temp)). 
Lisp does have arrays; if A is an array the (aref A n) returns the 
nth component of A and (setf (aref A n) x) does what would be 
written in C++ as A[n]=x. What happens if we call (swap n (aref A n)), 
when n is initially 4 and the array A is indexed starting at 1 and 
has components 5,4,3,2,1?

8. Give an example of a C++-style function and a suitable call for 
which reference parameters and value-result parameters would lead 
to different final states.

9. Give a tail-recursive version of the FACTORIAL (FACT) function
in Lisp.

10. Define a lisp function REPEAT that takes a function f, and an
integer n, and a value x, and returns f(f(...n times...f(x)...)).

11. Do the preceding problem using tail recursion.