• Accessing Lisp on the Sun System: For some reason, lisp is not on the path of most of you. In pandora or other CS Lan clients, lisp is found by typing /usr/old-local/bin/lisp (for some unknown reason). Under medusa it can be found by typing/usr/local/bin/lisp or just lisp.

• Lisp references: For now, we have parts of Chapter 15 in the textbook, along with class notes.

  Association of Lisp Users: ALU

  Online tutorials: Successful Lisp: How to Understand and Use Common Lisp
  Lisp Tutorial by Marc Schwarz
  Lisp Primer by Colin Allen and Maneesh Dhagat

  Elementary lisp book by David S. Touretzky: .ps, .pdf [1 MB].

  Elementary lisp book by David Cooper: .pdf, local .pdf [404 KB].

  Guy Steele's lisp reference book (probably too hard): .ps, .pdf [4.6 MB].

  Here are initial examples of functions in Lisp: .txt, .pdf, .ps.

  Here is a way you could do the first part of this assignment more easily: .txt, .pdf, .ps.

• Producing material to hand in: For this and the next recitation you can use Sun Common Lisp on ringer or any other Lisp system you have access to. The following interactive session shows how to use the lisp function dribble to create a log of a Lisp session for printing, so that you can turn in the results of this recitation. You can also use selection and copy from a terminal window to achieve the same result. The material in bold below is what you type.

  % lisp
  > 12
  12
  > (dribble 'file.out)  ; turn on logging
  ;;; Dribble file "FILE.OUT" started
  T
  > (+ 3 4 )
  7
  > (dribble)            ; turn off logging
  ;;; Dribble file "FILE.OUT" finished
  T
  > (quit)
  % cat FILE.OUT
  ;;; Dribble file "FILE.OUT" started
  T
  > (+ 3 4 )
  7
  > (dribble)
  ;;; Dribble file "FILE.OUT" finished
  

Basics:

1. Try out Lisp on the CS computers by logging in and typing

   
   % lisp
   

   to activate lisp, and

   
   > (quit)
   

   to quit. (The commonly used (exit) does not work.)

   ---

2. Try out numeric computations. Do

   
   > (setq a 4)
   > (setq b 5)
   

   and calculate

   
   a^2 + b^2
   sqrt(a^2 + b^2)
   (4/3)*pi*a^3 
   

   ---

3. Try

   
   > (setq x1 0)
   > (setq y1 0)
   > (setq x2 1)
   > (setq y2 0)
   > (setq x3 -1)
   > (setq y3 1)
   

   Use setq to assign

   
   a = sqrt((x2 - x1)^2 + (y2 -y1)^2)
   

   and similarly for b and c, to give lengths of the sides of a triangle. Then set

   
   alpha = arccos( (b^2 + c^2 - a^2) / (2*b*c)).
   

   and similarly for beta and gamma, to give the three angles of the triangle. Finally set

   
   sum = alpha + beta + gamma
   sumdeg = (180/pi)*sum
   

   ---

4. Try out car, cdr, and cons, using the following examples:

   
   > (setq x '(a b))
   > (setq y '(a b c))
   

   Now try

   
   > (car x),
   > (car y),
   > (cdr x),
   > (cdr y),
   > (car (cdr x)),
   > (car (cdr y)),
   > (cadr x),
   > (cadr y).
   > (cons x y),
   > (append x y),
   > (cons (car y) (cdr y))
   

   ---

5. Try out append and list:

    
   > (list 'a 'b 'c)
   > (list 'a '(b c) 'd)
   > (append '(a b) '(c d) '(e f))
   > (setq l '(a b))
   > (append l l)
   > (append l l l)
   > (list l l)
   > (list l l l)
   > (list 'l l)
   > (append 'l l)          [an error]
   > (append '(a) '() '(b) '())
   > (append '((a) (b)) '((c)(d)))
   > (list '((a)(b)) '((c)(d)))
   > (cons l l)
   > (cons 'l l)
   > (length '(a (b c) d))
   > (reverse '(a (b c) d))
   > (car '(cdr '(a b c)))
   > (car (cdr '(a b c)))
   > (cons 'a nil)
   > (setq x '(a b))
   > (cons (car x) (cons (cadr x) '(c d)))
   

Functions:

For this recitation and the next one, your Lisp functions should not have any iterative constructs (such as prog, do, etc.) but all iteration should be done with recursion. Inside functions you should not make use of the setf or setq functions.
1. Consider the follwing lisp function (the lisp functions defun and cond will be discussed in class):

    
   (defun factorial (n)
       (cond ((= n 0) 1)
             (t  (* n (factorial (1- n))))
       )
   )
   

   Save this function as a file named "fact.l". Then try out

   
   > (load "fact.l")
   > (factorial 10)
   > (factorial 20)
   > (factorial 50)
   

   ---

2. Mimic the factorial function above to define a function harmonic, where (harmonic n) returns the value

   
   1 + (1/2) + (1/3) + . . . + (1/(n-1)) + (1/n).
   

   1. First use the operator / with integers, so that the answers are rational numbers. [Try out n = 10, 20. As a check, the value of (harmonic 10) should be 7381/2520.]
   2. Then rewrite the harmonic function using constants with a decimal point to force Lisp to use floating point numbers. [Now as a check the value of (harmonic 10) should be 2.9289682539682538.]
   3. It turns out that (harmonic n) is approximately equal to log(n) + g, where g = 0.5772156649. . . is known as Euler's constant. Use Lisp to check the accuracy of this approximation for n = 10, 100, 1000. (Here log is the logarithm base e, which is available in Lisp under the name log.) [The accuracy should be better than 1/n.]

   ---

3. Write a recursive function fibonacci that will return the nth fibonacci number F[n], where

   
   F[0] = 0, F[1] = 1, and F[n] = F[n-1] + F[n-2].
   

   [For reference, (fibonacci 10) should return 55, (fibonacci 20) returns 6765 after a few seconds, and (fibonacci 30) returns 832040 after as much as several minutes. Why do you think this takes so long?]

   ---

4. Write a recursive function maxvec that finds the maximum of a simple list of numbers. [Hint: if the cdr is nil, just return the car, and otherwise return the maximum of the car and of maxvec applied to the cdr. For example, (maxvec '(2 5 6 3)) returns 6.]

   ---

5. Try out the function reverse in Lisp:

   
   (reverse '(a b c))
   (reverse '((a b c)))
   (reverse '(a (b c d) e))
   

   Define your own function reverse1 which will behave the same way as reverse, reversing the order of elements of a list at the top level only. [Hint: Invoke reverse1 recursively on the cdr and tack on the car at the end.]

   ---

6. Define a function count-atoms that will count the number of atoms in a list, at all levels. For example (count-atoms '(a (b c) (d (e) f))) should return 6. [Hint: Mimic list-atoms from class.]