LISP(ID:14/lis005)
A list processing system with emphasis on recursion and formalism
for LISt Processing.
John McCarthy et al, MIT late 1950s
Symbolic functional recursive language based on lambda- calculus, used especially for AI and symbolic math. Many dialects. Atoms and lists. Dynamic scope. Both programs and data are represented as list structures.
AI's mother tongue, a language based on the ideas of a) variable-length lists and trees as fundamental data types, and b) the interpretation of code as data and vice-versa. Invented by John McCarthy at MIT in the late 1950's. Accordingly, it has undergone considerable adaption. Modern variants are quite different in detail from the original LISP 1.5.
A list processing system with emphasis on recursion and formalism. (Sammett 1966)
Places
People:
Structures:
Related languages
| Church typed-lambda calculus | => | LISP | Influence | |
| FLPL | => | LISP | Influence | |
| GPS | => | LISP | Influence | |
| IPL | => | LISP | Influence | |
| V2 | => | LISP | Evolution of | |
| LISP | => | Advice Taker | Written using | |
| LISP | => | ASAS | Based on | |
| LISP | => | FRL | Extension of | |
| LISP | => | LAMA | Based on | |
| LISP | => | LISP 1.5 | Evolution of | |
| LISP | => | SDL | Influence | |
| LISP | => | SLPL | Influence |
References:
This paper will discuss programs to manipulate in a suitable formal language (most likely a part of the predicate calculus) common instrumental statements. The basic program will draw immediate conclusions from a list of premises. These conclusions will be either declarative or imperative sentences. When an imperative sentence is deduced the program takes a corresponding action. These actions may include printing sentences, moving sentences on lists, and reinitiating the basic deduction process on these lists.
Facilities will be provided for communication with humans in the system via manual intervention and display devices connected to the computer.
The advice taker is a proposed program for solving problems by manipulating sentences in formal languages. The main difference between it and other programs or proposed programs for manipulating formal languages (the Logic Theory Machine of Newell, Simon and Shaw and the Geometry Program of Gelernter) is that in the previous programs the formal system was the subject matter but the heuristics were all embodied in the program. In this program the procedures will be described as much as possible in the language itself and, in particular, the heuristics are all so described.
The main advantages we expect the advice taker to have is that its behavior will be improvable merely by making statements to it, telling it about its symbolic environment and what is wanted from it. To make these statements will require little if any knowledge of the program or the previous knowledge of the advice taker. One will be able to assume that the advice taker will have available to it a fairly wide class of immediate logical consequences of anything it is told and its previous knowledge. This property is expected to have much in common with what makes us describe certain humans as having common sense. We shall therefore say that a program has common sense if it automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows.
Extract: Introduction
Before describing the advice taker in any detail, I would like to describe more fully our motivation for proceeding in this direction. Our ultimate objective is to make programs that learn from their experience as effectively as humans do. It may not be realized how far we are presently from this objective. It is not hard to make machines learn from experience to make simple changes in their behavior of a kind which has been anticipated by the programmer. For example, Samuel has included in his checker program facilities for improving the weights the machine assigns to various factors in evaluating positions. He has also included a scheme whereby the machine remembers games it has played previously and deviates from its previous play when it finds a position which it previously lost. Suppose, however, that we wanted an improvement in behavior corresponding, say, to the discovery by the machine of the principle of the opposition in checkers. No present or presently proposed schemes are capable of discovering phenomena as abstract as this.
If one wants a machine to be able to discover an abstraction, it seems most likely that the machine must be able to represent this abstraction in some relatively simple way.
There is one known way of making a machine capable of learning arbitrary behavior; thus to anticipate every kind of behavior. This is to make it possible for the machine to simulate arbitrary behaviors and try them out. These behaviors may be represented either by nerve nets (Minsky 1956), by Turing machines (McCarthy 1956), or by calculator programs (Friedberg 1958). The difficulty is two-fold. First, in any of these representations the density of interesting behaviors is incredibly low. Second, and even more important, small interesting changes in behavior expressed at a high level of abstraction do not have simple representations. It is as though the human genetic structure were represented by a set of blue-prints. Then a mutation would usually result in a wart or a failure of parts to meet, or even an ungrammatical blue-print which could not be translated into an animal at all. It is very difficult to see how the genetic representation scheme manages to be general enough to represent the great variety of animals observed and yet be such that so many interesting changes in the organism are represented by small genetic changes. The problem of how such a representation controls the development of a fertilized egg into a mature animal is even more difficult.
In our opinion, a system which is to evolve intelligence of human order should have at least the following features:
All behaviors must be representable in the system. Therefore, the system should either be able to construct arbitrary automata or to program in some general purpose programming language.
Interesting changes in behavior must be expressible in a simple way.
All aspects of behavior except the most routine must be improvable. In particular, the improving mechanism should be improvable.
The machine must have or evolve concepts of partial success because on difficult problems decisive successes or failures come too infrequently.
The system must be able to create subroutines which can be included in procedures as units. The learning of subroutines is complicated by the fact that the effect of a subroutine is not usually good or bad in itself. Therefore, the mechanism that selects subroutines should have concepts of interesting or powerful subroutine whose application may be good under suitable conditions.
Of the 5 points mentioned above, our work concentrates mainly on the second. We base ourselves on the idea that: In order for a program to be capable of learning something it must first be capable of being told it. In fact, in the early versions we shall concentrate entirely on this point and attempt to achieve a system which can be told to make a specific improvement in its behavior with no more knowledge of its internal structure or previous knowledge than is required in order to instruct a human. Once this is achieved, we may be able to tell the advice taker how to learn from experience.
The main distinction between the way one programs a computer and modifies the program and the way one instructs a human or will instruct the advice taker is this: A machine is instructed mainly in the form of a sequence of imperative sentences; while a human is instructed mainly in declarative sentences describing the situation in which action is required together with a few imperatives that say what is wanted. We shall list the advantages of of the two methods of instruction.
Advantages of Imperative Sentences
A procedure described in imperatives is already laid out and is carried out faster.
One starts with a machine in a basic state and does not assume previous knowledge on the part of the machine.
Advantages of Declarative Sentences
Advantage can be taken of previous knowledge.
Declarative sentences have logical consequences and it can be arranged that the machine will have available sufficiently simple logical consequences of what it is told and what it previously knew.
The meaning of declaratives is much less dependent on their order than is the case with imperatives. This makes it easier to have after-thoughts.
The effect of a declarative is less dependent on the previous state of the system so that less knowledge of this state is required on the part of the instructor.
The only way we know of expressing abstractions (such as the previous example of the opposition in checkers) is in language. That is why we have decided to program a system which reasons verbally.
External link: Online copy
in Proceedings of the Symposium on the Mechanisation of Thought Processes. Teddington, Middlesex, England: The National Physical Laboratory, November 1958 view details
in Proceedings of the Symposium on the Mechanisation of Thought Processes. Teddington, Middlesex, England: The National Physical Laboratory, November 1958 view details
in Proceedings of the Symposium on the Mechanisation of Thought Processes. Teddington, Middlesex, England: The National Physical Laboratory, November 1958 view details
in SESSION: Automatic programming: theory and research view details
in SESSION: Automatic programming: theory and research view details
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, January-December 1960 view details
in [ACM] CACM 3(04) April 1960 view details
in [ACM] CACM 4(01) (Jan 1961) view details
in The Computer Journal 4(1) April 1961 view details
in The Computer Journal 4(1) April 1961 view details
in Artificial languages view details
This report describes several list structures and some important aspects of their implementation. It describes and compares FLPL, IPL-V, LISP and SLIP. It also gives examples of the use of slip in manipulating power series.
in Artificial languages view details
Introduction
The aim of the research reported here was to discover how one could build a computer program which could communicate with people in a natural language within some restricted problem domain. In the coarse of this investigation, I wrote a set of computer pro-grams, the STUDENT system, which accepts as input a comfortable but restricted subset of English which can be used to express, a wide variety of algebra story problems. The problems shown in Figure 1 illustrate some of the communication and problem solving capabilities of this system.
In the following discussion, I shall use phrases such as "the computer understands English". In all such cases, the "English" is just the restricted subset of English which is allowable as input for the computer program under discussion. In addition, for purposes of this report I have adopted the following operational definition of understanding. A computer "understands" a subset of English if it accepts input sentences which are members of this subset, and answers questions based on information centered in the input. The STUDENT system understands English in this sense. Extract: BASEBALL
Baseball is a question-answering system designed and programmed at Lincoln Laboratories by Green, Wolf, Chomsky and Laughery (19). It is a data base system in which the data is placed in memory in a prestructered tree format. The data consists of the dates, location, opposing teams and scores of some American League baseball games. Only questions to the system can be given in English, not the data.
Questions mast be simple sentences, with no relative clauses, logical or coordinate connectives. With these restrictions, the program will accept any question couched in words contained in a vocabulary list quite adequate for asking questions about baseball statistics. In addition, the parsing routine, based on techniques developed by Harris (21) , must find a parsing for the question.
The questions must pertain to statistics about baseball games found in the information store. One cannot ask questions about extrema, such as "Highest" score or "fewest" number of games won. The parsed question is transformed into a standard specification (or spec) list and the question-answering routine utilizes this canonical form for the meaning of the question. For example, the question "Who beat the Yankees on July 4th?" would be transformed into the "spec list":
Team (Losing)= New York
Team (winning) = ?
Date = July
Because Baseball does not utilize English for data input, we cannot talk about deductions made from information implicit in several sentences. However, Baseball can perform operations such as counting (the number of games played by Boston, for example) and thus in the sense that it is utilizing several separate data units in its store, it is performing deductions.
Baseball's abilities can only be extended by extensive re-programming, though the techniques utilized have some general applicability. Because the parsing program has a very complete grammar, and the vocabulary list is quite comprehensive for the problem domain, the user needs no knowledge of the internal structure of the Baseball program. No provision for interaction with the user was made.
Extract: Advice-taker
McCarthy's Advice-taker, though not designed to accept English input, would make an excellent base for a question-answering system. Fischer Black has programmed a system which can do all of McCarthy's Advice-Taker problems, and can be adapted to accept a very limited subset of English. The deductive system in Black's program is equtvalent to the propositional calculus.
in Artificial languages view details
in Artificial languages view details
in Berkeley, E.C., and Bobrow. D.G. (ed). "The Programming Language LISP, its Operation and Applications". MIT Press, 1966. view details
in Cybernetics. New York. 2. 1966, March-April view details
in [ACM] CACM 10(03) (March 1967) view details
in [ACM] CACM 10(03) (March 1967) view details
in Computers & Automation 16(6) June 1967 view details
in Computers & Automation 16(6) June 1967 view details
[ Book ] FOSTER, J. M.
List processing.
American Elsevier Publ., New York, 1967, 54 pp. $4.50.
This tiny (54 pages) monograph on list processing is a beautiful introduction to techniques which have been used for some time in many applications. Among the topics included are: 1) the representations of lists (both in the computer and externally); and 2) operations on lists, garbage collection, and typical list languages. One short chapter is also devoted to an example of list processing used in a program to perform syntactic analysis of language. All the examples in the book are programmed in an extended A~Go~ with added list processing functions, and are carefully chosen to illustrate important points about list processing. The book's principal weakness is its lack of depth, which is not really to be expected in such a brief monograph. The summary of the list processing languages IPL-V, LISP, FLIP, FLPL, and COMIT are too brief to give any real feeling for these languages to people who have not seen them before. But these are minor quibbles with a very fine book which will broaden the outlook of people who think of computers only as tools to manipulate numbers, and will allow them to begin to appreciate what can be done with list processing techniques for symbol manipula
tion. D. a. Bobrow, Cambridge, Mass.
in ACM Computing Reviews 9(01) January 1968 view details
History And Bibliography
Linear lists and rectangular arrays of information kept in consecutive memory locations were widely used from the earliest days of stored-program computers, and the earliest treatises on programming gave the basic algorithms for traversing these structures. [ For example, see J. von Neumann, Collected Works, vol. V, 113-116 (written 1947); M. V. Wilkes, D. J. Wheeler, S. Gill, The Preparation of Programs for an Electronic Digital Computer (Reading, Mass.: Addison-Wesley, 1951), subroutine V-1. ] Before the days of index registers, operations on sequential linear lists were done by performing arithmetic on the machine language instructions themselves, and this type of operation was one of the early motivations for having a computer whose programs share memory space with the data they manipulate.
Techniques which permit variable-length linear lists to share sequential locations, in such a way that they shift back and forth when necessary, as described in Section 2.2.2, were apparently a much later invention. J. Dunlap of Digitek Corporation developed these techniques in 1963 in connection with the design of a series of compiler programs; about the same time the idea independently appeared in the design of a COBOL compiler at IBM Corporation, and a collection of related subroutines called CITRUS was subsequently used at, various installations. The techniques remained unpublished until after they had been independently developed by Jan Garwick of Norway; see BIT 4 (1964), 137-140.
The idea of having linear lists in non-sequential locations seems to have originated in connection with the design of computers with drum memories; the first such computer was developed by General Electric Corporation during 1946-1948, and the IBM 650 was the most notable later machine of this type. After executing the instruction in location n, such a computer is usually not ready to get its next instruction from location n + 1 because the drum has already rotated past this point. Depending on the instruction being performed, the most favorable position for the next instruction might be n + 7 or n + 18, etc., and the machine can operate up to six or seven times faster if its instructions are optimally located rather than consecutive. [ For a discussion of the interesting problems concerning best placement of these instructions, see the author's article in JACM 8 (1961), 119-150. ] Therefore the machine design provides an extra address field in each machine language instruction, to serve as a link to the next instruction. Such a machine is called a "one-plus-one-address computer," as distinguished from MIX which is a one-address computer." The design of one-plus-one-address computers is apparently the first appearance of the linked-list idea within computer programs, although the dynamic insertion and deletion operations which we have used so frequently in this chapter were still unknown.
Linked memory techniques were really born when A. Newell, C. Shaw, and H. Simon began their investigations of heuristic problem-solving by machine. As an aid to writing programs that searched for proofs in mathematical logic, they designed the first " listprocessing" language IPL-II in the spring of 1956. (IPL stands for Information Processing Language.) This was a system which made use of links and included important concepts like the list of available space, but the concept of stacks was not yet well developed; IPL-III was designed a year later, and it included "push down" and "pop up" for stacks as important basic operations. (For references to IPL-II see "The Logic Theory Machine," IRE Transactions on Information Theory IT-2 (Sept. 1956), 61-70; see also Proc. Western Joint Comp. Conf. (Feb. 1957), 218-240. Material on IPL- III first appeared in course notes given at the University of Michigan in the summer of 1957.)
The work of Newell, Shaw, and Simon inspired many other people to use linked memory (which was often at the time referred to as NSS memory), mostly for problems dealing with simulation of human thought processes. Gradually, the techniques became recognized as basic computer programming tools; the first article describing the usefulness of linked memory for "down-to-earth" problems was published by J. W. Carr, III, in CACM 2 (Feb. 1959), 4-6. Carr pointed out in this article that linked lists can readily be manipulated in ordinary programming languages, without requiring sophisticated sub-routines or interpretive systems. See also G. A. Blaauw, IBM J. Res. and Dev. 3 (1959), 288-301.
At first, one-word nodes were used for linked tables, but about 1959 the usefulness of several consecutive words per node and "multilinked" lists was gradually being discovered by several different groups of people. The first article dealing specifically with this idea was published by D. T. Ross, CACM 4 (1961), 147-150; at that time he used the term "plex" for what has been called a "node" in this chapter, but he subsequently has used the word "plex" in a different sense to denote a class of nodes combined with associated algorithms for their traversal.
Notations for referring to fields within nodes are generally of two kinds: the name of the field either precedes or follows the pointer designation. Thus, while we have written "INFO(P)" in this chapter, some other authors write, for example, "P.INFO ". At the time this chapter was prepared, the two notations seemed to be equally prominent. The notation adopted here has been used in the author's lectures since 1962 and it has also been independently devised by numerous other people, primarily because it is natural to use mathematical functional notation to describe attributes of a node. (For example, see the article by N. Wirth and C. A. R. Hoare, CACM 9 (1966), 413-432.) Note that "INFO(P)" is pronounced "info of P" in conventional mathematical verbalization, just as f(x) is rendered "f of x." The alternative notation P.INFO has less of a natural flavor, since it tends to put the emphasis on P, although it can be read "P's info" the reason INFO(P) seems to be more natural is apparently the fact that P is variable, but INFO has a fixed significance when the notation is employed. By analogy, we could consider a vector A = (A [ l ] , A [ 2 ] , ..., A [ l00 ] ) to be a node having 100 fields named 1, 2,..., 100. Now the second field would be referred to as "2(P)" in our notation, where P points to the vector A; but if we are referring to the jth element of the vector, we find it more natural to write A [ j ] , putting the variable quantity "j" second. Similarly it seems most appropriate to put the variable quantity "P' second in the notation INFO(P).
Perhaps the first people to recognize that the concepts "stack" (last-in-first-out) and "queue" ( first-in-first-out) are important objects of study were cost accountants interested in reducing income tax assessments; for a discussion of the "LIFO" and "FIFO" methods of pricing inventories, see any intermediate accounting textbook, e.g., C. F. and W. J. Schlatter, Cost Accounting (New York: Wiley, 1957), Chapter 7. In 1947 A. M. Turing developed a stack, called Reversion Storage, for use in subroutine linkage (see Section 1.4.5). No doubt simple uses of stacks kept in sequential memory locations were common in computer programming from the earliest days, since a stack is such a simple and natural concept. The programming of stacks in linked form appeared first in IPL, as stated above; the name "stack" stems from IPL terminology (although "pushdown list" was the more official IPL wording), and it was also independently introduced in Europe by E. W. Dijkstra. "Deque" is a term introduced by E. J. Schweppe.
The origin of circular and doubly linked lists is obscure; presumably these ideas occurred naturally to many people. A strong factor in the popularization of these techniques was the existence of general List-processing systems based on them [principally the Knotted List Structures, CACM 5 (1962), 161-165, and Symmetric List Processor, CACM 6 (1963), 524-544, of J. Weizenbaum ] .
Various methods for addressing and traversing multidimensional arrays of information were developed independently by clever programmers since the earliest days of computers, and thus another part of the unpublished computer folklore came into existence. This subject was first surveyed in print by H. Hellerman, CACM 5 (1962), 205-207. See also J. C. Gower, Comp. J. 4 (1962), 280-286.
Tree structures represented explicitly in computer memory were described for the first time in applications to algebraic formula manipulation. The A-1 compiler language, developed by G. M. Hopper in 1951, used arithmetic expressions written in a three-address code; the latter is equivalent to the INFO, LLINK, and RLINK of a binary tree representation. In 1952, H. G. Kahrimanian developed algorithms for differentiating algebraic formulas represented in the A-1 compiler language; see Symposium on automatic Programming (Washington, D.C.: Office of Naval Research, May 1954), 6-14.
Since then, tree structures in various guises have been studied independently by many people in connection with numerous computer applications, but the basic techniques for tree manipulation (not general List manipulation) have seldom appeared in print except in detailed description of particular algorithms. The first general survey was made in connection with a more general study of all data structures by K. E. Iverson and L. R. Johnson [ IBM Corp. research reports RC-390, RC-603, 1961; see Iverson, A Programming Language (New York: Wiley, 1962), Chapter 3 ] . See also G. Salton, CACM 5 (1962), 103-114.
The concept of threaded trees is due to A. J. Perlis and C. Thornton, CACM 3 (1960), 195-204. Their paper also introduced the important idea of traversing trees in various orders, and gave numerous examples of algebraic manipulation algorithms. Unfortunately, this important paper was hastily prepared and it contains many misprints. The threaded lists of Perlis and Thornton actually were only "right-threaded trees" in our terminology; binary trees which are threaded in both directions were independently discovered by A. W. Holt, A Mathematical and Applied Investigation of Tree Structures (Thesis, U. of Pennsylvania, 1963). Postorder and preorder for the nodes of trees were called "normal along order" and "dual along order" by Z. Pawlak, Colloquium on the Foundation of Mathematics, etc. (Tihany, 1962, published by Akademiai Kiado, Budapest, 1965), 227-238. Preorder was called "subtree order" by Iverson and Johnson in the references cited above. Graphical ways to represent the connection between tree structures and corresponding linear notations were described by A. G. Oettinger, Proc. Harvard Symp. on Digital Computers and their Applications (April, 1961), 203-224.
The history of tree structures as mathematical entities, together with a bibliography of the subject, is reviewed in Section 2.3.4.6.
At the time this section was written, the most widespread knowledge about information structures was due to programmers' exposure to List processing systems, which have a very important part in this history. The first widely used system was IPL-V (a descendant of IPL-III, developed late in 1959); IPL-V is an interpretive system in which a programmer learns a machine-like language for List operations. At about the same time, FLPL (a set of FORTRAN sub-routines for List manipulation, also inspired by IPL but using subroutine calls instead of interpretive language) was developed by H. Gelernter and others. A third system, LISP, was designed by J. McCarthy, also in 1959. LISP is quite different from its predecessors: programs for it are expressed in mathematical functional notation combined with "conditional expressions" (see Chapter 8), then converted into a List representation. Many List processing systems have come into existence since then, of which the most prominent historically is J. Weizenbaum's SLIP; this is a set of subroutines for use in FORTRAN programs, operating on doubly linked Lists.
An article by Bobrow and Raphael, CACM 7 (1964), 231-240, may be read as a brief introduction to IPL-V, LISP, and SLIP, and it gives a comparison of these systems. An excellent introduction to LISP has been given by P. M. Woodward and D. P. Jenkins, Comp. J. 4 (1961), 47-53. See also the authors' discussions of their own systems, which are each articles of considerable historical importance: "An introduction to IPL-V" by A. Newell and F. M. Tonge, CACM 3 (1960), 205-211; "A FORTRAN-compiled List Processing Language" by H. Gelernter, J. R. Hansen, and C. L. Gerberich, JACM 7 (1960), 87-101; "Recursive functions of symbolic expressions and their computation by machine, I" by John McCarthy, CACM 3 (1960), 184-195; "Symmetric List Processor" by J. Weizenbaum, CACM 6 (1963), 524-544. The latter article includes a complete description of all of the algorithms used in SLIP. In recent years a number of books about these systems have also been written.
Several string manipulation systems have also appeared; these are primarily concerned with operations on variable-length strings of alphabetic information (looking for occurrences of certain substrings, etc.). Historically, the most important of these have been COMIT (V. H. Yngve, CACM 6 (1963), 83-84) and SNOBOL (D. J. Farber, R. E. Griswold, and I. P. Polonsky, JACM 11 (1964), 21-30). Although string manipulation systems have seen wide use and although they are primarily composed of algorithms such as we have seen in this chapter, they play a comparatively small role in the history of the techniques of information structure representation; users of these systems have largely been unconcerned about the details of the actual internal processes carried on by the computer. For a survey of string manipulation techniques, see S. E. Madnick, CACM 10 (1967), 420-424.
The IPL-V and FLPL systems for List-processing did not use either a garbage collection or a reference count technique for the problem of shared Lists; instead, each List was "owned" by one List and "borrowed" by all other Lists which referred to it, and a List was erased when its "owner" allowed it to be. Hence, the programmer was enjoined to make sure no List was still borrowing any Lists that were being erased. The reference counter technique for Lists was introduced by G. E. Collins, CACM 3 (1960), 655-657; see also the important sequel to this paper, CACM 9 (1966), 578-588. Garbage collection was first described in McCarthy's article cited above; see also CACM 7 (1964), 38, and an article by Cohen and Trilling, BIT 7 (1967), 22-30.
Unfortunately, too few people have realized that manipulation of links is not a magic, complex process that must be done by fancy List manipulation routines. There is still a widespread tendency to feel that the advantages of link manipulation can be obtained only by using a large List-processing system; actually, as we have seen in many examples throughout this chapter, it is quite easy to design linking algorithms which operate more efficiently than a general List-processing subroutine could possibly do. The author hopes that these detailed examples will help to convey a better-balanced attitude towards the use of structural links in data.
Dynamic storage allocation algorithms were in use several years before published information about them appeared. A very readable discussion is given by W. T. Comfort, CACM 7 (1964), 357-362 (an article written in 1961). The "boundary-tag' method, introduced in Section 2.5, was designed by the author in 1962 for use in a control program for the B5000 computer. The "buddy system" was first used by H. Markowitz in connection with the SIMSCRIPT programming system in 1963, and it was independently discovered and published by K. Knowlton, CACM 8 (1965), 623-625; see also CACM 9 (1966), 616-625. For further discussion of dynamic storage allocation, see the articles by Iliffe and Jodeit, Comp. J. 5 (1962), 200-209; Bailey, Barnett, and Burleson, CACM 7 (1964), 339-346; Berztiss, CACM 8 (1965), 512-513; and D. T. Ross, CACM 10 (1967), 481-492.
A general discussion of information structures and their relation to programming has been given by Mary d'Imperio, "Data Structures and their Representation in Storage," Annual Review of Automatic Programming 5 (Oxford: Pergamon Press), in press. This paper is also a valuable guide to the history of the topic, since it includes a detailed analysis of the structures used in connection with twelve List processing and string manipulation systems. See also the proceedings of two symposia, CACM 3 (1960), 183-234 and CACM 9 (1966), 567-643, for further historical details. (Several of the individual papers from these proceedings have already been cited above.)
An excellent annotated bibliography, which is primarily oriented towards applications to symbol manipulation and algebraic formula manipulation but which has numerous connections with the material of this chapter, has been compiled by Jean E. Sammet, Comput. Rev. 7 (July-August 1966), B1-B31.
in ACM Computing Reviews 9(01) January 1968 view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in [ACM] CACM 15(06) (June 1972) view details
in [ACM] CACM 15(06) (June 1972) view details
in [ACM] CACM 15(06) (June 1972) view details
in SIGPLAN Notices 12(08) August 1977 "Symposium on Artificial Intelligence and Programming Languages" view details
in SIGPLAN Notices 14(04) April 1979 including The first ACM SIGPLAN conference on History of programming languages (HOPL) Los Angeles, CA, June 1-3, 1978 view details
After introductory remarks, Jean Sammet, the Conference and Program Committee Chairman, introduces the keynote speaker and "the third programmer of the first large scale digital computer, Mark I," Capt. Grace Hopper of the US Navy. Capt. Hopper describes the very early history -- combining personal recollections and technical observations. It is an excellent historical talk, precisely establishing the milieu existing in the 1940s and early 50s, when the concept of using a computer to create programs was just emerging.
The FORTRAN presentation by John Backus emphasizes the importance of object efficiency for FORTRAN acceptance. He states that language design was never considered a problem; the real problem was to consistently produce object programs as efficient as hand-coded ones. The presentation captures the clear and unwavering focus of Backus's original team on that goal: a focus and dedication which characterized the direction of one of the most significant software projects in the history of computers.
The controversies in the committee designing ALGOL 60 are re-enacted in miniature on these tapes. Alan Perlis describes the American contributions, concluding that ALGOL has Influenced all languages since that time. "It's the mother's milk of us all." Peter Naur describes the European contributions and the origins of recursion in the language. A lively floor discussion involving John McCarthy, John Backus, and Fritz Bauer ensues. The Algol 60 committee got involved in "academic log rolling" according to McCarthy who also points out that the committee decision not to consider implementation led to a language which was not implementable as a whole. It was assumed that "everyone was a gentleman and none would propose something he didn't know how to implement. However there was no guarantee the combination was implementable."
The excerpt on the LISP lecture by John McCarthy emphasizes the features of the language and is an excellent description of its intellectual sources. Jean Sammet in presenting COBOL also clearly defines the influences on the language and how and why the choices were made in a series of committee meetings. These choices were very much colored by the decision to take "a short range composite approach good for at least a year or two."
The tapes show how differently some of these important languages developed. According to Douglas Ross, APT evolved out of application requirements; by contrast, the major features of JOVIAL were developed in a few minutes, relates Jules Schwartz, its sole designer. Geoffrey Gordon tells how GPSS also grew from feedback from application users. SIMULA, developed by Kristen Nygaard and Ole-Johan Dahl, didn't even start as a programming language. Charles Baker discusses the development of JOSS, and Thomas Kurtz, BASIC -- intended to make learning to program analogous to learning to drive a car: by doing it.
PL/I was the largest language represented at the conference. According to presenter, George Radin, much of the complexity and size is due to the necessity of defining the result of all operations on mixed types and to implicit typing. The excerpts of the presentations on SNOBOL by Ralph Griswold and APL by Kenneth Iverson establish the specific motivations for those languages: in both cases conserving human resources was considered very important.
The conference banquet tapes contain anecdotes by the conference speakers and by master of ceremonies Bernard Galler. These entertaining historical asides and footnotes sometimes give more insight into the how and why things happened than the more scholarly analyses. For example, George Radin's story about the PL/I committee's ordering pizza -- the pizza had everything anyone wanted -- says a great deal about how the committee functioned when designing the language.
These tapes constitute an important historical record. Unfortunately, the quality of the tapes is less than desired. They were not professionally produced and the picture quality is often quite poor. Still-photos by Robert McClure and Richard Wexelblat are used where the videotape is inadequate. However, the excerpts have been well selected by J.A.N. Lee, Jean Sammet, and Henry Tropp.
In his summary Fred Brooks says that "the best thing about this conference is the character set." He also points out that the presentations on the languages designed by a committee emphasized the process, whereas the presentations on single-author languages emphasized technical issues. These tapes capture the factors that have made the history: the personalities, the process, and the technology. They are interesting now and will be invaluable to future historians of the pioneering period of language development.
in ACM Computing Reviews March 1982 view details
It is a difficult book to review adequately. One must ask if it conveys the same message to that vast majority of information processing specialists who were not in the business at the time of the events recounted as it does to those of us who played an active role in some of the developments as they happened. Judicious inquiry of younger readers of the book suggests that rather more of the informal flavor comes through than one might suspect at first. In that sense the book "tells it like it was," although some of the text makes it quite clear that programming language designers have the same kind of selective and prismatic memories that other people have.
The plan of the book is straightforward. Thirteen specific languages were selected by the conference organizers, and the book contains, for each language: a formal paper; a transcript of the presentation; a transcript of remarks by a designated discussant; a transcript of a subsequent question and answer session; the full text of all questions submitted; a biography of the authors. In addition there is the full text of the Keynote Address presented by Captain Grace Murray Hopper, itself required reading, and a series of appendices, including summaries of each language.
As stated in the introductory material on the organization of the conference, the criteria for selection of the languages to be included were: "that the languages 1) were created and in use by 1967; 2) remain in use in 1977; and 3) have had considerable influence on the field of computing." The 1967 cutoff was to insure at least ten years perspective. The result of applying these criteria was:
ALGOL 60
APL
APT
BASIC
COBOL
FORTRAN
GPSS
JOSS
JOVIAL
LISP
PL/I
SIMULA
SNOBOL
This general review cannot pursue the specific language chapters; that is a task for individual reviews elsewhere in CR. Some overall comments are in order, however. The formal papers are not simply personal recollections of the authors. An organized procedure was established to guide each author in preparing an account according to established historical practice, thus maximizing the archival value of the papers. It appears to have worked, for the authors systematically -- and in some cases, apparently, painfully -- searched for old records, letters, and memoranda. The vignettes that surface therefrom are fascinating.
No one should be surprised that the accounts of the camel (designed by committee) languages, ALGOL 60 and COBOL, have a somewhat different flavor from the others. There is a gold mine for students of decision making processes in this book. The conference organizers are to be commended for providing two accounts of ALGOL 60, one from the American and one from the European point of view. The contrasting perceptions and the almost recursive discussion are both intriguing and delightful.
This reviewer's one regret is that it was impossible to capture and document the conversations that occurred over the coffee cups and in the corridors. In summary, this is a superb book, a must for all computer professionals. It is also one of the very few records of a conference of any sort where the reader gets a feeling for what it was like to actually be there. This reviewer was there and reading this book almost four years after the conference brought back delightful memories with preternatural clarity.
in ACM Computing Reviews March 1982 view details
Every once in a while, we get a unique glimpse of history from someone who helped shape it. Such is the case in John McCarthy's discussion of the early years in the life of LISP. LISP afficionadoes and students of programming languages will enjoy this article very much. It provides insight into the practical forces that gave birth to the main elements of LISP -- recursion, CAR, CDR, conditional expressions, garbage collection, and the LISP interpreter itself. Although it has been often misunderstood as a purely theoretical formalism, LISP has managed to remain a most effective programming language in the area of artificial intelligence.
Paul Abrahams' recollections about the early history of LISP also appear as the CD ... DR of this paper. As one of McCarthy's original six graduate students at MIT in the late 1950s, Abrahams gives additional insights into LISP and related languages of the time.
This article, as well as the rest of the book in which it appears, provides very interesting reading. It was revealing to this reader that LISP was born out of practical needs rather than a desire to create a wholly pure and perfect device for realizing recursive functions. Nevertheless, like ALGOL, LISP's practical usefulness may be overshadowed in the long run by its unique and lasting contributions to the theory of programming languages and data structures.
in ACM Computing Reviews March 1982 view details
The particular interests of the authors show in the variety of organization and emphasis found in the papers. John Backus describes the background of the FORTRAN project, some of the design decisions, the documentation and implementation. Alan Perlis emphasizes the many people involved in the ALGOL design, from before 1958, through the Zurich and Paris meetings, culminating in ALGOL 60. Peter Naur concentrates on the design decisions made between the Zurich and Paris meetings. The disagreements which surface in appendices to his paper make for fascinating reading. Kristen Nygaard describes the many changes which the design of SIMULA went through from 1961 through 1971, from SIMULA I to SIMULA 67.
The book is not a dry history -- many statements seem particularly surprising in hindsight. John Backus says of FORTRAN, "As far as we were aware, we simply made up the language as we went along. We did not regard language design as a difficult problem, merely a simple prelude to the real work of designing a compiler which could produce efficient programs." Jean Sammet stresses with regard to COBOL, "We were going to recommend a short range composite approach good for at least the next year or two."
The history of the technical decisions is particularly well researched and presented. Many ideas were taken directly from other languages, such as the separation of the data description and executable statements in COBOL, deriving from FLOW-MATIC. Some seemed to occur almost casually, such as Thomas Kurtz commenting on the design of BASIC, "Around 1960 or 1961, after a visit to the PDP-1 time-shared computer at MIT, I can clearly recall John McCarthy saying, 'Why don't you guys do time sharing?' Shortly afterward I said to Kemeny, 'I think we ought to do time sharing.' Kemeny responded, 'OK.' And that was that!" Other decisions stemmed from deadlocks, as Alan Perlis described, when a European member of the ALGOL committee declared "No! I will never use a period for a decimal point." The proposal from Joseph Wegstein for three levels of language calmed the situation. The ALGOL paper and appendices by Peter Naur present different views of the same experience. Even a project consisting of only two people can produce its share of excitement. Kristen Nygaard describes the shock of a switchboard operator at overhearing a violent argument between two men in a hallway. She was reassured that it was just Dahl and Nygaard discussing SIMULA.
One thing which emerges from many of the papers is the deep involvement which a language design can elicit from its designers. John Backus and Jean Sammet both describe many late, long hours.
But this book is not just a series of papers by knowledgeable authors. It is itself a history of the History of Programming Languages Conference held in Los Angeles in 1978. Jean Sammet, the General Chairman, describes how the conference was put together. There are many valuable ideas here for potential conference organizers. The Conference Historian, Henry Tropp, provides a historical perspective and suggests archiving of design papers. The keynote address is by Grace Hopper. Its transcript captures the qualities of innovation and humor which make her talks such an experience. The author talks are based on the papers, so there is much redundancy of material. The main value to be gained by the duplication is the opportunity to discover the human side of the authors, which comes out in the more informal relation to the audience. Jean Sammet brings down the house with her lament that students are not given more than a passing exposure to COBOL before they receive their degrees in computer science.
The question and answer sessions were often as interesting as the talks. The book gives John Backus's answer to the question why the letters I through N were chosen to designate integers. The readability of these sections attest to the effort which Richard Wexelblat put into the editing of this volume. The History of Languages represents a tremendous amount of effort from a great many people, and is a book which programmers as well as language designers will find both instructive and enjoyable.
in ACM Computing Reviews March 1982 view details
Time sharing made feasible the economic use of remote distributed terminals and opened up the possibilities of interactive computer use in schools. We had recently implemented TELCOMP, one of the new breed of high-level interactive programming languages. TELCOMP was a dialect of JOSS, the first "conversational" (i.e., interpretive) language, developed in 1962-63 by Cliff Shaw of the Rand Corporation; its syntax was similar to that of BASIC, which had not yet appeared. Like BASIC, TELCOMP was a FORTRAN-derived language originally designed for numerical computational applications. Shortly after TELCOMP was created, we decided to introduce it to children as a tool for teaching mathematics and in 1965-66, under U.S. Office of Education support, explored its use as an auxiliary resource in eight elementary and secondary schools served by the BBN time-sharing system. Students were introduced to TELCOMP and then worked on standard arithmetic, algebra, and trigonometry problems by writing TELCOMP programs. The project strongly confirmed our expectation that the use of interactive computation with a high-level interpretive language would be highly motivating to students. Extract: LOGO based on LISP
Incredibly, the best model for the new language (which was to be as simple as possible) turned out to be LISP, the lingua franca of artificial intelligence, often regarded (by non-LISP users) as one of the most difficult and formidable of languages. Of course, the syntax of Logo is much more familiar and accessible than that of LISP Essentially, though, Logo is LISP and is thus both an easy and a powerful language. The power is not evident in most existing microcomputer implementations, mainly because of their small memory and restricted performance.
External link: Onlne copy at the Atari Archives
in Ditlea, Steve (ed) "Digital Deli: The Comprehensive, User-Lovable Menu of Computer Lore, Culture, Lifestyles and Fancy by The Lunch Group & Guests" Workman Publishers: New York, 1984. view details
in SIGPLAN Notices 23(02) February 1988 view details
in SIGPLAN Notices 23(02) February 1988 view details
in SIGPLAN Notices 23(02) February 1988 view details
in SIGPLAN Notices 23(02) February 1988 view details
Resources
- comp.lang.lispx
" - HerberT STOYAN's Online Biography
external link - Herbert Stoyan's Online History
external link - Herbert Stoyan's Online Lisp resources
external link