Introduction

Name

LISP is an acronym for "LISt Processing Language" - so named because the list is one of the primary data structures in the language. Symbolic AI regards symbolic lists as being a key part of the way intelligent beings and systems actually store and manipulate information.

History

LISP is the second oldest higher-level language (after FORTRAN), first developed by John McCarthy (then of MIT) following the Dartmouth Conference of 1956 that is often taken as the birth of the discipline of Artificial Intelligence. Though it has been used in other areas, it is primarily identified with the field of AI and was the "lingua franca" of AI work for many years (arguably still so).

In LISP's early years, mutually incompatibile dialects proliferated as it was implemented on different platforms. In 1984, a standardization effort resulted in the development of Common Lisp, as defined in Guy Steele, Common Lisp: The Language. (The second edition of this book remains one of the best-selling LISP books on amazon.com's ranking). Common Lisp became an ANSI standard in 1994. Today, most implementations of LISP attempt to adhere to the Common Lisp standard.

One early dialect of LISP - Scheme - has survived to the present day, and is also a standardized and widely used language. While it resembles Common Lisp, it also differs from it in a few ways that cause some to regard it as a distinct language. At the same time, some ideas that were pioneered in Scheme (e.g. static versus dynamic scoping of names) also found their way into Common Lisp - not surprising given that the same individual (Guy Steele) was a co-creator of Scheme as well as the author of the definition for Common Lisp. This page will discuss Common Lisp.

Resources

Two important books on LISP have been made freely available by their publishers on the Internet:

Basic Concepts

LISP Belongs to the Functional Language Paradigm

LISP is the earliest representative of the functional programming language paradigm. Unlike procedural and object-oriented languages - whose theoretical model of computation is the Turing Machine, LISP's theoretical model of computation is the Lambda calculus developed by Alonzo Church. (It can be shown that the two models of computation are equivalent in power - that is, any algorithm that can be expressed in one model can also be expressed in the other).

This difference might be understood in terms of the following diagram:

In procedural languages, code operates on data; in object-oriented languages, objects encapsulate code and data and interact with one another; in functional languages data flows through functions but has no separate existence of its own. That is, in procedural languages data is passive; in OO languages it is active; in pure functional languages it is ephemeral.

However, most functional languages (including LISP) provide a mechanism for keeping certain data in existence even when it is not flowing through functions. In LISP, this takes the form of what Common Lisp calls "special variables" - essentially equivalent to what in other programming languages are called "global variables". That is to say, though LISP is a functional language, it is not a pure functional language (though it could be used as one by avoiding imperative constructs.)

LISP Uses a Variant of Prefix Notation

LISP uses a variant of prefix (Polish) notation called Cambridge Polish Notation. All expressions are fully parenthesized, with the first element of an executable form being the name of a function, macro, or special form. For example, the expression written as 1 + 2 * 3 - 4 in traditional infix notation is written as (- (+ 1 (* 2 3)) 4) in LISP.

Representation of Information

