Simon Willison’s Weblog

Basic Lisp

30th September 2002

Basic Lisp

Typically, Lisp is run as an interactive interpreter. People write a whole load of Lisp in a test file and then load it in to the interpreter and try it out to see if it works. Lisp is a very dynamic language—functions can be redefined on the fly and it is perfectly possible to shoot yourself in the foot (by redefining Lisp internals for example) if you really want to.

To load a file full of pre-written Lisp code, use (load "filename.ext"), which is the equivalent of typing in all of the lines from the file at the interactive prompt. Files can be edited and reloaded simply by re-calling the load function.

Reminder: In Lisp, all functions are called using (func arg1 arg2 ...) syntax. Language such as C and Java provide two ways of calling functions—function(arg, arg, ...) and infix notation such as arg + arg (the plus sign is really a call to an addition function). Infix notation is quicker to understand initially as it duplicates the way maths is taught at school but it is far more limited than argument notation as it can only ever deal with two arguments. Lisp only has the more powerful multiple arguments method of calling functions.

EuLisp and euscheme

We will be using Eulisp on the course, which was partially developed by professors at the University of Bath who have also written an implementation of the language (covered by a BSD style language and available from here). The easiest implementation to use for educational purposes is called euscheme, which despite the thoroughly confusing name is a Lisp interpreter and not a Scheme interpreter. It can be run on the University unix machines by typing euscheme, and exited by hitting Ctrl+D (sometimes several times if the interpreter is currently in a debug loop).

The language euscheme is written partly in C and partly in euscheme itself. It has a C kernel which handles basic things such as memory management, garbage collection and low level functions such as addition. The rest of the interpreter is written in Lisp.

When you are typing things in to the euscheme interpreter you are actually interacting with a Lisp function called read-eval-print. The debug loop (described below) is itself a recursive call to this interactive function.

Debugging

In euscheme, errors in interpreted code will plunge you in to a debug loop complete with a debug prompt. The debug loop provides additional functionality—type help: at the debug prompt for a list of debug options. The most important debug command is bt: (backtrace) which lists all of the functions that have been called to get to the current state of the interpreter. This can be invaluable for debugging large programs. Another useful command is top: which will instantly snap you out of the debug loops and take you back to the standard prompt.

length

The length function returns the length of a list:

> (length '(1 2 3))
3
>

The single quote is important, as without it Lisp would attempt to interpret the symbol 1 as a function which would cause an error.

Note: Entering length '(1 2 3) without the outer brackets will result in the interpreter evaluating the command as two separate expressions.

Data Structures and Lists

In Lisp, the only built in data structure is the list. Lists are very flexible and can be used to define a whole variety of more complex structures through nesting lists—for example:

(x x x x) - a list
(x x) - a pair
(x (x x)) - a nested list

There are three principle operations that can be performed on a list:

1. Return the first thing in the list
2. Return the remaining things in the list
3. Add an item to a list to make a new, longer list

1 and 2 are accessors. 3 is a constructor. The lisp functions that accomplish these operations are called, respectively, car, cpr and cons. These functions take their names from the registers of the IBM 704 computer, which was used by John McCarmack to write one of the first Lisp implementations.

car = first, cdr = rest and cons is the constructor.

(car '(a b c)) returns a
(cdr '(a b c)) returns (b c)
(cons 'a '(b c) returns (a b c)

So, if x is a list, (cons (car x) (cdr x)) == x

If you try to run car or cdr on something that is not a list you will get an error. (car ()) is the source of much debate in the Lisp world—in euscheme it will raise an error, but in some Lisp implementations it will return an empty list.

Jargon: A proper list is a list that is not empty.

In theory, you can build lists by repeatedly calling the cons function. In practise, Lisp provides a much more convenient method in the form of the list function:

> (list 1 4 66)
(1 4 66)
>

Some interesting Lisp function results

> (*)
1
> ''two
(quote two)
> (cons () ())
(())
>

Finally, note the difference between '(a b c) and (list a b c)—while the quote method returns the list exactly as written, the list function will attempt to evaluate each argument before returning.