Lisp programming language

Lisp (which stands for "LISt Processing") is a programming language oriented towards functional programming. Its prominent features include prefix-notation syntax, dynamic typing (variables are type-neutral, but values have implicit type), and the ability to treat source code as first-class objects.

Not counting the various machine languages and assembly languages, Lisp is the second-oldest programming language still in widespread use; only Fortran is older. Like Fortran, it has changed greatly since its early days.

Strictly speaking, Lisp is now not a single language but a family of similarly-styled languages with an instantly recognizable appearance. These are known as Lisp dialects; the most well-known are Common Lisp and Scheme.

History Lisp was invented by John McCarthy in 1958 while he was at MIT. McCarthy published its design a paper in Communications of the ACM[?] in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". (Part II was never published.) He showed that with a couple of simple operators and a notation for functions (see minimal lisp below) you may build a whole programming language.

Lisp was originally implementated on an IBM 704 computer, and two instructions on that machine became the primitive operations for decomposing lists: car (Contents of Address Register) and cdr (Contents of Decrement Register). Most dialects of LISP still use car and cdr for the operations that returning the first item in a list and the rest of the list respectively.

Because of its expressiveness and flexibility, Lisp became popular with the artificial intelligence community. However, Lisp had its downsides as well: programs generate a large amount of intermediate output, which take up memory and have to be garbage collected. This made it difficult to run Lisp on the memory-limited stock hardware of the day. In the 1970s, an increasing user community and generous government funding led to the creation of LISP machines: dedicated hardware for running Lisp environments and programs.

During the 1980s and 1990s, a great effort was made to unify the numerous Lisp dialects into a single language. The new language, Common Lisp, was essentially a superset of the dialects it replaced. In 1994, ANSI published the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp." By this time the world market for Lisp was much smaller than in its heyday.

The language is amongst the oldest programming languages still in use as of the time of writing in 2003. Algol, Fortran and COBOL are of a similar vintage, and Fortran and COBOL are also still being used.

Syntax Lisp is an expression-oriented language. Unlike most other languages, no distinction is made between "expressions" and "statements"; all code and data are written as expressions. When an expression is evaluated, it produces a value (or list of values), which then can be embedded into other expressions.

McCarthy's 1958 paper introduced two types of syntax: S-expressions (Symbolic Expressions), which are also called sexp's, and M-expressions[?] (Meta Expressions), which express functions of S-expressions. M-expressions never found favour, and almost all LISPs today use S-expressions to manipulate both code and data.

The heavy use of parentheses in S-expressions has been criticized -- one joke acronym for Lisp is "Lots of Irritating Superfluous Parentheses" -- but the S-expression syntax is also responsible for much of Lisp's power: the syntax is extremely regular, which facilitates manipulation by computer.

The reliance on expressions gives the language great flexibility. Because Lisp functions are themselves written as lists, they can be processed exactly like data: programs can easily be written to manipulate other programs. This is known as metaprogramming[?]. Many Lisp dialects exploit this feature using macro systems, which make it possible to extend the language almost without limit.

A Lisp list is written with its elements separated by whitespace, and delimited by parentheses. For example,

 (1 2 "foo")

is a list whose elements have the values 1, 2, and "foo". These values are implicitly typed: they are respectively two integers and a string, and do not have to be declared as such. The empty list () is also represented as nil.

Expressions are written as lists, using prefix notation[?]. The first element in the list is the name of a form, i.e. a function, operator, macro, or "special form" (see below.) The remainder of the list are the arguments. For example, the function list returns its arguments as a list, so the expression

 (list 1 2 "foo")

evaluates to the list (1 2 "foo"). If any of the arguments are expression, they are recursively evaluated before the enclosing expression is evaluated. For example,

 (list 1 2 (list 3 4))

evaluates to the list (1 2 (3 4)). Note that the third argument is a list; lists can be nested.

Arithmetic operators are treated similarly. The expression

 (+ 1 2 3 4)

evaluates to 10. Note that this is much more compact (if less familiar) than "1+2+3+4", which is the equivalent under infix notation.

"Special forms" provide LISP's control structure. For example, the special form if takes three arguments. If the first argument is non-nil, it evaluates to the second argument; otherwise, it evaluates to the third argument. Thus, the expression

 (if nil
     (list 1 2 "foo")
   (list 3 4 "bar"))

evaluates to (3 4 "bar"). (Of course, this would be more useful if a non-trivial expression had been substituted in place of nil!)

