LISP (List Processing) is not simply a programming lanuage unique among all programming languages; it is a realization of a theoretical construction in the area of mathematical logic by Alonzo Church known as the lambda calculus of recursive functions. LISP is the physical relaization of this abstract computational tool, and was created by John McCarthy in the years 1956-1958. Thus, it is also one of the oldest and enduring programming languages, having only FORTRAN as rival. Though most modern implementations of LISP are very large languages with "environment lists" for saving function definitions and variable values, hundreds of functions, hence also of reserved words, additional data types such as numericals, strings, arrays, structures, macros, etc., the fundamentals are very few and can be used to display the unique thought processes that are involved in LISP programming. These additions are more a matter of convenience for the programmer.
LISP is essentially an interpreted language as opposed to being compiled. Although LISP compilers have been developed, an essential feature of LISP is destroyed when programs are compiled. This feature, especially dear to the area of AI is that a function written in LISP is also a data object of LISP, which is to say that a function in LISP is a list. A theoretical consequence of this fact is that programs can be written in LISP which modify themselves: a LISP program can, in a fashion determined by the programmer, learn.
I'm going to describe the most primitive form of LISP, and not get involved in the additional complexities of modern implementations such as "Common Lisp". Where other programming languages are centered on the concept of iteration, LISP is centered on recursion. While other languages start immediately with a collection of data types: integer, floating point, character, string, ...; LISP has only two primitive data types, atom and list. The concept of list is defined recursively:
0) An atom cannot contain anything
1) A list is a list of elements that can be lists or atoms
For example, using standard notation of '(' and ')' as list
delimiters, white space as entity separators.
(a (b c) (d (e f)))
is a list of three elements whose first element is a, whose second
is the list (b c) and whose third element is the list (d (e f)).
After submitting a list to the LISP interpreter program, the interpreter attempts to "evaluate" the list. This references the central function of LISP called, reasonably enough (eval). The secondary functions called (car) and (cdr), the latter being pronounced either "cuder" or "cudder", define operations on lists that are used to dissect lists and pull out their pieces. The (car) operation is "return the first element of the list". The (cdr) operation is "return the list with the first element deleted".
Before giving examples of using (car) and (cdr), there are a few more things to say about the evaluation process and the syntax of LISP functions. A function is given in the form:
(function-name argument-1 argument-2 ... argument-3)
where presumably, you have given the right number of argruments
in the right order if a specific number and order is required.
In the the cases of (car) and (cdr), only one argument is taken.
What is actually done when more arguments are given is not
necessarily determined and is interpreter dependent.
The other thing to remember is that before the function is evaluated, the arguments of the function are evaluated. Thus entering
(car (a (b c) (d (e f))))
is sure to generate an error (unless some provisions have been secretly
made so that eval knows how to evaluate the list that is the argument to (car).
We often want the interpreter to accept a list literally and not
attempt an evaluation.
To do this, there is the function (quote), which says to (eval),
"don't evaluate my argument.
Now for some examples. The LISP prompt often takes the form "->", which we'll use for the entry string and underneath, we'll write the returned value. Notice that LISP functions are just like mathematical functions: they take arguments and return values.
Examples:
-> (quote (a (b c) (d (e f))))
(a (b c) (d (e f)))
-> (car (quote (a (b c) (d (e f)))))
a
-> (cdr (quote (a (b c) (d (e f)))))
((b c) (d (e f)))
-> (car (cdr (quote (a (b c) (d (e f))))))
(b c)
-> (car (cdr (cdr (quote (a (b c) (d (e f)))))))
(d (e f))
Using car and cdr we have pulled out each of the three elements of
the original list.
Clearly, one can use these functions to pull out any of the atoms
of the list.
What happens if we ask for the evaluation
-> (cdr (cdr (cdr (quote (a (b c) (d (e f))))))) ?
There are no elements of the list left to delete on the third
application of (cdr), so this should return an empty list
-> (cdr (cdr (cdr (quote (a (b c) (d (e f)))))))
()
It is a convention, and perhaps a logically infelicitous one,
of most LISP interpreters to equate the empty list with a selfevaluating
atom called "nil".
Thus,
-> (cdr (cdr (cdr (quote (a (b c) (d (e f)))))))
nil
-> ()
nil
-> (quote ())
nil
-> nil
nil
The primary boolean function (predicate function in "lispese") is the one which distinguishes between the two data types atom and list. The predicate function is called (atom), and returns t if its argument does not evaluate to a list, and nil otherwise. Like many primitive verbs of human languages, (atom) is morphologically irregular. If other more complex data types are introduced, it is useful to have other similar predicates (atomp) and (listp), which have morphological conformity with all subsequently defined predicates in that they have a terminal 'p' (standing as a predicate marker in the function name). The values that atom returns sets the stage for the two internally defined selfevaluating boolean values "nil" and "t".
Examples:
-> nil
nil
-> t
t
-> (atom ())
t
-> (atom ())
t
-> (atom nil)
t
-> (atom t)
t
-> (atom (quote a))
t
-> (atom (quote (a b)))
nil
An important addition to LISP in any real programming situation is the internally maintained environment list. Some implementations allow several of these. The environment list allows the global assignment of values to symbolic atoms. The primitive function to make this assignment is (set), which is used as follows:
-> (set (quote a) (quote b))
b
The function (set), as any other lisp function returns a value,
and it is the value that has now been assigned to the symbolic atom 'a'.
Note that both arguments will be evaluated and to be kept literal,
must be quoted. After the above evaluation, there is the side effect
in the evironment list so that
-> a
b
That is, 'a' now evaluates to 'b'.
A symbol to which a value can be set should at least start with
an alphabetic or one of a set of allowable symbols, but may contain
numerics after that. This is a common convention, that has no
particular logic to it. A symbolic atom can be assigned a value
that is any admissable data type.
-> (set (quote xyzzy) (quote (a (b c) (d (e f)))))
(a (b c) (d (e f)))
and then
-> xyzzy
(a (b c) (d (e f)))
and
-> (cdr (car (cdr (cdr xyzzy))))
((e f))
Most often, though not always, the symbolic atom to which we want to assign a value is known and fixed. (There are ways of combining atoms to make new atoms.) The constant quoting of the the first argument to (set) becomes irksome, so for convenience another function is always present, (setq), which does not evaluate it's first argument. We could, and usually would, write the previous (set) as
-> (setq xyzzy (quote (a (b c) (d (e f)))))
(a (b c) (d (e f)))
Numbers quickly enter the picture as specialized data types, together with the standard algebraic operations that they admit. They evaluate to themselves and cannot be assigned values: they are not "symbolic atoms". The various atoms are usually typed (or at least pretyped) by the lexical analyzer. Although heavy duty lisp interpreters are quite capable of dealing with transcendental functions of complex variables, for simplicity we'll just use integers for examples.
-> (setq x (plus 1 2 3 4))
10
with
-> x
10
the return value of the list evaluation of (plus 1 2 3 4)
having been assigned as value of the symbolic atom x.
For a language starting so simply, Lisp has as its primitive and first conditional a rather complex structure (cond). Its syntax looks like this:
(cond ( <predicate1> <return1> )
( <predicate2> <return2> )
...
( <predicateN> <returnN> )
( t <return> ) )
In evaluating the (cond) list, the interpreter evaluates the
first predicate list, <predicate1>; if it evaluates to t,
the return expression is evaluated and that value is returned.
If <predicate1> does not evaluate to t, <predicate2> is
evaluated, and so on down the list.
The final t as predicate, which is just good form,
is the default return, so all contingencies have been accounted for.
Lambda binding is a way of assigning a value to a symbolic atom on the fly; it is not set in the environment list, and is understood only locally in the computational sequence. It is also a way of creating a locally defined function.
Example:
-> ((lambda (x) (car (cdr x))) (quote (a b c)))
b
This requires a little explanation.
The binding function (lambda) assigns the local symbol 'x' to the
evaluation of the expression (quote (a b c)), and then evaluates the
"local functional form" (car (cdr x)). The value of x, i.e., (a b c)
is understood only within this expression, and is not accessible from
any computational list structure that may contain it.
Note that the lambda expression
(lambda (x) (car (cdr x)))
sits in the position of a named function but is a nameless
proceedure given explicitly. During the execution of a Lisp
program, contingencies that arise can cause special functions
of this type since they are lists can be created on the fly, as
needed and applied to arguments.
Function definitions also, ultimately use lambda bindings but, these definition lists are then set and stored in the environment. There are several ways of defining functions, the several again for convenience of writing shorter code. We'll take the middle ground and define a function using (define)
-> (define (first (lambda (x) (car x))))
first
A function "first" is now bound in the environment list and can
be used exactly as any of the internal functions.
-> (first (quote ((a b) (c d)) ) )
(a b)
One can also use the form (defun) which hides the lambda binding
-> (defun first (x) (car x))
first
This does exactly the same thing; the value of the symbol "first"
will be the same in either case and one can see it:
-> first
(define (first (lambda (x) (car x))))
There are several standard short hand coding notations to make the programmer's life a little easier. Most of these are called "read macros" and are loaded automatically as definitions when the interpreter is fired up. One deal with the seemingly ubiquitous (quote) function.
(quote (a b c))
one can also write
'(a b c)
The other has to to with relieving the complexity of interleaving
uses of (car) and (cdr), so that the following notations are equivalent:
(car (cdr x)) <-> (cadr x)
(cdr (car x)) <-> (cdar x)
(cdr (cdr x)) <-> (cddr x)
(cdr (cdr (cdr x))) <-> (cdddr x)
Any number of (car)s and (cdr)s may be so reduced, just
mind or 'a's and 'd's.
A few function examples:
; File: /usr/lib/ulisp/hanoi.L ; ; Tower of Hanoi Problem - ; ; E.g. (hanoi 5) returns a list of the sequence of moves for 5 disks ; ; Sources: Lisp (second edition), P. H. Winston & B. K. P. Horn, pp.112-114 ; Addison-Wesley (1984); ; Metamagical Themas, Douglas Hofstadter, pp. 425-430 ; Basic Books (1985). ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; N disks on spindle A to start (defun hanoi (N) (transfer 'A 'B 'C N) ) ; (defun move-disk (from to) (list (list 'move 'disk 'from from 'to to)) ) ; (defun transfer (from to spare N) (cond ( (eql N 1) (move-disk from to) ) ( t (append (transfer from spare to (sub1 N)) (move-disk from to) (transfer spare to from (sub1 N)))) ) ) ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; END ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; File: /usr/lib/ulisp/mandc.L ; ; The missionary and the cannibals problem - adapted for ULISP ; ; Source: Programming Languages (second edition), Allen B. Tucker, ; pp. 344-246, McGraw-Hill (1986) ; ; Usage: (mandc) ; (defvar EMPTY-BANK '(0 0 0)) ; (defun mandc () (prog ( q history ) ; Init queue and possible moves (setq possibles '( (0 2 1) (0 1 1) (1 1 1) (1 0 1) (2 0 1))) (setq q (list (list (list '(3 3 1) EMPTY-BANK)))) repeat ; this loop is repeated until the left bank is empty (cond ( (equal (caaar q) EMPTY-BANK) ; Is left bank empty? ; Show answer and end (print 'SOLUTION-PATH: ) (return (display (reverse (car q)))) ) ; Discard a path if either cannibalism occurs or path ; represents a loop ( (or (eaten (caar q)) (member (caaar q) history)) (setq q (cdr q)) (go repeat) ) ) ; Now add this state to the history and expand to next state (setq history (cons (caaar q) history)) (setq q (append (expand (car q) possibles) (cdr q))) (go repeat) ) ) (defun eaten (state) ; This function checks for cannibalism by looking at the left bank ; the car state. There, if M is 1 or 2 and M != C, then there is ; cannibalism on one bank or the other. Otherwise there is none. (and (or (equal (caar state) 1) (equal (caar state) 2)) (not (equal (caar state) (cadar state))) ) ) (defun expand (path possibles) ; This function develops all possible moves out of the current state. (cond ( (null possibles) nil) ( (moveok (car path) (car possibles)) (cons (cons (move (car path) (car possibles)) path) (expand path (cdr possibles)))) ( t (expand path (cdr possibles))) ) ) (defun moveok (state onemove) ; Here, we subtract the number of missionaries and cannibals in the ; boat from the number remaining on the current bank, to be sure that ; we don't take more than are there. (cond ( (zerop (caddar state)) ; See if boat is on the right (subtractall (cadr state) onemove) ) ( t (subtractall (car state) onemove) ) ) ) (defun subtractall (triple onemove) ; This function subtracts all three numbers in a single move of the boat ; from the contents of a bank, and returns nil if any one of the ; differences < 0 (not (negp (apply 'min (mapcar 'sub triple onemove)))) ) (defun move (state onemove) ; This function carries out a move by subtracting the numbers in a ; single move of the boat from one bank and adding them to the other. (cond ( (zerop (caddar state)) ; Check for boat on right (list (mapcar 'add (car state) onemove) (mapcar 'sub (cadr state) onemove)) ) ( t (list (mapcar 'sub (car state) onemove) (mapcar 'add (cadr state) onemove)) ) ) ) (defun display (path) (puts "\n Shore1 Shore2\n m c b m c b\n" ) (display2 path) ) (defun display2 (path) ; This function displays the resulting solution (cond ( (endp path) 'END ) ( t (print (car path)) (display2 (cdr path)) ) ) )
; File: /usr/lib/ulisp/math/quadratic.L ; ; The quadratic formula returning a list of the roots of a ; quadratic equation with real or complex coefficients. ; (define (quadratic (lambda (A B C) (prog (D TR) (setq D (divide (discriminant A B C) (mult 2 A))) (setq TR (minus (divide B (mult 2 A)))) (return (list (add TR D) (sub TR D))) ) ))) ; ; (define (discriminant (lambda (A B C) (sqrt (sub (mult B B) (mult 4 (mult A C)))) ))) ;
; /usr/lib/ulisp/fix-pt.L ; ;; Find a fixed point of a function ;; Adapted from SCHEME language ;; Cf Byte February 1988 p.208 ; ;; NB The amount of recursion depending on the C stack can easily blow the ;; stack if it cannot be fixed large enough, or allowed (depending on the ;; processor) to grow large enough. ;; ;;;;;;;;;;;;;;;;;;;;; Example: ; With (defun plogp (p) (minus (mult p (log p)))) ; ; (fix-pt 'plogp .38) -> .367879 ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Note the use of multiple lambda bodies and a function which defines functions. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #| ; The original (define (fix-pt (lambda (f initial-value) (setq epsilon 1.0e-10) (define (close-enough? (lambda (v1 v2) (lessp (abs (sub v1 v2)) epsilon)))) (define (loop (lambda (value) (let ((next-value (f value))) (if (close-enough? value next-value) next-value (loop next-value)))))) (loop initial-value) ))) |# ;;;; The modification (define (fix-pt (lambda (f initial-value) (setq epsilon 1.0e-10) (putd 'close-enough? '(lambda (v1 v2) (lessp (abs (sub v1 v2)) epsilon))) (putd 'loop '(lambda (value) (let ((next-value (funcall f value))) (if (close-enough? value next-value) next-value (loop next-value))))) (loop initial-value) ))) ;;
-----------------------------------------------------------
Allen, John
Anatomy of Lisp
McGraw-Hill 1978 ISBN 0-07-001115-X
A book for serious lispians that is not so much concerned
with teaching the language or its use, but rather with its
logic and structure; indispensible reading for anyone with
an interest in implementing, hacking, or simply knowing the
nuts, bolts and considerations of implementations.
I have been anonymously informed by a reader of comp.lang.lisp
that this brilliantly written book is now out of print.
-----------------------------------------------------------
Steele, Guy l. jr.
Common Lisp: The Language
Digital Press 1984 ISBN 0-932376-41-X
A perfectly brilliant exposition of its subject, with just
enough of "anatomy" to make it the perfect companion to the
previous reference. To code a good lexical analyzer for
lisp, merely follow the prescription given on pp. 335-338.
Common Lisp the Language, 2nd Edition - ONLINE
-----------------------------------------------------------
Friedman, Daniel p.;felleisen, matthias
The Little Lisper
M.I.T. Press 1987 ISBN 0-262-56038-0
A fun introduction to the basic concepts of lisp programming
for the programatically intimidated. Good bedtime reading
for the children.
-----------------------------------------------------------
Wilensky, Robert
Lispcraft
Norton 1984 ISBN 0-393-95442-0
Nice exposition with useful code examples.
-----------------------------------------------------------
Winston, Patrick Henry; Horn, Berthold K. P.
lisp 2d ed.
addison 1984 ISBN 0-201-08372-8
Nice exposition with useful code examples, from algebra
and AI.
-----------------------------------------------------------
Tucker, Allen B.
Programming Languages (2d. edition) (Chapter 9)
McGraw-Hill 1977 ISBN 0-07-065416-6
Comparison with other programming languages.