Lisp: Tears of Joy, Part 3

Genesis

By now, most of us agree that LISP is the world’s greatest programming language. For those of you who still disagree, and think it probably stands for “Lots of Irritating Superfluous Parentheses”, my suggestion would be to read this article with a few bottles of strong beer (for the hacker types) or wine (for the high brow literary elite).

Guy L Steele Jr and Richard P Gabriel, in their paper “The Evolution of LISP” [PDF], say that the origin of LISP was guided more by institutional rivalry, one-upmanship, and the glee born of technical cleverness that is characteristic of the hacker culture, than by a sober assessment of technical requirements.

How did it all start? Early thoughts about a language that eventually became LISP started in 1956, when John McCarthy attended the Dartmouth Summer Research Project on Artificial Intelligence. Actual implementation began in the fall of 1958. These are excerpts from the essay “Revenge of the Nerds” by Paul Graham:

LISP was not really designed to be a programming language, at least not in the sense we mean today, which is something we use to tell a computer what to do. McCarthy did eventually intend to develop a programming language in this sense, but the LISP that we actually ended up with was based on something separate that he did as a theoretical exercise—an effort to define a more convenient alternative to the Turing Machine. As McCarthy said later, “Another way to show that LISP was neater than Turing machines was to write a universal LISP function, and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval, which computes the value of a LISP expression… Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper, with no thought that it would be used to express LISP programs in practice.

Some time in late 1958, Steve Russell, one of McCarthy’s graduate students, looked at this definition of eval and realised that if he translated it into machine language, the result would be a LISP interpreter.

This was a big surprise at the time. Here is what McCarthy said about it later in an interview:

Steve Russell said, “Look, why don’t I program this eval,” and I said to him, “Ho, ho, you’re confusing theory with practice; this eval is intended for reading, not for computing.” But he went ahead and did it. That is, he compiled the eval in my paper into [IBM] 704 machine code, fixing bugs, and then advertised this as a LISP interpreter, which it certainly was. So at that point LISP had essentially the form that it has today…

Suddenly, in a matter of weeks, I think, McCarthy found his theoretical exercise transformed into an actual programming language — and a more powerful one than he had intended. (Read the complete essay here.)

Now, despite how much I love LISP and think that all the pages of LINUX For You should be dedicated to it, I also know that if I want to keep writing for this magazine, I need to stick to the word limit. So, as interesting as the origin of LISP is, we should now move on to the real task at hand… (and for those who’ve lost the plot, it is learning LISP).

Defining local variables in LISP

To define a local variable, use the let command. A let expression has two parts; the first is a list of variable declarations, where we can declare one or more local variables — valid within the body of the let. The second is the body of the let, where we can use these variables. The expressions in the body are evaluated in order. Here’s an example:

> (let ( (x 18)
        (y 13)
        (z 15))
    (+ x y z))
46

Here, I have defined three local variables x, y, and z, and assigned them values of 18, 13 and 15, respectively. Each pair of local variable names and values assigned to them need to be surrounded by a set of parentheses. Also, the indentation, white-space, and line breaks are discretionary — and therefore, you can stack up the variables and their values in a let expression to resemble a table. This is why I have placed y directly underneath x and z directly below y. Figure 1 identifies the parts of the let.

Defining local functions in LISP

To define a local function, use the flet command. This, too, has two parts: (1) function declaration; and (2) the flet body, where the function may be called. The function declaration itself consists of a function name, the arguments to that function, and the function body, where we put the function’s code. As with let, we can define one or more functions within the scope of the flet. But remember that these are local functions visible only in the body — they may not call one another, and so cannot be recursive. Here’s an example:

> (flet ( (foo(n)
                 (+ n 5))
             (bar(n)
                 (+ n 10)))
    (bar (foo 2)))
17

Here, I have declared two functions: foo and bar. In this code example, the body of the flet first calls foo with 2 as its argument, to return a value of 7; it then calls bar to add 10 to this value, leading to 17 as the final value of the whole flet expression. See Figure 2.

Let’s see what happens when bar tries to call foo in its function body:

> (flet ( (foo(n)
                 (+ n 5))
            (bar(n)
                (+ (foo 2) n)))
        (bar 10))

*** - EVAL: undefined function FOO
The following restarts are available:
USE-VALUE	:R1		Input a value to be used instead of (FDEFINITION 'FOO).
RETRY		:R2		Retry
STORE-VALUE	:R3		Input a new value for (FDEFINITION 'FOO).
ABORT		:R4		Abort main loop
>

That’s right! You get slapped in the face with an error (Figure 3). The flet command creates local functions, which are invisible inside another function body.

To define recursive local functions, use labels. Local functions defined by a labels expression can refer to any other functions defined there, including themselves. This is identical in its basic structure to the flet command. Here’s the preceding code, written with labels:

> (labels ( (foo(n)
                 (+ n 5))
            (bar(n)
                (+ (foo 2) n)))
        (bar 10))
17

In this code example, the body of the labels expression calls the local function bar. Since labels allows local functions to see each other, the bar function calls another local function (from inside its body). That is foo, which adds 2 to 5, resulting in a value of 7, which in turn is added to 10 — the argument of the bar function, resulting in a final value of 17.

This is where I have to leave you this month (as I have run out of space!) but before I go, I would like to thank everybody who wrote in to provide feedback about the article last month.