LISP Notes

This list includes all Lisp forms needed in this class.

Atoms

Unlike other languages, LISP has only a few primitive data types, called atoms.

t                       true
nil                     false
A, Cow, moo             symbols
1, 2, 3                 numbers
"hey there"             strings

Quoted Forms

A quoted form is a LISP expression that is not immediately evaluated. This is often used to create list literals.

'abc                    Unevaluated symbol
'(1 2 3)                The list (1 2 3), which is not evaluated.  Ex:
                                 (+ 1 2)  -> 3
                                '(+ 1 2)  -> (+ 1 2)

Boolean expressions

(eq x y) returns t if x and y are the same number or the same list. Note: there are other equality tests (eql, equals, etc.). For 334, the distinctions should be not important and eq should sufficient for the problems we do.

                            (eq 1 1)  ->  t
                            (eq 1 2)  ->  nil
                          (eq 'A 'A)  ->  t
                          (eq 'A 'B)  ->  nil
                        (eq nil nil)  ->  t

(< x y) is an arithmetic comparison. Other comparisons include: >, >=, or, and, not.

                            (< 1 2)  ->  t
                            (< 2 1)  ->  nil

(atom x) returns t if x is an atom and nil if x is a list.

                          (atom 'A)   ->  t
                          (atom nil)  ->  t
              (atom (car '(A nil)))   ->  t
              (atom (cdr '(A nil)))   ->  nil

(member x l) returns nil if x is not in the list, or t (or some other non-nil value) if x is in the list.

                 (member 'A '(A B))   ->  t
                 (member 'C '(A B))   ->  nil

Arithmetic expressions

(+ e1 ... en) sums the numbers e1 … en. *, -, / operators work similarly.

                            (+ 1 2 3)  -> 6

Other operators include mod, sin, cos, etc.

                            (mod 7 3)  -> 1

Lists

nil is the empty list.

(cons x ls) the list containing x, followed by the elements in list ls.

                            (cons 'A nil)   -> (A)
                            (cons 'A (B))   -> (A B)
                            (cons nil nil)  -> (nil)

(car ls) is the first element of the list ls.

                            (car '(A B C))  -> A
                    (car (cons 'A '(B C)))  -> A

(cdr ls) is the list ls, excluding the first element.

                                 (cdr nil)  -> nil
                            (cdr '(A B C))  -> (B C)
                    (cdr (cons 'A '(B C)))  -> (B C)

(append l1 l2) is the list containing the elements from l1, followed by the elements from l2.

                     (append '(A B) '(C D)) -> (A B C D)

(length ls) is the length of the list.

                              (length nil)  -> nil
                         (length '(A B C))  -> 3

Conditionals

(cond (p1 e1) ... (pn en)) evaluates each pi in order until it finds a true guard. It then evaluates the expression for that guard:

            (cond ((eq 0 1) 2) (t 3))  -> 3
            (cond ((eq 0 0) 2) (t 3))  -> 2

(if p e1 e2) is more readable syntax for a cond that defines a familiar “if-then-else” structure. Use cond if you have more than two conditions to test.

            (if (eq 0 1) 2 3)  -> 3
            (if (eq 0 0) 2 3)  -> 2

Function definitions

(defun f ls body) defines a function named f, with arguments ls.

                    (defun fact (x) 
                            (cond ((eq x 0) 1)
                                  (t (fact (- x 1)))))

                    (defun mult(x y) (* x y))

(lambda ls body) is an anonymous function expression (aka, a lambda expression).

                    ((lambda (x) (* x x)) 3) -> 9

Higher-order Operations

A higher-order function is a function that takes another function as input. Since functions are first-class values in LISP, higher-order functions are not special in LISP. Nevertheless, a small number of fundamental higher-order functions are used frequently in LISP programs.

(mapcar #'f l) maps the function f over the elements of list l, returning a new list.

                            (mapcar #'atom '(A (2 3) B)) -> (t nil t)
                            (mapcar #'(lambda (x) (+ x 2)) '(1 3)) -> (3 5)

The #’ in front of a lambda or function name extracts the “functional object” assocated with that function or lambda expression. The functional object for a function “f” records the number of arguments expected by f, the code for the body of f, etc.

(apply #'f (e1 ... en)) is equivalent to (f e1 ... en).

                            (apply #'* '(2 2 3))  -> 12
                            (apply #'fact '(1 2 3 4))  -> (1 2 6 24)

(funcall #'f e1 ... en) is equivalent to (f e1 ... en).

                            (funcall #'* 2 2 3)  -> 12
                            (funcall #'fact 1 2 3 4)  -> (1 2 6 24)

For all of these higher-order operations, note that you do not need #' in front of a parameter name that stores a function you have passed into a function. You only need #’` when you refer directly to the symbol for a function definition:

			(defun reverse-map (f l) 
			       (mapcar f (reverse l)))
			(reverse-map #'- '(1 2 3))       ->   (-3 -2 -1)

Impure Features

Here for completeness only. You should not use these in your programs unless explictly told to do so.

(defvar ls '(a b c)) defines a variable ls with value '(a b c).

(rplaca ls x) updates ls to be '(x b c).

(rplacd ls (x)) updates ls to be '(a x).