Lisp (programming language)
Lisp (coined from "list processing") is an early programming language with a simple prefix-notation syntax, dynamic typing (that is, untyped variables but typed values), and special features for processing lists. Unqualifed, the term Lisp usually refers to a family of lisp-like languages.
It is notable for having a large amount of reflexive power, Lisp programs are in the form of Lisp data (lists). It is therefore very easy to write Lisp programs that read, write, and manipulate Lisp programs. In many Lisp languages this is made use of in the macro system.
The language was invented by John McCarthy in 1958 whilst he was at MIT; he published a paper in CACM in 1960 titled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (part II was never published). The initial implementation was on an IBM 704 and two instructions of that machine became the primitive Lisp operations for decomposing lists: CAR (Contents of Address Register) and CDR (Contents of Data Register) are the operations for returning the head and tail of a list respectively.
In McCarthy's paper he introduces two syntaxes: S-expressions (symbolic expressions, sometimes called "sexp"s) and M-expressions (meta expressions, for expressing functions of S-expressions). M-expressions never found favour and pretty much all Lisps today use S-expressions for both programs and data. It is the S-expression syntax that is responsible for Lisp commonly being criticised as being "full of parentheses".
Probably due to its expressiveness and flexibility Lisp became popular with the artificial intelligence community. In the 1970s an increasingly large user community, government funding (?), and the difficulty of executing Lisp programs efficiently on stock hardware, led to the creation of dedicated hardware for running Lisp programs: Lisp machines.
During the 1980s and 1990s there was a great effort made to unify the many varied Lisp dialects that had sprung up. The new language was to be called Common Lisp. In 1994 ANSI published "ANSI X3.226-1994 Information Technology Programming Language Common Lisp" effectively standardising the language. Unfortunately the world market for Lisp was much smaller than in its hey day.
The language is amongst the oldest programming languages still in use as of the time of writing in 2001. Algol, Fortran and COBOL are of a similar vintage, and Fortran and COBOL are also still being used.
Example program
There is only one important syntax rule: in a list (f x y z), f represents the function that is to be applied to the arguments x, y, z. If you just want to talk about the list without applying the function, you write '(f x y z). Lisp programs consists of function calls only, and therefore are often programmed recursively.
Factorial seems to be the first program that lots of Lisp hackers learn:
(defun factorial (n)
"Compute the factorial of the integer n."
(if (<= n 1)
1
(* n (factorial (- n 1)))))
An alternate, more efficient (see tail recursion) version of factorial also typically learned:
(defun factorial (n &optional (acc 1))
"Computer the factorial of the integer n."
(if (<= n 1)
acc
(factorial (- n 1) (* acc n))))
Another typical example is this function which reverses a list:
(defun reverse (l)
"reverse the list l"
(if (null l)
'()
(append (reverse (cdr l)) (list (car l)))))
Object systems
Various object systems and models have been built into/along side Lisp, including:
Genealogy and Variants
- LISP (McCarthy's original version while at MIT)
- MACLisp (MIT's Project MAC, no relation to Apple's Macintosh, direct descendant of LISP
- ZetaLisp MACLisp successor, wound up on the Lisp machines, direct descendant of MACLisp
- InterLisp Also developed originally at MIT (?), later a "west coast" Lisp used on the Xerox lisp machines, descendant of LISP
- Franz Lisp (originally a Berkeley project?) later run by Franz, Inc.
- Common Lisp (grand unification), descended mainly from ZetaLisp and Franz, some InterLisp input
- Gold Hill Common Lisp, early PC implementation
- Coral Lisp, Macintosh implementation
- Scheme, re-imagining of Lisp
- AutoLisp, "scripting langauge" for the AutoCAD product
- emacs lisp, "scripting langauge" for the Emacs editor
- Oak Lisp, a version with object-oriented basis, everything is an object