a. Property lists. The idea of providing each atom with a list of properties was present in the first assembly language implementation. It was also one of the theoretical ideas of the Advice Taker, although the Advice Taker (McCarthy 1959) would have required a property list for any expression about which information was known that did not follow from its structure. The READ and PRINT programs required that the print names of atoms be accessible, and as soon as function definition became possible, it was necessary to indicate whether a function was a SUBR in machine code or was an EXPR represented by list structure. Several functions dealing with property lists were also made available for application programs which made heavy use of them.
b. Insertion of elements in lists and their deletion. One of the original advertised virtues of list processing for AI work was the ability to insert and delete elements of lists. Unfortunately, this facility coexists uneasily with shared list structure. Moreover, operations that insert and delete don't have a neat representation as functions. LISP has them in the form of the rplaca and rplacd pseudo-functions, but programs that use them cannot be conveniently represented in logic, because, regarded as functions, they don't permit replacement of equals by equals.
c. Numbers. Many computations require both numbers and symbolic expressions. Numbers were originally implemented in LISP I as lists of atoms, and this proved too slow for all but the simplest computations. A reasonably efficient implementation of numbers as atoms in S-expressions was made in LISP 1.5, but in all the early LISPs, numerical computations were still 10 to 100 times slower than in FORTRAN. Efficient numerical computation requires some form of typing in the source language and a distinction between numbers treated by themselves and as elements of S-expressions. Some recent versions of LISP allow distinguishing types, but at the time, this seemed incompatible with other features.
d. Free variables. In all innocence, James R. Slagle programmed the following LISP function definition and complained when it didn't work right:
The object of the function is to find a subexpression of x satisfying p[x] and return f[x]. If the search is unsuccessful, then the continuation function u[] of no arguments is to be computed and its value returned. The difficulty was that when an inner recursion occurred, the value of car[x] wanted was the outer value, but the inner value was actually used. In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.
I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell's turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. Unfortunately, time did not permit writing an appendix giving the history of the problem, and the interested reader is referred to (Moses 1970) as a place to start. (David Park tells me that Patrick Fischer also had a hand in developing the FUNARG device).
e. The ``program feature''. Besides composition of functions and conditional expressions, LISP also allows sequential programs written with assignment statements and go tos. Compared to the mathematically elegant recursive function definition features, the ``program feature'' looks like a hasty afterthought. This is not quite correct; the idea of having sequential programs in LISP antedates that of having recursive function definition. However, the notation LISP uses for PROGs was definitely an afterthought and is far from optimal.
f. Once the eval interpreter was programmed, it became available to the programmer, and it was especially easy to use because it interprets LISP programs expressed as LISP data. In particular, eval made possible FEXPRS and FSUBRS which are "functions" that are not given their actual arguments but are given the expressions that evaluate to the arguments and must call eval themselves when they want the expressions evaluated. The main application of this facility is to functions that don't always evaluate all of their arguments; they evaluate some of them first, and then decide which others to evaluate. This facility resembles Algol's call-by-name but is more flexible, because eval is explicitly available. A first order logic treatment of ``extensional'' FEXPRs and FSUBRs now seems possible.
g. Since LISP works with lists, it was also convenient to provide for functions with variable numbers of arguments by supplying them with a list of arguments rather than the separate arguments.
Unfortunately, none of the above features has been given a comprehensive and clear mathematical semantics in connection with LISP or any other programming language. The best attempt in connection with LISP is Michael Gordon's (1973), but it is too complicated.
h. The first attempt at a compiler was made by Robert Brayton, but was unsuccessful. The first successful LISP compiler was programmed by Timothy Hart and Michael Levin. It was written in LISP and was claimed to be the first compiler written in the language to be compiled.
Many people participated in the initial development of LISP, and I haven't been able to remember all their contributions and must settle, at this writing, for a list of names. I can remember Paul Abrahams, Robert Brayton, Daniel Edwards, Patrick Fischer, Phyllis Fox, Saul Goldberg, Timothy Hart, Louis Hodes, Michael Levin, David Luckham, Klim Maling, Marvin Minsky, David Park, Nathaniel Rochester of IBM, and Steve Russell.
Besides work on the LISP system, many applications were programmed, and this experience affected the system itself. The main applications that I can remember are a program by Rochester and Goldberg on symbolic computation of impedances and other functions associated with electrical networks, J.R. Slagle's thesis work on symbolic integration directed by Minsky, and Paul Abrahams' thesis on proof-checking.