Comp 372 sample exam answers

Sorry these are late.

> 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.

(defun equal (x y)
     (cond ((and (atom x) (atom y))  (eql x y))    ; atomic case
           ((or (atom x) (atom y)) nil)       ;; one atom and one nonatom!
           (t (and (equal (car x) (car y)) (equal (cdr x) (cdr y))))))
 
Note the third cond clause (and, for that matter, the first) returns
a Boolean expression representing the return value. Also note that
the above EQUAL works equally well (so to speak) for both lists and atoms.


> 2. Write a function UNIQ, 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.

For each element of the list, if it appears in the remaining part of the list,
take it out. Only the final instance will be saved.
 
(defun uniq (L)
     (do ((result nil))
         ((null L) (return result))
        (if (not (member (car L) (cdr L)))
            (setf result (cons (car L) result)))
        (setf L (cdr L)))) 

This looks like it should be easy with REMOVE-IF, except that
REMOVE-IF applies its predicate to each *element* of the list,
and that predicate has no "access" to the cdr of the list at that point.
We need something that doesn't work with the successive elements,
but instead works with the successive cdrs, as below:
    

> 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 #'(lambda (L) (if (not (member (car L) (cdr L)))
                                      (setf result (cons (car L) result))))
                    lis)
           result))
 
Note the similarity to #2.


> 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)...)). 
> Also give the ML type of this function.
 
Applying no functions (null flis) means x is unchanged:

fun listapplier (flis, x) = if null flis then x 
                            else hd(flis) (listapplier(tl flis, x));

Note that hd(flis) above is a *function* being applied.
At this point in our ML study, this is admittedly pretty obscure.

The type of this function is:
	((`a -> `a) list * `a) -> `a
That is, the parameter is a tuple consisting of the function list,
and an x of arbitrary type `a. The functions in the list must then
all be of type `a->`a.


> 5. What is the type of the following ML functions:
> (a). fun foo (nil) = 0.0 | foo(h::t) = h + foo(t);

real list -> real;  foo adds up a list of reals. The result type
must be real because 0.0 is, and since we're adding h to the result type,
that means the list components must also be real.

> (b). fun bar (L) = if null L then 0 else (hd(L))(1) + bar(tl(L));
    (int -> int) list -> int
L is a list and the result type is int. Since hd(L) is being applied to 1,
hd(L) must be a function, that takes an int as argument. It must also 
return int, because the result must be compatible with 0. 

If L is the list of int->int functions [f1,...,fn], then bar(L) is
f1(1)+f2(1) + ...+ fn(1).

 
> 6. Consider the following function in C++. Rewrite it so that it 
> does not use assignment. 

Or, more specifically, so that it uses recursion instead of a loop.

> 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;
> }
 
int looper (int i, int m, int n) {
    if (i<n) {
	return looper(i+1, m+2*(i+1)+1);
    } else return m;
}

main() {
    cout << "The answer is: " << looper(0, 0, readint());
}


> 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?
 
The idea here is that we're exchanging n and a[n].
The swap statement expands into 
    (let ((temp n)) (setf n (aref A n)) (setf (aref A n) temp))
Temp would be set to 4. With the array as above, the first setf
would leave n = (aref A 4) = 2.

The problem occurs with the second setf: (setf (aref A n) temp).
N is now *2*, not 4, and so we assign TEMP to (aref A 2).
N has *changed* since we entered the function, and so we update
the wrong A[N].

With C++ reference parameters, we would evaluate the *locations* of
both arguments at the time of entry to swap. Here, though, the 
location of (aref A n), which depends of course on n, isn't evaluated
until the expression is actually used. In the meantime, n changed.


> 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.

This can only occur if there is *aliasing*: two names for one variable.

int n = 5;  // global
void foo(int x, int y){ ++x; ++y;}
...
foo(n, n);   // the call

With value-result parameters, both x and y are initialized to 5, 
both are incremented to 6, and then *both* are copied back into n.
The final value of n is 6.

With reference parameters, both x and y are aliases for n.
When x is incremented, n is incremented to 6. When we increment y,
we really increment n again, to 7. The final value of n is 7.


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

(defun fact (n) (auxfact n 1))

(defun auxfact (x y) ;; computes x! * y
    (if (= x 0) y
        (auxfact (1- x) (* x y))))


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

(defun repeat (f n x)
    (if (= n 1) (funcall f x)   ;; or (if (= n 0) x ...)
        (funcall f (repeat f (1- n) x))))


> 11. Do the preceding problem using tail recursion.

We just move the call to f in the recursion to *inside*:

(defun repeat (f n x)
    (if (= n 1) (funcall f x)   ;; or (if (= n 0) x ...)
        (repeat f (1- n) (funcall f x))))