An Overview of Lisp
(from Paradigms of Artificial Intelligence Programming
by Peter Norvig)
Contents:
1. Special forms for definitions: defun, defmacro, defvar, derparameter,
defconstant, defstruct
2. Special forms for conditionals: cond, if, when, unless, case
3. Special forms for variables: setf, let, let*, lambda, push, pop, incf, decf
4. Functions and special forms for repetition (looping):
dolist, dotimes, do, do*, loop, mapc, mapcar,
some, every, find, reduce,
recursion
5. Other special forms: #', progn, trace, return
6. Macros: defmacro
7. List functions: see the table of list functions
8. Comparison of eq, eql, equal, equalp
9. Functions on sequences (arrays): nth, elt, aref, char, bit, sbit, svref
10. Functions for maintaining tables: association lists: assoc, rassoc
Hash tables, property lists
11. Functions on trees: copy-tree, tree-equal
12. Functions on numbers: +, -, *, / etc. See the table
13. Functions on sets: intersection, union, set-difference, member, subsetp,
adjoin
14. Destructive function: nconc
15. Overview of data types: See the table
16. Input/Output: read, read-char, read-line, write, print, princ, prinl,
with-open-file, format, terpri
17. Debugging tools: apropos, describe, inspect, documentation
Timing tools: time
18. Evaluation: funcall, apply, eval
19. Returning multiple values: round
1. Special forms for definitions - used to introduce new global functions,
macros, variables, and structures.
(defun function-name (parameter...) "optional documentation" body...)
(defmacro macro-name (parameter...) "optional documentation" body...)
Three forms for introducing special variables.
(defvar variable-name initial-value "optional documentation")
(defparamter variable-name value "optional documentation")
(defconstant variable-name value "optional documentation")
All the def- forms define global objects.
Structures:
(defstruct structure-name "optional documentation" slot...)
Example:
(defstruct name
first
(middle nil)
last
)
This automatically defines the constructor function make-name,
the recognizer predicate name-p, and the accessor functions
name-first, name-middle, and name-last
Example creation of a name structure:
(setf b (make-name :first 'Barney :last 'Rubble))
>(name-first b) => BARNEY
>(name-middle b) => NIL
>(name-last b) => RUBBLE
>(name-p b) => T
>(name-p 'Barney) => NIL
>(setf (name-middle b) 'Q)
>#S(NAME :FIRST BARNEY :MIDDLE Q :LAST RUBBLE)
Back to Contents
2. Special forms for Conditionals
(cond (test result...)
(test result...)
...
)
The tests usually involve a set of parenthesis; often the form
of the cond looks like:
(cond ((test) result...)
((test) result...)
...
( t result...)
)
The forms "when" and "unless" operate like a single cond clause. Both forms
consist of a test followed by any number of expressions, which are evaluated
if the test is true for "when" and if the test is false for "unless".
The "and" form tests whether every one of a list of conditions is true, and
"or" whether any is true. Both work left to right and stop as soon as the
final result can be determined.
Here's a table of equivalences:
conditional if form cond form
(when test a b c) (if test (progn a b c)) (cond (test a b c))
(unless test x y) (if (not test) (progn x y)) (cond (not test) x y)
(and a b c) (if a (if b c)) (cond (a (cond (b c)))
(or a b c) (if a a (if b b c)) (cond (a) (b) (c))
(case a (b c) (t x)) (if (eql a 'b) c x) (cond ((eql a 'b) c) (t x))
Back to Contents
3. Special forms for dealing with Variables and Places
Lisp C
(setf x 0) x = 0;
(setf (aref A i j) 0) A[i,j] = 0;
(setf (rest list) nil) list->next = nil;
(setf (name-middle b) 'Q) b.middle = 'Q';
Let forms:
(let ((variable value)
...
)
body
)
Example:
(let ((x 40)
(y (+ 1 1))
)
(+ x y)
) => 42
Lambda version:
((lambda (variable ...)
body)
)
((lambda (x y)
(+ x y)
)
40 ;;two parameters
(+ 1 1)
)
Let* - use when you want to use one of the newly introduced variables
in a subsequent value computation.
(let* ((x 6)
(y (* x x))
)
(+ x y)
) => 42
Push and Pop (both change the list)
(push x list) == (setf list (cons x list))
(pop list) == (let ((result (first list))
)
(setf list (rest list))
result
)
Increment and decrement functions
(incf x) == (incf x 1) == (setf x (+ x 1))
(decf x) == (decf x 1) == (setf x (- x 1))
Two examples, determining the winner:
(defstruct player
(score 0)
(wins 0)
)
(defun determine-winner (players)
"Increment the WINS for the player with the highest score"
(incf (player-wins (first (sort players #'>
:key #'player-score)))))
This is the same as:
(defun determine-winner (players)
"Increment the WINS for the player with the highes score"
(let ((temp (first (sort players #'> :key #'player-score))))
(setf (player-wins temp) (+ (player-wins temp) 1))))
Back to Contents
4. Functions and Special Forms for Repetition (looping)
dolist loop over elements of a list
dotimes loop over successive integers
do, do* general loop, sparse syntax
loop general loop, verbose syntax
mapc, mapcar loop over elements of lists(s)
some, every loop over list until condition
find, reduce, etc. more specific looping functions
recursion general repetition
DOLIST:
(dolist (variable list optional-result)
body...
)
Example:
(defun length1 (list)
(let ((len 0))
(dolist (element list)
(incf len))
len ;;Return len when "let" is done
)
)
DOTIMES:
(dotimes (variable number optional-result)
body ...
)
DO (a general loop construct)
(do ((variable initial next)
...
)
(exit-test result)
body...
)
Example:
(defun length3 (list)
(do ((len 0 (+ len 1))
(lst list (rest lst))
)
((null lst) len)
)
)
MAPCAR:
(mapcar #'- '(1 2 3)) => (-1 -2 -3)
(mapcar #'+ '(1 2) '(10 20)) => (11 22)
(mapcar #'+ '(1 2) '(10 20) '(100 200)) => (111 222)
Many functions accept keywords that allow the user to vary the test
for comparing elements, or to only consider part of the sequence:
(remove 1 '(1 2 3 2 1 0 -1)) => (2 3 2 0 -1)
(remove 1 '(1 2 3 2 1 0 -1) :key #'abs) => (2 3 2 0)
(remove 1 '(1 2 3 2 1 0 -1) :test #'< ) => (1 1 0 -1)
(remove 1 '(1 2 3 2 1 0 -1) :start 4) => (1 2 3 2 0 -1)
Some have corresponding functions ending in -if or -f-not that take a
predicate rather than an element to match against:
(remove-if #'oddp '(1 2 3 2 1 0 -1)) => (2 2 0)
(remove-if-not #'oddp '(1 2 3 2 1 0 -1)) => (1 3 1 -1)
(find-if #'evenp '(1 2 3 2 1 0 -1)) => 2
The following two tables assume these two values:
(setf x '(a b c))
(setf y '(1 2 3))
(every #'oddp y) => nil test if every element satisfies the predicate
(some #'oddp y) => t test if some element satisfies the predicate
(mapcar #'- y) => (-1 -2 -3) apply function to each element and return
result in a list
(mapc #'print y) => prints 1 2 3 perform operation on each element
This table lists functions that have -if and -if-not versions and also
accept keyword arguments.
(member 2 y) => (2 3) see if element is in list
(count 'b x) => 1 count the number of matching elements
(delete 1 y) => (2 3) omit matching elements
(find 2 y) => 2 find first element that matches
(position 'a x) => 0 find index of element in sequence
(reduce #'+ y) => 6 apply function to successive elements
(remove 2 y) => (1 3) like delete, but makes a new copy
(substitute 4 2 y) => (1 4 3) replace elements with new ones
Repetition through recursion
Example:
(defun length (lst)
(if (null lst)
0
(+ 1 (length (rest lst)))
)
)
Recursive view of a list:
"a list is either the empty list or an element consed onto another list"
Two basic views of a list:
"list-as-sequence" non-recursive view
"list-as-first-and-rest" recursive view
One view is not necessarily better than the other.
Recursive functions can be inefficient if the compiler must allocate
memory for each recursive call (backtracking).
Tail recursion is more efficient:
(defun length (lst)
(length-aux lst 0))
(defun length-aux (sublist len-so-far)
(if (null sublist)
len-so-far
(length-aux (rest sublist) (+ 1 len-so-far)))
)
Back to Contents
5. Other Special forms: #', PROGN, TRACE, RETURN
#'f == (function f)
(progn
(setf x 0)
(setf x (+ x 1))
x
) => 1
PROGN is the equivalent of a begin..end block in other languages,
but used INFREQUENTLY in Lisp. Programs written in a functional
style never need a sequence of actions, because they don't have
side-effects.
(trace length) traces the function length.
(untrace length) turns off the trace.
Back to Contents
6. Macros: DEFMACRO
(defmacro while (test &rest body)
"Repeat body while test is true"
`(loop (unless ,test (return nil))
,@body))
The backquote character inidicates that what follows is mostly
a literal expression, but may contain some components that are to be
evaluated. Anything marked with a leading "," is evaluated and inserted
into the structure. Anything marked with a ",@" must evaluate to a list
that is spliced into the structure: each element of the list is inserted,
without the top-level parenthesis.
Examples of backquote:
(setf test1 '(a test)) => (A TEST)
`(this is ,test1) => (THIS IS (A TEST))
`(this is ,@test1) => (THIS IS A TEST)
`(this is .,test1) => (THIS IS A TEST)
`(this is ,@test1 -- this is only ,@test1)
=> (THIS IS A TEST -- THIS IS ONLY A TEST)
At the end of a list, the ., has the same effect as ,@
Back to Contents
7. Functions as Lists
Assume the following assignments:
(setf x '(a b c))
(setf y '(1 2 3))
A table of list functions:
(first x) x=> a first element of a list
(second x) => b second element of a list
(third x) => c third element
(nth 0 x) => a nth element of a list, 0 based
(rest x) => (b c) all but the first element
(car x) => a
(cdr x) => (b c)
(last x) => (c) last cons cell in a list
(length x) => 3
(reverse x) => (c b a)
(cons 0 y) => (0 1 2 3) add to front of list
(append x y) => (a b c 1 2 3) append together elements
(list x y) => ((a b c) (1 2 3)) make a new list
(list* 1 2 x) => (1 2 a b c) append last argument to others
(null nil) => T predicate is true of an empty list
(null x) => NIL ...and false for everything else
(listp x) => T predicate is true of a list including nil
(listp 3) => NIL ...false for nonlists
(consp x) => T predicate is true for non-nil lists
(equal x x) => T true for lists that look the same
(equal x y) => NIL
(sort y #'>) => (3 2 1) sort a list according to a comparison
(subseq x 1 2) => (B) sub-sequence with given start and end points
(cons 'a 'b) => a.b dotted pair, single cons cell
Back to Contents
8. Comparison of EQ, EQL, EQUAL, EQUALP
eq tests for the exact same object
eql tests for objects that are either eq or are equivalent numbers
equalp is like equal except it also matches upper and lower case
letters and numbers of different types
x y eq eql equal equalp
'x 'x T T T T
'0 '0 ? T T T ? - Depends on implementation
'(x) '(x) nil nil T T
'"xy" '"xy" nil nil T T
'"Xy" '"xY" nil nil nil T
'0 '0.0 nil nil nil T
'0 '1 nil nil nil nil
= , tree-equal, char-equal, and string-equal These are
specialized predicates that compare numbers, trees,
characters, and strings
Back to Contents
9. Functions on sequences NTH, ELT, AREF, CHAR, BIT, SBIT, SVREF
(nth n list)
(elt sequence n)
(aref array n)
(char string n)
(bit bitvector n)
(sbit simple-bitvector n)
(svbit simple-vector n)
Back to Contents
10. Functions for maintaining tables
Association List: a list of dotted pairs, where each pair consists
of a key and a value. Together, the list of pairs form a table.
Given a key, we can retrieve the corresponding value from the table,
or verify that there is no such key stored in the table.
Example:
(setf state-table
'((AL . Alabama) (AK . Alaska) (AZ . Arizona) (AR . Arkansas)))
(assoc 'AK state-table) => (AK . ALASKA)
(cdr (assoc 'AK state-table)) => ALASKA
(assoc 'TX state-table) => NIL
RASSOC is used to search a table for a value rather than by key
(rassoc 'Arizona table) => (AZ . ARIZONA)
(car (rassoc 'Arizona table)) => AZ
HASH TABLES:
(setf table (make-hash-table))
(setf (get-hash 'AL table) 'Alabama)
(setf (get-hash 'AK table) 'Alaska)
(setf (get-hash 'AZ table) 'Arizona)
(setf (get-hash 'AR table) 'Arkansas)
To retrieve values:
(gethash 'AK table) => ALASKA
(gethash 'TX table) => NIL
PROPERTY LISTS: a property list is a list of alternating
key/value pairs
a-list: ((key . value) (key . value) ...)
p-list: ((key value key value ...)
(setf (get 'AL state) 'Alabama)
(setf (get 'AK state) 'Alaska)
(setf (get 'AZ state) 'Arizona)
(setf (get 'AR state) 'Arkansas)
To retrieve values:
(get 'AK 'state) => ALASKA
(get 'TX 'state) => NIL
Back to Contents
11. Functions on Trees
A list with 3 elements or a tree with 5 non-null leaves
((a b) ((c)) (d e))
COPY-TREE creates a copy of a tree, and TREE-EQUAL tests if two
trees are equal by traversing cons cells.
(setf tree '((a b) ((c)) (d e)))
(tree-equal tree (copy-tree tree)) => T
Back to Contents
12. Functions on Numbers
(+ 4 2)
(- 4 2)
(* 4 2)
(/ 4 2)
(> 100 99)
(= 100 100)
(< 99 100)
(random 100) => 42 random number from 0 to 99
(expt 4 2) => 16
(sin pi) => 0
(asin 0) =>0.0
(min 2 3 4) => 2 (also max)
(abs -3)
(sqrt 4)
(round 4.1) => 4 also truncate, floor, ceiling
(rem 11 5) remainder, also mod
Back to Contents
13. Functions on Sets
(setf r '(a b c d))
(setf s '(c d e))
(intersection r s) => (c d)
(union r s) => (a b c d e)
(set-difference r s) => (a b)
(member 'd r) => (d)
(subsetp s r) => NIL
(adjoin 'b s) => (b c d e)
(adjoin 'c s) => (c d e) don't add duplicates
lists integers bit vectors
intersection logand bit-and
union logior bit-ior
set-difference logandc2 bit-andc2
member logbitp bit
length logcount
(bit-and #*11110 #*11001) => #*11000
(logand #b11110 #b11001) => 24 #b11000
Back to Contents
14. Destructive function NCONC
(setf x '(a b c))
(setf y '(1 2 3))
(nconc x y) => (A B C 1 2 3)
x => (A B C 1 2 3)
y => (1 2 3)
Back to Contents
15. Overview of Data Types
character #\c
number 42
float 3.14159
integer 42
fixnum
bignum
function #'sin
symbol sin
null nil
keyword :key
sequence (a b c) sequences include lists and vectors
list (a b c) a list is either cons or null
vector #(a b c)
cons (a b c) a cons is a non nil list
atom t anything that is not a cons
string "abc"
array #1A(a b c)
structure #S(type ...) structures are defined by defstruct
hash-table hash tables are created by make-hash-table
Almost every data type has a recognizer predicate
TYPE-OF
(type-of 123) => FIXNUM
TYPEP
(typep 123 'fixnum) => T
(typep 123 'number) => T
SUBTYPE
(subtype 'fixnum 'number) => T
Specialized data types:
Type Example Explanation
t 42 Every object is of type t
nil No object is of type nil
complex #C(0 1) Imaginary numbers
bit 0 0 or 1
rational 2/3 Integers and ratios
ratio 2/3
simple-array #1A(x y)
readtable
package
pathname
stream
random-state
Back to Contents
16. Input/Output
read, read-char, read-line
print, princ (doesn't print the quotes)
prinl prints without the newline and space
write
with-open-file
format
terpri terminate print line
Example:
(with-open-file (stream "test.text" :direction :output)
(print '(hello there) stream)
(princ 'goodbye stream))
GOODBYE ; and creates the file test.text
(with-open-file (stream "test.text" :direction :input)
(list (read stream) (read-char stream) (read stream)
(read stream nil 'eof)))
((HELLO THERE) #\G OODBYE EOF
(format t "hello world)
hello world
NIL
(format t "~&~a plus ~s is ~f" "two" "two" 4)
two plus "two" is 4.0
NIL
~& means move to a new line
~a means print the arguments as princ would
~s means print the arguments as prinl would
~f means print the number in floating point format
format returns nil
(let ((numbers '(1 2 3 4)))
(format t "~&~{~r~^ plus ~} is ~@r"
numbers (apply #'+ numbers)))
one plus two plus three plus four plus five is XV
~r prints the next argument, which should be a number, in English
~@r prints the number as a roman numeral
~{...~} takes the next argument, which must be a list, and
formats each element of the list according to the format
string inside the braces.
~^ exits from the enclosing ~{ ...~}
Back to Contents
17. Debugging tools
(step expression)
apropos, describe, inspect, documentation
(apropos 'string)
MAKE-STRING
...
(assert test-form (place...) format-ctl-string format-arg...)
Timing tools
(defun f (n) (dotimes (i n) nil))
(time (f 100000))
Back to Contents
18. Evaluation
funcall - apply a function to individual arguments
apply - apply a function to a list of arguments
eval - passed a single argument, which should be a complete form
Back to Contents
19. Multiple values - round
(round 5.1) => 5 .1 returns two values
Back to Contents