[Up- imhofaq] [Map] [Prior: prehistory] [Robot Wisdom home page]

LISP and symbolic computation

Writing elegant programming code is a really hard task! Designing algorithms and data structures requires such a difficult sort of analytic thought, it's a wonder anyone can do it well, at all. The main barrier to AI is the need to innovate new ways of thinking about programming-- such as object-oriented design, and declarative code. (Jargon is the greatest enemy of the required clarity of thought!)

(Briefly, object-oriented design recognizes that each type of data- object-- number, character-string, database record, text document, etc.-- has its own set of properties and 'verbs' that the programmer must define. This definition of a 'type' can be called a 'type object'. "Declarative" languages like Prolog try to free programmers from thinking about what specific sequence of actions the computer will go thru, allowing them instead to spell out a series of 'declarative' statements that the computer is then able to determine a sequence from, on its own.)

(There's an interesting new school of thought (UK) that argues that programming is essentially a form of data-compression.)

The LISP language was invented by John McCarthy home page in 1958, to simplify the handling of arbitrary lists of arbitrary data objects. LISP builds (almost) everything out of "cons cells", an elegant structure consisting of two memory locations, and nothing else. These may hold pointers to other cons cells, or to numbers - and these numbers may represent quantities, or qualities, concepts, symbols . Out of these simple building blocks, patterns of data can be constructed that embody real- world intelligence.

Raw computer memory can be represented like this (each cell usually holds 32 bits, and has a unique 32-bit address, so each cell can 'point to' any other cell):

 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|

The same memory, now viewed as a 'heap' of cons cells (2 * 32 = 64 bits):

 _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_|
 _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_|
 _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_|
 _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_|
 _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_| |_|_|

The 'CDR' (KUH-der) of any cell (the second half) points to the next cell in the list, the 'CAR' (first half) can point to any arbitrary cell or numerical value:

 ___ ___    ___ ___    ___ ___    ___ ___    ___ ___
|   |   |  |   |   |  |   |   |  |   |   |  |   |   |
|__\|/__|  |___|___|  |___|___|  |___|___|  |___|___|
   / \_______
 _V_ ___    _V_ ___    ___ ___    ___ ___    ___ ___
|   |   |  |   |   |  |   |   |  |   |   |  |   |   |
|__\|/__|  |___|___|  |___|___|  |___|___|  |___|___|
   / \_____________________________
 _V_ ___    ___ ___    ___ ___    _V_ ___    ___ ___
|   |   |  |   |   |  |   |   |  |   |   |  |   |   |
|___|___|  |___|___|  |___|___|  |___|___|  |___|___|

The basic task of a LISP program is to wander along a straight chain of cons cells, pointer to pointer to pointer, looking for some pattern in the other half of the cell. LISP-code represents these chains very elegantly by enclosing them in parentheses:

       (pattern1 pattern2 pattern3 ... )

This crawl-and-compare strategy is the normal approach to search , but search is an aspect of computation that should be minimized, because it necessarily proceeds relatively slowly. Speed gains require that data be sorted , again, into neat systematizations, accessible via an indexing system . (Hash tables are a poor compromise, allowing at best the fastest possible search in cases where systematic indexing is impossible.)

LISP is cleverly designed to allow a great deal of flexibility in incremental program modification, and for this reason it's much favored by symbolic AI researchers. But it's not very efficient, and it may foster a sloppy attitude towards economical coding. The early successes of expert systems developed in LISP led to a sudden influx of venture capital, starting around 1980, into companies developing dedicated LISP hardware, a financial 'bubble' that had collapsed by 1988, as expert-system development moved on to C, and competitive LISP compilers became available for general-purpose microcomputers.

Slight differences of 'dialect' in the many different early LISPs led to severe problems translating applications between computer platforms. To solve this, an impressive 'Common LISP' standard was hacked out, by committee. An object-oriented extension to the Common LISP standard is called the Common LISP Object System (CLOS, often pronounced CEE-loss). The 'meta-object protocol' problem for CLOS remains under debate: what sorts of information should type-objects (etc) know about their objects, and how should it be accessed?

Another direction LISP might yet evolve in will be to supplement its two- element cons cells with eight-element cells, for building well- balanced content-addressable hierarchies. (See the upcoming section on stories.)

Resources

GNU Emacs is a fully programmable word processor written in 'elisp', and can make a useful development platform for many sorts of text-oriented AI research. Jennifer Myers of Northwestern University has put together some very nice Web pages on emacs, including one for tracking down the software itself for various platforms and a sort of emacs home page.

A nice Web version of the emacs manual is also available. Intro to Emacs LISP

A Mac version of Xemacs is now finally available.

Various free- and shareware verisons of LISP are collected at MIT.

A short introduction to CLOS (Common Lisp object-oriented programming extension) by Jeff Dalton is available.

A Lisp FAQ is also available by anonymous ftp, from the same ftp locations as the comp.ai.status-quo FAQ (see biblio at end)

Newsgroups:
comp.lang.lisp,
comp.lang.lisp.franz,
comp.lang.lisp.mcl,
comp.lang.lisp.x,
comp.org.lisp-users,
comp.std.lisp

Steele's beautifully-written text is the standard reference for Common LISP. Incredibly enough, it's available on the Web in its entirety!

John McCarthy, net curmudgeon, can usually be found on rec.arts.books.