I put this on my website a long time ago, maybe around 1996, as an HTML page. This is it moved to my blog.
Contents
Introduction
LISP is short for List Programming. It was created by John McCarthy circa 1960, and is used today mainly in AI. There are many dialects of LISP, though Common LISP is now the agreed standard.
LISP is an interpreted, functional language with no in-built Object-Orientated mechanisms (Note from 2015: ANSI Common Lisp does now). Type-checking is loose, and because the program is capable of creating and executing new code during run-time, type-checking occurs at run-time.
LISP is characterised by it’s unusual, but simple, notation. Everything in LISP is a list. Lists are space-separated lists of elements in parentheses. For instance, (a b c).
There is no distinction between the program and the data which the program uses. This allows programs to manipulate their own commands, which in turn allows programmers to act as meta-programmers.
A LISP program may create lists which it may then process. A List may contain other lists or atoms. All lists resolve to atoms, so all Lists which contain other lists are actually processed as lists of simple atoms. This method is intended to allow symbolic programming through use of recursive functions.
This neat concept enables straightforward coding of some classes of problems, but
makes it harder to code most other programs. Data structure and process are emergent
rather than clearly defined, so the program architecture is not easily apparent.
Evaluation
Using functions
The first element in the list may be a function name or simple operator. The other
elements in the list are then regarded as the parameters to the function.
For instance, (* 2 3) or (foo 2 5).
Almost all expression in LISP are of this form. In fact, many of the languages’s keywords are simply pre-defined LISP functions, which must be used in the same manner as other functions. There are many of these built-in functions, which I will not describe here.
Preventing evaluation
If LISP attempts to evaluate a list which does not begin with a function name (For instance, (1 2 3)) then execution will halt with an error. When such lists are passed as parameters, the quote keyword (or its abbreviation: ‘ ) is used. This prevents the interpreter from first attempting to evaluate the list into an atom. For instance, ( foo 2 ‘(a b c) ).
Building new lists
To return a list from a function, the list function may be used. Without using this, LISP would attempt to evaluate the list before it is returned.
For instance, (list a b c) evaluates to (a b c)
Note: Programs can force the evaluation of a list using the eval keyword.
Defining functions
The defun keyword can be used to define new functions. For instance,
( defun timesthree(x) (* x 3) )
defines a function which multiplies a value by 3. The new function may be used as so:
(timesthree 2) evaluates to 6.
Conditionals
cond
By using the convention that a zero value is false and a non-zero value is true, LISP allows conditional branching and boolean logic.
The cond function takes a series of condition-result pairs. This construct is similar to a Switch-Case block in C. For instance,
( defun abs-val(x)
(cond ( (< x 0) (-x) )
( (>= x 0) x )
)
)
if
The if function takes an expression to be examined as true or false, and returns one of its two other parameters, depending upon the result. For instance,
(if (< x 0) (-x) x)
Boolean operators
The and and or functions act as boolean operators. Their left to right checking gives rise to a side-effect which is often used as a conditional branching technique. and stops checking when it encounters one item which is false, while or stops checking when it encounters one true item.
Recursion
LISP has no loop constructs, so recursion is the only way to process data. A recursive function is a function which calls itself. This technique recognises that an operation on some data may be best expressed as the aggregate of the same operation performed on each item of data of which it is comprised. Obviously this technique is best used with data structures which have the same form at both higher and lower levels, differing only in scale.
This focus on recursion is the reason for LISP’s popularity with AI researchers, who often attempt to model large-scale behaviour in terms of smaller-scale decisions. For instance, recursion is often used in LISP to search state spaces.
Many of the lists used in LISP programs would be better referred to as trees. Lists are simply the mechanism used to represent those trees.
The car and cdr functions are generally used to recurse (or ‘walk’) through the elements in a tree, while cons is often used to gradually build build tree structures to form the result of a recursive operation. By also using the null function to test for an empty list, we can walk through the tree structure, dealing with successively smaller pieces of the tree.
car returns the first element of a list. For instance, ( car ‘(a b c) ) evaluates to a.
cdr returns the list with the first element removed. For instance, ( cdr ‘(a b
c) ) evaluates to (b c).
cons is an associated function which is used to build tree structures, often to form the result of a recursive operation. Note that it does not simply concatenate lists, but undoes the effects of a hypothetical use of car
and cdr. For instance, ( cons ‘(a b) ‘(c d e) ) evaluates to ( (a b) (c d e)) rather than (a b c d e).
Note that the use of these functions can lead to a great deal of inefficient copying.
Variables
Global variables
The set function sets the item referred to. Note that the item does not need to be an explicitly named variable. For instance,
(set x ' (a b c) ) (set (car x) 1 ) - car x refers to 1st element in x.
x now evaluates to (1 b c).
Local variables
The let function declares a local scope.
The parameters to the let function are a list of local variables and a list of expression which may use these local variables. The let function effectively brackets the expressions, providing them with their own local variables. For instance,
(let (a b) (...) (...) )
declares a and b as local variables, then evaluates the LISP statements contained in its list.