Unit 7 — LISP

Slide 1 of 55

The problem: The Shuffled Shopping List

A robot keeps its shopping list in a language called LISP. Its owner types three lines into the robot:
```
(SETQ BAG '(APPLE MILK BREAD JAM))
(DEF SWAP (L) (CONS (CADR L) (CONS (CAR L) (CDDR L))))
(CONS (CAR BAG) (SWAP (CDR BAG)))
```
What is the value of the last line?
On an ACSL contest, the Intermediate and Senior papers ask exactly this kind of question: a few lines of LISP, and "what is the value of the final statement?" Right now these lines probably look like a jumble of brackets. By the end of this unit you will read them easily: Lesson 1 teaches how LISP writes a calculation, Lesson 2 how it takes lists apart and builds new ones, and Lesson 3 how it stores values in variables and defines new functions. At the end you will answer the robot's question by hand, and you will also write a Python program that does the same shuffle to any list.
- Read atoms, lists and NIL, and evaluate LISP calls from the innermost brackets outward.
- Use ACSL's arithmetic functions and the tests EQ, POS, NEG and ATOM.
- Take lists apart and build them with CAR, CDR, CONS, REVERSE and shortcuts such as CADR.
- Trace programs that use SETQ, SET, EVAL, DEF and DEFUN, and write list functions in Python.
Lesson 1 — Atoms, lists and arithmetic

Division: Intermediate and above.

LISP was invented in the 1950s by John McCarthy. Its name means LISt Processing, and everything in it is built from just two things.
- An atom is a single item: a number such as 23 or -4, or a word such as HELLO.
- A list is some items inside round brackets, separated by spaces: (23 HELLO 821). An item of a list can itself be a list: (1 (2 3) 4) has three items, and the middle one is the list (2 3).
The list with nothing inside, (), has a special name: NIL. NIL is the only thing in LISP that counts as both an atom and a list.
Every statement is a function call

A LISP statement is always a list whose first item names a function and whose other items are its arguments:
```
(function arg1 arg2 ... argn)
```
The function comes first, before its arguments. So where you would write 2 + 3 in maths, LISP writes (ADD 2 3).
To find the value of a statement, LISP first finds the value of every argument, and then calls the function on those values. When an argument is itself a statement, you work it out first, so you always work from the innermost brackets outwards.
Example 1. (MULT (ADD 1 2) (SUB 9 4))

Rewrite it one step at a time, replacing each innermost statement by its value:
```
(MULT (ADD 1 2) (SUB 9 4))
(MULT 3 5)
15
```
The value is 15. In Python you would write the same calculation with ordinary brackets:
```
print((1 + 2) * (9 - 4))
```
Scroll the code for more ↓
Output
```
15
```

The arithmetic functions

Statement	Value
`(ADD x1 x2 ...)`	the sum of all its arguments
`(MULT x1 x2 ...)`	the product of all its arguments
`(SUB a b)`	a − b
`(DIV a b)`	a ÷ b
`(SQUARE a)`	a × a
`(EXP a n)`	a to the power n

ADD and MULT take any number of arguments: (ADD 1 4 2 3) is 10. SUB and DIV take exactly two, and the order matters: (SUB 3 10) is -7, not 7.

ACSL also lets you write the first four with their usual symbols: + for ADD, - for SUB, * for MULT and / for DIV. So (* 2 (+ 1 1 1)) is the same as (MULT 2 (ADD 1 1 1)), and its value is 6.

Example 2. (ADD (SQUARE 3) (EXP 2 4) (- 1 5))

```
(ADD (SQUARE 3) (EXP 2 4) (- 1 5))
(ADD 9 16 -4)
21
```
Watch out: (- 1 5) is 1 − 5 = -4. The first argument is always the one you subtract from.
```
print(3 * 3 + 2 ** 4 + (1 - 5))
```
Scroll the code for more ↓
Output
```
21
```
Division and exact answers

DIV gives the true quotient, so it can have a decimal part: (DIV 30 4) is 7.5. When the quotient is a whole number, it is a whole number: (DIV 12 -4) is -3.

