Overview
LISP (for "LISt Processing") was created by John McCarthy at M.I.T. in the mid-1950s. It has one of the simplest syntaxes of any programming language and yet is extremely powerful. For decades it was the language of choice for artificial intelligence work, and it encourages a very different way of thinking about programs compared with algorithmic languages such as Python, C++ or Java.
ACSL questions in this category give you one LISP expression, or a short sequence of statements, and ask for the value of the final expression. Success depends on knowing a small set of built-in functions and on evaluating carefully from the inside out.
Key Concepts:
- Everything in LISP is either an atom (a number or a symbol) or a list (items inside parentheses). NIL, also written
(), is the only thing that is both. - Every statement is a function call written as
(function arg1 arg2 ... argn). - Arguments are evaluated first (innermost parentheses first), then the function is applied.
- A leading quote
'means "take this literally, do not evaluate it".
Key Concepts
Syntax
A list is built by writing its elements inside parentheses. The list (23 (this is easy) hello 821) has four elements; the second element is itself a list. The atoms in that list are 23, this, is, easy, hello and 821.
To evaluate (MULT (ADD 2 3) (ADD 1 4 2)): (ADD 2 3) is 5, (ADD 1 4 2) is 7, and (MULT 5 7) is 35. Some functions take any number of arguments; others take a fixed number. Every statement returns a value, which is an atom or a list.
Basic Functions: SET, SETQ, EVAL, ATOM
(SET 'x value)binds the atom x to the value and returns the value. The quote on x is needed because SET evaluates its first argument.(SETQ x value)is the same as SET but automatically treats its first argument as quoted, so no quote is written.(EVAL expr)returns the value of its argument after evaluating it one more time.(ATOM expr)returns true if the argument is an atom and NIL if it is a list.
| Statement | Value | Comment |
|---|---|---|
(SET 'a (MULT 2 3)) | 6 | a is an atom with a value of 6 |
(SET 'a '(MULT 2 3)) | (MULT 2 3) | a is a list with 3 elements |
(SET 'b 'a) | a | b is an atom whose value is the symbol a |
(SET 'c a) | (MULT 2 3) | c is a copy of a's value, a 3-element list |
(SETQ EX (ADD 3 (MULT 2 5))) | 13 | EX has a value of 13 |
(SETQ VOWELS '(A E I O U)) | (A E I O U) | VOWELS is a list of 5 elements |
(SETQ p '(ADD 1 2 3 4)) | (ADD 1 2 3 4) | p is a list with 5 elements |
(ATOM 'p) | true | The quoted p is an atom |
(ATOM p) | NIL | Unquoted p evaluates to the 5-element list |
(EVAL p) | 10 | The list (ADD 1 2 3 4) is evaluated |
List Functions: CAR, CDR, CONS, REVERSE
(CAR x)returns the first element of list x.(CDR x)(pronounced "could-er") returns the list x without its first element. The result is always a list.(CONS a x)returns a new list made by putting a at the front of list x.(REVERSE x)returns list x in reverse order (only the top level is reversed).- CAR and CDR can be chained with a shorthand:
(CADR x)means(CAR (CDR x)), the second element;(CDDAR x)means(CDR (CDR (CAR x))). Read the letters between C and R from right to left.
| Statement | Value |
|---|---|
(CAR '(This is a list)) | This |
(CDR '(This is a list)) | (is a list) |
(CONS 'red '(white blue)) | (red white blue) |
(SETQ z (CONS '(red white blue) (CDR '(This is a list)))) | ((red white blue) is a list) |
(REVERSE z) | (list a is (red white blue)) |
(CDDAR z) | (blue) |
Arithmetic Functions
| Function | Result |
|---|---|
(ADD x1 x2 ...) or (+ ...) | sum of all arguments |
(SUB a b) or (- a b) | a - b |
(MULT x1 x2 ...) or (* ...) | product of all arguments |
(DIV a b) or (/ a b) | a / b (exact division, so 54/4 is 13.5) |
(SQUARE a) | a × a |
(EXP a n) | an |
(EQ a b) | true if a and b are equal, NIL otherwise |
(POS a) | true if a is positive, NIL otherwise |
(NEG a) | true if a is negative, NIL otherwise |
User-defined Functions
(DEF name (parameters) body) defines a new function. (DEFUN is sometimes used instead of DEF.) For example, (DEF SECOND (args) (CAR (CDR args))) defines SECOND, which returns the second element of its argument: (SECOND '(a b c d e)) is b. When a user-defined function is called, substitute the argument for the parameter name in the body and evaluate as usual.
Examples
Evaluate (MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 6 (SUB 2 5))).
- (ADD 6 5 0) = 11
- (MULT 5 1 2 2) = 20
- (SUB 2 5) = -3, so (DIV 6 -3) = -2
- (MULT 11 20 -2) = -440
Value: -440
Evaluate (CDR '((2 (3)) (4 (5 6) 7))).
The quoted list has two elements: (2 (3)) and (4 (5 6) 7). CDR removes the first element and returns what is left, which is a list containing one element.
Value: ((4 (5 6) 7))
(SETQ X '(RI VA FL CA TX))
(CAR (CDR (REVERSE X)))- X is bound to the list (RI VA FL CA TX).
- (REVERSE X) = (TX CA FL VA RI)
- (CDR ...) = (CA FL VA RI)
- (CAR ...) = CA
Value: CA
(SETQ X '(a c s l))
(DEF WHAT (args) (CONS args (REVERSE (CDR args))))
(DEF SECOND (args) (CONS (CAR (CDR args)) NIL))| Statement | Value | Why |
|---|---|---|
(WHAT X) | ((a c s l) l s c) | CDR is (c s l), reversed is (l s c); CONS puts the whole list X in front |
(SECOND X) | (c) | second element c, CONSed onto the empty list |
(SECOND (WHAT X)) | (l) | second element of ((a c s l) l s c) is l |
(WHAT (SECOND X)) | ((c)) | CDR of (c) is NIL, reversed is NIL; CONS gives ((c)) |
Practice Problems
Write list answers with parentheses and single spaces, for example (A B C). Spacing and capitalisation are ignored when checking.
Problem 1 Junior
Evaluate the following expression:
(ADD (MULT 3 4) (SUB 10 4) (DIV 12 3))Solution
- (MULT 3 4) = 12
- (SUB 10 4) = 6
- (DIV 12 3) = 4
- (ADD 12 6 4) = 22
Value: 22
Problem 2 Junior
Evaluate the following expression:
(CAR (CDR '(RED GREEN BLUE YELLOW)))Solution
- (CDR '(RED GREEN BLUE YELLOW)) removes the first element: (GREEN BLUE YELLOW)
- (CAR (GREEN BLUE YELLOW)) returns the first element: GREEN
This is the same as (CADR '(RED GREEN BLUE YELLOW)), the second element of the list.
Value: GREEN
Problem 3 Intermediate
Evaluate the following expression:
(CONS (CAR '(A B C)) (REVERSE '(D E F)))Solution
- (CAR '(A B C)) = A
- (REVERSE '(D E F)) = (F E D)
- (CONS A (F E D)) puts A at the front of the list: (A F E D)
Value: (A F E D)
Problem 4 Intermediate
What is the value of the last expression?
(SETQ X '(3 5 7 9))
(SUB (MULT (CADR X) (CAR (REVERSE X))) (CADDR X))Solution
- X = (3 5 7 9)
- (CADR X) = (CAR (CDR X)) = (CAR (5 7 9)) = 5
- (REVERSE X) = (9 7 5 3), so (CAR (REVERSE X)) = 9
- (MULT 5 9) = 45
- (CADDR X) = (CAR (CDR (CDR X))) = (CAR (7 9)) = 7
- (SUB 45 7) = 38
Value: 38
Problem 5 Senior
What is the value of the last expression?
(DEF F (L) (CONS (CAR (CDR L)) (REVERSE (CDR (CDR L)))))
(SETQ Y '(P Q R S))
(F (F Y))Solution
F takes the second element of its argument and puts it in front of the reversed remainder (everything after the second element). Apply it twice.
- Inner call, (F Y) with L = (P Q R S):
- (CAR (CDR L)) = (CAR (Q R S)) = Q
- (CDR (CDR L)) = (R S), reversed = (S R)
- (CONS Q (S R)) = (Q S R)
- Outer call, F of (Q S R):
- (CAR (CDR L)) = (CAR (S R)) = S
- (CDR (CDR L)) = (R), reversed = (R)
- (CONS S (R)) = (S R)
Value: (S R)