(Click or use local copy.)

CS 3723/3721  Programming Languages  Spring 2005  Recitation 10  Lisp: Basics and Functions     Week 10: Mar 28 - Apr 1  Due (on time): 2005-04-04  23:59:59  Due (late):        2005-04-08  23:59:59

Recitation 10 must be submitted following directions at: submissions with deadlines 2005-04-04  23:59:59 (that's Monday, 4 April 2004, 11:59:59 pm) for full credit. 2005-04-08  23:59:59 (that's Friday, 8 April 2004, 11:59:59 pm) for 75% credit.

Basics:

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

   (You must convert these to Lisp notation, using S-expressions, with the function first.)

   ---

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

   The final answer should be approximately equal to the sum of the angles in a triangle, that is, 180.

   ---

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

   ---

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

   ---

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

   Special Note (Spring 2005): Only gcl on the Linux machines seems to be doing these calculations in double precision.

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

   ---

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

   ---

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

   ---

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

Contents of submission for Recitation 10: Last Name, First Name; Course Number; Recitation Number. Answers to questions 1 through 9 above. In several cases, such as numbers 3, 4, and 5, it's just a matter of providing a log of your runs of lisp. In case a questions asks you to define a function (6, 7, 8, 9), you must supply runs of the function, as well as the code for the function.