This book writes every number answer the same way: a whole number with no decimal point (-3, never -3.0), and anything else as a decimal (7.5, 0.25). Contest questions are chosen so that the decimals always stop, like halves, quarters and eighths.
Python's / always gives a decimal, even when the answer is whole, so a program has to decide how to print it:

print(30 / 4)
print(12 / -4)
a = 12
b = -4
if a % b == 0:
    print(a // b)
else:
    print(a / b)

Output

7.5
-3.0
-3

a % b == 0 means "b goes into a exactly". Then a // b gives the whole-number answer, -3, with no .0 on the end.

True or NIL: EQ, POS and NEG

Some functions answer a yes-or-no question. ACSL writes "yes" as true and "no" as NIL.

Statement Value

(EQ a b) true if a and b are equal, otherwise NIL

(POS a) true if a is positive (greater than 0), otherwise NIL

(NEG a) true if a is negative (less than 0), otherwise NIL

So (EQ (ADD 2 3) 5) is true, (POS (SUB 4 4)) is NIL (0 is not positive), and (NEG -7) is true.

A real LISP program prints T instead of true. In this book, and on ACSL answer sheets, write true.

Put it together: this program reads one LISP statement that uses ADD, MULT or SUB, with only numbers as arguments, and prints its value. The input (ADD 4 7 1) prints 12.
```
line = "(MULT 2 -3 5)"
inside = line[1:len(line) - 1]
parts = inside.split()
print(inside)
print(parts)
```
Scroll the code for more ↓
Output
```
MULT 2 -3 5
['MULT', '2', '-3', '5']
```
The slice line[1:len(line) - 1] keeps everything except the first and last characters, which removes the two brackets. Then split gives the function name first and the numbers after it, still as text.

The whole program is saved as assets/l1.py.

Statement	Value
`(EQ a b)`	`true` if a and b are equal, otherwise `NIL`
`(POS a)`	`true` if a is positive (greater than 0), otherwise `NIL`
`(NEG a)`	`true` if a is negative (less than 0), otherwise `NIL`

Try it

line = input()
inside = line[1:len(line) - 1]
parts = inside.split()
name = parts[0]
numbers = []
for k in range(1, len(parts)):
    numbers.append(int(parts[k]))
result = 0
if name == "ADD":
    for value in numbers:
        result = result + value
elif name == "MULT":
    result = 1
    for value in numbers:
        result = result * value
elif name == "SUB":
    result = numbers[0] - numbers[1]
print(result)

Run it from this unit's folder:
```
python assets/l1.py < assets/l1/1.in
```
A product starts at 1 and a sum starts at 0, so that ADD and MULT work for any number of arguments. Try assets/l1/2.in and assets/l1/3.in as well.
Lesson 2 — Taking lists apart and building them

Division: Intermediate and above.
Quote: "take this as it is"

When LISP sees a list, it tries to call it as a function. (RED WHITE BLUE) would mean "call the function RED with arguments WHITE and BLUE", which is not what you want when you mean a list of three colours.

A quote mark ' in front of something tells LISP: do not work this out, just take it as it is.
- '(RED WHITE BLUE) is the list of three atoms.
- 'RED is the atom RED itself.
In the questions, every list of data has a quote in front of it. The quote is not part of the value: the value of '(RED WHITE BLUE) is (RED WHITE BLUE).
CAR and CDR

These two functions take a list apart.
- (CAR x) is the first item of the list x.
- (CDR x) is the list x without its first item (say it "could-er").
Statement Value

(CAR '(RED WHITE BLUE)) RED

(CDR '(RED WHITE BLUE)) (WHITE BLUE)

(CAR '((1 2) 3 4)) (1 2)

(CDR '((1 2) 3 4)) (3 4)

(CDR '(SOLO)) NIL

Watch out:
- CAR gives an item, which can be an atom or a list. CDR always gives a list.
- The CDR of a list with one item is the empty list, NIL.
- In ((1 2) 3 4), the first item is the whole list (1 2), not the 1.
CONS and REVERSE

These two build new lists.
- (CONS x y) puts x at the front of the list y. The second argument is always a list.
- (REVERSE x) gives the items of the list x in the opposite order.
Statement Value

(CONS 'A '(B C)) (A B C)

(CONS '(1 2) '(3 4)) ((1 2) 3 4)

(CONS 'A NIL) (A)

(REVERSE '(1 2 3)) (3 2 1)

(REVERSE '((1 2) 3 4)) (4 3 (1 2))

Watch out: CONS adds one item, even when that item is a list: (CONS '(1 2) '(3 4)) has three items, not four. REVERSE turns round only the top-level items; the list (1 2) inside stays (1 2).
Example 3. (CONS (CAR '(X Y Z)) (REVERSE (CDR '(1 2 3))))

Statement	Value
`(CAR '(RED WHITE BLUE))`	`RED`
`(CDR '(RED WHITE BLUE))`	`(WHITE BLUE)`
`(CAR '((1 2) 3 4))`	`(1 2)`
`(CDR '((1 2) 3 4))`	`(3 4)`
`(CDR '(SOLO))`	`NIL`

Statement	Value
`(CONS 'A '(B C))`	`(A B C)`
`(CONS '(1 2) '(3 4))`	`((1 2) 3 4)`
`(CONS 'A NIL)`	`(A)`
`(REVERSE '(1 2 3))`	`(3 2 1)`
`(REVERSE '((1 2) 3 4))`	`(4 3 (1 2))`

(CONS (CAR '(X Y Z)) (REVERSE (CDR '(1 2 3))))
(CONS X (REVERSE (2 3)))
(CONS X (3 2))
(X 3 2)

The value is (X 3 2).

Shortcuts: CADR and friends

Taking a CAR of a CDR is so common that LISP has a shortcut. (CADR x) means (CAR (CDR x)): the letters between the C and the R are the steps, and you do them from right to left, the letter next to the R first.

Shortcut	Means	What it gives
`CADR`	`(CAR (CDR x))`	the second item
`CDDR`	`(CDR (CDR x))`	the list without its first two items
`CADDR`	`(CAR (CDR (CDR x)))`	the third item
`CAAR`	`(CAR (CAR x))`	the first item of the first item
`CDAR`	`(CDR (CAR x))`	the first item, without its first item
`CDDAR`	`(CDR (CDR (CAR x)))`	the first item, without its first two items

Example 4. (CDDAR '((5 6 7 8) 9))

Read CDDAR from right to left: first A (a CAR), then D, then D.

CAR of ((5 6 7 8) 9)   is  (5 6 7 8)
CDR of (5 6 7 8)       is  (6 7 8)
CDR of (6 7 8)         is  (7 8)

The value is (7 8).

ATOM

(ATOM x) is true when x is an atom and NIL when x is a list.

Statement	Value
`(ATOM 'RED)`	`true`
`(ATOM 25)`	`true`
`(ATOM '(RED WHITE))`	`NIL`
`(ATOM (CAR '((1 2) 3)))`	`NIL`, because the `CAR` is the list `(1 2)`
`(ATOM (CADR '((1 2) 3)))`	`true`, because the `CADR` is the atom `3`

Lists in Python

A LISP list of atoms fits naturally into a Python list of strings. CAR is just the item at position 0. CDR is a new list holding every item after the first; build it with a loop and append.

items = ["RED", "WHITE", "BLUE"]
first = items[0]
rest = []
for k in range(1, len(items)):
    rest.append(items[k])
print(first)
print(rest)
print(items)

Output

RED
['WHITE', 'BLUE']
['RED', 'WHITE', 'BLUE']

The loop starts at position 1, so the first item is skipped. The original list items is not changed; LISP never changes a list when it takes its CAR or CDR, and neither should your program.

CONS also builds a new list: start a list holding the new first item, then append every item of the old list after it.

items = ["WHITE", "BLUE"]
result = ["RED"]
for item in items:
    result.append(item)
print(result)

Output

['RED', 'WHITE', 'BLUE']

To print a list the LISP way, as (RED WHITE BLUE) with single spaces, glue the text together one item at a time. An empty list prints as NIL.

def show(items):
    if len(items) == 0:
        return "NIL"
    text = "("
    for k in range(len(items)):
        if k > 0:
            text = text + " "
        text = text + items[k]
    return text + ")"


print(show(["RED", "WHITE", "BLUE"]))
print(show(["SOLO"]))
print(show([]))

Output

(RED WHITE BLUE)
(SOLO)
NIL

The space goes before every item except the first, so there is no extra space after the last item.

Put it together: this program reads a list of atoms, such as (TOM ANN SAM), and prints its CAR on the first line and its CDR on the second. It is saved as assets/l2.py.

Try it

def show(items):
    if len(items) == 0:
        return "NIL"
    text = "("
    for k in range(len(items)):
        if k > 0:
            text = text + " "
        text = text + items[k]
    return text + ")"


line = input()
inside = line[1:len(line) - 1]
items = inside.split()
rest = []
for k in range(1, len(items)):
    rest.append(items[k])
print(items[0])
print(show(rest))

Run it from this unit's folder:
```
python assets/l2.py < assets/l2/1.in
```
It prints TOM and then (ANN SAM). Try assets/l2/2.in, a list with one atom: its CDR prints as NIL.
Lesson 3 — Variables and new functions

Division: Intermediate and above.

SETQ and SET

SETQ gives a variable a value. The value of the SETQ statement is the value it stores.

Statement	Value	What happens
`(SETQ N (ADD 3 4))`	`7`	`N` now holds `7`
`(SETQ COLORS '(RED WHITE BLUE))`	`(RED WHITE BLUE)`	`COLORS` now holds a list of 3 atoms
`(SETQ S '(ADD 3 4))`	`(ADD 3 4)`	`S` holds a list; the quote stops it being worked out

After these lines, a variable name without a quote stands for its value: (CAR COLORS) is RED, and (MULT N 2) is 14.

SET does the same job, but you must quote the variable's name yourself: (SET 'N 7) is the same as (SETQ N 7). (The Q in SETQ stands for "quote": it quotes the name for you.)

Watch out: quote or no quote makes all the difference.

```
(SETQ COLORS '(RED WHITE BLUE))
(CAR COLORS)
(CAR 'COLORS)
```
(CAR COLORS) is RED, because COLORS is replaced by its value. (CAR 'COLORS) is an error: 'COLORS is just the atom COLORS, and an atom has no CAR. In the same way, (ATOM COLORS) is NIL (its value is a list), but (ATOM 'COLORS) is true (the name itself is an atom).
EVAL: work it out one more time

(EVAL x) takes the value of its argument and works it out again.
```
(SETQ S '(ADD 3 4))
(EVAL S)
```
The argument S is worked out first, as always, giving the list (ADD 3 4). Then EVAL works out that list as a statement, giving 7. S itself still holds the list (ADD 3 4); EVAL does not change it.
The same idea works with names. If P holds 5 and W holds the atom P, then W is worked out to P, and (EVAL W) works out P to get 5.
DEF and DEFUN: new functions

DEF defines a new function. ACSL also writes it as DEFUN; the two mean the same thing.
```
(DEF FINAL (L) (CAR (REVERSE L)))
```
This defines a function called FINAL with one parameter, L. Its body is (CAR (REVERSE L)). To work out (FINAL '(4 5 6)), put the argument in place of L everywhere in the body and work that out:
```
(FINAL '(4 5 6))
(CAR (REVERSE (4 5 6)))
(CAR (6 5 4))
6
```
A function can have several parameters, and one function can call another:
```
(DEFUN HALF (X) (DIV X 2))
(DEFUN AVG (A B) (HALF (ADD A B)))
(AVG 4 7)
```
(AVG 4 7) is (HALF (ADD 4 7)), which is (HALF 11), which is (DIV 11 2), which is 5.5.

Python has the same idea: DEF in LISP is def in Python.

def half(x):
    return x / 2


def avg(a, b):
    return half(a + b)


print(avg(4, 7))

Output

5.5

Tracing a short program

A contest question gives several statements in order and asks for the value of the last one. Work through them from top to bottom, and keep a small table of what each variable holds, exactly as when you trace a Python program.

Example 5.
```
(SETQ X '(2 (3 4) 5))
(SETQ Y (CADR X))
(DEF F (A B) (MULT A (SUB B 1)))
(F (CAR Y) (CADDR X))
```
After line X Y

1 (2 (3 4) 5)

2 (2 (3 4) 5) (3 4)
Line 3 only defines F. In line 4, (CAR Y) is 3 and (CADDR X) is 5, so the value is (F 3 5) = (MULT 3 (SUB 5 1)) = (MULT 3 4) = 12.

After line	`X`	`Y`
1	`(2 (3 4) 5)`
2	`(2 (3 4) 5)`	`(3 4)`

Back to the robot

Now the robot's question is easy.

(SETQ BAG '(APPLE MILK BREAD JAM))
(DEF SWAP (L) (CONS (CADR L) (CONS (CAR L) (CDDR L))))
(CONS (CAR BAG) (SWAP (CDR BAG)))

SWAP puts the second item first, then the first item, then everything after the second: it swaps the first two items.

(CDR BAG)                      is  (MILK BREAD JAM)
(SWAP '(MILK BREAD JAM))       is  (CONS BREAD (CONS MILK (JAM)))
                               is  (BREAD MILK JAM)
(CONS APPLE (BREAD MILK JAM))  is  (APPLE BREAD MILK JAM)

The value is (APPLE BREAD MILK JAM): the robot swapped the second and third items and left the rest alone.

Put it together: the same shuffle in Python. Each LISP function becomes a small Python function that returns a new list, and swap is built from them exactly as SWAP is built in LISP. The program reads a list of at least three atoms and prints the value of (CONS (CAR BAG) (SWAP (CDR BAG))) for it. It is saved as assets/l3.py.

Try it

def show(items):
    if len(items) == 0:
        return "NIL"
    text = "("
    for k in range(len(items)):
        if k > 0:
            text = text + " "
        text = text + items[k]
    return text + ")"


def car(items):
    return items[0]


def cdr(items):
    rest = []
    for k in range(1, len(items)):
        rest.append(items[k])
    return rest


def cons(first, items):
    result = [first]
    for item in items:
        result.append(item)
    return result


def swap(items):
    return cons(car(cdr(items)), cons(car(items), cdr(cdr(items))))


line = input()
bag = line[1:len(line) - 1].split()
print(show(cons(car(bag), swap(cdr(bag)))))

Run it from this unit's folder:
```
python assets/l3.py < assets/l3/1.in
```
It prints (APPLE BREAD MILK JAM), the answer you worked out by hand. Try assets/l3/2.in and assets/l3/3.in too.
cdr(cdr(items)) is the Python version of CDDR: the inner call runs first, just as the letter next to the R comes first.
- Every LISP statement is a function call: the first item names the function, and the rest are its arguments.
- A quote means "take this as it is", so a quoted list is data, not a call.
- CAR is the first item; CDR is a new list of everything after it, and the CDR of a one-item list is NIL.
- SETQ stores a value, DEF and DEFUN make new functions, and a variable table keeps your trace straight.
You can now find the value of a short LISP program, such as the shopping list's (APPLE BREAD MILK JAM).

Unit 7 — LISP

The problem: The Shuffled Shopping List

Lesson 1 — Atoms, lists and arithmetic

Every statement is a function call

The arithmetic functions

Division and exact answers

True or NIL: EQ, POS and NEG

Lesson 2 — Taking lists apart and building them

Quote: "take this as it is"

CAR and CDR

CONS and REVERSE

Shortcuts: CADR and friends

ATOM

Lists in Python

Lesson 3 — Variables and new functions

SETQ and SET

EVAL: work it out one more time

DEF and DEFUN: new functions

Tracing a short program

Back to the robot