Linear lisp(ID:3979/lin007)L-Expression Lisp, with more than two elements in the list Structures: Related languages
References: MCCARTHY, JOHN. Recursive functions of symbol expressions and their computation by machine, part I. Comm. ACM 3, 4 (April 1960), 184-195. In this paper, the author introduces a mathematical formalism for computing recursive functions; a list processing language (LISP) for computing partial functions of Symbolic Expressions; and finally, the realization of this language as a programming system for the 704 computer. The mathematical formalism is built around conditional expressions of the form: (pi ~ e1, p2 ~ e2 ~ ~ Pn ~ en), where the pj'S are predicates having the values of Truth, Falsity, or else are undefined. The value of the conditional expression is the expression ej, if pj is true and all pk. k < j, are false. If no such pj exists, the conditional is undefined. After clearly distinguishing between forms and functions, the author then introduces Church's Lambda notation, by means of which functions can be expressed in terms of the basic form and ordered lists of the variables and their arguments. Thus, the form X2-y3/z would be expressed as \((x, y, a), X2-y3/z)' and, if paired with an ordered list of arguments (m, n2, na), would produce an unambiguous value for the function. Such Lambda expressions can then be defined recursively by conditional expressions through the use of a second notational convention which allows the function to use itself as an argument. The types of lists dealt with in the system are called S- Expressions, and are in the form of an ordered pair. Each element of the pair may be either another S-Expression or else any distinguishable symbol. Such a symbol, which may be a collection of characters, is called atomic to distinguish it from an S-Expression. The LISP language has as its basic set of operations two predicates and three basic " SFunctions" which when used in conjunction with conditional expressions and recursive definition allow the building of a very powerful set of operations. The two predicates atom (x) and eq (x' y) give the value of Truth depending upon whether the list is composed of a single atomic symbol, or the two atomic symbols x and y are equal. The three basic "S-Functions" are "car (x)" which has for its value the first element of the S-Expression x; "car (x)" which has for its value the other half of the S-expression; and "cons (x, y)" which forms a new S-Expression comprised of the two arguments. (Car and cdr are undefined for the case of an atomic argument.) The author introduces a number of specialized S-Functions and predicates of S-Expressions which are defined recursively from the elementary ones. A special notation and set of conventions are then defined in order to describe S- Functions themselves as S-Expressions using the normal, rather limited character set available on most existing computers. The LISP programming system as it existed on the 704 is then described in moderate detail, covering topics such as the actual representation of the S-Expressions as a list structure in the computer, how S functions were represented by programs, and the mechanics of pushdown lists for recursive computation. The author then generalizes S-Expressions (which are two- element lists) to allow L-Expressions composed of many- element lists. The corresponding language, called "Linear LISP" is then introduced, but not fully explored. The final discussion in the paper pertains to the parallel which can exist between recursive functions and a program flow chart. It is far easier to criticize than to create, and nothing that the reviewer says should be allowed to detract from the fact that this system represents a pioneering attempt to slide a reasonable mathematical foundation under a rather slippery subject, as well as the fact that the programming system described exists, and has been used with marked success for many symbol processing problems. (These are, however, not described in this paper.) As a presentation, this paper puts a needless burden on the reader by a rather loose introduction and frequent change of notational conventions, symbols, and definitions, many of which seem to be introduced rather casually as they are needed. To come to questions of more substance, "undefined" expressions and the corresponding recursions which might never terminate were inadequately treated, and might well be vital in any real usage of the system. The reviewer feels that several rather important issues pertaining to machine capacity and speed have been left unanswered by this as well as other similar papers. Undoubtedly, special languages are needed for manipulating lists. There appear to be at least two tacitly acknowledged criteria for such languages: First, all symbols, with the exception of punctuation marks, should be treated as if they were created equal. That is, for full generality (or perhaps democracy) no concept of number or measure should be allowed to creep into the formal system. Second, one should somehow start off with the bare minimum of primitive operations from which all others can be (and presumably are) built up. While it would appear that this leads to a more elegant mathematical formulation of the system, there is a serious reservation that it leads to difficult notation problems for the user as well as an inefficient computing scheme for the machine. Could it be that we are in a sense reducing the machine to our own level? Some functions undoubtedly should be defined recursively, and some lists should be scanned by starting at the first element and working through it essentially by brute force, but if a recursive operation is always used seriously as a computational procedure some rather startling inefficiencies can be guaranteed. For example, addition or multiplication by recursion, or for that matter, sorting a list into order, are rather horrible to contemplate. It would appear that before any language, such as LISP, can lay claim to be a basis for a theory of computation, it must be armed with tools that would enable it to determine its own efficiency as a means to achieve a given end, vis-a-vis other methods. Herbert M. Teager, Cambridge, Mass. in ACM Computing Reviews 2(01) January-February 1961 view details |