A further critical characteristic of LISP - which most functional languages do not share, is that there is absolutely no syntactic distinction between functions and data. For example, in one context, (car '(volkswagen golf)) may be a piece of data representing a particular motor vehicle. In another context, it may be taken as the application of the function car to the list (volkswagen golf). (It turns out that, since car is a defined operation in LISP, this form is meaningful and has the value volkswagen!)

In McCarthy's original paper, data objects were referred to as s-expressions (symbolic expressions). Common Lisp defines a rather complex hierarchy of data types; however, there are only a few core types of s-expression that have been part of the language since the beginning. These include:

It is sometimes helpful to picture the way that LISP represents a list in terms of dotted pairs (conses). For example, the list (this is a list) is represented internally as (this . (is . (a . (list . nil)))), which looks like this in memory:

The following is the complete type hierarchy of Common Lisp. Note well that every s-expression is either an atom or a list, except for () / nil, which is both!

Common Lisp type name Printed form example(s)
Atom
Symbolx, this-is-a-symbol, *so-is-this*, 1+, nil, ()
Keyword:test
Number
Integer
Fixnum123, -4, #o377 (octal), #b10100011 (binary)
Bignum12345678901234567890,
Ratio4/5
Float
Short-Float-1.3s-4
Single-Float-1.3e-4, .00013
Double-Float-1.3d-4
Long-Float-1.3l-4
Complex#c(3.2 4.0)
Character#\A, #\a, #\Control-A (all 3 different as characters)
Bit0, 1 (printed only, cannot be read)
Vector#(1 2 3), #(apples bananas cumquats)
Bit-Vector#*101010
String"This is a string"
Array#2a((1 2 3) (4 5 6))
Structure#s(student-info :first-name john :last-name jones :gpa 2.37)
(valid only if the structure student-info has been defined by defstruct)
List
True List(1 2 3), (), nil
Dotted List(1 . 2),   (1 2 (3 . 4))

Variables and Expressions

Variables

A symbol (other than one of the self-evaluating ones listed below) is regarded as the name of a variable when it is evaluated. LISP is a dynamically typed language - a variable does not have a declared type, but simply takes on the type of its current value. Common Lisp recognizes two kinds of variables.

Common Lisp uses two separate namespaces for the use of a symbol as a special form / macro / function name and the use of a symbol as a variable name. Thus, for example, the following is legal (though arguably a source of confusion)

(setq setq 3)
This would cause the variable whose name is setq to be given the value 3. When the LISP interpreter sees the name setq as the first element of a list to be evaluated, it takes it as the name of a special form; but any time the LISP interpreter sees a symbol like setq elsewhere, it takes it as the name of a variable. (This turns out to be one of the significant differences between LISP and Scheme; the latter has only a single namespace, so a given symbol cannot be both the name of a variable and the name of a special form / macro / function.

Expressions

In LISP, code takes the form of expressions to be evaluated. For example, (+ 3 4) is an expression that calls for applying the addition operation to the two numbers 3 and 4, yielding the result 7. We noted earlier that LISP makes absolutely no syntactic difference between data and code. As a result, any LISP s-expression might potentially be treated as an expression to be evaluated - which may or may not be meaningful. For example, we could attempt to evaluate (3 4 5) - but the result would be an error since this s-expression is not meaningful when viewed as code.

When attempting to evaluate a form, LISP uses the following rules:

Evaluating Functions

As noted above, any list whose first element is a symbol is regarded as either the application of a function or of a special form or macro to the remaining elements of the lists, regarded as its arguments. The LISP interpreter handles these quite differently, though.

When a function call is evaluated, the interpreter first evaluates each of the arguments in the list, and then applies the specified function to the result.

Example: consider the following form:
(+ (* 2 3) (* 4 5)))
When evaluating it, the interpreter first evaluates the form (* 2 3), then the form (* 4 5). To evaluate (* 2 3), it first evaluates 2 and then 3. Since numbers are self-evaluating forms, their values are 2 and 3, and when the interpeter applies * to these evaluated arguments, the result is 6. Something similar happens when (* 4 5) is evaluated to yield 20. Then the function + is applied to these evaluated arguments 6 and 20, yielding the final result 26.

Example: consider the following code excerpt:

(setq a 4)
(setq b 5)
(+ a b)

When evaluating (+ a b), the interpreter first evaluates the forms a and b. Each is taken as the name of a variable, and the most recent values assigned to those variables (4 and 5) are used. Finally, the interpreter applies the function + to these values, yielding 9.

Evaluating Special Forms and Macros

If the first symbol in a list to be evaluated is the name of a special form or macro, the interpreter does not evaluate the arguments. However, the special form or macro may evaluate some of the arguments - how this is handled varies from special form / macro to special form / macro. For example, the special form setq evaluates its second argument, but not its first.

Example: consider the second line of the following code excerpt:

(setq a 1)
(setq a (+ 2 3))
Because the special form setq evaluates its second argument, the form (+ 2 3) is evaluated, yielding 5. However, the form a is not evaluated - so 5 is assigned to a. (If setq were a function or a special form that evaluated both of its arguments, the operation would mean that 5 should be assigned to 1 - obviously an absurd operation!)

Some Common Lisp Special Forms, Macros, and Functions

The following are but a few of the special forms, macros, and functions of Common Lisp.

Some Special Forms and Macros

List Operations

The list operations are often best understood by picturing what they do in diagrammtic form, as done below. All are functions, which means that the arguments are evaluated before the operation is performed.

Arithmetic

LISP supports the arithmetic operations found in most programming languages, plus many unique ones as well. Most of the operations take any number of arguments - e.g. (* 2 3 4 5) evaluates to 120. All are functions, which means that the arguments are evaluated before the operation is performed.

Tests

These are functions that apply some test one or two values (variables or expressions - evaluated before the test is applied) and either succeed (evaluating to t) or fail (evaluating to nil).

Comparisons

LISP supports the standard comparisons on numbers, but most can take one up to any number of arguments, rather than just two. (In the case of two arguments, they behave in the traditional way.) All of the arguments must be numbers.

Input-Output

Common Lisp provides a large number of input output operations. Input operations are functions whose value is some input read from an external stream; output operations are typically functions which have the side effect of printing something on an external stream and also return as their function value that which was printed.

Copyright © 2009 - Russell C. Bjork. Permission for non-commercial reproduction for educational use is hereby granted; all other rights are reserved.