Edsger W. Dijkstra on Lisp

LISP has been jokingly described as "the most intelligent way to misuse a computer". I think that description a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.

In Departments of Computing Science, one of the most common confusions is the one between a program and its execution, between a programming language and its implementation. I always find this very amazing: the whole vocabulary to make the distinction is generally available, and also, the very similar confusion between and computer and its order code, remarkably enough, is quite rare. But it is a deep confusion of long standing. One of the oldest examples is presented by the LISP 1.5 Manual: halfway their description of the programming language LISP, its authors give up and from then onwards try to complement their incomplete language definition by an equally incomplete sketch of a specific implementation. Needless to say, I have not been able to learn LISP from that booklet!

LISP is a good example. In the early sixties we have suffered from a piece of computer science folklore, viz. that the crucial test whether on had designed "a good language" was, whether one could write its own interpreter in itself. I have never understood the reason for that criterion --it was suggested that such a language definition would solve the problem of the definition of (particularly) the semantics of the language--, the origin of the criterion was the example of LISP, which was "defined" by a ten-line interpreter written in LISP, and that, somehow, set the standard. (I found this hard to accept because when I started to study LISP from the LISP 1.5 Manual, I could not understand it: after an incomplete definition of the language, its authors try to supplement these deficiencies by an equally incomplete sketch of a specific implementation, and that was a confusion if there ever was one!) This unfortunate LISP-interpreter formulated in LISP has somehow given mechanistic (or "operational") language definitions an undeserved aura of respectability, and its unwholesome influence can be traced right through the Vienna Definition Language and ALGOL 68 --what I knew-- and even --what I learned this week to my surprise and disappointment-- to the work of Dana S. Scott. It is enlightening to know --what I also learned later that week-- that LISP's most awful property, viz. "shallow binding" --now religiously defended by its addicts!-- is described by McCarthy as "a mistake" in that ten-line interpreter (which, of course, it is,)!

It was the complete entanglement of language definition and language implementation that characterized the discussion after Mary Shaw's presentation, and it was the entanglement that left many of the Europeans flabbergasted. It was also this entanglement that made it possible for me to read the LISP 1.5 Manual: after an incomplete language definition, that text tries to fill the gaps with an equally incomplete sketch of an —of the?— implementation. Yet LISP 1.5 conquered in the decade after the publication of that manual a major portion of the American academic computing community. This, too, must have had a traceable influence. Why did LISP never get to that position in Europe? Perhaps because in the beginning its implementation made demands beyond our facilities, while later many had learned to live without it. (I myself was completely put off by the Manual.)

Four slots were filled by G. J. Sussman (Artificial Intelligence Laboratory, MIT) and a similar number by D. S. Wise (Department of Computer Science, Indiana University). Both belonged very much to the LISP subculture, neither of the two proved a single theorem, both showed too much and made such heavy use of anthropomorphic terminology that they were painful to listen to. Sussman's transparencies were printed, but overloaded; Wise's transparencies were handwritten, but very messy. Not used to Sussman's lecturing style - is it called "teaching by example"? - I found him very tiring to listen to; he spoke very fast but told very little, since he used most of his words to go in detail through a number of almost identical examples. Wise struck me as rather old-fashioned: he seemed to talk about the implementation of LISP in very much the same way as people did in the early sixties. LISP's syntax is so atrocious that I never understood its popularity. LISP's possibility to introduce higher-order functions was mentioned several times in its defence, but now I come to think of it, that could be done in ALGOL60 as well. My current guess is that LISP's popularity in the USA is related to FORTRAN's shortcomings.

Q We have seen Lisp emerge in documenting constructs?

A Lisp was great at the time of its inception if only for a radically new way of using machines. It has suffered the fate of having been elevated to a status of de facto standard with all its defects. Despite its conceptual novelty a lot of the design of Lisp is terribly amateurish even by the standards of the time. When I read the first manual, the Lisp 1.5 manual, published in 1961, I could not believe my eyes. It was an extremely poor language. Now it has become the defacto standard of the AI community, which now suffers from Lisp, the way the rest of the world suffered from Fortran.

Then LISP emerged as programming vehicle for symbol manipulation. LISP can be viewed as a highly successful exercise in the mechanization of applied logic. For computing science, its cultural significance is that it liberated computing from the narrow connotations of number crunching by including all formal processes --from symbolic differentiation and integration to formal theorem proving-- as computational activities.

As said, FORTRAN and LISP were the two great achievements of the 50s. Compared with FORTRAN, LISP embodied a much greater leap of imagination. Conceptually FORTRAN remained on familiar grounds in the sense that its purpose was to aid the mechanization of computational processes we used to do with pen and paper (and mechanical desk calculators if you could afford them). This was in strong contrast to LISP whose purpose was to enable the execution of processes that no one would dream of performing with pen and paper.

At the time LISP's radical novelties were for instance recognized by its characterization as "the most intelligent way of misusing a computer", in retrospect we see its radical novelty because it was what is now known as a language for "functional programming", while now, 40 years later, functional programming is still considered in many CS departments as something much too fancy, too sophisticated to be taught to undergraduates. LISP had its serious shortcomings: what became known as "shallow binding" (and created a hacker's paradise) was an ordinary design mistake; also its promotion of the idea that a programming language should be able to formulate its own interpreter (which then could be used as the language's definition) has caused a lot of confusion because the incestuous idea of self-definition was fundamentally flawed. But in spite of these shortcomings, LISP was a fantastic and in the long run highly influential achievement that has enabled some of the most sophisticated computer applications.

I must confess that I was very slow on appreciating LISP's merits. My first introduction was via a paper that defined the semantics of LISP in terms of LISP, I did not see how that could make sense, I rejected the paper and LISP with it. My second effort was a study of the LISP 1.5 Manual from MIT which I could not read because it was an incomplete language definition supplemented by equally incomplete description of a possible implementation; that manual was so poorly written that I could not take the authors seriously, and rejected the manual and LISP with it. (I am afraid that tolerance of inadequate texts was not my leading characteristic).

Things changed in 1960, when a transatlantic cooperation created the programming language ALGOL 60, an event that my colleague F. E. J. Kruseman Aretz for good reasons has chosen to mark the birth of Computing Science. The reasons were good because ALGOL 60 introduced a handful of deep novelties, all of which have withstood the test of time. Let me review them briefly.

Firstly there is the introduction and use of Backus-Naur-Form (or BNF for short), a formal grammar to define the syntax of the programming language. More than anything else, ALGOL 60's formal definition has made language implementation a topic worthy of academic attention, and this was a crucial factor in turning automatic computing into a viable scientific discipline.

Secondly there was the block structure and the concept of the local variable, with the beautiful synthesis of lexicographic scope with dynamically nested lifetimes. The lexicographic scope led to a unified notation for mathematical quantification, while the nested lifetimes opened the door to the next novelty.

This was recursion. Logicians knew it, LISP had incorporated it, but ALGOL 60 gave it a firm place in imperative programming.