LISP Homework Solutions

Introduction

This web page provides answers to most of the questions asked in the LISP Homework assignment. (Some of the box and pointer diagrams are missing.) I apologize for the messy page layout; this is what you get when you save a complex Word document as a web page.

What is the difference between typing the following items at the interpreter's top level?
In each case, tell what will be displayed and how the interpreter determined the information displayed.

Answers: A is a symbol, and the interpreter will return its value binding unless it doesn’t have one, in which case the interpreter will signal an error. 'A is a quoted symbol, and the interpreter will return A, the symbol’s print name. #\A is the character A, and the interpreter will return that character.

Evaluate the following expressions.
Be sure to check your answers using clisp before handing your work in!

(car '(a b c) )
(cdr '(w x y z) )
(car '((red 1 ) (orange 2)))
(cdr '((performances 3) (size-of-hall 250)))
(car (cdr '(( silver gold) (oil vinegar))))
(cdr (car '((#\a #\b) ("c" "d"))))
(cdr (car (cdr '((("smith" 35) ("brown" 26)) (("jones" 45) ("marsh" 43))))))
(car (car (cdr '(cdr ((rent (+ (* 1/3 actual-rent) parking-space)) (food (+ groceries restaurants)) (heat (* 15 avg-temp-of-month)))))))
(+ (car '(1 2 3)) (cadr '(4 5 6)))

Answers: A, (X Y Z)
(RED 1)
((SIZE-OF-HALL 250))
(OIL VINEGAR)
(#\b)
((“marsh” 43))
(RENT (+ (* 1/3 ACTUAL-RENT) PARKING-SPACE))
6

Write the sequence of CARs and CDRs that will pick the symbol CHAIR out of the following lists:

(table lamp chair shelf)
((table lamp) (chair computer))
(computer (shelf) ((chair)) (((sofa))))
((((table) file-cabinet) chair) telephone)

Answers: (car (cdr (cdr '(table lamp chair shelf))))
(car (car (cdr '((table lamp) (chair computer)))))
(car (car (car (cdr (cdr '(computer (shelf) ((chair)) (((sofa)))))))))
(car (cdr (car '((((table) file‑cabinet) chair) telephone))))

You should read Chapter 15 of the Wilensky book before answering the next questions. Note that (cons 'a 'b) is the same as '(a . b). For example, the dotted-pair representation of (a b s) is (a . (b . (s . nil))). The spaces are required around the dots when you type this, by the way. The difference between a dotted pair and a list is that the cdr of each cons cell in a list is a pointer to another cons cell, except the cdr of the last cons cell, which is NIL. But a dotted pair is a cons cell with a cdr that points to something other than another cons cell (or NIL).

First draw the following lists as box and pointer diagrams; then write them as dotted pairs. In the box and pointer diagrams, you can just write the Print Name of symbols instead of showing the whole 4-part structure for each symbol.

(apples bananas strawberries)
(values (first-value second-value))
((my-symbol "my-string") #\C)

Answers: (apples . (bananas . (strawberries . nil)))
(value . ((first‑value . (second‑value . nil)) . nil))
((my‑symbol . (“my‑string” . nil)) (#\C . nil))

Draw box and pointer diagrams for the following lists:

(a (b c) d (e (f)) g)
(canary (parrot dove) pigeon (chicken (duck)))

Draw box and pointer diagrams for the following lists, dotted pairs, and combinations:

(patrick gregory james)
(brian . eric)
(marc . (steve . harold)) [Clisp prints this as (marc steve . harold) -- Why?]

The (steve . harold) pair is a cons cell that does not look like a list, but the other cons cell looks like the first part of a list.

(ruth (myrna . florence))
((marlene . elizabeth) . irene)

((peanut . butter) . (butter . (jelly . bread))) [How does Clisp print this one?]

((PEANUT . BUTTER) BUTTER JELLY . BREAD) The third dot looks like a list with BUTTER as its CAR. Note that this list has two pointers to the same symbol, BUTTER.

(((chocolate . cake) . cinnamon) . icing)
((beth . "555-5843") (patrick . "555-1293"))
((beth "555-5843") (patrick "555-1293"))
((x . nil) . (y . (z . nil)))
((x) y z)

This diagram is the same for both of the two forms above.

(nil . nil)