Lisp

This article is about the programming language. For the speech disorder, see Lisp (impediment).

Lisp, created by John McCarthy in 1958, is one of the oldest extant, high-level computer programming languages, dating from the same era as Fortran and COBOL. Lisp takes its name from "List Processing", since one of its prominently featured data structures is the linked list. Lisp is still used, and sometimes taught, in universities, and has had enormous influence on the field of computer programming. Lisp derives some of its ideas from Alonzo Church's lambda calculus, although the language is not a literal implementation of that formalism. Features in the spirit of the lambda calculus are probably easiest to see in Scheme.

At McCarthy's request, the word Lisp now designates the family of languages that has resulted from his original design, and no longer any specific language, dialect, or implementation. For this reason, the American National Standards Institute (ANSI) relating to Lisp, X3.226/1994, is a standard for the language Common Lisp, in order that other members of the Lisp language family not be affected. Likewise, the ISO standard, ISO/IEC 13816:1997(E), defines a language named ISLisp.

Language properties

The following list represents a series of powerful software language concepts in which Lisp was really the pioneer.

• Garbage collection/automatic storage management
• Dynamic typing
• Object Oriented Programming (Common Lisp Object System)
• Meta Object Protocol
• Self-contained compiler
• Source code as a data structure
• Closures

Others

• Marco system

A Brief Look at Lisp: Hello World

This section showcases the most popular Lisp dialect: Common Lisp. It should be remembered that there are other dialects which may invalidate these examples.

The Hello World program is traditionally the first program an aspiring programmer writes when learning a new language. Its function is to write some short text to some output device (often a computer screen). It turns out that Hello World is a rather bad way to introduce someone to the Lisp programming language, since it shows very few of its important features. Computer custom dictates that we write it down, however:

; This is one of the simplest possible Lisp programs. 
; It prints the words "Hello, World!" to standard output.

(print "Hello, World!")

Analysis. The defining data type of Lisp is the linked list. A list is written between parentheses, with spaces to separate elements. Lisp programs are themselves lists, and this program consists of one list with two elements. The first is the symbol print and the second is the text string "Hello World!". Lists which are part of a program commonly start with a function name:

(function arg1 arg2 arg3 ...)

Note also the difference between a symbol and a string. For symbols, the case does not matter. We could have written PRINT or even pRiNT, and these are the same as far as Lisp is concerned. This is a remnant from the time when some computers handled only UPPER CASE TEXT, and has been kept in order not to break legacy code. For strings however, the case is significant.

Everything from a semicolon to the end of the line is a comment. Comments are ignored by Lisp. Their purpose is to explain to human programmers the function of the code.

Sidetrack: Evaluation

If you entered the above program into a Lisp interpreter (go ahead and try!) you will probably see two Hello Worlds printed. This is because every Lisp object evaluates to a value! In this case, the print function evaluates to its argument, and the interpreter has been configured to always print the resulting value. Evaluation is recursive, starting at the outermost level and going inwardswards. It works such that:

• Literals such as 1, 7/4, "ape" evaluate to themselves, and
• Functions provide rules for evaluating their arguments recursively.

For instance, the + function evaluates to the sum of its arguments. Its arguments are either numbers, in which case we are done since numbers always evaluate to themselves. More commonly, the arguments are other functions which then have to be evaluated and so on. We shall see that this recursion is one of the most important properties of Lisp.

A Better Hello World for Lisp

We proposed earlier that Hello World was not the best way to showcase Lisp to first-time users. We shall now provide a slightly better example, which shows some of the language's distinctive features:

; Factorial: calculates the factorial of its argument. 
; Recall the definition of the factorial.
; If n is a natural number, we define the factorial of n as:
;
;     n! = n * (n - 1) * (n - 2) * ... * 2 * 1.
;
; And additionally: 0! = 1.

(defun fact (n) 
  (if (= n 0)
    1
    (* n (fact (- n 1)))))

Analysis. First, we notice that lists can contain other lists; this program has five levels. We'll go through the lines one at a time.

defun is a macro which defines new functions for our use. One of the key ideas in Lisp (as in most programming languages) is to divide your program into several functions. Each function should take arguments and produce a single return value. In Lisp the return value is the last value which was evaluated. This line asks Lisp to associate the symbol fact with the function which takes one argument (a number) and evaluates to the factorial of that argument.

if is a macro which evaluates its first argument and checks if it is true. If it is, if evaluates to its second argument. If not, to the third. You can think of it as "if (...) then (...) else (...)". In this case, it checks whether n is equal to 0. Notice that = is also a function, namely the function that takes two numbers and checks for numerical equality.

Boolean truth/falsity in Lisp is handled such that the empty list NIL is false, and everything else is true. There is also a dedicated T value to indicate truth.

Now what this function essentially says is "if n = 0, the factorial is 1. Otherwise, the factorial is n times the factorial of (n - 1)". This is the beauty of recursion. If you do not see it yet, imagine what will happen when n gets smaller and smaller. One strength of programs constructed in this fashion is that we need not prove their correctness for every input value. We need only prove that:

• It works for the number 0, or for the list of length zero (NIL) and,
• Given that it works for the number k, it will work for the number k + 1. (or lists of those lengths)

Naturally, such theoretical proofs do not protect from the possibility that the user will ask for the factorial of a decimal number, or even a text string!

Popular Myths About Lisp

Lisp is sometimes mischaracterized as an "interpreted" language. In fact, Lisp compilers have been available for decades. Some very important and influential research in compiler design has been done in Lisp. For example, the notion of continuation-passing style was invented for Scheme.

Lisp is sometimes mischaracterized as a language that only has lists for container types. In fact, for several decades, all major Lisps have had a rich variety of container types, such as arrays, strings, hash tables, and user-defined class instances.

Members of the Lisp Language Family

There have been many members of the Lisp language family. Some of the more prominent Lisps are:

• BBN Lisp

• Eulisp
• Lisp 1.5
• INTERLisp
• MACLisp
• Portable Standard Lisp
• Zetalisp

Lisps in more recent use are:

• Autolisp
• Common Lisp
• Emacs Lisp
• ISLisp

Languages which were inspired by Lisp:

• Scheme
• Dylan
• Haskell

Significant Applications

Some of the many historically important applications that have been created in Lisp:

• ELIZA (emulator/parody of human therapist)
• MACSYMA (symbolic algebra)
• SHRDLU (natural language understanding)
• Lisp Machine (Lisp-based hardware and operating systems)

External Links

• Common Lisp HyperSpec
• Programming in Emacs Lisp
• ISLisp Programming Language
• Scheme Programming Language

References

• John McCarthy History of Lisp