The Survival of LISP

 

As a programming language, LISP is characterized by the following ideas:

1. Computing with symbolic expressions rather than numbers.
2. Representation of symbolic expressions and other information by list structure in computer memory.
3. Representation of information on paper, from keyboards and in other external media mostly by multi-level lists and sometimes by S-expressions. It has been important that any kind of data can be represented by a single general type.
4. A small set of selector and constructor operations expressed as functions, i.e. car, cdr and cons.
5. Composition of functions as a tool for forming more complex functions.
6. The use of conditional expressions for getting branching into function definitions.
7. The recursive use of conditional expressions as a sufficient tool for building computable functions.
8. The use of -expressions for naming functions.
9. The storage of information on the property lists of atoms.
10. The representation of LISP programs as LISP data that can be manipulated by object programs. This has prevented the separation between system programmers and application programmers. Everyone can ``improve'' his LISP, and many of these ``improvements'' have developed into improvements to the language.
11. The conditional expression interpretation of Boolean connectives.
12. The LISP function eval that serves both as a formal definition of the language and as an interpreter.
13. Garbage collection as the means of erasure.
14. Minimal requirements for declarations so that LISP statements can be executed in an on-line environment without preliminaries.
15. LISP statements as a command language in an on-line environment.

Of course, the above doesn't mention features that LISP has in common with most programming languages in its ``program feature''.

All these features have remained viable and the combination must be some kind of approximate local optimum in the space of programming languages, because LISP has survived several attempts to replace it, some rather determined. It may be worthwhile to review a few of these and guess why they didn't make it.

1. SLIP included list processing in Fortran. It used bidirectional lists and didn't allow recursive functions or conditional expressions. The bidirectional lists offered advantages in only a few applications but otherwise took up space and time. It didn't encourage on-line use, since Fortran doesn't.
2. Formac was another Fortran based language that was pushed for a while by part of IBM. It was dedicated to manipulating a class of algebraic formulas written in Fortran style and was also oriented to batch processing.
3. Formula Algol was dedicated to the linguistic pun that the elementary operations can be regarded as operating on numbers or on formulas. The idea was that if a variable x has no value, then operations on expressions involving x must be regarded as operating on the formula. A few programs could be written, but the pun proved an inadequate basis for substantial programs.
4. One of the more interesting rivals to LISP is (or was) POP-2. It has everything that LISP has except that its statements are written in an Algol-like form and don't have any list structure internal form. Thus POP-2 programs can produce other POP-2 programs only as character strings. This makes a much sharper distinction between system programmers and application programmers than in LISP. In LISP, for example, anyone can make his own fancy macro recognizer and expander.
5. Microplanner is an attempt to make a higher level general purpose language than LISP. The higher level involves both data (pattern matching) and control (goal seeking and failure mechanisms). Unfortunately, both proved inadequately general, and programmers were forced to very elaborate constructions, to new languages like CONNIVER with even more elaborate control features, and eventually many went back to LISP.

   One generic trouble seems to be that no-one adequately understands pattern directed computation which always works very nicely on simple examples, but which leads to over complicated systems when generalized. We can see this in LISP in certain macro expansion systems like that of the LISP machine [WM78].

6. I should mention Prolog, but I don't understand it well enough to comment.