CSE 341 -- Lisp Quiz -- Answer Key

October 20, 1995


50 minutes, open book and notes, 70 points total

Your name:


  1. [3 points per subquestion -- 18 points total] What is the result of evaluating the following Lisp expressions? If there is more than one expression, assume that they are evaluted in order, but just give the result of evaluating the last one. If the expression will give an error when evaluated, say so.
    1. (* 2 (+ 3 4) 5) 70

    2. (mapcar #'(lambda (x) (* x 10)) '( 1 2 3 4)) (10 20 30 40)

    3. (cond ((equal 1 3) (/ 1 0)) (t (* 2 9))) 18

    4. (let ((x 3) (y 4)) (let ((x 10) (y (+ x 2))) (+ x y))) 15

    5. (defun munge (x) (setf (first x) 100) (setf (rest x) nil)) (let* ((a (list 1 2 3)) (b (list a a))) (munge a) b) ((100) (100))

    6. (let ((a (list 1 2 3)) (b 10)) (dolist (j a b) (setf b (+ j b)))) 16

  2. [5 points per subquestion -- 15 points total] For each of the following cons cell diagrams, write a Lisp expression that returns that list. Don't use global variables (use a let if you need intermediate variables). Use functions with side effects only if strictly necessary. For example, given the diagram:
                     ________       __________
                    |   |   |      |     |  /|
                    | o | --|----->|  o  | / |
                    |_|_|___|      |__|__|/__|
                      |               | 	     
                      |               |	    
                     BILL          HILLARY   
    
    your answer should be (list 'bill 'hillary) or simply '(bill hillary).

    1. 	   ________       __________
      	  |   |   |      |     |  /|
      	  | o | --|----->|  o  | / |
      	  |_|_|___|      |__|__|/__|
      	    |               | 	     
      	    |               |	    
                 ________       __________
                |   |  /|      |     |  /|
                | o | / |      |  o  | / |
                |_|_|/__|      |__|__|/__|
                  |               | 	     
                  |               |	    
                  X               Y
      
      '((x) (y))

    2.                                        
                  ________________
                  |               |
                 _|______       __________
                | | |   |      |     |  /|
      	  | o | --|----->|  o  | / |
      	  |___|___|      |__|__|/__|
      	                    | 	     
                                  |	    
                                  X
      
      
      
      (let ((s '(x))) (cons s s))

    3.                 	
                 ________       __________
                |   |   |      |     |  /|
      	  | o | --|----->|  o  | / |
      	  |_|_|___|      |__|__|/__|
      	    |   |           | 	     
                  |   |           |	    
                  |___|           X
      
      
      
      (let ((s (list nil 'x))) (setf (first s) s) s)

  3. [10 points] Write a recursive Lisp function three-times that takes a list of atoms (which may be empty), and returns a new list of the same length, where each element in the new list is a list of length three, with the original element occurring three times. (If you did assignment 2 this should be easy!) Examples: (three-times '(x y z)) evaluates to ((X X X) (Y Y Y) (Z Z Z)) (three-times '(fred)) evaluates to ((FRED FRED FRED)) (three-times '()) evaluates to NIL (defun three-times (s) (if (null s) nil (let* ((a (first s)) (three-a (list a a a))) (cons three-a (three-times (rest s))))))

  4. [2 points] Is your recursive three-times function tail-recursive? Why or why not?

    It isn't tail recursive, since there is a call to cons that takes the result of the recursive call and augments it. (This is an example of augmenting recursion.)

  5. [10 points] Write another version of three-times that uses the built-in applicative operators rather than recursion. Don't define any auxiliary functions using defun. (defun three-times (s) (mapcar #'(lambda (a) (list a a a)) s))

  6. [15 points] Consider the following function sum-of-squares that takes a list of numbers and returns the sum of their squares. (For simplicity it doesn't do error checking.) (defun sum-of-squares (s) (if (null s) 0 (+ (* (first s) (first s)) (sum-of-squares (rest s))))) This function is not tail-recursive. Why not? Can a tail recursive version be written? If so, give a tail recursive version.
(defun sum-of-squares (s) (aux-sum-of-squares s 0)) (defun aux-sum-of-squares (s sum) (if (null s) sum (aux-sum-of-squares (rest s) (+ sum (* (first s) (first s))))))