CS-431
Concepts of Programming Languages
LISP NOTES
BASIC DEFINITIONS
NUMBER
An optional + or - followed by a digit, followed by zero or more
digits.
ATOM (or atomic symbol)
Either (a) a number, or (b) a letter followed by zero or more letters
or digits.
S-EXPRESSION
is either (a) an atom, or (b) a list of s-expressions, i.e., a '('
followed by zero or more s-expressions, followed by a ')'.
SYNTAX OF THE LISP LANGUAGE
Every s-expression is a syntactically legal program! However, most s-
expressions are not meaningful as programs. The function that executes
s-expressions is called EVAL. This function defines the semantics of
LISP.
EVAL
EVAL takes one s-expression and returns another s-expression as the
value of the first one. The rules of evaluation are the following:
1. If the expression is a number, T or NIL, then the value of the
expression is the expression itself.
2. If the expression is a list of the form
(function-name arg1 arg2 ...argk),
then the value is found by first evaluating each argument and then
calling function-name with these values.
Examples
>15
15
>t
t
>(plus 5 3)
8
>(times 2 6)
12
>(plus (times 2 3) 5)
11
3. If the expression is of the form:
(reserved-word arg1 arg2 .. argk),
then the value depends on reserved-word. The arguments may or may not
be evaluated.
EXAMPLE
(SETQ x (PLUS 2 5))
SETQ assigns a value to an atom. The first argument is not evaluated,
but second is. The value associated with this expression is the value
assigned to X, thus
(SETQ X (PLUS 2 5))
7
We say that x is bound to the value 7. SETQ returns the value of the
second argument and has the side effect of assigning this value to the
first argument.
4. If the expression is an atom, other than a number, then the value is
the last value assigned to it. If no value has been assigned, than an
error results.
EXAMPLES OF S-EXPRESSIONS
- Atom
- (this is an atom)
- (A B C)
- (A (B) C)
- ( (A B) C (D E ) )
- (PLUS (times 5 6) (PLUS 3 -5) )
- () null list = nil
- ( () ) not a null list
- ( () () )
Thus, S-expressions are either atoms (including numeric atoms) or
lists.
INVALID S-EXPRESSIONS
- (A B) 3 (5)
- )(
- ((())
- ())(
- ( A B C
ANOTHER RESERVED WORD: QUOTE
EXAMPLES
(QUOTE A) evaluates to A
(QUOTE (A B) ) evaluates to (A B)
(QUOTE (THIS IS A LIST) ) evaluates to (THIS IS A LIST)
Thus, the value of an expression of the form
(QUOTE s-exp ) is s-exp
This can be abbreviated as 's-exp , i.e.
(QUOTE A) is equivalent to 'A
(QUOTE (A B)) is equivalent to '(A B)
PLUS, TIMES and QUOTE are examples of "primitives" or "reserved words",
i.e., functions provided by the system.
SOME LISP PRIMITIVES
CAR
The expression (CAR L) returns the first element of the list L.
EXAMPLE
Suppose L is bound to (a b c). Then, (CAR L) => a
If L is bound to ((x y) (a) c), then (CAR L) => (x y)
NOTE: CAR is a reserved word. In this case, the argument is evaluated
before applying the function CAR. Thus,
(CAR (QUOTE (X (Y)))) = x
(CAR '(X (Y))) = x
What will be the result of:
(CAR (m n))? (undefined function m)
(CAR 'a)? (error, bad argument)
(CAR nil)? (nil, depending on system)
NOTE: nil is considered an atom and a list
CDR
takes a list as argument, and returns a list containing all but the
first element of the given list.
If L is (A B C) then (cdr L) => (B C)
If L is (a), then (cdr L) => nil
(cdr '((a x) (y z ))) => ((y z))
NOTE:
(car (cdr '(a b c))) => b
but
(car '(cdr '(a b c))) => cdr
COMBINING CAR AND CDR
(car (cdr '(A B C ))) = (cadr '(A B C))
(cdr (car (cdr '(A (x y) (z))))) = (cdadr '(A (x y) (z)))
EXERCISE
(a) Evaluate
(cdr '((a b) (c d)))
(cdar '((a b) (c d)))
(cadar '((a (b)) (x y)))
(b) Get the symbol P out of :
(A O P G)
((A O)) (P G))
(((A) (O) (P) (G)))
(((A) (O) (P) (G)))
((((A))) ((O)) (P) G)
SOME LISP PREDICATES
Predicates are functions that return true or false. In Lisp, false is
nil, and true is t or anything other than nil.
ATOM
The expression (ATOM arg) returns t if arg is an atom, nil otherwise.
(SETQ L '(a))
(ATOM L) => nil
(ATOM 'L) => true
(ATOM 'a) => true
(ATOM '(a)) => nil
EQ
The expression (EQ arg1 arg2) returns true if arg1 and arg2 are atoms
and the same (temporary definition)
(EQ 'a 'a) => t
(EQ '(a) '(a)) => nil
NULL
The expression (NULL arg) returns true if arg is a null list.
(NULL '()) => t
(SETQ L nil)
(NULL L) => t
(NULL 'x) => nil
(NULL '(())) => nil
EQUAL
The expression (EQUAL arg1 arg2) returns t if arg1 and arg2 are
equal, whether atoms or lists.
MEMBER
The expression (MEMBER arg1 arg2) returns t if arg1 is an element
in the list arg2
(SETQ L '(a b))
(MEMBER 'a L) => t
(MEMBER 'c L) => nil
(SETQ LL '((a b) (a b)))
(MEMBER L LL) => t
(MEMBER 'a LL) => nil
(MEMBER 'a '(x (a) y)) => nil
NOTE: arg1 must be a top level element of arg2
(SETQ x 'a)
(MEMBER x '(x y)) => nil
(MEMBER x '(x a b) ) => t
(MEMBER 'x '(x y z) ) => t
(MEMBER 'a atom) => error!!
APPEND
Puts together the elements of all lists supplied as arguments.
(SETQ L1 '(x y))
(SETQ L2 '(r (s)))
(APPEND L1 L2) => (x y r (s))
(APPEND L1 L2 L2) => (x y r (s) r (s))
(APPEND '(a) '(b) '( )) => (a b)
NOTE: append does not modify its arguments.
(APPEND L1 'L) error: arguments must be lists.
(APPEND '((a) ((b))) '(a (b))) => ((a) ((b)) a (b))
LIST
Makes a list out of its arguments.
(LIST 'a) => (a)
(LIST '(a b)) => ((a b))
(LIST '(x) 'y 'z) => ( (x) y z)
(SETQ L '(x y))
(LIST 'L) => (L)
(LIST L) => ((X Y))
(LIST L L) => (( X Y) (X Y))
CONS
The expression (CONS arg1 arg2) returns a list whose first element is
arg1 and whose "cdr" is arg2.
(SETQ L '(x))
(CONS 'A L) => (A x)
(CONS 'A '(X)) => (A X)
(CONS '(a) L) => ((a) x)
(CONS L L) => ((x) x)
(CONS 'a '()) => (a)
thus:
(LIST 'a) = (CONS 'a nil)
(LIST 'a 'b) = (CONS 'a (CONS 'b nil))
OTHER PREDICATES
(NUMBERP x) true if x is a number
(> x y) true if x > y
(< x y) true if x < y
(ZEROP x) true if x = 0
These predicates expect numbers as arguments.
MORE ARITHMETIC
(+ x y) returns the sum of x and y
(* x y) returns the product of x and y
(- x y) returns the difference of x and y
(/ x y) returns the quotient of x and y
(1+ x) returns x+1
(1- x) returns x-1
(max x1 x2 ... xk) returns the maximum among x1, x2, ... xk
(min x1 x2 ... xk) returns the minimum among x1, x2, ... xk
THE CONDITIONAL STATEMENT
The syntax is the following:
(COND ( )
........
( ))
is any s-expression, while is a sequence of
zero or more s-expressions. This statement is similar to if-elsif-
elsif-else.
The first antecedent found to be true causes the execution of the
corresponding consequent. The value returned by the COND expression is
the value of the last expression evaluated within the body of the COND.
EXAMPLES
1) (COND ( (NULL L) 'Empty )
( t 'Not-empty))
NOTE: The antecedent is either nil or not nil. It does not necessarily
have to be t!!. Thus, the following example is equivalent to the above:
(COND ( L 'Not-empty)
( t 'Empty) )
2) A COND expression for NOT U
(COND (U nil)
( t t ))
3) A COND expression for (or A B)
(COND ( A t)
( B t) Returns t or nil
( t nil) )
Another version:
(COND (A t) Returns nil or not nil
(t B))
FUNCTIONS IN LISP
Functions are defined using the following syntax:
(defun function-name ()
)
EXAMPLES
1) Our own version of OR:
(defun my-or (A B)
(COND
(A t)
(t B)
)
)
2) Our own version of AND:
(defun my-and (A B)
(cond
(A B)
(t nil)
)
)
3) The function del-a takes an atom a and a list l, and returns a list
consisting of the first occurrence of a within l plus all the elements
in l to the right of a.
(defun del-a (a l)
(cond
((null l) nil)
((equal a (car l)) (cdr l))
( t (del-a a (cdr l)))
)
)
4) The function last returns the last element of a list.
(defun last (l)
(cond
((null l) nil)
((null (cdr l)) (car l))
(t (last (cdr l)))
)
)
5) Our own version of member:
(defun our-member (e l)
(cond
((null l nil)
((equal e (car l)) t)
(t (our-number e (cdr l)))
)
)
6) The function count-atoms determines the total number of atoms at all
levels in the list l.
(defun count-atoms (l)
(cond
((null l) 0)
((atom l) 1)
(t (+ (count-atoms (car l)) (count-atoms (cdr l))))
)
)
7) The function subst replaces each occurrence of y anywhere in the
list z with x.
(defun subst (x y z)
(cond
((null z) nil)
((equal y z) x)
((atom z) z)
(t (cons (subst x y (car z)) (subst x y (cdr z))))
)
)
EXERCISE
Trace the following call by hand:
(subst 'a 'b '(c b a)) ==> (c a a)
THE TRACE STATEMENT
The call (trace function-name) causes LISP to print a trace of
function-name.
EXAMPLE
(defun last (l)
(cond
((null l) nil)
((null (cdr l)) (car l))
(t (last (cdr l)))
)
)
> (trace mylast)
;; Tracing function MYLAST.
> (mylast '(a b c d e f))
1. Trace: (MYLAST '(A B C D E F))
2. Trace: (MYLAST '(B C D E F))
3. Trace: (MYLAST '(C D E F))
4. Trace: (MYLAST '(D E F))
5. Trace: (MYLAST '(E F))
6. Trace: (MYLAST '(F))
6. Trace: MYLAST ==> F
5. Trace: MYLAST ==> F
4. Trace: MYLAST ==> F
3. Trace: MYLAST ==> F
2. Trace: MYLAST ==> F
1. Trace: MYLAST ==> F
INTERNAL REPRESENTATION OF LISTS IN LISP
Lists are represented using "cons" cells, i.e., a cell that holds 2
pointers. The left pointer points to the car of the list, while the
right pointer points to the cdr of the list.
EXAMPLES
List Representation
---------
(a) | | | / |
--|------
|
V
a
--------- --------- ---------
(a b c) | | | --|-->| | | --|-->| | | / |
--|------ --|------ --|------
| | |
V V V
a b c
(a (b))
((a) b)
((a) (b))
(a (b c))
DIFFERENCE BETWEEN EQ AND EQUAL
Oblist
1. (SETQ x 'a) x
(SETQ y 'a) y
a
In this case, eq and equal both return t.
Oblist
x
2. (SETQ x '(a b)) y
(SETQ y x) a
b
Again, in this case eq and equal both return t.
Oblist
3. (SETQ x '(a b)) x
(SETQ y '(a b)) y
a
b
In this case, eq returns nil but equal returns t !
ANOTHER EXAMPLE
The function del-last deletes the last element of a list.
(defun del-last (l)
(cond
((null l) nil)
((null (cdr l)) nil)
(t (cons (car l) (del-last (cdr l))))
)
)
OTHER FUNCTIONS
READ
Reads the next s-expression from the input. For example, the expression
(setq x (read)) reads the next s-expression from the input and assigns
it to x.
PRINT
Prints its argument and advances to the next line.
PRINC
Prints its argument.
LENGTH
Returns the number of top level elements of a list.
NTH
The expression (nth k l) returns the kth element in list l.
LOOPS IN LISP
THE LOOP STATEMENT
The syntax of the LOOP statement is:
(loop
s-exp1
s-exp2
....
s-expk
)
EXAMPLE
(setq x 5)
(loop
(cond ((equal x 5) (return)))
(princ x)
(terpri)
(setq x (1- x))
)
THE DOLIST STATEMENT
The syntax of the dolist statement is:
(dolist (x )
s-exp1
s-exp2
....
s-expk
)
x is bound to the first element of , the body of the loop is
executed, x is bound to the second element of , etc.
EXAMPLE
(dolist (z '(2 5 8 9))
(princ (+ 2 z))
)
THE DO STATEMENT
EXAMPLE:
(do ((x '(a b c) (cdr x)) (y '(10 20 30 40 50) (cddr y)))
((null x) (princ 'the-end))
(princ x)(princ " ")(princ (- y 5))(terpri)
)
THE PROG STATEMENT
Example
The function my-length returns the number of top level elements in the
list L.
(defun my-length (L)
(prog (sum)
(setq sum 0)
loop
(cond
((null L) (return sum))
(t (setq sum (1+ sum))
(setq L (cdr L))
(go loop) )
)
)
)
Another version:
(defun my-length (L)
(prog (sum)
(setq sum 0)
loop
(cond ((null L) (return sum)))
(setq sum (1+ sum)
(setq L (cdr L))
(go loop)
)
)
Example
The function my-reverse reverses the elements of a list.
(defun my-reverse (L)
(prog (temp)
loop
(cond ((null L) (return temp)))
(setq temp (cons (car L) temp))
(setq L (cdr L))
(go loop)
)
)
Example
The function exp raises m to the power n.
(defun exp (m n)
(prog (result exponent)
(setq result 1)
loop
(cond ((= n 0) (return result)))
(setq result (* n result))
(setq n (1- n))
(go loop) )
)
Note:
All arguments in Lisp are passed by value. A variable is bound with
respect to a procedure (or function) if it appears in the procedure's
parameter list. A variable is free with respect to a procedure if it
does not appear in the procedure's parameter list.
Mapcar
EXAMPLE
Write a function that takes a list and/or an argument and returns a
list that indicates whether the corresponding element of l is an atom
or a list:
(defun A-L (l)
(cond
((null l) nil)
((atom (car l)) (cons 'atom (A-L(cdr l))))
( t (cons 'list (A-L (cdr l ))))
)
)
Another way:
(defun A-L1 (x)
(COND
((atom x) 'ATOM)
( T 'LIST)
)
)
We can now write A-L as follows
(defun A-L (l) (mapcar #'A-L1 l))
Example
(setq l '(1 2 3 4 5))
(mapcar #'add1 l)
(2 3 4 5 6)
(mapcar #'evenp l)
(nil t nil t nil)
Functions With 2 Arguments
(setq L1 '(1 2 3))
(setq L2 '(10 20 30))
(mapcar #'plus L1 L2)(11 22 33)
(mapcar #'equal L1 L2)(nil nil nil)
(setq L3 '( (a) (b) (c)))
(mapcar #'cons L1 L2)((1 a) (2 b) (3 c))
APPLY
Takes 2 args., both of which are evaluated. First arg is a
function and second a list of args to the function.
Examples
1. (apply #'cons '(a (b c))) same as (cons 'a '(b c)) = (a b c)
2. (setq L '(1 2 3))
(plus L) does not work!
But (apply #'plus L) works, and does the same as (plus 1 2 3)
The function count-atoms was defined as:
(defun count-atoms (L)
(COND
((null L) 0)
((atom L) 1)
( t (+ (count-atoms (car L)) (count-atoms (cdr L))))
)
)
Using mapcar:
(defun count-atoms (L)
(COND
((null L) 0)
((atom L) 1)
( t (apply #'+ (Mapcar #'count-atoms L)))
)
)
EXAMPLE
Given the function func that takes a number as its argument and returns
another number, compute the sum of func applied to each element of a
list L. Call this function SUMA. For example, if func is SQUARE and L
is (l 2 3) then (SUMA 'SQUARE L) = 14.
SUMA is defined as follows:
(defun suma (func L)
(apply #'+ (mapcar func L))
)
FUNCALL
Similar to apply, but the arguments are not given in a list:
(apply #'cons '(a (b c))) is the same as (funcall #'cons 'a '(b c))
SET
Similar to SETQ, but it evaluates both arguments.
(setq x 'a)
(set x 'b)
then x has the value a, and a has the value b.
EVAL
The argument must evaluate to a lisp expression. Eval evaluates this
expression.
1. (setq x '(cons 'a '(b c)))
(eval x) = (a b c)
2. (setq a 'b)
(setq b 'c)
(eval a) = c
3. (eval (cons '+ '(2 3))) = 5
LAMBDA EXPRESSION
The syntax is:
(lambda (arg1 arg2 …)
s-exp1
s-exp2
…
s-expk
)
A lambda expression is a function without a name. It can be used the
same way as a function:
>((lambda (x) (setq y (+ x 1))) 5)
6
> y
6
With Mapcar:
(setq L '(5 0 -2 1))
(mapcar
'(lambda (n)
(cond
((< n 0) 'neg)
((equal n 0) 'zero)
((> n 0) 'pos)
)
) L)
(pos zero neg pos)
Solution to depth using mapcar and apply:
(defun depth (L)
(cond
((null L) 1)
((atom L) 0)
(t (+ (apply #'max (mapcar #'depth L)) 1))
)
)
EXAMPLE
(defun inc (par)
(setq par (+ par 10))
(setq free par)
)
(setq par 15)
(setq free 10)
(setq arg 10)
(inc arg)
free = 20
par = 15
arg = 10
Mapcar and lambda
rep-a: if element is a return x
(defun rep-a (el)
(COND
((equal el 'a) 'x)
(t el)
)
)
Replace all a's with x in list L
(defun rep-a-l (l)
(mapcar #'rep-a l)
)
can also be written as:
(defun rep-a-l (l)
(mapcar #'(lambda (el)
(cond
((equal el 'a) x)
(t el )
)
) L)
)
Now, define rep-atom: If el is equal to at, return x
(defun rep-atom (el at x)
(cond
((equal el at) x)
( t el)
)
)
We now want to apply this to a list L. We cannot do it as before. We
must have:
(defun rep-atom-l (L at x)
(mapcar #'(lambda (el)
(cond
((equal el at) x)
(t el)
)
) L )
)
This function replaces all elements in L that are equal to at with x.
MACROS
Suppose loc is a list of the form (city state zip)
(setq loc '(cocoa florida 32744))
To get the state we can evaluate (cadr loc) Florida
(defun get-state (L) (cadr L))
We can write this as a macro, as follows:
(defmacro get-state (L)
(cons 'cadr (list L))
)
A call to the macro has the form:
(get-state loc)
The macro is expanded first, then the resulting expression is
evaluated.
(get-state loc) -> (cadr L) -> florida.
POP
Given a list L, say (a b c), set L to (cdr L).
(defmacro pop (x)
(list 'setq x (list 'cdr x))
)
For the call (pop L) -> (setq L (cdr L)) -> (b c)
PUSH
(defmacro push (a stack)
(list 'setq stack (list 'cons a stack))
)
(push xx stack2) -> (setq stack2 (cons xx stack2))
BACK QUOTE
It is similar to the normal quote, except that commas within its scope
have the effect of unquoting the following expression.
Example
(setq x 'abc)
`(a b ,x) -> (a b abc)
With @
(setq ucf '(university of central florida))
'(,@ucf Orlando) -> (university of central florida Orlando)
Can use to write Macros:
(defmacro pop (L)
`(setq ,L (cdr ,L))
)
Another (better) version:
(defmacro pop (L)
`(prog1
(car ,L)
(setq ,L (cdr ,L))
)
)