Comp 372: Programming Languages         Program 2       Dordal  Oct 11, 1999
Due: Oct 20, 1998

Write the following functions in lisp:


1. fibonnaci (or just "fib")
This is to use recursion to calculate the fibonnaci numbers:
1 1 2 3 5 8 13 21 34 55 ...
(fib 0) and (fib 1) are both 1.  Each subsequent number is the sum
of the preceding two. Thus, a simple version is 
   (defun fib (n)
        (if (<= n 1)
            1
            (+ (fib (- n 1)) (fib (- n 2)))))
However, this performs very badly, as discussed in section 6.9.
The text there gives an iterative version; you are to stick with
recursion, but to have (fib n) return *two* values using VALUES
(section 5.5): the nth fibonnacci number as the first value,
and the n-1th fibonnacci number as the second value. This allows
a recursive implementation that is very efficient: to calculate
(fib n), we call (fib (- n 1)) *once* and add the two values it returns.
Of course, (fib n) must also return the n-1th fibonnacci number
as its second value.


2. swap.
If a is nil, and b is 5, then after (swap a b), a should be 5 and b
should be nil. Such a function can only be written as a macro. A call
to (swap a b) should expand into something like
	(let ((temp a)) (setf a b) (setf b temp))
You may assume that the variable TEMP is not one of the two parameters
passed to SWAP (why would this matter?); extra credit though if you
can write SWAP so that it doesn't require this assumption.
The use of DEFMACRO is discussed in sections 10.2 and 10.3.


3. printlines.
The first arg should be a number, representing an indentation value.
The remaining args should be printed, one per line, indented by the
appropriate amount. Any number of remaining args is acceptable. Use
FORMAT to print each output arg. You will need to use the &rest keyword
to handle a variable number of args.  See section 6.3 for &rest info.


4. eval-to-death
This function takes a symbol, and evaluates it, if it has been assigned
a value. If it gets a symbol again, it repeats the process, It stops
when it reaches an undefined symbol, a non-symbol, or a symbol that has
appeared previously in the sequence.

For example, suppose we have (setf a 'b) (setf b 'c). Now
(eval-to-death 'a) should return (a b c), stopping at c because c is
undefined. If we (setf c 3), then (eval-to-death 'a) should return (a b c 3). 
Finally, if we (setf c 'a), then (eval-to-death 'a) should return (a b c a); 
the presence of 'a' twice in the list indicates a cycle of assignments.

The following are useful: (boundp x) returns t if x evaluates to a
symbol that has a value; nil otherwise. (symbol-value x) returns the
value of the symbol that is the value of x. (eval x) can also be used.

I strongly recommend you use a do loop, rather than recursion.