Lisp is a functional programming language intended for use in an interactive environment. It is quickly and easily adaptable to a user’s specific problem, and is unique in that semantics were the primary design focus instead of complicated syntax. Lisp is the most popular language used in artificial intelligence research as a result of its extensibility and inherent nature to simplify exploratory programming.

Overview

John McCarthy originally developed Lisp (which stands for LISt Processing) at MIT around 1960. It is the second oldest programming language in widespread use today (after FORTRAN), and is the preferred language for research in artificial intelligence (AI). Lisp is a functional language, and as a result requires a different way of thinking about problems than in languages that follow the more common imperative paradigm such as FORTRAN, Pascal, and C/C++. The functional paradigm, along with Lisp-specific features, makes it easy to define new languages (especially useful in AI work), and to quickly develop working programs.

In the years following the language’s creation, many dialects emerged (e.g. MacLisp, InterLisp, Scheme, Franz Lisp, and Zetalisp). The inability for code written in one dialect to be smoothly ported to another dialect led to the need for a standardized language. The compromise was originally defined in a book entitled Common Lisp, by Guy Steele in 1984. An ANSI committee was formed, and Common Lisp, incorporating the Common Lisp Object System (CLOS), became the first object-oriented ANSI-standardized language.

Description & Analysis

At a low level, Lisp is a tool to manipulate symbolic expressions. These "s-expressions" are either atomic symbols (a symbol that denotes a value) or a list of smaller s-expressions. The Lisp interpreter provides functions that operate on s-expressions. A list is interpreted as a function call. The first element of the list (called the head) is considered the function name, and the remaining elements (collectively called the tail) are the function parameters. The interpreter will return the result of applying the function to the parameters. S-expressions allow Lisp programmers to avoid ambiguities and limitations found in other languages. The use of the s-expression also means that programs and data have the same form. This is a powerful concept that allows programs to actually create, alter, and/or execute other programs.

As mentioned above, Lisp is a functional programming language. Solving a problem in Lisp is a matter of expressing the problem as a composition of functions. A program in Lisp is primarily a function whose definition is a list of function calls. Ordinarily, the parameters passed to the functions are the return values of other nested functions. Lisp functions may also call themselves. In fact, the primary control structure in Lisp is function recursion.

Besides the functional paradigm, two additional features aid in Lisp’s originality. First is that Lisp is designed to be interactive. Compilers do exist, however the interpreter is an important element involved in writing Lisp programs. Any function (remember, the main program is a function) can be called with parameters through the interpreter, and its results will be immediately returned to the user. In many of the problems that the language is used to solve, a solution is not evident at first glance. The interpreter makes exploratory programming much simpler. Secondly, Lisp is quite extensible through either additional functions or user-defined macros. Functions are not uncommon to programming languages, but a Lisp function can actually be created within a currently running Lisp program. This ability is a result of Lisp’s use of the aforementioned s-expression.

The simplistic programming style of Lisp, using s-expressions, frees the programmer from dealing with the complicated syntax found in many languages. Instead, focus can be placed solely on the semantic problem. This would appear to be a benefit, but since the style is uncommon, the lack of a structured syntax is just as well an obstacle for unfamiliar users.

There are a number of problems in computer science for which Lisp has become the preferred language for many programmers. Wade Hennessey enumerates these problems in his book Common Lisp (McGraw-Hill, 1989). A partial list includes: emulating human vision, doing symbolic algebra, developing special-purpose languages, exploring natural language understanding, and theorem proving.

Commercial Products

Allegro CL - Franz Inc.
http://www.franz.com/

Allegro CL is based on ANSI-standard Common Lisp and CLOS. Support is provided for automatic memory management, incremental compilation, and user-defined macros. Code can be modified while in the design environment, and object and class structures can be changed while a program is running, without source code. Allegro CL is available for Windows (NT, 95) and a variety of Unix platforms. The Windows version features a visual programming environment for ease in creating Windows GUI programs. In addition, Franz Inc. also provides distributed system support, database management, and interface management, with additional Allegro products.

LispWorks / Liquid Common Lisp - Harlequin Ltd.
http://www.harlequin.com/

Harlequin Ltd. has two Common Lisp software applications available, LispWorks and Liquid Common Lisp providing availability for Windows and multiple Unix platforms. These applications support a machine-independent language model, debugging within the language model, automatic memory management, and advanced object-oriented programming. Also featured are: an incremental compiler and dynamic loader; browsers for classes, generic functions and compilation errors; a build system manager; and complete on-line documentation.

Macintosh Common Lisp (MCL) - Digitool, Inc.
http://www.digitool.com/

MCL is an object-oriented dynamic programming language for the Macintosh, which implements ANSI-standard Common Lisp and CLOS. Features include an incremental compiler, automatic memory management, window-based debugger, a source code stepper, and a dynamic object inspector. In addition, MCL allows visual creation of the Macintosh user interface, and the support of functions created in languages such as C, Pascal, and assembler.

Useful Links

The Common Lisp HyperSpec
http://www.harlequin.com/ education/books/HyperSpec/FrontMatter/index.html

While not the actual ANSI Common Lisp standard, it is a complete reference based on the standard (with permission from ANSI and X3) that is much easier to understand and navigate. The site includes a table of contents and two indexes, for quick reference.

Common Lisp the Language, 2nd Edition
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/clm.html

The entire text, by Guy L. Steele Jr. This book was written before the ANSI standard, but remains a useful reference.

An Introduction and Tutorial to Common Lisp
http://www.apl.jhu.edu/~hall/lisp.html

This site is located at the Johns Hopkins University. It includes Common Lisp book recommendations, online resources for both beginner and advanced users, and Lisp-related papers.

CMU Common Lisp Repository
http://www.cs.cmu.edu/ afs/cs.cmu.edu/project/ai-repository/ai/lang/lisp/0.html

Site maintained and located at he School of Computer Science at Carnegie Mellon University. Includes various Lisp code, documentation, freeware and shareware implementations, technical reports and papers, and miscellaneous utilities for programming in Lisp.

Home Page of John McCarthy
http://www-formal.stanford.edu/jmc/

John McCarthy is Professor of Computer Science at Stanford University, whose research is mainly focused on topics in artificial intelligence. He is the originator of the Lisp programming language. This site includes links to many of his published papers and notes.