Another special form, defun, is used to define functions. The arguments to defun are a list of arguments and the expression that the function evaluates to.

Minimal Lisp

A minimal Lisp needs just a few functions implemented in an underlying language (such as machine language, or C on Unix systems):

• car -- given a pair, return the first element;
• cdr -- given a pair, return the second element;
• cons -- construct a new pair with given first and second elements;
• quote -- denote an expression as literal, not to be interpreted;
• eq -- compare two objects for equality, returning true or false values;
• if or cond -- a single- or multiple-condition branch operation; and
• some mechanism to define functions, such as Common Lisp's defun, or else lambda and Scheme's define.

All the other functions may be implemented in terms of these -- albeit not very efficiently. Actual Lisp systems implement a much larger set of functions than this.

Example programs Here are some examples of Lisp code. While not typical of Lisp programs used in industry, they are typical of Lisp as it is usually taught in computer science courses.

As the reader may have noticed from the above discussion, Lisp syntax lends itself naturally to recursion. Mathematical problems such as the enumeration of recursively-defined sets are simple to express in this notation. This function evaluates to the factorial of its argument:

 (defun factorial (n)
   (if (<= n 1)
       1
     (* n (factorial (- n 1)))))

This is an alternative function, which is more efficient in most Lisp systems because it uses tail recursion:

 (defun factorial (n &optional (acc 1))
   (if (<= n 1)
       acc
     (factorial (- n 1) (* acc n))))

This function takes a list argument and evaluates to the reverse of the list. (Lisp actually has a built-in reverse function which does the same thing.)

 (defun reverse (l &optional acc)
   (if (atom l)
       acc
     (reverse (cdr l) (cons (car l) acc))))

Object systems Various object systems and models have been built on top of, alongside, or into Lisp, including:

• Flavors, built at MIT
• The Common Lisp Object System, CLOS (descended from Flavors)

CLOS features multiple inheritance, multiple dispatch ("multimethods"), and a powerful system of "method combinations". In fact, Common Lisp, which includes CLOS, was the first object-oriented language to be officially standardized.

Genealogy and Variants Over its almost fifty-year history, Lisp has spawned many variations on the core theme of an S-expression language. Moreover, each given dialect may have several implementations -- for instance, there are more than a dozen implementations of Common Lisp.

Differences between dialects may be quite significant -- for instance, Common Lisp and Scheme do not even use the same keyword to define functions! Within a dialect that is standardized, however, conformant implementations support the same core language, but with different extensions and libraries.

Note: The following list is a mix of dialects and implementations, and is not in chronological order!

• Lisp -- McCarthy's original version, developed at MIT.
• Common Lisp -- descended mainly from ZetaLISP and Franz, with some InterLISP input. Prevaling standard for industrial use today.
• MacLisp -- developed for MIT's Project MAC (no relation to Apple's Macintosh), direct descendant of LISP.
• ZetaLisp[?] -- used on the Lisp machines, direct descendant of MACLisp.
• InterLisp[?] -- developed at MIT, later adopted as a "west coast" Lisp for the Xerox Lisp machines. A small version called "InterLISP 65" was published for Atari's 6502-based computer line.
• Franz Lisp -- originally a Berkeley project; later run by Franz, Inc.
• Gold Hill Common Lisp -- an early PC implementation of Common Lisp.
• Coral Lisp -- an implementation of LISP for the Macintosh.
• Scheme -- a minimalist LISP originally designed for teaching; an early user of lexical variable scoping rather than dynamic scoping.
• AutoLISP/Visual LISP -- customization language for the AutoCAD product.
• Emacs Lisp -- scripting language for the Emacs editor.
• Oak Lisp -- an object-oriented Lisp based on Scheme.
• Cambridge Lisp -- originally implemented on IBM mainframes; published by Metacomco for the Amiga.
• the Knowledge Representation System
• Lispkit Lisp -- a purely functional ("pure Lisp") dialect implemented on a virtual machine (the SECD machine) and used as a testbed for experimentation with functional language concepts.

See also

• http://www.cliki.net/ -- the Common Lisp Wiki
• http://www.cons.org/ -- a collection of Lisp-related sites
• Bill Schelter (LISP programmer)
• Kent Pitman (LISP programmer)
• an interactive LISP course (http://www.psychologie.uni-trier.de:8000/projects/ELM/elmart)
• Design patterns (http://www.norvig.com/design-patterns/) in Lisp