CSCI 334: Principles of Programming Languages, Spring 2022

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

Due on Wednesday, March 2 by 10pm

Read “Introduction to the Lambda Calculus, Part 1” in the course packet.

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

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?
For this problem, evaluate the expressions listed below. Be sure to put those expressions in a file called problems04.lisp, and paste the output of each expression into a comment next to each expression. I should be able to run this file using the clisp interpreter
```
$ clisp < problems04.lisp
```
to verify that your comments match the output that I see.

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

Length

Your response should be short: at least 150 words and no more than 400 words total.

Submission Instructions

Commit your response to your short responses repository. You must commit both your .tex source file and your generated .pdf. You are required to use LaTeX to typeset your response.

QUESTION RESPONSE FILE MUST BE NAMED reading04.pdf.

LISP FILE MUST BE NAMED problems04.lisp.