CS 381, Spring 2002
Homework Number 1
Due: Monday, April 15, in class
Lisp Representation

Section 15.4.1 of the text introduces a notation called the box notation for representing lists. Some further examples are found in section 15.5.2. Box notations are useful for understanding what is going on in a Lisp program.

For this homework I want you to hand in box notation descriptions of the following:

• Show the box notation representation of '(A B C).
• Show the box notation representation of '(A (B C)).
• Show the representation of the result obtained after executing the expression (cons 2 '(3 4)).
• Do the same for the expression (append '(a b) '(c d)).
• Do the same for the expression (cons '(a b) '(c d)).
• Explain how the value 3 is produced as the result of the following expression (car (car '((3 4) (5 6)))). You can do this by pointing to, in the box notation, the value passed as argument to each function invocation, and then describe the value yielded by each function invocation.
• In a similar way, trace the execution of each of the recursive calls in (length '(a b c)). Again, you can do this by drawing the box notation, and then pointing to the various parts that are passed as argument at each step, and indicate the result generated by each of the recursive calls.
• Again in a similar fashion, trace the arguments in the function sumAll (from programming assignment 1) when it is applied to the input '((1 2)(3 (4 5))).