Unit 7 — LISP

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

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

15

The arithmetic functions

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

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)

7.5
-3.0
-3

True or NIL: EQ, POS and NEG

Some functions answer a yes-or-no question. ACSL writes "yes" as true and "no" as 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)

MULT 2 -3 5
['MULT', '2', '-3', '5']

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

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

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.

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

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

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.

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)

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

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)

['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([]))

(RED WHITE BLUE)
(SOLO)
NIL

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.

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.

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

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

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.

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.

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.