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. 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. Everthing in LISP is a list. Lists are space-separated lists of elements in parentheses. e.g. (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.
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.
e.g. (* 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 (e.g. (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. e.g ( 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.
e.g. (list a b c) evaluates to (a b c)
N.B. Programs can force the evaluation of a list using the eval keyword.
The defun keyword can be used to define new functions.
e.g.
( 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.
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.
e.g.
( 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.
e.g.
(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.
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. e.g. ( car '(a b c) ) evaluates to a.
cdr returns the list with the first element removed. e.g. ( 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. e.g. ( 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.
Global variables
The set function sets the item referred to. Note that the item does not need to be an explicitly named variable.
e.g.
(set x ' (a b c) )
(set (car x) 1 ) - car x refers to 1 st 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.
e.g.
(let (a b)
(...)
(...)
)declares a and b as local variables, then evaluates the LISP statements contained in its list.
Copyright © Murray Cumming. Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
