LISP programming language

(Redirected from LISP)

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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. Not counting machine languages and assembly languages, Lisp is the second-oldest programming language still in widespread use; only Fortran is older. Like Fortran, Lisp has changed a lot since its early days. In fact, there are now many different languages with "Lisp" in their names, and it is probably better to regard "Lisp" as the name of a family of languages rather than of a single language.

Lisp is notable for having a large amount of reflexive power. Lisp programs are written in the form of Lisp data (lists). It is therefore very easy to write Lisp programs that read, write, and manipulate Lisp programs. Many dialects of Lisp take advantage of this with powerful macro systems, which make it possible to extend the language almost without limit.

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 computer, and two instructions of that machine became the primitive Lisp operations for decomposing lists: car (Contents of Address Register) and cdr (Contents of Decrement Register) are the operations for returning the first item in a list and the rest of the 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", but which is also responsible for much of Lisp's power; regular syntax facilitates manipulation by computer.

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 heyday.

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.

Syntax

Lists are delimited by parentheses and have elements separated by whitespace: (1 2 "foo"). A Lisp program is built out of lists, although (contrary to persistent rumours) Lisp data does not consist entirely of lists.

Lisp is an expression-oriented language: it doesn't distinguish between "expressions" and "statements" as many languages do; everything is an expression and returns a value or list of values.

Most Lisp expressions are function applications.

What other languages write as

f(a,b,c)

Lisp writes as

(f a b c)

. Thus, not

1+2+3+4

or

add(1,2,3,4)

but

(+ 1 2 3 4)

.

The same prefix syntax is used for "special forms" and "macros": the first item in the list, in these cases, determines how the remaining items will be processed. Whether any given expression is a function application, a special form or a macro application depends on its first element.

Example programs

The following programs are not typical of real Lisp programs. They are typical of Lisp as it is usually taught in computer science courses.

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))
  "Compute 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. (Note that Lisp actually already has a reverse function for this purpose.)

(defun reverse (l &optional (acc '()))
  "reverse the list l"
  (if (null 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
  • CLOS, the Common Lisp Object System (descended from Flavors)

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

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. 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.
  • 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, designed for teaching, the first Lisp dialect to have lexical scoping rather than dynamic scoping
  • AutoLisp, scripting language for the AutoCAD product
  • Emacs Lisp, (a. k. a. elisp) scripting language for the Emacs editor
  • Oak Lisp, a version with object-oriented basis, everything is an object
  • Cambridge Lisp, originally implemented on IBM mainframes, published by Metacomco for the Amiga, among possible other platforms.

/Talk