Prompts for “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” and “LISP Notes”

Due on Wednesday, March 4 by 11:59pm

---

Read “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”, pp. 1–16 (up to but not including part f) and pp. 22–27 (up to but not including part d). Also read LISP Notes.

Commit your response as a PDF to your short responses repository. You are encouraged (but not required) to use LaTeX to typeset your response. You will also submit a small amount of code to your reading response repository for the last question.

---

1. McCarthy discusses the definitions of a few functions (“S-functions”) of S-expressions in LISP on p. 188:

    car[(m_1, m_2, ..., m_n)] = m_1
    cdr[(m_1, m_2, ..., m_n)] = (m_2, ..., m_n)
    cdr[(m)] = NIL
    cons[m_1; (m_2, ..., m_n)] = (m_1, m_2, ..., m_n)
    cons[m_1; NIL] = (m)
   

   These functions bear a striking resemblance to a set of functions you recently implemented in C. What are the meaning of car, cdr, and cons in terms of those C functions?

2. The algorithm described in pp. 22–27 in part 4c was the first of its kind and spawned an entirely new area of research in computer science. This algorithm is still essentially in use today in many real-world programming languages. What is McCarthy talking about and why is it so important?

3. For this problem, use the LISP interpreter clisp. The clisp interpreter is installed for you on the Unix lab machines in TCL 312 and TBL 301, but you may also install it on your own machine by visiting (clisp.sourceforge.io) and following the instructions there.

   Typing clisp will start up the LISP read-eval-print loop (REPL). This is a good way to experiment with code. Type (quit) to quit the REPL.

   When developing a solution to a homework problem, I recommend putting your LISP code into a file and then running the interpreter on that file. This mimics the way the graders will run your code.

   For example, to run the program in the file example.lisp, type

   clisp < example.lisp
   

   at the command line. The interpreter will read, evaluate, and print the result of expressions in the file, in order. For example, suppose example.lisp contains the following:

   ; square a number
   (defun square (x) (* x x))
      
   (square 4)
   (square (square 3))
      
   (quit)
   

   Evaluating this file produces the following output:

   SQUARE
   16
   81
   Bye.
   

   LISP evaluates the function declaration for square, evaluates the two expressions that apply square to the given arguments, and then quits. It is important that the program ends with (quit) so that clisp will exit and return you to the Unix shell. If your program contains an error (or you forget the (quit) expression), clisp will print an error message and then wait for you to type some input. Type in (quit) to exit the interpreter, or type Ctrl-D to return to the REPL.

   The dialect of LISP we use is described briefly in the LISP Notes page of the course webpage. Note that it differs slightly from the syntax that McCarthy uses in his paper.

   The following short examples should help you start thinking like a LISP programmer.

   • What is the value of each of the following expressions? Try to work them out first on paper, then verify your answers using the computer.
     • (car '(inky clyde blinky pinky))
     • (cons 'inky (cdr '(clyde blinky pinky)))
     • (car (car (cdr '(inky (blinky pinky) clyde))))
     • (cons (+ 1 2) (cdr '(+ 1 2)))
     • (mapcar #'(lambda (x) (/ x 2)) '(1 3 5 9))
     • (mapcar #'(lambda (x) (car x)) '((inky 3) (blinky 1) (clyde 33)))
     • (mapcar #'(lambda (x) (cdr x)) '((inky 3) (blinky 1) (clyde 33)))
   • Write a function called hello-world that returns the string "hello world".