Cover

Kazimir Majorinc

As Powerful as Possible

eval[e; a] = [atom[e] → assoc[e; a]; atom[car[e]] → [eq[car[e]; QUOTE] → cadr[e]; eq[car[e]; ATOM] → atom[eval[cadr[e]; a]]; eq[car[e]; EQ] → eq[eval[cadr[e]; a]; eval[caddr[e]; a]]; eq[car[e]; COND] → evcon[cdr[e]; a]; eq[car[e]; CAR] → car[eval[cadr[e]; a]]; eq[car[e]; CDR] → cdr[eval[cadr[e]; a]]; eq[car[e]; CONS] → cons[eval[cadr[e]; a]; eval[caddr[e]; a]]; T → eval[cons[assoc[car[e]; a]; cdr[e]]; a]]; eq[caar[e]; LABEL] → eval[cons[caddar[e]; cdr[e]]; cons[list[cadar[e]; car[e]]; a]]]; eq[caar[e]; LAMBDA] → eval[caddar[e]; append[pair[cadar[e];evlis[cdr[e];a]]; a]]]

Title

Kazimir Majorinc: As Powerfull As Possible Major ideas of Lisp in McCarthy’s period

Licence info

Multimedijalni institut ISBN 978-953-7372-28-6

CIP script is avialable in computer catalogue of National and University Library in Zagrebu with number 000910180. Zagreb, July 2015. This book is licensed under:

Creative Commons Attribution - NoDerivatives 4.0 international

licence.

Translated from Croatian into English by A. Müller and published online with written permission by the author of the work.

As Powerful as possible - Major ideas of Lisp in McCarthy’s period

7.1 Imperative and algebraic language -> 40 7.2 Basic types and commands -> 41 7.3 Subprograms and “functions” -> 43 7.4 Symbolic expressions -> 44 7.5 Attribute lists -> 45 7.6 Lists and representation of symbolic expressions -> 45 7.7 Functions for analys and synthesis of words and refferencing -> 48 7.8 Free memory manipulation -> 49 7.9 Basic operations on whole lists -> 50 7.10 Function maplist

Elements of functional programming -> 53

8.1 New function maplist -> 54 8.2 McCarthy’s lambda expressions -> 55 8.3 Language simplification -> 58 8.4 Recursive function implementation -> 60 8.5 Functional and Imperative style -> 60 8.6 Non-definability of list function -> 61 8.7 Substitution functions and function apply -> 62 8.8 Help functions and apply implementation -> 63 8.9 Automated memory control -> 66 8.10 Rochester’s lambda expressions -> 66 8.11 Programs forming -> 67 8.12 Functional compositions of car and cdr -> 67 8.13 Function compute -> 67

Pure Lisp -> 68

9.1 Mathematical expressions -> 72 9.2 Conditional expressions -> 72 9.3 Recursive and mutually recursive defined functions -> 73 9.4 Lambda-expressions -> 74 9.5 Label expressions -> 75 9.6 Free and bound variables -> 76 9.7 Remark on mutually recursive functions -> 77 9.8 Definition of symbolic expressions -> 77 9.9 Differences with earlier definitions -> 78 9.10 Meta-expressions -> 80 9.11 S-functions -> 80 9.12 Elementary S-functions -> 81 9.13 Remarks on McCarthy’s definition of S-functions -> 83 9.14 Examples of non-elementary S-functions -> 85 9.15 Abbreviation and function list -> 89

9.16 Functions as arguments to functions -> 89 9.17 Remark on elimination (mozda removal) of acronyms and non-elementary S-functions -> 90 9.18 Translation of M-expressions into S-expressions -> 92 9.19 Remark on M-expressions translation -> 95 9.20 Mathematical definition of S-function eval -> 97 9.21 The S-function eval -> 101 9.22 Remarks for definition of eval function -> 103 9.23 The Universal S-function apply -> 105 9.24 An Interpreter for Lisp -> 106 9.25 S-functions and computability theory -> 107 9.26 Simulation of Turing machines with S-function -> 108 9.27 Questions about S-functions not decidable with S-function -> 114

9.28 Programs as S-functions -> 116 9.29 Representing symbolic expressions in computer memory -> 117 9.30 Differences between symbolic expressions and list structure -> 118 9.31 Garbage collection -> 119

10 Linear Lisp -> 121 10.1 L-Expressions -> 122 10.2 Elementary functions -> 123 10.3 Factorization of subexpressions -> 124

Binary Lisp -> 125
Slagle’s language for symbol manipulation -> 127
Symbolic expressions as a language syntax -> 129
Fortran-like commands, the function program, the power of multiparadigmatism of Lisp -> 132

14.1 Coding of machine state and fortran-like commands -> 133 14.2 The S-function program -> 134

14.3 Simultaneous execution of fortran-like commands and symbol ordering -> 135 14.5 The power of the language from programmer’s perspective -> 137

Woodward-Jenkins arithmetics -> 139
Lisp 1.5 -> 142

16.1 Pure Lisp -> 144 16.2 Using property lists -> 147 16.3 Pseudo-functions -> 149 16.4 Special forms -> 151 16.5 Fexprs -> 151 16.6 Programs in Lisp -> 153 16.7 Functional arguments -> 155 16.8 Special operator prog -> 158 16.9 Gensym and oblist -> 159 16.10 Symbols T, ** T ** and NIL -> 161 16.11 Arithmetics -> 162 16.12 Fields (Clojures???)-> 163 16.13 Logic -> 163

Mathematical theory of computation -> 165

17.1 Functions defined by basic functions -> 167 17.2 Functionals -> 167 17.3 Removability of label-expressions -> 168 17.4 Conditional expressions are not functions -> 171 17.5 Non-computable functions -> 171 17.6 Multivalued functions -> 172 17.7 Recursive definition for sets of symbolic expressions -> 172 17.8 Recursive induction -> 173 17.9 Abstract syntax of programming languages -> 174 17.10 Semantics -> 176

Gilmor’s lisp-like language -> 178

18.1 Conditional expressions -> 179 18.2 Quote and label -> 179 18.3 Abstract machine -> 180

Memoization -> 182
New function eval -> 186

20.1 Augmented Lisp -> 187 20.2 New eval -> 188 20.3 Anonymous lambda and label -> 189

First implementations of Lisp -> 190
Images -> 195

Bibliography -> 196

1. Introduction

“In developing LISP our first goal is to describe a language which is as powerful as possible from the point of view of the programmer.”^1

Most programmers meet Lisp for the first time through some of the many quotes and aphorisms which, sometimes exaggerated, emphasize beauty, elegance and power of the language. Thus, for example, understanding of Lisp is called enlightenment; it is claimed that experience with Lisp programming makes a programmer a better programmer, even if one will never use Lisp in their entire life. The language is, as a joke of course, prescribed mystycal attributes; god (or gods) have written the universe in Lisp, and the Lisp community is described as a cult.

If a programmer decides to study Lisp, he will probably conclude that Lisp is a surprisingly powerful, but also an equally surprisingly simple programming language. Power is less questionable; if a language designer wishes to create a powerful language and invests enough time and effort, it is hard not to succeed. Simplicity is strange; it leaves the impression that Lisp is discovered and not created. A similar impression was left on members of the ARTIFICAL INTELLIGENCE project at U.S. MIT, who developed Lisp, imaginged as powerful, but practical and very complex language. To the contrary on what might be expected, Lisp was becoming simpler and simpler during the development. It was when the main designer, John McCarthy, wrote an article which introduced Lisp to the public that the project members recognized Lisp as “the subject of beauty” and worth studying for its own sake.

In the following decades, some members of the Lisp community have tried to make the language more general, more powerful, and simpler by a more accurate description of the ways in which programmers think. Other numerous attempts at advancements were driven by the desire to make the language more efficient, practical, popular, and even profitable. Even when compromises were made, designers have tried to identify, keep and perhaps also improve important qualities of the language. Lisp influenced other programming languages. To a lesser degree, other programming languages had influence on Lisp. Different motives, priorities and solutions have led to dissolution and framgentation of the community and to the development of numerous, quite different dialects, and communities gathered around those dialects.

In the context of a fragmented community and the existence of numerous interpretations of main ideas, if one wishes to understand Lisp, it is hard to avoid a historical approach, by the studying the ideas in the form they had when they evolved. As a rule, the most interesting period is the earliest one. This book tries to expose the evolution and development of Lisp’s main ideas during the first few years in which John McCarthy has led the language’s development.

There has already been efforts to systematically present main ideas in early period of Lisp. John McCarthy himself has given several presentations and has written several articles on the subject. Early Lisp history is more thoroghly explored by Herbert Stoyan. Beside Stoyans book Lisp, Anwendungsgebiete, Grundbegriffe, Gechichte from 1980, published only in German language and today hardly avaialable, all works about Lisp history are written in a form that assumes good Lisp familiarity. This book is written to be understandable by any programmer with little experience in any specific programming language.

During the writing of the manuscript for this book, the author has held several presentations in Hacklab Mama in Zagreb. Discussions with the Hacklab members had lots of influence on content and form of this book.

In original documents, the name Lisp was usually written in capitalized letters: LISP. In this book, the currently common and more practical form, Lisp is used. The original way of writing is kept only in quotes.

1 McCarthy, Programs in Lisp, AIM-012, 1959, p. 4

2 Early influences on McCarthy

Hundreds of people have participated in development of Lisp. Yet, for the author of the language is unqestionably considered an American, John McCarthy (1927-2011), a researcher of artificial intelligence. Lisp, the programming language suitable for solving problems in field of artificial intelligence, is one McCarthy’s first projects.

2.1 TECHNOLOGICAL ENTHUSIASM

McCarthy is often considered a visionary^2, a man whose work looks toward the future. Amongs many projects, he also wrote and maintened web pages with futuristic themes.^3

His scientific and life interests, McCarthy considered as consequences of the fostering. Mother Ida and father Jack were communist activists who back then had strong belief in the science, technology and unstoppable progress of humankind. The children red popular scientific literature from the soviet and McCarthy especially liked a book by Mikhail Ilina, 100 000 Whys.^4 Political views, as well as the confidence in the science, the parents managed to successfully transfer over to John. McCarthy also noticed similar interests amongst other children fostered in communist families. McCarthy considered himself a “radical optimist:” he believed that outcome will be successful even if people don’t listen to his advices.^5

2.2 FINITE AUTOMATA AND EXPLICIT FACT REPRESENTATIONS

McCarthy was an exceptionally good student. Hi went out high school two years earlier then expected. He started mathematical studies 1944 by entering the third year courses, but he was expelled from the university because of him skipping the physical education classes. After shorter break he was anyway allowed to continue the studies.^6

Conference Hixon Symposium for Cerebral Mechanisms in Behaviour in Pasadena, 1948., especially presentation by John von Neumann about automatons that could replicate, mutate and evolve, intrigued McCarthy about artificial intelligence.^8,9

McCarthy’s first important idea is representation of an intelligent actor and its environment with finite automata. Despite von Neumanns recommendation to publish his ideas, McCarthy refuses because of impossibility to represent facts about the environment in finite automata.^10 Until the end of his studies he researched partial differential equations. Between 1951 and 1958 he changed several different jobs, mainly in higher education institutions.

The second important idea, McCarthy developed 1952. Problems are, he presumed, decided by a function that tests problems solution. Then we can find solution for a problem by applying inverse of that function.^11 McCarthy published a paper, but he faced same problems as with the previous idea.^12 Shortly and for the last time he returns to differential equations.

First failures ascertained McCarthy that intelligent automata must process explicit representations of facts.^13 That insight is basic for later McCarthy’s work, “the logic of artificial intelligence” and clear inspiration for the development of Lisp.

2.3 DIGITAL COMPUTERS AS INTELLIGENT AUTOMATON

Digital computers can imitate all automatons with finite number of states. If intelligent machines are even possible, it will certainly be digital computers equipped with appropriate programs. This idea today seems like an unnecessary trivialitet, but for the very first researchers it wasn’t selfevident. Alan Turing started to represent that idea 1947.,^14 but he published it first 1950.^15 McCarthy came to same conclusion summer 1955., while working in IBM’s center in Poughkeepsie under leadership by Nathaniel Rochester, the constructor of the personal computer.

2 Lord, John McCarthy has passed, 2011 3 McCarthy, Progress and its sustainability, 1995 4 Shasha & Lazere, Out of their minds …, 1995, p23. 5 McCarthy Susan, What your dentist doesn’t want you to know, 2012 6 Nilsson, John McCarthy, 1927-2011, 2012, p3. 7 von Neumann, The general and logical theory of automata, 1951. 8 McCarthy, The logic and philosophy of artificial intelligence, 1988., p3. 9 “Q. What is artificial intelligence? A. It is the science and engineering of making intelligent machines, especially intelligent computer programs.” McCarthy, What is Artificial Intelligence?, 2007., p2. 10 “It considered a brain as a finite automaton connected to an environment also considered as an automaton. To represent the fact that the brain is uncertain about the environment is like, I considered an ensemble (i.e. a set with probabilities) of environment automata. Information theory applied to this ensemble permitted defining an entropy at time 0 when the brain was first attached to the environment and later when the system had run for a while and the state of the brain was partially dependent on which environment from the ensemble had been chosen.The difference of these entropies measured how much the brain had learned about the environment.” McCarthy, The logic and philosophy of artificial intelligence, 1888., p2 11 McCarthy, The inversion of functions defined by Turing machines, 1956., p177 12 McCarthy, The logic and philosophy of artificial intelligence, 1988., p3 13 “McCarthy thought that even if the ‘brain automaton’ could be made to act intelligently, it’s internal structure wouldn’t be an explicit representation of human knowledge. He thought that somehow brains did explicitly represent and reason about ‘knowledge’, and that’s what he wanted computers to be able to do.” Nielsson, John McCarthy 1927-2011., p4 14 Turing, Lecture to the London Mathematical Society on 20 February 1947. 15 Turing, Computing machinery and intelligence, 1950 16 McCarthy, The philosophy of AI and AI philosophy, 2008., p713

3. Darthmouth Project

McCarthy, then employed at Dahrmounth College, his acquaintance from the studies and inventor of “neural nets” Marvin Minsky, Rochester, founder of the information theory Claude Shannon and unsigned Oliver Selfridge^17, wrote in August 1955. “A Proposal for the Dartmouth summer research project on artificial intelligence” and send it to a possible financier. Attractive and pretencious, previously almost unused fraze “artificial intelligence” which was coined by McCarthy^19 was soon accepted as a name for the entire field of computer technology.

3.1 LANGUAGE OF THE INTELLIGENT COMPUTERS

Proponents belived a computer can imitate every aspect of human intelligence and anounced attempts of solving many hard problems. They even anounced particular interests and plans. McCarthy belived it was necessary for the development of intelligent machines to apply standard methods of trial and error on “higher level of abstraction”. Just like humans use language for solving complex problems by making propositions and trying them, so would intelligent machines do as well. He intended to develop a language suitable for such use.^30 Already developed languages were easy to describe with informal mathematic and informal mathematic was easily translated into those languages, and it was also easy to test for correctness of the proof. The language of intelligent machines should also have some advantages of natural languages: be concisive, universality (in a natural language it is possible to define and adequately use any language), selfreferencing and propositional expression.

Probably from that period, there is a preserved short, undated McCarthy’s manuscript The programming problem which contains almost identical ideas, but also points out that language should be explicit: there should not be possibility for different interpretations of a procedure’s meaning.^21

Lisp can be viewed as an attempt to realize McCarthy’s ambition from 1955.

3.2 IN-BETWEEN IPL AND FORTRAN

The summer project was accepted and realized next, 1956. year. Despite participation of tenth of most famous researchers, expected breakthroughs were not achieved. Reasons of relative unsuccess were later explained by McCarthy with shortage of financial means, poor colaboration between researchers who hold to their own projects and difficultness of the problem which propponents underestimated. Minsky presented an idea for a geometry theorem solver. Ray Solomonoff started work on algorithmic complexity and Alex Bernstein presented a chess program. Instead of a work on the language, McCarthy presented “alfa-beta heuristic” for games like chess.^22

Despite not developing the announced language, McCarthy acquainted himself with work of Allen Newell, Cliff Shaw and Herbert Simon who prestened program LOGIC THEORIST (LT) written in INFORMATION PROCESSING LANGUAGE (IPL).^33 IPL supported single linked lists and recursions. Commands were calls to subprograms and could not be directly composited. McCarthy felt back then a need, even a passion, for “algebraic language” in which expressions would be written as in mathematic or Fortran, but which, like IPL, would make lists processing and recursion possible. Such language would significantly simplify expression analysis and subexpression refactoring compared to IPL.^34

17 McCarthy, The logic and philosophy of artificial intelligence, 1988. p3. 18 “Do not develop your artificial intelligence, but develop that intelligence which is from God. From the latter results virtue; from the former, cunning.” Giles, Cuhang Tzu - mystic, moralist and social reformer, 1889. p232. 19 Andresen, John McCarthy: father of AI, 2003, p84. 20 McCarthy et al.,/A proposal …/, 1955., p10. 21 Stoyan, Early LISP History (1956-59), 1984. p.300. 22 McCarthy, Dartmouth and beyond, 2006 23 Newell & Shaw, Programing the Logic Theory Machine, 1957 24 McCarthy, History of LISP, 1981., p. 174

4. FLPL

Barely a half year later, McCarthy was offered opportunity to participate in creation of a language he wanted. Early 1957. Rochester started project GEOMETRY THEOREM MACHINE after the mentioned idea by Minsky. Head of the project was Herbert Gelernter, and McCarthy was a consultant. McCarthy suggested^25 to use Fortran, developed for numerical computations, but also considered as usable for logical computations, instead of planned IPL for the IBM 704 computer.^26 “Function call nesting” makes it possible to describe very complex operations on numbers in one command in Fortran. Gelernter and McCarthy attribute to themselves discovery that even lists could be processed in the same way.^27,28 Fortran augmented by numerous special functions was considered a new language and was named “FORTRAN-compiled list-processing language” - FLPL. McCarthy worked on the project until fall 1958.

4.1 OPERATIONS ON WORDS

Memory in IBM 704 computer is divided in words (“registers”), each 36 bits in size. Bits are divided in groups named by their usual use in machine language; prefix holds bits S, 1 and 2; decrement holds bits 3-17; tag holds bits 18-20; and finally, address holds bits 21-35.^29

IMAGE 1. Graphical representation of a word in IBM 704 computer.

Some of functions defined in FLPL extracted parts of words. For example, if j is address of a word in computer memory, then calls to functions XCPRF(/j/), XCDRF(/j/), XCTRF(/j/) and XCARF(/j/) returned value contained in respective parts of the word at address j: prefix, decrement, tag, address; in order. Some functions were defined as compositions of functions XCDR and XCAR. For example, XCDADF(/j/) is equivalent XCDRF(XCARF(XCDRF(/j/))).

Other functions were, conversely, writing values into words. For example, callling functions XSTORAF(/j/, /k/) and XSTORDF(/j/, /k/) wrote value k into address part or the decrement part of the word at adress j.

4.2 LISTS

Support for list processing in FLPL was adaptation of list support from IPL for IMB 704 computer. FLPL authors talk about ”NSS memory” and ”NSS lists”,^30 where NSS are initials of Newell, Simone and Shaw, the authors of IPL. List processing is reduced to processing individual words in memory.

Lists in FLPL were made of simple ”list elements”. Relative long word length in IBM 704 made it possible to represent list elements in a single computer word. In address part is address of data in memory. In decrement part is address of next list element or 0 - if next element does not exists.

IMAGE 2. A list element.

List elements are as a rule not stored in the memory consecutively.

IMAGE 3. List (0.71412, 2.71828, 3.141259) at adress 1001.

Because of the optimisation, data that fits in fifteen bits can be stored directly into adress part of the word. In FLPL, lists are just abstraction used by programmers, not a special type of data. Functions for processing lists take as argument address of the first element in the list.

Such represented lists are flexible, of varying lenghts and make it possible to quckly insert and remove data. On the other side, it is not possible to directly access, for example, a hundredth piece of data in a list, but that data has to be accessed stepwise, in hundred steps.

4.3 LIST CREATION

Free memory at the start of a program execution is stored in a special, intern list lavst (list of avialable storage). From lavst comes words needed for list creation and words longer not needed for the program execution are stored there.

Most important function for list creation is XLWORDF. For example, call to function XLWORDF(1,2,3,5) removes word from lavst, writes 1,2,3 and 5 in respective parts (prefix, decrement, address and tag respectively), and also returns, as a value, address for that word. There were other, similar functions. XLWORDF could be, as a function, composed with other functions, which at the time wasn’t an obvious idea.^31

Particularly, elements of a list can contain, as data, also other lists. That gives rise to complex list structures - name taken from IPL. For example, expression

XLWORDF(1,XLWORDF(2,3),4,XLWORDF(5,6))

would during computation create a list structure and return it as a result.

Since the “address part” of a list element contains address of data, it was possible for multiple different lists to contain same data. That useful possibility makes certain operations on lists more complex. For example, if we wish to remove a data from a list, it is not clear if the memory occupied by that data could be freed, since it is possible that same data is still contained in some other list. The solution applied in FLPL is introduction of a kind of ownership over data. If first bit of a list element is 1, then when list element is erased, data is erased as well. If first bit contains 0, then data is “borrowed” and erasing the list element does not erase the data itself.

IMAGE 4. Two list elements containing same data. The lower list element “borrows” the data.

Taking care of the previous, call to function XERASEF(/j/) erases list element at adress j, a call to function XTOERAF(/j/) erases entire list at address j; respective data is erased as well - if so is decided by value of bit 1.

Example FLPL program is a program that tests membership in a list.^32

FUNCTION MEMBER(X, L) LI=L 1 IF LI=0 2, 4, 2 2 EL=XCARF(LI) IF EL=X 3, 5, 3 3 LI=XCDRF(LI) GOTO 1 4 MEMBER=0 GOTO 6 5 MEMBER=1 6 RETURN END

FLPL didn’t support recursive functions. Language authors belived that recursion could be emulated by storing intermediate results in lists or even by letting calling function modificate the caller program^33, but during the writing of GEOMETRY THEOREM MACHINE there were no needs for that.

Similarity between processed expressions and lists themselves were also observed, but it is not clear if that similarity was somehow exploited by the language authors^34.

McCarthy tried during the summer 1958. without success, to write a progam for expression differenciation in FLPL. Besides the lack of support for recursion^35, he was also bothered with clumpsy branching of the program execution, for which early Fortran is well-known for today. Since Gelernters group was satisfied with FLPL, McCarthy concluded that he has to develop a new language^36. Many elements from FLPL found its place in Lisp.

25 Gelernter et al., A Fortran-compiled list-processing language, 1960., p.88. 26 Backus et al., The Fortran − automatic coding system for the IBM 704, 1956., p.2. 27 Gelertner et al., A Fortran-compiled list-processing language, 1960., p.88. 28 McCarthy, /An algebraic language …/, AIM 001, 1958., p.3. 29 704 electronic data-processing machine − manual of operation, IBM, New York, 1955. 30 Gelernter et al, A Fortran-compiled list processing language, 1959., p. 37-1-2. 31 McCarthy, The logic and philosophy of AI, 1988., p. 4. 32 Stoyan, List processing, 1992., p. 151. 33 McCarthy, History of Lisp, 1981., p. 189. 34 “The authors have since discovered a further substantial advantage of an algebraic list-processing language … It is the close analogy that exists between the pucture of an NSS list and a certain class of algebraic expressions that may be written within the language.” Gelernter et al., A Fortran-compiled list-processing language, 1959., p. 37-3. 35 “If FORTRAN had allowed recursion, I would have gone ahead using FLPL. I even explored the question of how one might add recursion to FORTRAN. But it was much too kludgy.” Shasha & Lazere, Out of their minds …, 1998., p. 27 36 McCarthy, History of Lisp, 1981., p. 176.

5. A proposal for a compiler

After the Summer project, McCarthy took a job at MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT). By the end of 1957., after initial experiences with FLPL, he send an about twenty pages long memorandum, A proposal for a compiler, to the head of the computer centre. Suggested compiler was very ambitious, interesting and full of possibilities. Still, it didn’t posses the unique conceptuality nor elegance which Lisp, particularly “pure Lisp”, will have.

In some parts of the Proposal, McCarthy’s reasoning is abstract and maybe not very precise. The development of the language was, seemengly, soon stopped. Announced continuations for A Proposal for a compiler was never written.

5.1 PROGRAMMING LANGUAGE AS A COORDINATE SYSTEM

McCarthy again asks what is a good programming language. According to thoughts in Proposal from Dartmouth project, a programming language has to be a combination of a natural and a mathematical language. Natural language alone is not precise enough, and the existing mathematical language expresses declarative instead of necessary imperative expressions and does not make defining possible. Natural language is used for defining.

Programming language can, according to McCarthy, be seen as a coordinating system. A program is defined by a combination of “variables”, where variables are not symbols with values, as normally used in programming languages, but different “attributes” or “aspects” of a program, possibly so that desired changes in a program can be achieved by changing as few number of variables as possible. For example, for McCarthy are typographical conventions and language commands themselves variables. There are four kind of variables:

system variables, whose values can’t be changed by either the programmer or the program, but are changed if the programming system is changed.
program variables, whose values are defined by a programmer, but which can not be changed during the computation
program segment variables, whose values can be different in different parts of a program and
computation variables, which change their values during the execution of a program.

System becomes more powerful if variables become easier to change. For example, “typographical conventions” and even statements themselves should be “computation variables”, i.e. can be changed during the program execution^37.

5.2 PROGRAMMERS FREEDOM

Most important property of suggested language is, according to McCarthy himself, programmers freedom to define new statements^38. Equivalence statements would make it possible to introduce abbreviations for any expression. The compiler could be changed and augmented by statements from the compiled program. Announced are also elements of declarative programming^39. Programs could generate and compile other programs and change the compiler code, written in same language. Especially, they could compile interpreters, and then generate code executed by those interpreters.

5.3 LOGIC VALUES AND FUNCTIONS

Suggested language would support logical values (in original called propositional values) 0 and 1 and usual propositional operators, including implication and exclusive disjunction. For example, expressions like following would be possible:

P = Q AND ((A = B) OR P).

5.4 FUNCTION IF

Important innovation is function IF, more comfortable to work with than the same named function in Fortran. For example, expression

A = IF(P, X+Y: Q, U+V: (A=B), A+B: OTHERWISE, B)

is equivalent to a command in contemporary pseudocode

A = if P then X + Y else if Q then U + V else if A = B then A + B else B

Also, it is equivalent to some later conditional expressions in Lisp.

5.5 SYNTAX

The syntax for the suggested language is unusual and interesting, despite being just roughly outlined. Characterizing is the porgram division in two to four columns. For example, progam

X | Y Y | X

represented “parallel” command for assignmenet and it would have changed values of variables X and Y without use of common, third, intermediate variable. The program in a modern pseudocode

for j in L do if B[ j ] > 0 then A[B[ j ]+C[ j ]] := R[ j ] · S[ j ] end.

would be written in the suggested language as

Quantifier Quantity Condition Value

j ∈ L | A(B(J)+C(J)) | B(J)>0 | R(J)*S(J).

5.6 LISTS

The langue would also support algebraic expressions, logic values and operations, “short-curcuit” calculations and single-linked lists, as known in FLPL. In the document is also a first graphical representation of lists:

IMAGE 5. Graphical view of a list.^40

Defined are also functions for extracting parts of words, like in FLPL, but with simplified names like CAR and CDR.

5.7 MULTIVALUED FUNCTIONS AND FUNCTION COMPOSITION

Beside unusual syntax, a special for the suggestion is support for multivalued functions. Division with rest is probably the simplest example of a need for such function. Defined was also functional composition, with same notation as in mathematics. Description of those possibilities in the suggestion is pretty brief, but examples are illustrative enough.

Function PI reassigns it’s own arguments. For example, values

(PI(1,2,2,3))(X,Y,Z)

are values X,Y,Y and Z respective. Function PI is useful for writing expressions involving functions with multiple values. Same is true for function I1, an identity function of one variable and one value.

For example, let Q(A,B,C) be a function with two values: solutions of the quadratic equality A·X^2 + B·X + C. Let PLUS be a function that adds arbitrary number of arguments. Expression that computes sum of both solutions for equality A·x^2 + B·x + C and coeficients A and C could be

(PLUS ○ (Q,I1,I1) ○ PI(1,2,3,1,3))(A,B,C).

McCarthy didn’t try to explain how such function would be useful and he never returned to the idea of multivalued functions.

37 “The statements themselves … are computational variables here since the program can generate source language program in the course of operation and can call in the compiler to compile it.” McCarthy, A proposal for a compiler, 1957., p. 4. 38 “The most important feature of the source language of this system is the freedom it gives the programmer to define new ways of expressing himself.” McCarthy, A proposal for a compiler, 1957., p. 4. 39 “The ability to describe a computation by giving final state of the machine in terms of the initial state without haying to worry about intermediate changes to the variabless used in the computation.” McCarthy, A proposal for a compiler, 1957., p. 5. 40 After illustration from McCarthy, A proposal for a compiler, 1957., p. 15.

6. Suggestion for a programing language

Within a framework of interntational initiative for creation of a “universal programming language” which later gave birth to programming language Algol, american Association for Computing Machinery (ACM), founded Ad hoc comittee for programming languages in the beginning of 1958. The committee decided that the new language has to be higher, “algebraic programming language.” Fortran already satisfied that requirement, but as intellectual property of IBM, it wasn’t acceptable. A sub-comittee whose members, besides McCarthy, a MIT representant, were also authors of then current programming languages John Backus, Alen Perlis and William Turanski, put together a Suggestion for a programming language, the starting point for ACM delegation on meeting in Zürich, in summer 1958.^41 A suggestion for programming language was not remarkably ambitious as the year older A suggestion for a compiler, but it contained a few important ideas.

6.1 CONDITIONAL STATEMENT

Instead of clumpsy conditionall branch in Fortran, conditional statement had form

p1 → e1, p2 → e2, …, pn → en

where p1, …, pn are logical expressions, and e1, …, en are any statements and it was executed so that p1, …, pn are computed until first true-valued statement pi was found. Then the corresponding ei statement was executed.

Here, for the difference from Suggested compiler, the conditional statement is not an expression.

6.2 GO TO STATEMENT

Statements could have names. Names where symbols, series of signs that starts with a letter. For example, TR is a name for statement

(TR) X = 2 + 2.

Very expressful statement was

GO TO e

“Designation statement” e could have several forms. Most simply, it could be used as a label in a program. For example

GO TO TR.

It could also have form s(I), where s is a symbol, and I is an expression that computes a number. For example, if there is a “declarative statement” in a program

SWITCH Q(A, B, C, D, E)

then after

GO TO Q(2+2)

the program execution continues from the statement with name D. Finally, a statement e could have form (c) where c is a kind of conditional branch, as an example,

GO TO (D<0 -> NOSOLUTIONS, D=0 -> ONESOLUTION, D>0 -> TWOSOLUTIONS).

6.3 MACRO STATEMENT

Suggested was also a kind of a macro statement. For example, executing statement

LABEL P(A, B)

a part of program between statemetns marked with names A and B becomes value P. Then statement

P(L1 -> X, L2 -> Y)

executes a part of program P, but with temporary substitution of symbols X and Y with symbols L1 and L2.

McCarthy wasn’t present at meeting in Zürich, but in final language form, today known as Algol 58, were included some of viewed suggestions. Accepted was conditional GO TO, but functionality of LABEL statement was transfered to another statement. McCarthy’s belowed^42 conditional statements were not accepted.

During May 1958., McCarthy held a talk at MIT under the name An algebraic coding system at which time, according to note by a student Jamer R. Slagle, he talked about augmenting Fortran with Churchs lambda statements, function compositions and multivalued funcionts^41.

In summer 1958., in a letter to Perlis and Turanski, McCarthy suggests changes to the Suggestion. The changes were important and far-reaching. The biggest challenge in designing the new language should be “possibility to change the language from within the language itself”^43. An intermediate language should be introduced in prefix form. Entire program should be an expression of intermediate languages^44.

6.4 HIGHER ORDER FUNCTIONS

Name of functions should be variables, so that it is possible, for example, to write

f = sin g = f + cos a = g(3).

Suggested is process of defining higher order functions; addition, substraction, multiplication and division of arithmetic functions, differenciation and integration as well as possibility to define other higher order functions. Especially, introduced was composition, so that for example,

(f ○ g)(x) = f(g(x)).

6.5 LAMBDA-STATEMENTS

McCarthy points out that expressions in elementary mathematics, for example x + y sometimes denote a value, and sometimes a function. In a programming language such ambiguity has to be avoided, so McCarthy, maybe for the first time in the history of programming languages^45, suggests introduction of Churchs lambda notation. For example, statement

lamda(x, y)(x + y)

denotes the function

(x,y) -> x + y.

Such defined functions would be applied to numbers, but also to other “forms”. For example, statement

lambda(x, y)(x + y)(3, 4)

would be computed to number 7, and statement

lambda(x, y)(x + y)(a + 1, b)

into expression (a + 1) + b. Basic operations on forms should also be supported.

McCarthy has, in lesser grade, continued to participate in Algol development, suggesting some ideas which he already applied in Lisp^46.

41 Perlis, The American side of the development of ALGOL, 1981., p. 77. 42 Stoyan, Early LISP history (1956-59), 1984., p. 300. 43 McCarthy, Some proposals for the Volume 2 (V2) language, 1958., p. 1. 44 Stoyan, Early LISP history (1956-59), 1984., p. 303. 45 Stoyan, Early history of LISP (1956-59), 1984., sl. 22. 46 McCarthy, On conditional expressions and recursive functions, 1959.

7 Imperative Lisp

McCarthy and Minsky, then employed at american MIT, started in September 1958.^47 a work on project ARTIFICAL INTELLIGENCE. The work was relatively well documented with numerous articles and presented at conferences and in intern documents, Artifical Intelligence Memo (AIM), Research Laboratory of Electronic, Quaterly progress report (RLE QPR) and by student works. “The Uncle”^48,49, McCarthy was, following the examples of projects LOGIC THEORY MACHINE - IPL and GEOMETRY THEOREM MACHINE - FLPL, intended to develop an “expert system”, ADVICE TAKER^50, and a programming language for “manipulation with symbolic expressions” in which the system would be written^51. After the presentation to the public, despite McCarthy not abandoning the ADVICE TAKER, the work died out and is barely mention in numerous intern and published documents^53,54. The programming language, was on contrary, intensely developed.

In the beginning described just as ”an algebraic language for the manipulation of symbolic expressions“^55 and ”symbol manipulating language“^56, the language soon got name “LISP (List Processer)”^57, and somewhat later, “LISP (List Proces- /sor)”^58. Sometimes the name “List Processing Language” was also used. Association of name LISP and “List Processer” has soon weakened, and thus sometimes is written that name LISP comes from ”List processing“^60 and even term ”LISP Processor” is used^61. The name of the language was mainly written with capital letters, but McCarthy sometimes used, today more usual form, “Lisp”^62.

John McCarthy is considered the author of the language^63. Members of the project were first “hackers” which worked “in atmosphere … of unlimited ambition and enthusiasm”^65. McCarthy didn’t prohibited other members of the project from including their own ideas in the language^66. Steven “Slug” B. Russell, was the “compiler”^67: he would personally translate McCarthy’s Lisp programs into assembly, he developed the interpreter and took part in design of the language. Robert Brayton and David C. Luckham^68 were first students who worked on the project, and successfuly wrote the first compiler in assembler. David M. R. Park helped in writing the compiler and such contributed to desing of the language^69, as well as Rochester^70, then part-time employed at MIT. Klim Maling wrote a compiler in Lisp. Daniel J. Edwards wrote the first “garbage collector”. Phylllis Fox wrote Lisp I. the manual. First users were Rochester, Slagle, Paul W. Abrahams, Louis Hodes, Seymor Z. Rubentein and Solomon H. Goldberg. Finally, Minsky, Dean Arden, Shannon, Hartley Rogers, Roland silver and Alan Tritter were interested observers and commentators^71.

First draft of the language was written in September 1958. Followed was gradual, continuous developmnet and big number of changes until November^72 1962. when McCarthy leaves for Stanford university because of disagreement with supervisers about development of the “time sharing”^73. Only sidestep from the continuty was “pure Lisp”, a subset of really implemented Lisp which McCarthy wrote in spring 1959. for the purpose of presenting the basic principles of the language. Despite McCarthy’s wish to continue to lead Lisp development^74, the center of the language development stayed at MIT.

7.1 IMPERATIVE AND ALGEBRAIC LANGUAGE

Already in the beginning of September^75, McCarthy wrote first memo, An algebraic language for the manipulation of symbolic expressions. The title is just a description for a language which then yet had no name. Some details were better described in later memos, especially in the third one.

First design of the language was, according to McCarthy’s description ”language of imperative statements“^76, called “imperative Lisp”. McCarthy described that dialect later as ”a Fortran-like language with list structures“^77, also, not much more than FLPL. “Imperative Lisp” was, according to team members, a pragmatically designed language^78.

The phrase, “algebraic language”, ment for McCarthy a higher programming language in which, for difference of the assembler and machine languages, is possible to write complex expressions. Advantages of such languages were not yet widely recognized, so McCarthy explained that programs are shorter and simpler. He points out that “exit” from one procedure can be used as “entry” into another so there is no need to name intermediate results^79.

It seems that McCarthy doubted if the language should be specialized for symbolic processing. Thus at the beginning of the Memo^80, he writes that the language is not suitable for presenting “lists of fixed lenghts” and acces to data in a list in different order than the one in which data is in the list, which is a large, unacceptable shortcoming for a general purpose programming language. Though, already after few pages, McCarthy introduces “field” type, so it seems that the idea of a specialized language was immediately refuted^81.

7.2 BASIC TYPES AND STATEMENTS

The language supports some usual types of data. Arithmetic was supposed to be same as in Fortran. Whole words in computer memory are a distinct type. Propositional quantities true and false, were represented with one bit: 1 and 0. Propositional statements are expressions that have propositional values. Functions that return propositional values, for example < i = are called predicates. “Imperative Lisp” was based on statements; especially on the statement for the assignmenet (orig. arithemtic or replacement statement), the most important statement for lists processing^82. Statement for the assignmenet has usual form,

l = r

where r is any statement and l is the name of a variable or “indexed variable”, for example, a=15 or A(i)=15, or a function call. For example, cwr(3)=15 writes value 15 in word at address 3.

Iteration statement do, taken from Fortran, was supposed to support iteration through segments of integer numbers as well through lists. At times of memorandum writing, the details were not yet decided.

More statements can be organized in compound statement using “vertical brackets” / and \. For example,

/ t = a a = b \ b = t.

Conditional expressions that should be distinguished from conditional branching have form

(p_1 -> e_1, p_2 -> e_2, …, p_n->e_n)

where p_1, …, p_n are propositional expressions and e_1, …, e_n are any statements. p_1, …, p_n are computed in order until value of one of them, for example p_i, evaluates to 1. The value e_i is then the value for entire conditional expression. If none of p is not true, then the statement that contains the conditional expression is not executed.

Flow control is taken from Suggestion by ad hoc committee. Places in a program are marked with symbols and are considered as values of a special, localisation type. The program flow is redirected with special statement go(/e/) where e is expression that computes the positional value. For example,

/ i = 0 loop i = i + 1 \ go(loop).

Operations over location values are limited, but it is possible to use conditional expressions. It is also possible to use set-statement, for example

set(A; q_1, …, q_m)

to define field A that contains location values q_1, …, q_m and then to use statement go(A(e)), where e is an expression that evaluates into natural number.

7.3 SUBPROGRAMS AND “FUNCTIONS”

The language included about twenty already defined functions and subprograms, but programmers can also define their own subprograms and functions. Definition of a function and a subprogram is made of a header, for example

subroutine eralis(J) or function copy(J),

after which a complex command follows. Execution of subprograms and functions is interrupted with return statement. A function returns, as a result of computation, the last value calculated before the return statement. For example

function abs(x) / (X<0) -> -X, X=0 -> 0, X>0 -> X) \ return.

Function can also be defined by simpler statements, for example,

abs(X) = (X<0 -> -X, X=0 -> 0, X>0 -> X)* (58).

Subprograms and functions are called the usual way, for example, abs(-3), copy(L).

Subprograms and functions can be recursive, i.e. call themselves. Recursion is especially useful when processing lists. That property of “imperative Lisp” is an important improvement in regard to FLPL.

Functions are values of special, functional type and thus can also be used as arguments in calls to other subprograms and functions. McCarthy writes that possibilities of functional type are not exploited in their entirety in the “early system”^84.

Functions in “imperative Lisp” differ from the usual mathematical functions. Function values for same agruments can be different because it depends on memory state. Functions can change values of variables and memory registers.

7.4 SYMBOLIC EXPRESSIONS

Symbolic Expressions, whose processing “imperative Lisp” was intended for, are sequences of charachters in special form, useful for translation of mathematical symbols and logical expressions, but also for processing with help of a computer. For example, mathematical expression

x · (x + 1) · sin y

can be written as a symbolic expression

(times,x,(plus,x,1),(sin,y)).

That form reminds of so called, polish notation, but parenthesis enables use of functions with variable number of arguments, as with times for example. Symbolic expressions can be used as data in programs for “manipulating sentences of formal language”, theorem proofing, development of Advice taker, formula simplifing symbolic derivations and integration, compilers, in programs for processing expressions which number and length vary in unpredictable ways.

Symbolic expressions are defined more formally. Symbols are sequences of one or more charachters. Especially, sequences of signs that represents numbers are symbols also. For example, times, X, plus, 1, sin and Y are all symbols.

All symbols are symbolic expressions
If e_1, …, e_m are symbolic expressions, then (e_1, …, e_m) is also a symbolic expression.

For example, (plus,x,1) is a symbolic expression because plus, x, and 1 are symbolic expressions. Similarly, (sin,y) and (times,x,(plus,x,1),(sin,y)) are symbolic expressions.

7.5 PROPERTY LISTS

In computer memory symbols are represented with data structures called ”property lists”. Property lists, a generalization of ”symbol table” in IBM 704 assembler, holds basic data about a symbol: name used for printing, address in memory of property list itself, information if symbol is a number, variable or a constant and similar. Information from the symbol list can be used by the compiler, but also by a programmer.

Property lists can be changed with declarative statements in unexpected form

I declare(…)

where punctuation (…) represents expression in form (a; /p1/, …, /pn/) which adds expressions p1, …, pn to property list a, or in form (/a1, …, an, p/) which adds expression p to a property lists of symbols a1, …, an.

Syntax close to the natural language was not used more during the language developmnet under the McCarthy’s leadership, and McCarthy didn’t liked when it appeared in later Lisp versions^85.

7.6 LISTS AND SYMBOLIC EXPRESSIONS REPRESENTATION

Symbolic expressions are in computer memory represented with data structures called lists.

Moreover, the form of symbolic expressions seems to be inspired exactly by the simplicity of translating them into lists^86,87.

List implementation is similar to that of FLPL, beside names of functions for list processing being somewhat different. The only McCarthy’s innovation regarding lists in “imparetive Lisp” is clear graphical illustration of lists that is still in use today.

IMAGE 6. Graphical view of list structure representing the symbolic expression (a, (b,c),(b,(d,e)),f).^88

Rectangles represent “list elements”, single words in computer memory. Left and right rectangle-halfs represent respective address- and decrement part of the word. The order of address and decrement word parts is reversed in the graphical view in respect to order as in the computer word, because members of the project found it natural^89 or because it was the usual order in IBM 794 assembler^90. The arrow replaces the address of a word. A symbol written in “address” or “decrement” part of a rectangle denotes that respective part of the word contains the address of the property list for that symbol. First element in property list, in address part, has value null - in that way can programs recognize a property list of other lists.

Same symbolic expression can be represented by different list structures. It is sufficient that list elements are in different places in memory.

Despite the graphical view not showing the other parts of words than address and decrement, those parts are still used in “imperative Lisp”. If the address part of a list element contains a sublist address, data in prefix part of list element (more precisely, in bits 1 and 2, which McCarthy calls indicator) determined if a sublist could be erased too when a list is erased. In later Lisp development such control of memory was abandoned. Property lists of symbols do not belong to any list, and are not erased if a list is erased.

Like in FLPL, lists are not implemented as a special data structure but are an abstraction, a way of thinking by programmers. Programs process addresses of list elements, and assumed lists are in programs represented by the address of the first list element. Such simplification of lists to memory addresses was later criticized as “too close to hardware”^91. McCarthy hoped that list operations could be defined at level of entire lists, but his experience told him that most of list operations still has to be defined at level of list elements^92.

Lists can also “modell” sequences, mathematical objects that don’t have relation to sequences of signs. For example, 2, 3, 5, 7, 11 is a finite sequence.

IMAGE 7.Graphical vew of a list that modells the sequence 2, 3, 5, 7, 11 and whose external representation is (2,3,5,7,11).

Once modelled as lists, sequences also has their “external representation” in form of symbolic expressions. For example a list that modells finite sequence 2, 3, 5, 7, 11 has extern representation (2,3,5,7,11). Finite sequences are often written in similar form, as ordered n-tuples, even in mathematical texts.

McCarthy didn’t explictly expressed intention to represent entire program in list form. Stoyan’s thesis is that, considering the idea that compiler should be written in Lisp itself as expressed in memo introduction, McCarthy already had such ideas^93. That thesis seems valid, especially considering the mentioned Letter to Perlis and Turanski.

7.7 FUNCTIONS FOR WORD ANALYSIS AND SYNTHES AND REFERENCING

Defined is a number of functions for extraction of word parts. For example, calls to functions add(/e/), dec(/e/) and ind(/e/) returns values of address, decrement and indicator parts which are results of computing expression e. Some functions extracted values of arbitrary bits or word segments.

Few functions constructed values of words. For example, comb 4(/p,d,t,a/) returns value of a word constructed by writing values p, d, t and a in respective parts of the word (prefix, decrement, tag and address).

Reference functions compute values of words or parts of words at given address. For example, calls to functions cwr(3), car(3), cdr(3) and cir(3) return values of a word at address 3 and respective address, decrement and indicator part of that word. Reference function names are abbreviations, for example, “[C]ontent of the [A]ddress part of [R]egister”.

Data can be written directly to memory addresses, by using statements for the assignement and reference functions. Alternative is made of functions stwi, star, stdr, etc, so that, for example, stwr(3,15) has same result as cwr(3) = 15.

7.8 FREE STORAGE MANAGEMENT

Management of free memory is taken from FLPL. Free storage list has same structure as other lists and contains memory currently not in program use. It is allocated at program execution. Functions that use memory for conpucting new lists or adding new elements to already existing lists use and remove words from free storage list.

IMAGE 8. Putting symbol x in third place in list L.

Construction functions choose first word from the free storage list, remove it from the free storage list, write some value in it and as a result return the address of that word. Call to function consw(e) writes e into a word. Call to function consel(/a/, /d/) writes value a into address part and value d into decrement part of a word. Seems that names consw and consel come from the phrases “construct word” and “construct element”^95. There are other similar functions.

Function list constructs new list from function arguments. Value list(i_1, …, i_n) is a list that contains values i_1, …, i_n.

“Imperative Lisp” still didn’t have a “garbage collector”. Function erase returns memory addresses that are no longer needed for computation to free storage list. For example, call to function erase(3) returns third word in memory to free storage list. Value of function erase is the old content of newly released word.

7.9 BASIC OPERATIONS OVER WHOLE LISTS

The way lists are defined makes it possible to define operations on whole lists. Call to subprogram eralis(/J/) erases entire list structure whose first element is at address J and returns freed memory to free storage list. McCarthy defines subprogram eralis in “imperative Lisp”; it is the first example of subprogram in the memo and as such can be considered the first documented program in Lisp.

subroutine eralis(J) / J = 0 → return go (a(cir(J)) a(1) jnk = erase(car(J)) a(0) eralis(dec(erase(J))) return a(2) eralis(car(J)) \ go (a(o))

Subprogram eralis analyses first element of a list. If the list is empty, the subprogram ends execution. If not, then branching is done depending on the value of the indicator in first list elemenet.

If the indicator has value 0, then the value in the address part of the list element is the address of “borrowed” sublist which should not be erased from the memory. Subprogram eralis erases element of the list by calling function erase and applies itself on the rest of the list.
If the indicator has value 1, in the address part of the list element is a data address; eralis erases that data by calling erase, removes first element of the list by calling function erase and applies itself on the rest of the list.
Finally, if indicator has value 2, then the data is a list that is not “borrowed”; eralis applies itself on that data, and afterwards removes first list element by calling function erase and applies itself on the rest of the list.

A curiosity is the first syntax error in a Lisp program: in the last row, instead of 0, McCarthy wrote small letter o.

Function copy constructs and returns as a value of computation a copy of the list structure at last given address. Memory in which the copy is stored is taken from the list of free storage. Function is defined by conditional expression in which basic case is solved directly, and rest of cases by recursive call of same function, applied on the rest of the list. That pattern is later applied on many other functions. Function search looks up elements of list structure that satisfy a given criteria. Funcion equal checks equality of list structures at given addresses.

7.10 FUNCTION MAPLIST

Function maplist which applies a given function on data in list has important role in further Lisp development. In the first memo maplist is defined briefly and unprecisely^96, but ambiguities can be avoided on basis by exempel^97 and later McCarthy’s explanation^98. For example, the value of symbolic expression

(maplist(list(1,2,3),x,x*x))

is computed so that variable x associates value of all items whose address is in addres part of list elements in list(1,2,3). For all those values x*x is computed, i.e. 1,4 and 9. A new list is formed, from list elements taken from the free storage list in whose address part is written addresses at which are results of previous computation. That list is returned as a function value.

IMAGE 9. Result of applying maplist(list(1,2,3),x,x*x).

Generally, the expression maplist(/L/, /J/, /f(J)/), where L is an expression that computes to a list, J is a symbol, f(J) an expression given by inserting symbol J in function f, is computed so that (1) variable J assumes all values in L; (2) for every of values J is computed value f(J) and (3) a new list is formed where in address parts of list elements are values f(J). That list is returned as a value of the computation.

47 Stoyan, Early LISP history (1956-59), 1984., p. 304. 48 Levy, Hackers, 2010., p. 36. 49 “The teacher was a distant man with a wild shock of hair and an equally unruly beard — John McCarthy. A master mathematician, McCarthy was a classically absent-minded professor; stories abounded about his habit of suddenly answering a question hours, sometimes even days after it was first posed to him.” Levy, Hackers, 2010., p. 11. 50 McCarthy, Programs with common sense, 1959., p. 75-92. 51 McCarthy & Minsky, Artificial Intelligence in RLE QPR 052, 1959., p. 129. 52 McCarthy, Situations, actions and causal laws, 1963., p. 1. 53 “The main problem in realizing the Advice Taker has been devising suitable formal languages covering the subject matter about which we want the program to think.” McCarthy, A basis for mathematical theory of computation, 1963., p. 69. 54 Stoyan je nezavisno rekonpuirao Advice Taker in Programmiermethoden der Künstlichen Intelligenz, 1988., p. 193-231. 55 McCarthy, An algebraic language …, AIM-001, 1958., p. 1. 56 McCarthy, A revised definition of maplist, AIM-002, 1958., p. 1. 57 McCarthy, Revisions of the language, AIM-004, 1959., p. 9. 58 McCarthy, Recursive functions …, AIM-008, 1959., p. 1. 59 McCarthy et al., Artificial intelligence u RLE QPR 053, 1959., p. 122. 60 Berkeley i Bobrow, LISP − its operations and applications, 1964., p. 4. 61 Edwards, Secondary storage in LISP, AIM-063, 1963., p. 13. 62 McCarthy, Recursive functions …, AIM-008, 1959., p. 13-17. 63 Abrahams, Discussant’s remarks in HOPL I, 1981., p. 192. 64 Levy, Hackers, 2010. 65 Minsky, Introduction to COMTEX Microfische edition …, 1983., p. 10. 66 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 67 Russell, Adventures and pioneering with John, 2012. 68 Personal communication with Brayton and Luckham, 2012. 69 Personal communication with Brayton and Luckham, 2012. 70 Rochester, AIM-005, 1959. 71 Stoyan, Early History of LISP (1956-1959) (slides), 1984., p. 24-6. 72 Stoyan, LISP, Anwendungsgebiete, Grundbegriffe, Geschichte, 1980. 73 McCarthy, An interview with John McCarthy, 1989., p. 4. 74 “Maintenance and further development of LISP will be continued by Professor J. McCarthy, who is now at Stanford University. We plan to continue close association with his group.” Minsky, Artificial intelligence, RLE QPR 068, 1963., p. 159. 75 Stoyan, Early LISP History (1956-1959), 1984., p. 304. 76 McCarthy, Revisions of the language, AIM-003, 1958., p. 1. 77 McCarthy, The logic and philosophy of AI, 1988., p. 5. 78 Abrahams, Transcript of discussant remarks, in McCarthy, History of Lisp, 1981., p. 193. 79 McCarthy, An algebraic language …, AIM-001, 1958., p. 3. 80 “… this language is best suited for representing expressions whose number and length may change … It is not so convenient for representing lists of fixed length where one frequently wants the n-th element where n is computed rather than obtained by adding 1 to n − l.” McCarthy, An algebraic language …, AIM-001, 1958., p. 2. 81 McCarthy, An algebraic language …, AIM-001, 1958., p. 7-8. 82 “Programs for manipulating list pucture are written mainly in terms of replacement statements (i.e. of the form a = b).” McCarthy, An algebraic language …, AIM-001, 1958., p. 11. 83 Both function definitions abs* are written for purpose of this book. All McCarthy’s examples in the original memo are too complex to be used in this place. 84 McCarthy, An algebraic language …, AIM-001, 1958., p. 7. 85 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 86 McCarthy, An algebraic language …, AIM-001, 1958., p. 18. 87 Stoyan, Lisp history, 1979., p. 45. 88 After illustration in McCarthy, An algebraic language …, AIM-001, 1958., p. 5. 89 Faase, The origin of CAR and CDR in LISP, 2006. 90 Abrahams, Transcript of discussant’s remarks, in McCarthy, History of Lisp, 1981., p. 192. 91 Landin, Next 700 programming languages, 1966., p. 160. 92 McCarthy, An algebraic language …, AIM-001, 1958., p. 5. 93 Stoyan, Early LISP history (1956-1959), 1984., p. 305. 94 According to McCarthy, Revisions of the language, AIM-003, 1958., p. 7. 95 Slagle, A heuristic program …, 1961., p. 17. 96 “Maplist (L,J,f(J)). The value or this function is the address of a list formed from the list L by mapping the element J into f(J).” McCarthy, An algebraic language …, AIM-001, 1958., p. 17. 97 Funkcija za diferenciranje: function diff(L) / diff=(… car(L)=”x” → 1, car(L)=”plus” → consel(“plus”, maplist(cdr(L), J, diff(J))), \ …) McCarthy, An algebraic language …, AIM-001, 1958., p. 20. 98 “The version of maplist in memo 1 was written “maplist(L,J,f(J))” where J is a dummy variable which ranges over the address parts of the words in the list L and f(J) was an expression in J.” McCarthy, Symbol manipulating language, AIM-004, 1958., p. 4.

8. Elements of functional programming

In period from September 1958. to March 1959. Lisp developed gradually and continuously, without some major redesign. Changes in that period led, mainly, toward what would later be called “pure Lisp” and which is described in McCarthy’s first article about Lisp^99.

8.1 NEW MAPLIST FUNCTION

In second memo McCarthy criticizes first version of maplist function^100,101 which was called by expression maplist(/L/, /J/, /f(J)/). First, it would be better if in function call values J were elements of list L instead of address parts of list elements^102. If a list element is known, it’s address part can be calculated. Reversal is not valid.

A second, more important objection, is that a name of a variable can not be used “conclusively” as a function argument. For example, if a first version of maplist function is called by expression

maplist(list(1,2,3),x,x*x) (*)

subexpressions x and x*x will be calculated and results of calculations passed to maplist function. While evaluating x*x there will be error, because variable x does not have a defined value, and if such value is defined somewhere in the program, the result will not have the data needed for calculating the expression (*).

Thus McCarthy defines new version of maplist function. The function is called by expression in form

maplist(/L/, /f/),

where L is an expression whose value is a list, and f is an expression whose value is a function. For example, the value of function call maplist(list(1,2,3),car) is a list constructed from values obtained by applying function car on all list elements obtained by computing list(1,2,3).

IMAGE 10. The result of computing maplist(list(1,2,3),car).

Defintion of maplist function resolves all ambiguities.

maplist(L,f) = (L = 0 → 0, 1 → cons(f(L), maplist(cdr(L),f))).^103

Function cons^104 takes a word from the free storage list, in address part of the word writes address f(L) and in the decrement part address of maplist(crd(L),f).

8.2 MCCARTHY’S LAMBDA-EXPRESSIONS

The second version of maplist function, in this form, is more limited than the previous version. For example, with second version it is not possible to write an equivalent of the expression

maplist(list(1,2,3),x,x*x)

as in first version of maplist function. Therefore McCarthy returns to the idea from Letter to Perlis and Turanski. He defines “a functional abstraction” as an expression which gives rules for computing function appliction on arguments. An expression like x*x+y does not have such property. For example, if we try to calculate

(x*x+y)(3,4)

it is not clear which values should be associated with parameters x and y. McCarthy’s lambda-expressions^105, for example λ(x,y,x*x+y) inspired by Church’s^106 satisfy that criteria. Value of expression

λ(x,y,x*x+y)(3,4)

equals value 3*3+4. More generally, value λ(/J/, /E/)(/e/) is a value of expression obtained by substitution of argument e into J and E. Similar holds for lambda-expressions with multiple variables. For example, call to second version of the function

maplist(list(1,2,3),λ(J,car(J)))

is equivalent to call of the first version of function maplist(list(1,2,3),J,J).

Important McCarthy’s example is definition of the function for derivation diff^107 which skillfully exploits the second version of the maplist fucntion and lambda-expressions.

diff(L,V)= (L=V → C1, car(L)=O → C0, car(L)=plus → cons(plus, maplist(cdr(L), λ(J, diff(car(J), V)))), car(L)=times → cons(plus, maplist(cdr(L), λ(J, cons(times, maplist(cdr(L), λ(K, (J≠K → copy(car(K)), 1→diff(car(K), V)))))))), 1 → error)

C0 and C1 represent constants 0 and 1. It should be noted that 1 is the last condtion in previos definition, i.e. it is calculated in “all other cases”. The program is unusually skillfully and elegantly written, especially for the time when McCarthy barely could have lots of experience in writing programs in Lisp.

From the historical distance, it is not obvious that lambda-expressions are the best solution for the problem with maplist function. Lambda-expressions are a consequent development if the idea that functions can also be arguments for other functions. Nonetheless, the need to use non-evaluated symbols and expressions as arguments persisted and was alter solved more generally, by introducing the “special operator” QUOTE. Considering this, we could say that lambda-expressions are introduced in Lisp too early, or perhaps, even accidentally. Despite, almost all Lisp dialects continue to keep lambda-expressions^108.

There are also opinions that differences between Lisp and lambda calculus are big^109,110 as well as that λ-calculus is a basis for Lisp^111,112,113. McCarthy himself refuted the later ones as “a myth”.^114

8.3 SIMPLIFICATION OF THE LANGUAGE

McCarthy realized soon^115 that for all needed operations, it is enough to use just address and decrement part of the word. Among big number of functions for processing single words, left were only few. Some functions got new names.

Functions^116 add(/w/) and dec(/w/) extracts address and decrement part of a word which is the value of expression w.

Function comb(/a/, /d/) evaluates the value of a word that contains values a and d in address and decrement parts.

Functions cwr(/n/), car(/n/) and cdr(/n/) returns the value of a word n, respective of the address and the decrement part of the word at the address whose value is n.

Function consw(/w/) writes value w in a word taken from the free storage list and returns the address of that word.

Function cons(/a/, /d/) writes values a and d in address and decrement part of a word taken from the free storage list and returns address of that word.

Function erase(/L/) returns word at address L to the free storage list, and as a result returns the previous value of the word L.

Supported were also a few operations over whole lists. Call to function copy(/L/) copies entire list structure at address L, taking as needed words from the free storage list.

copy(L) = (L=0 → 0, car(L)=0 → L, 1 → cons(copy(car(L)), copy(cdr(L))))

Function equal(/L1/, /L2/) compares list structures at addresses L1 and L2 and returns 1 if they are equal, 0 otherwise.

equal(L1,L2) = (L1=L2 → 1, car(L1)=0 ∨ car(L2)=0 → 0, 1 → equal(car(L1), car(L2)) ∧ equal(cdr(L1), cdr(L2)) )

The condition in second line is needed because the address part of the first element in property lists contains number 0. If L1 and L2 are at different addresses (which is guaranteed by condition L1=L2) and at least one of L1 and L2 is a property list, then equal(L1,L2) has value 0.

Subprogram eralis(/L/) erases entire list structure at address L.

subroutine (eralis(L)) / L = 0 ∨ car(L) = 0 → return M = erase(L) eralis(add(M)) eralis(dec(M)) \ return

Subprogram is considerably simpler than one in the previous chapter, but now it can not recognize if elements in a list to be erased are “borrowed”.

Defined is also a subprogram print and function read which as a result returns address of a list constructed on bases of a symbolic expression written on a punched card or other medium.

Functions that modify values of list elements, star and stdr are removed from the language, but as it will be seen, temporary.

8.4 RECURSIVE FUNCTION IMPLEMENTATION

Functions maplist, diff and some others are recursive; they call themselves. Implementation of recursive functions was somewhat of a difficulty because different instances of same functions use same variables.

The problem was solved by storing “protected temporary storage”, that holds symbols and values that have to be preserved during a call to same function, on a “public stack”, at the time called public push down list.^117 Called function first store contents of it’s protected temporary memory on the stack, evalueates value that has to be returned, and then from the stack reconstructs “protected temporary storage”. The solution is genuine, but not complex, and was already discovered by Turing^118.

8.5 FUNCTIONAL AND IMPERATIVE STYLE

Today it is widely assumed that programs written in functional style are more “elegant”, but less effecient than programs written in imperative style. Despite that terminology like “functional” and “imperative style” were yet not used, those differences were very fast discovered. Beside the previous one, “functional definition” of the function maplist

maplist(L,f) = (L = 0 → 0, 1 → cons(f(L), maplist(cdr(L),f))).

McCarthy defined in the fourth memo a second, imperative version.

maplist(L,f) = / L = 0 → return(0) maplist = cons(f(L),0) M = maplist a1 L = cdr (L) cdr(M) = cons(f(L),0) cdr(L) = 0 → return(maplist) M = cdr(M) \ go(a1)

The imperative version was about four times faster. McCarthy, nevertheless, was not keen to recommend writing programs in less clear, imperative style^119. He speculated that compiler could translate programs from one style into another, but he didn’t see how such compiler could be written. Instead, he pragmatically decided that few number of frequently used programs for which speed is important should be written in imperative, and all the others in functional style. Also, prominent is the difference in use of statement return.

8.6 UNDEFINIABILITY OF FUNCTION LIST

McCarthy widens discussion about already briefly described function list. The function can be described with equalities

list(i) = cons(i,0) list(i_1, …, i_n) = cons(i_1, list(i_2, …, i_n)).

McCarthy observes that list is defined recursively with number of arguments, and that such list can not be defined in Lisp, but has to be implemented in a Lisp compiler^20.

8.7 SUBSTITUTIONAL FUNCTIONS AND FUNCTION APPLY

McCarthy introduces somewhat enigmatic term of substituional functions which are “applied” on a list of arguments^121. Substituional functions are symbolic expressions, for example,

(subfun, (x,y), (times,x,y)).

If the above substituional function is “applied” over a list of arguments

((plus,a,b),(minus,a,b))

the result is

(times,(plus,a,b),(minus,a,b)).

Generally, the result of “applying” a substitutional function

(subfun, (x_1, …, x_n), e)

where x_1, …, x_n are symbols, e any expression, on a list of arguments

(e_1, …, e_n)

if a value of expression e’ which is obtained by simultaneous substitution of all free occurence of x_1, …, x_n in e with arguments e_1, …, e_n in order.

McCarthy didn’t wrote exactly what it means that substitutional functions are “applied” on an argument list. Today is custom to say, for example, that expression car(/e/) denotes applying of function car on expression e. But, in about fifty pages of the memo that were written to date, McCarthy just once

uses the word “apply” in that context, and that relatively informally too^122. Almost certainly, for “applying” substitutional functions, he ment evaluateing expressions if the form

apply(l, f)

where l is a list of arguments, f a substituion function and apply a Lisp function. For example, if

f has value (subfun, (x,y),(times,x,y)) and l has value ((plust,a,b),(minus,a,b))

then

apply(l, f) has value (times,(plust,a,b)),(minus,a,b)).

8.8 HELP FUNCTIONS AND IMPLEMENTATION OF APPLY

Despite early form of apply not being particularly complex, for the implementation of apply are needed help functions, less important, but interesting search, subst, sublis and error.

Function search finds data that satisfy given criterion in a list; if it finds it, it returns given function of that data; if it is not found, it returns given value. For example, call to function

search(list(1,2,3), λ(x,x+x=2), λ(x,x*x*x), 0).

has value 8. Arguments to function call are a list in which to search for data, a predicate that has to be satisfied, a function to apply on found data that satisfy the predicate and value that is returned if no data satisfies the predicate.

search(L,p,f,u)=(L=O → u, p(L) → f(L), 1 → search(cdr(L),p,f,u))

Function subst implements substitution. For example, if l is an expression with value (A,B), v an expression with value (X,Y), m an expression with value ((X,Y),C,(X,Y)). Then subst(/l/, /v/, /m/) has value ((A,B),C,(A,B)). More generally, if l, v, and m are expressions, the expression subst(/l/, /v/, /m/) has as it’s value the result of substituting value l for value v in m.

subst(L,V,M)= (M=0 → 0, equal(M,V) → copy(L), car(M)=0 → M, l → cons(subst(L,V,car(M)), subst(L,V,cdr(M))))

The condtion car(M)=0 means that value M is a symbol (property lists has value 0 in address part of the first element).

Function sublis implements multiple substituions, coordinated in list of form ((l1,v1), …, (ln,vn)), where li is a symbolic expression to be substituted in and vi symbolic expression to be substituted. For example, if

p is an expression with value ((X,A),((Y,Z),(B,C))), e is an expression with value ((X,Y),X,Y,(Y,Z))

than call to function

sublis(/p/, /e/) has value ((A,Y),A,Y,(B,C)).

Definition of function sublis is quite sofisticated.

sublis(P,E) = maplist(E, λ(J,search(P, λ(K,equal(car(J), car(car(K)))), λ(K,copy(car(cdr(car(K))))), (car(car(J))=O → car(J), 1 → subst(P,car(J)))))

The definition contains two errors. In list line instead of subs should be sublis. The second, the program will not work if the expression in which substution is to be done, E, is trivial - a symbol. For example, if p is an expression with value ((X,A),(A,B)), e an expression that has value (X,A,X,A) then call to function sublis(/p,e/) has value (A,B,A,B).

Function pair creates a list of pairs, needed for use in function sublis. If l and v are expressions whose values are (/l1, …, ln/), (/v1, …, vn/) then call to function pair(/l,v/) has value ((/l1,v1/),…,(/ln,vn/)).

pair(Ll,L2)=( Ll=O ∧ L2=0 → 0, Ll=O ≠ L2=0 → error, l → cons(cons(copy(car(Ll)), cons(copy(car(L2)), 0)), pair(cdr(Ll), cdr(L2))))

Function error is called in exceptional cases and writes messages about a misstake and information useful for the error analysis.

After definition of all help function, the defintion of apply function is brief

apply(L,f) = (car(f) = subfun → sublis(pair(car(cdr(f)), L), car(cdr(cdr(f)))), 1 → error)

Substitutional functions are an important step in Lisp development. Because of them, a very general and important function apply is defined which later was understood as an “universal function”.

One could think that function apply is simpler then function maplist so that

apply(L,f) = car(maplist(list(L),f)).

The previous expression, though, is valid only for functions of one variable, while apply can be used on functions with arbitrary number of variables.

8.9 AUTOMATIC MEMORY MANAGEMENT

Functions for erasing list elements and whole lists, erase and eralis as described in the first memo, are not used in next three memos. There is an indicative McCarthy’s comment together with above apply function. He realizes that function pair constructs new list, and that this list is not assigned to any variable, and thus can not be erased with function eralis. Instead of using an assignement statement to solve that problem, McCarthy realized that, if we don’t write a compiler that inserts instructions for erasing such, “help lists”, they will always “steal the memory”^123,124,125.

8.10 ROCHESTER’S LAMBDA EXPRESSIONS

Rochester observed that McCarthy’s lamda-expression does not allow for definition of recursive functions. As it will show later, it is still possible - but is not easy. For that reason he introduces other, more expressive lambda-expression (he calls them “function abstractions”) in which the name of function is specified. For example, function that checks if there is a symbol var in a property list of a symbol is defined with lambda expression

λ(F(K),(K=0 → 0, car(K) = var → 1, 1 → F(cdr(K)))).^126

Variable F does not have value outside of the lambda-expression. Rochester’s lambda-expressions will become slightly changed and re-named into label-expressions in “pure Lisp”.

8.11 PROGRAM FORMATTING

Rochester was the first to start formatting in today custom way, by indenting lines and also explicitly recommends such notation. For example, the above program is formatted almost identically to Rochester’s original. Other members of the Lisp community didn’t accept that idea for a quite long time. Identing lines is explicitly mentioned in Lisp 1.5 manual^127.

8.12 COMPOSITION OF CAR AND CDR FUNCTIONS

Rochester’s contribution is also a shorter notation of compositions of car and cdr. For example, instead of car(cdr(cdr(L))) it could be written caddr(L).^128 However, this idea is not new; it was applied already in FLPL.

Despite names like caddr being practical, and they are accepted in almost all Lisp dialects, to the author of this book the idea is not unquestionable. Symbols like caddr are not just names, but contain also information that human, the programmer, must decode. This data is then unavialable, or at least harder to obtain for processing by the program.

8.13 FUNCTION COMPUTE

In Memo 7. McCarthy describes, but does not define, subprogram compute(L,C) where L is an expression to be computed, and C is an address on which to store the result of computing L. The value of caling compute(L,C) is a program in assembler, in list form.^129 Implementation of functions that proces the language expressions in the language itself is a Lisp specialty.

99 “The development of the LISP system went through several stages of simplification in the course ot its development and was eventually seen to be based on a scheme for representing the partial recursive functions of a certain class of symbolic expressions.” McCarthy, Recursive functions …, AIM-008, 1959., p. 1. 100 McCarthy, A revised version of MAPLIST, AIM-002, 1958. During the process of writing this book, only the first page of AIM-002 was accesible to public. That page is identical to the start of second chapter of AIM-004 so, maybe, the entire AIM-002 is contained in AIM-004. 101 McCarthy, Revisions of the language, AIM-004, 1958. 102 McCarthy, Revisions of the language, AIM-004, 1958., p. 4. 103 That and many ohter functions in this book are formated by breaking and indenting lines, as it is custome today, but not at the time when original documents were written. Formatting helps a lot with readability. 104 That function was in AIM-001 called consel. 105 McCarthy didn’t use term “McCarthy’s lambda-expressions”, but “functions” wich today is not sufficiently precise. More suitable term “lambda-expressions” come into use later, and attribute “McCarthy’s” is needed in order to differ from other lambda-expressions, especially Church’s and Rochester’s. 106 Church, The calculi of λ-conversion, 1941. 107 McCarthy, Revisions of the language, AIM-004, 1958., p. 7. 108 Important exception is PicoLisp by a German Alexandre Burger. Burger, The PicoLisp reference. 109 Cianalgini & Hindley, Lambda calculus, in Wiley Enc. of Comp. Sci., 2008., p. 5. 110 Barendregt & Barensen, Introduction to λ-calculus, 2000., p. 30. 111 Weizenbaum, Review of “The LISP 2 programming language …”, 1967., p. 236. 112 Moore & Mertens, The nature of computation, 2011., p. 295. 113 Mac Lane, Group extensions for 45 years, 1988., p. 29. 114 “That was fine for that recursive definition of applying a function to everything on the list. No new ideas were required. But then, how do you write these functions? And so, the way in which to do that was to borrow from Church’s Lambda Calculus, to borrow the lambda notation. Now, having borrowed this notation, one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn’t understand the lambda calculus, really. In particular, I didn’t understand that you really could do conditional expressions in recursion in some sense in the pure lambda calculus. So, it wasn’t an attempt to make lambda calculus practical, although if someone had started out with that intention, he might have ended up with something like LISP.” McCarthy, History of LISP, 1981., p. 190. 115 McCarthy, Revisions of the language, AIM-003, 1958., p. 1. 116 More precise would be to write “function call”, but for the simplicity it is custom to write just “function.” Same holds for the rest of this text. 117 Russell, Explanation of big “P”, AIM-009, 1959., p. 2. 118 Turing, Proposed electronic calculator, 1945., p. 12. 119 “One is very reluctant to say that routines like maplist should be described by programs like the above which is certainly much less clear than the previous description.” McCarthy, Revisions of the language, AIM-004, 1958., p. 8. 120 McCarthy, Revisions of the language, AIM-004, 1958., p. 16. 121 McCarthy, Revisions of the language, AIM-004, 1958., p. 19. 122 McCarthy, Revisions of the language, AIM-003, 1958., p. 6. 123 McCarthy, Revisions of the language, AIM-004, 1958., p. 20. 124 “When I wrote this program for differentiation … it was just much too awkward to write Erasure, that is erasing things. … So, I thought very hard “Is there some way in which we can eliminate having to have explicit erasure, in order to be able to write the differentiation function in a way corresponds to the way that mathematicians describe it?” They don’t describe, they don’t mention erasing anything in the calculus textbook, so I worked hard on that and came up with garbage collection.” McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 125 McCarthy, The logic and philosophy of AI, 1988., p. 5. 126 Rochester, AIM-005, 1958., p. 15. 127 McCarthy et al., LISP 1.5 programmer’s manual, 1962., p. 16. 128 Rochester, AIM-005, 1958., p. 14. 129 McCarthy, Notes on the compiler, AIM-007, 1958., p. 1.

9. Pure Lisp

The development from “impterative Lisp” to the end of 1958. was very quick and excellently documented. During this period, McCarthy realized that combination of expressed ideas does not just make for a practical programming language, but also an “elegant mathematical system” for describing computable functions, more “clean” than Turing machines and theory of recursive functions. Such reasoning motivated further simplifications, partly for the esthetic reasons, and partly because of the desire for development of techniques for proofing corectness of programs^130.

In few intern memos and repports written during the March and April 1959. under the same title, ”Recursive functions of symbolic expressions and their computation by machine”, the simplified Lisp is already defined and precisely described^132,133,134. In Memo 8. McCarthy tried to use descriptive names for functions: first, rest and combine instead of car, cdr and cons. Him and Russell tried to convince other project memebers to use new names, but without success.^135 Already in next Memo McCarthy gives up on new names. In September 1959. Lisp is presented at ACM conference^136.

The text got it’s final form of about tenth of pages long article published in early 1960. under the same title.^137 Some ideas, mainly relation between Lisp and comutation theory^138 were noted only in intern documents. Announced continuation of the article was supposed to contain examples of computations with algebraic expressions, but was never written^139.

Surprisingly even for members of AI project, Lisp turned out as a language whose important property is - beauty.^140 It seems that some readers has certain problems with understanding of basic ideas of the language^141.

In time when it was developed, the new dialect didn’t have a special name. It was simply called “LISP”. Only with appereance of sufficiently different Lisp 1.5, the dialect starts to be called “pure”^142 and somtimes also a “vanilla Lisp”.^143 “Pure Lisp” is sometimes also wrongly identified with Lisp I., an intern version of practical Lisp that predeccesed more familiar Lisp 1.5. Intern, the group members also called it RSFE Lisp.^144 A special implementation of “pure Lisp” did not exist, so it could be also understood as a sub-language of implemented Lisp.

McCarthy tried several times to approximately frame “basis of Lisp”. He describe it as a “programming system for using IBM 704 computer for computing symbolic expressions in form of S-expressions”^145 or “a method of generating recursive function over symbolic expressions”.^146

Definitions and theses from several articles and intern documents can be organized in about ten groups.

Introduced is a set of rules for forming mathematical expressions, especially for expressions which define functions.
Defined are symbolic expressions or S-expressions as a special kind of new symbols. For example, A, B, DA, E1, (A,B), (A,(B,C),(B,(DA,E1))) are all symbolic expressions. Symbolic expressions are only kind of data in “pure Lisp”.
Defined are functions over symbolic expressions or S-functions. There are few primitive S-functions. All other S-functions are defined with help of few facilities as noted in 1. For example, append is a function that for pair (A,B) and ((A)) assigns (A,B,(A)).
Every S-function is defined by some mathematical expression. For sake of not confusing definitions of S-functions with symbolic expressions, parenthesis are exchanged for rectangle brackets, and commas with semi-colons. Thus written expressions are called meta-expressions. For example, λ[[x]; append[x; x]] is a meta-expression that that defines S-function which assignes append[x;x] to symbolic expression x. From definition of every S-function is apparent how to calculate the value of that function for given arguments.
Defined is translation of meta-expressions into S-expressions. Used is “Cambridge polish notation”. For example, meta-expression append[x;x] is translated to (APPEND,X,X). It is also written as
append[x; x]^* = (APPEND,X,X).
Analog to universal Turing machine, defined is a universal S-function apply which can replace any other S-function. Precisely, if f is an S-function, and f^* a translation of meta-expression with which f is defined, then
/f/[arg_1; arg_2; …; arg_n] = apply[f^*; (arg_1, arg_2, …, arg_n)]

for all S-expressions arg_1, …, arg_n.
Defined is another important function, eval, that computes “value” of S-expression with given argument “values”. For example, if S-function append “assignes” S-expressions then
eval[(APPEND,X,Y); ((X,(A)),(Y,((B))))] = (A,(B)).
Described is, as a rough sketch, implementation of the system. Of special importance is implementation of symbolic expressions in form that is today called single linked lists, already described in the first memo.
Proved is that every program can be represented by an S-function.

9.1 MATHEMATICAL EXPRESSIONS

At first sight surprisingly, McCarthy devoted significant part of the article to mathematical ideas and notation.^147 Some forms of expressions that were earlier introduced as part of Lisp, are now introduced as mathematical expressions.

Partial functions are functions not defined over entire domain field. Predicate expressions are expressions that can be true or false, that is, whose values are true (denoted by sign T) or false (denoted by sign F). Predicates are functions which, for those argument values for which they are defined, have values T or F.

9.2 CONDITIONAL EXPRESSIONS

In function definitions computed differently for different arguments are usually used phrases in natural language or two-dimensional expressions in form like

−x for x < 0

|x| = 0 for x = 0 x for x > 0

For that purpose, McCarthy introuces conditional expressions. For example, the absolute value can be defined by a conditional expression

x	= (x < 0 → − x, x = 0 → 0, x > 0 → x).

Contitional expressions can also be used outside the context of defining functions. For example,

(2 + 2 = 5 → 2^2 + 3^3, 2 + 2 = 4 → 4).

If we need to compute the value of a conditional expression, it is not necessary to compute all subexpressions. For example, in previous expression it is necessary to evaluate 2 + 2 = 5. Since it is not the case, evaluating 2^2 + 3^3 is not necessary.

More generally, conditional expressions have form

(p_1 → e_1, …, p_n → e_n)

where p_1, …, p_n are predicate expressions, and e_1, …, e_n are any expressions. Value of a conditional expressions is computed so that expressions p_1, …, p_n are evaluated in order, until the first p_i with value T is found. Then the corresponding e_i is evaluated and obtained result is the value of entire conditional expression. If all p_1, …, p_n are false, or some of sub-expressions that has to be evaluated does not have defined value, then the value of conditional expression is not defined.

Instead of last condition is often used T. For example,

x	=(x < 0 → − x, x = 0 → 0, T → x).

Conditional expressions can, for example, replace all predicate conjuctions.

p ∧ q = (p → q, T → F) p ∨ q = (p → T, T → q) ~ p = (p → F, T → T) p ⊃ q = (p → q, T → T).

9.3 RECURSIVE AND SIMULTANEOUS RECURSIVE FUNCTION DEFINITIONS

Functions can be defined by expressions in which name of the function appears on both left and right side of the equality, for example

n! = (n = 0 → 1, T → n · (n − 1)!).^148

Functions are sometimes, although not often, defined with “simultaneous recursion”. For example, functions f, g and h can be defined by expressions

f(n) = g(n – 1) + h(n – 1) g(n) = (n = 1 → 1, T → f(n) + h(n − 1)) h(n) = (n = 1 → 2, T → f(n) + g(n – 1)).

McCarthy mentioned that simultan recursive functions are possible in Lisp and that he will use them if needed^149. In important example described later (functions eval, evlis and evcon) simultan recursion is indeed used.

9.4 LAMBDA-EXPRESSIONS

Functions are usually defined before being used in expressions. For example, function is first defined by an expression like

f(x) = sin(x) + cos(x)

and then used in expressions, for example, f(3). If numbers where threated in same way, we would have to write something like

a = 3 + 4 x = 2 + a.

Under influence of Church’s lambda calculus McCarthy introduces lambda-expressions, which makes it possible to use functions in the same expression, without introducing their name. For example, lambda-expression that defines the function f is equal to

λ((x), sin(x) + cos(x))

and instead of f(3) it is written

λ((x), sin(x) + cos(x))(3).

More generally, if e is a mathematical expression, and x_1, …, x_n are variables, then expression

λ((x_1, …, x_n), e)

defines function which to n-tuple (c_1, …, c_n) assignes the value of expression e in which x_1, …, x_n has values c_1, …, c_n in order.

9.5 LABEL EXPRESSIONS

Functions can be defined recursively, with expressions in which function name appears both on left and right side of equality. For example,

fact(n) = (n = 0 → 1, T → n · fact(n − 1))

Since a recursive function on first sight calls itself, it seems at first that such function can not be defined with lambda-expressions. For that reason McCarthy introduces Rochester’s lambda-expressions, somewhat changed and renamed in label-expressions, with which even recursive functions can be defined and which can be used inside other expressions. For example, function that computes factorials can be defined with expression

label(fact, λ((n), (n = 0 → 1, T → n· fact(n − 1)))).

Function name, fact, used in the label-expression does not have value outside that label-expression. For example, in expression

label(fact, λ((n), (n = 0 → 1, T → n· fact(n − 1))))(5) + fact(10)

the second addend is not defined.

More generally, if e is a mathematical expression that contains a call to function f with n variables, x_1, …, x_n, then expression

label(f, λ(x_1, …, x_n), e))

defines function that to n-tuple (c_1, …, c_n) assignes value of expression e in which x_1, …, x_n has values c_1, …, c_n in order. Name of that function inside expression e is f.

At time of Lisp development, McCarthy, despite the inspiration form Church’s lambda calculus, never red his book to the end. If he did, he would have known that introduction of label-expression is not necessary, even though alternative function definitions without label-expressions are considerably more complex, about which McCarthy later also wrote^150.

9.6 FREE AND BOUND VARIABLES

Occurrence of variables in expressions can be divided on free and bound. For example, all occurrences of variables x and y in the expression y^2 + x are free, and in expression λ((x, y), y^2 + x) are bound. In the expression

x + λ((x), x^2)(3)

first occurrence of variable x is free, but second and third are bound.

Generally, all occurrences of variables x_1, …, x_n in λ((x_1, …, x_n),e) are bound. Other occurrences of variables in λ((x_1, …, x_n),e) are free (bound) if they are free (bound) in expression e. Occurrence of varible f in the expression label(f, λ((x_1, …, x_n), e)) is bound.

In other expressions (those that are not lambda- or label-expressions) occurrence of variables are free (bound) if they are free (bound) in sub-expressions. A trivial occurrence of a variable (for example, x is a variable in expression x) is free.

Typically, for computing an expression value it is necessary to know values of free variables. For example, for computing f(x)*f(x) it is needed to know value of x and definition of f. Sometimes expressions can be evaluated without knowing values of free variables. For example, for computing f(x)-f(x) it is only needed to know that function f is defined for value x.

9.7 REMARK ON SIMULTANEOUS RECURSIVE FUNCTIONS

McCarthy didn’t examined simultaneous recursion, more than giving it’s definition. On a first sight, it seems that simultan recursion can define some functions which are not possible to define without it. This, though, is not true. Let

f1(x_1, …, x_n) = e_1, … fk(x_k, …, x_n) = e_k.

be a system of simultaneous recursive function definitions, where e_1, …, e_k are expressions containing f_1, …, f_k. Then it is possible in entire system to substitute expressions in form

f1(a_1, …, a_n) s g(1, a_1, …, a_n), … fk(a_1, …, a_n) s g(k, a_1, …, a_n)

so that the system transforms into a recursive definition of function g

g(i, x_1, …, x_n) = {i = 1 → es_1, …, i = k → es_k}

where es_1, …, es_k are results of substitution in expressions e_1, …, e_k. Function g can be defined with label-expression. Further, functions f_1, …, f_k can be defined with non-recursive definitions

f_1(x_1, …, x_n) = g(1, x_1, …, x_n), … f_k(_xk, …, x_n) = g(k, x_1, …, x_n).

9.8 DEFINITION OF SYMBOLIC EXPRESSIONS

“Pure Lisp” has just one kind of data: symbolic expressions or S-expressions. It could be said that symbolic expressions form the foundation for Lisp, in a way that sets are foundation for mathematics. Symbolic expressions are a subset of the set of all possible sequence of symbols, chosen for the suitability to express mathematical and logical formulas.

Atomic symbols or, shorter, symbols are finite sequences of capital letters, digits and single spaces. For example, A, ABA and APPLE PIE NUMBER 3 are symbols.

A symbol sequence e is a symbolic expression if:

e is atomic symbol, or
e = (e_1·e_2) where e_1 and e_2 are symbolic expressions.

For example, (A·B) and (A·B)·XYZ) are symblic expressions, but not symbols. Symbolic expressions in form (e_1·e_2) are called ordered pairs or dotted pairs of symbolic expressions e_1 and e_2.

Sequence of symbols (e_1, e_2, …, e_n) where e_1, e_2, …, e_n are symbolic expressions is called a list of symbolic expressions e_1, e_2, …, e_n. A list (e_1, e_2, …, e_n) is an abbreviation for the symbolic expression

(e_1·(e_2 (…(e_n·NIL)…))).

For example, (A,B) is abbreviation for (A·(B·NIL)). As defined, () is abbreviation for NIL.

McCarthy calls even lists for symbolic expressions^151 which is less precise, but shorter and it does not require lot of effort to avoid confusions.

9.9 DISTINCTION BETWEEN FORMER DEFINITIONS

Definition of symbolic expressions in article from 1960. distincts itself from the previous ones. Introduced are ordered pairs, less suitable for representing mathematical and logical formulas, and expressions of form (e_1, e_2, .., e_n) are degraded to abbreviations for symbolic expressions. McCarthy didn’t explain reasons for that change, which is understandable: “old definitions” of symbolic expressions where not published and discussion of those would just confuse reader of the time.

Reasons can be alluded from the symbolic expressions definition in Memo 8. which was discarded in the paper from 1960^158.

Atomic symbols are symbolic expressions.
Nul-expression, indiated with Λ, is a symbolic expression.
If e is a symbolic expression then (e) is also a symbolic expression.
If e_1 and (e_2) are symbolic expressions then (e_1, e_2) is also a symbolic expression.

Definition from Memo 8. is not completely correct. According to this definition, for example, (A,B,C) is not a symbolic expression, which certainly was not McCarthy’s intention. A correct defintion that might correspond to McCarthy’s intention might look like this:

1’. Atomic symbols are symbolic expressions. 2’. Nul-expression (() can also be used as a notaion instead of Λ) is a symbolic expression. 4’. If e_0 and (e_1, e_2, …, e_n), n≥0, are symbolic expressions, then (e_0, e_1, e_2, …, e_n) is also a symbolic expression

Described error in Memo 8. seems as an oversight, unfinished analysis which gives us an insight in what author wanted: to define symbolic expressions so they can be built by the function cons, and not, as in “imperative Lisp”, with problematic function list.

Shortcoming of corrected function from Memo 8. is that cons could not be used on all symbolic expressions; second argument can not be a symbol. The definition from the paper from 1960. is almost sure consequence of a wish to define function cons over all pairs of symbolic expressions, and at the same time to keep lists.

Unfortunately, with the symbolic expression definition from the 1960 paper, term list become ambiguous. Lists are called sequences of symbols (e_1, …, e_n) as well as the internal representation of such mathematical expressions in memory so that sometimes it needs to be emphasized what kind of a list is in question.

9.10 META-EXPRESSIONS

As “arithemtic-expressions” are “about numbers”, so are meta-expressions (M-expressions) “about” S-expressions. McCarthy describes meta-expressions as usual mathemtical phrases, that use “conventional mathematical notation” with few important changes. Semmicolon is written instead of comma, rectangle brackets are written instead of parenthesis, it is no longer allowed with capital letters in name of functions and variables^153. Purpose of those changes is the distinction of meta-expressions from S-expressions. Notation for truth and falsehood in a meta-expression are S-expressions T and F.

Symbolic expressions are a special, trivial form of meta-expressions, similar as numbers are a trivial form of arithmetic expressions. Thus, for example, T is a symbolic expression and also a meta-expression.

9.11 S-FUNCTIONS

McCarthy defines “class” of partially defined functions over S-expressions which he calls S-functions. He defines S-functions in two steps. First, he lists five elementary S-functions. Thereafter, he shows how new S-functions can be defined with those already defined functions. There are no other S-funcions beside those mentioned above. S-functions coincide with all computable functions over S-expressions. Proof of that statement follows from ability to define Turing machines in Lisp.

9.12 ELEMNTARY S-FUNCTIONS

Elementary S-functions atom. For example,
atom[X] = T, atom[(X·Y)] = F.

value atom[x] is defined for all S-expressions x and have value T if x is atomic symbol, F otherwise. On first sight looking unusual, atom[()] = T because () is an abbreviation for NIL.

Elementary S-function eq. For example,
eq[X;Y] = F, eq[X;X] = T, eq[X;(X·Y)] is not defined.

Generally, value eq[x;y] is defined only if x and y are atomic symbols and has value T if x and y are same symbols, F otherwise.

Elementary S-function car. For example,
car[(A·B)] = A, car[(A,B,C)] = A.

Value car[e] is defined only if e is non-atomic expression, i.e. e = (x·y). Then

car[(x·y)] = x.

elementary S-function cdr. For example,
cdr[(A·B)] = B. cdr[(A,B,C)] = (B,C).

Value cdr[e] is defined only for non-atomic symbol expressions e, i.e. e = (x·y) and

cdr[(x·y)] = y.

Elementary S-function cons. For example,
cons[A;B] = (A·B), cons[A;(B,C)] = (A,B,C).

Generally, cons[x;y] = (x·y) for all S-expressions x and y.

If symbolic expressions were defined as in early versions of Lisp, the second argument would not be allowed to be a symbol.

McCarthy points out important relation between S-functions car, cdr and cons.

car[cons[x; y]] = x cdr[cons[x; y]] = y

If x is not atomic symbol, then also

cons[car[x]; cdr[x]] = x.

We could ask why McCarthy choosed those particular functions, and not some others. McCarthy himself never tried to answer that question. It is certain that McCarthy could define all functions which he tried to define in few previous months with help of those five elementary functions. We also know that all elementary functions are “computable”: for all given arguments, a human can compute value of the function. Moreover, it is possible to do it in finite time, linearly dependent in number of arguments.

Elementary functions are not independent. For example, cons can be defined with help of car and cdr:

cons[x; y] = z such that car[z]=x i cdr[z]=y.

Equally so, car and cdr can be defined with help of cons:

car[x] = z such that there exists y so that cons[z; y] = x /cdr[x] = y such that there exists z so that cons[z; y] = x

Those definitions are correct, but they don’t produce an algorithm for computing cons[x;y]. If he accepted such method of defining S-functions, McCarthy would “loose computability” of S-functions.

9.13 REMARKS WITH MCCARTHY’S S-FUNCTION DEFINING

McCarthy’s described way in wich other S-functions can be defined with help of elementary functions briefly^154 and leaves ambiguities, which are, luckily, resolved with numerous examples. For example, S-function ff is defined for all expressions and returns first element in S-expression, ignoring parantheses. Exempelwise,

ff[((A·B)·(C·D))] = A.

That S-function is defined by meta-expression

ff[e] = [atom[e] → e; T → ff[car[e]]].

More generally, S-functions are defined with meta-expressions of form

f[x1; …; xn] = e,

where f is a name of function, x_1, …, x_n are variables, e is a meta-expression build by composing s-functions, equality predicate, logic conjuctions, conditions, lambda- and label-expressions. If f is a recursive functions, then name of that functions appears also on a right side of the equality.

McCarthy suggests^155 that S-functions can also be defined with expressions like

ff = label[ff; λ[[e]; [atom[e] → e; T → ff[car[e]]]]].

More general, S-functions are defined with meta-expressions in form

f = label[f, λ[[x_1; …; x_n]; e]], / = λ[[x_1; …; x_n]; e],

where f, x_1, …, x_n and e are same as for the form /f/[x_1, …, x_n] = e.

In later texts, for example, Slagle’s dissertation^156, both ways are explicitly stated, and were supported in many if not perhaps all implementations of the language. It seems appropriate to name those two ways of defining functions in order, implicit and explicit definition of a function, terms that McCarthy didn’t use.

Defining methos for S-functions still does not comprehend all methods used in mathematics. For example, the expression

/f/[x] = [[∃y][cons[y; y] = x] → T, T→ F]

can not be used to define a S-function. Common to all methods which can be used to define S-functions is that they are constructive, i.e. a definition of S-function also gives the procedure wich can be used to compute the value of that function, if such a value exists.

It is important to note that same S-function can be defined with different meta-expressions. For example, function ff can also be defined with expression

ff = label[ff; λ[[e]; [atom[e] → e; T → ff[car[e]]]]]

as well as with expression

ff = label[ff; λ[[e]; [~atom[e] → ff[car[e]]; T → e]].

14 EXAMPLES OF NON-ELEMNTARY S-FUNCTIONS

McCarthy cites numerous examples of S-functions. Examples are important because they show the style in which Lisp programmers think, and clarify of the authors intentions.

S-functions caar, cadr, cdar, cddr, caaar, caadr … are all defined with

meta-expressions

caar[x] = car[car[x]], cadr[x] = car[cdr[x]], cdar[x] = cdr[car[x]], ··· For example,

cadr[(A,B,C)] = car[cdr[(A,B,C)]] = car[(B,C)]= B.

McCarthy also calls S-functions caar, cadr, cdar, cddr, caaar, caadr … for “abbreviations”.

S-function ff. Value ff/[e] is the first element in S-expression /e, ignoring

parentheses. For example

/ff/[((A·B)·(C·D))] = A.

S-function ff is defined by meta-expression

ff[e] = [atom[e] → e; T → ff[car[e]]].

S-functions subs. Value subst[x;y;z] is result of “substituting” expression x in every occurrence of atomic symbol y in expression z. For example,
subst[(A·B); C; ((C·D)·E)] = (((A·B)·D)·E).

S-function subst is defined by meta-expression

subst[x; y; z] = [atom[z] → [eq[z; y] → x; T → z]; T → cons[subst[x; y; car[z]]; subst[x; y; cdr[z]]]].

S-function equal. Value equal[x; y] is defined for all symbolic expressions x and y and equals T if a given x and y are same S-expression, symbol for symbol, F otherwise. For example,
equal[(A·B); (A·B)] = T.

S-function equal is defined by meta-expression

equal[x; y] = [[atom[x] ∧ atom[y] ∧ eq[x; y]] ∨ ~atom[x] ∧ ~atom[y] ∧ equal[car[x]; car[y]] ∧ equal[cdr[x]; cdr[y]]]].

S-function null. Value null[x] is T if x equals NIL; F otherwise. S-function null is defined by meta expression
null[x] = atom[x] ∧ eq[x; NIL].
S-function append. For example,
append[(A,B,C); (A,C,A)] = (A,B,C,A,C,A).

S-function append is defined by meta-expression

append[x; y] = [null[x] → y; T → cons[car[x]; append[cdr[x]; y]]].

S-function among. Value among[x; y] is T if x occures as a list element of list y; F otherwise. For example,
among[X; (A,B,X,C)] = T.

S-function among is defined by meta-expression

among[x; y] = [~null[y] ∧ [equal[x; car[y]] among[x; cdr[y]]]].

S-function pair. For example,
pair[(A,B,C); (X,(Y,Z),U)] = ((A,X),(B,(Y,Z)),(C,U)).

S-function pair is defined by meta-expression

pair[x; y] = [null[x] ∧ null[y] → NIL; ~atom[x] ∧ ~atom[y] → cons[list[car[x]; car[y]]; pair[cdr[x]; cdr[y]]]]

where list[x; y] is an abbreviation for cons[x; cons[y; NIL]] = (x,y).

S-funcion assoc. Variables are often associated values, for example, x = b,

y = sin b. Information about associations can be encoded with S-expressions like ((X,B),(Y,(SIN,B))). Value assoc[s; a] is an expression associated with symbol s in the association list a; first one if there are multiple such associations. For example,

assoc[X;((X,B),(Y,(SIN,B)),(X,C))] = A.

S-function assoc is defined by meta-expressions

assoc[x; y] = [eq[caar[y]; x] → cadar[y]; T → assoc[x; cdr[y]]]

If S-expressions are defined as single linked lists, then computing value of S-function assoc is in some cases innefficient for reasons that McCarthy warned about in the first memmo: for example, for computing

/assoc/[X,((A,e_1),(B,e_2),…,(Z,e_26))]

has to call itself 23 times.

S-function sub2. Value sub2[x; y] is the first symbol in association list x

associated with y. If such symbol does not exist, it remains y.

sub2[((X,A),(Y,(B,C)),(Z,D)); Y] = (B,C), sub2[((X,A),(Y,B)); Z] = Z

S-function sub2 is defined by meta-expression

sub2[a; x] = [null[a] → x; eq[caar[a]; x] → cadar[a]; /T → sub2[cdr[a]; x]].

S-function sublis. S-fucntin sublis is a generalization of sub2; value sublis[x; y] is a result of substituting atomic symbols in S-expression y with values associated in list x. For example
sublis[((X,(A,B)),(Y,(B,C))); (A,(X·Y))] = (A,((A,B)·(B,C))).

S-functin sublis is defined by meta-expression

sublis[a; x] = [atom[x] → sub2[a; x]; T → cons[sublis[a; car[x]]; /sublis[a; cdr[x]]]].

S-fucntions first, rest, second, third … Despite McCarthy giving up on attempt to change names car, cdr and cons with first, rest and combine nothing stops from defining those functions.
first[l] = car[l] rest[l] = cdr[l]

Analogous, often are also defined functions

second[l] = cadr[l] third[l] = caddr[l] …

9.15 ABBREVATION AND FUNCTION LIST

McCarthy also introduces the important function and abbreviation list.^157. For example

list[A; B; (A,B); C] = (A,B,(A,B),C).

Function is defined by expression

/list/[e_1; …; e_n] = cons[e_1; cons[e_2; …; cons[e_n; NIL]…]].

Definition is mathematically correct, but it differs from the previous ones: it contains three dots - which can not be removed because list has to be defined for arbitrary number of arguments. From that follows that list is not an S-function, despite McCarthy not writing it out explicitly. Still, list can be used in meta-epressions as an abbreviation, as long is at can be substituted by repeated use of funcion cons.

9.16 FUNCTIONS AS LIST ARGUMENTS

McCarthy points out that we can define many “useful” functions which takes other functions as arguments. He lists example of function maplist which for list the (l_1, l_2, …, l_n) and function f assignes list

(f[(l_1, l_2, …, l_n)], f[(l_2, …, l_n)], …, f[(l_n)]).

For example

maplist[(A,B,C); λ[[x]; x]] = ((A,B,C),(B,C),(C)).

Definition of maplist is

maplist[l; f] = [null[l] → NIL; T → cons[f[l]; maplist[cdr[l]; f]]].

Functions that takes other functions as agruments are specially useful for defining other functions, which McCarthy shows with example of a function of two variables, dff. Value, diff[y;x] is a derivation of expression y in variable x. Expression y can be an atomic symbol or a symbolic expression in form (PLUS, e_1, …, e_n) or (TIMES, e_1, …, e_n), where e_1, …, e_n are symbolic expressions which can be first argumnets to function diff.

Second argument of function diff is a symbol on which to differentiate.

diff[y; x] = [atom[y] → [eq[y; x] → ONE; T → ZERO ]; eq[car[y]; PLUS] → cons[PLUS; maplist[cdr[y]; λ[[z]; diff[car[z]; x]]]]; eq[car[y]; TIMES]] → cons[PLUS; maplist[cdr[y]; λ[[z]; cons[TIMES; maplist[cdr[y]; λ[[w]; [~eq[z; w] → car[w]; T → diff[car[w]; x]]]]]]]]]

9.17 REMARK ABOUT ABBREVATION ELEMINATION AND NON-ELEMENTARY S-FUNCTIONS

While defining new functions, it is possible to use previously defined non-elementary S-functions. Despite McCarthy not stating it explicitly, for understanding later McCarthy’s definitions it is important to note that every S-function definable by abbreviations, predicate operators and names of previously defined non-elementary functions, can also be defined without those elements. For example, from the definition

pair[x; y] = [[null[x] ∧ null[y]] → NIL; [~atom[x] ∧ ~atom[y]] → cons[list[car[x]; car[y]]; pair[cdr[x]; cdr[y]]]]

we can eleminate operators ∧ and ~ as well as abbreviation list. We get function

pair[x; y] = [[null[x] → null[y]; T → F] → NIL; [[atom[x]→F; T→T] → [atom[y] → F; T →T ]; T → F] → cons[cons[car[x]; cons[car[y]; NIL]]; pair[cdr[x]; cdr[y]]]].

S-function null “has” M-expression

λ[[x]; atom[x] ∧ eq[x; NIL]]

from which by elimination of logical conjuction ∧ is derived

λ[[x]; [atom[x] → eq[x; NIL]; T → F]].

If that expression is inserted instead of null in defintion pair we obtain

pair[x; y] = [[λ[[x]; [atom[x] → eq[x; NIL]; T → F]][x] → λ[[x]; [atom[x] → eq[x; NIL]; T → F]][y]; T → F] → NIL; [[atom[x] → F; T→T]→[atom[y] → F; T → T]; T → F] → cons[cons[car[x]; cons[car[y]; NIL]]; pair[cdr[x]; cdr[y]]]]

Final defination for the function pair, far less understandable, is ekvivalent to the starting one and does not contains names of non-elementary functions nor abbreviations.

Functions that are defined by simultaneous recusion could be eliminated first after substituting simultaneously recursive functions by previosly described functions or some other equivalents, but not with simultaneous recursive definitions.

By naive elemination of call to previously defined functions by insertion of according lambda- or label-expressions, original function definition can be made exponentially larger. For example, let

f_0[x] = cons[f_1[x]; f_1[cons[x; x]]] f_1[x] = cons[f_2[x]; f_2[cons[x; x]]] … f_n − 1[x] = cons[f_n[x]; f_n[cons[x; x]]].

and finally

f_n[x] = x.

By inserting f_1 in defintion f_0 we obtain

f_0[x] = cons[cons[f_2[x]; f_2[cons[x; x]]]; /cons/[f_2[cons[x; x]]; f_2[cons[cons[x; x]; cons[x; x]]]]]

in which f_2 appears four times, and if we continue with such inserting, function f_n would occur 2^n times. Method used for eliminating simultaneously recursive definitions can be used here as well. Instead of defining n functions in one variable, we should define one function in two variables

[i; x] = [i = 0^* → f_0[x]; … i = n^* → f_n[x]],

where 0^*, …, n^* are some S-expressions. Now we can insert definitions of functions f_0, …, f_n and in obtained expression substitue all calls f_i[x] with f[i;x]. Obtained is recursive definition for function f. From that definition, f can be defined by a label expression label[f;λ[[i; x]…]] and from f_0[x]=f[0^*; x] comes

f_0 = λ[[x]; label[f; λ[[i; x]…]][0^*; x]].

There is not much differences if functions f_0, …, f_n are functions in several variables.

9.18 TRANSLATION OF M-EXPRESSIONS INTO S-EXPRESSIONS.

Translations of meta-expression e into S-expression is denoted by e^*. There are six rules for translation, depending on which kind translated meta-expression is.

Symbolic expressions. If e is a symblic expression, then e^* = (QUOTE, e). For example,
T^* = (QUOTE,T).
Name of functions and variables. If e is function or variable name then e^* is also a name, with small letters just being capitalized. For example,
xyz^* = XYZ.
S-fucntion application. Let f/[e_1; …, e_n] be applied S-function; /f is function name or expression which defines the function. Then,
/f/[e_1; …; e_n]^* = (f^*,e_1^*, …, e_n^*).

For example,

cons[T; xyz]^* = (CONS,(QUOTE,T),XYZ), λ[[x]; cons[x; x]][A]^* = (λ[[x]; cons[x; x]]^*,(QUOTE,A))
Conditional expression. Let [p_1 → e_1; …; p_n → e_n] be a conditional expression, where p_i and e_i are any meta-expressions. Then
[p_1 → e_1; …; p_n → e_n]^* = (COND,(p_1^*,e_1^*),…,(p_n^*,e_n^*)).

For example,

[eq[z; y] → x; T → z]^* = (COND,((EQ,Z,Y),X), ((QUOTE,T),Z)).

The rule for conditional expression translation was later criticized by McCarthy because it leads to big number of parentheses.^158
Lambda-expressions. Let λ[[x_1; …; x_n], m] be a lambda expression; x_1; …; x_n any variables, m any meta-expression.
λ[[x_1; …; x_n]; m]^* = (LAMBDA,(x1^*,…,x_n^*),m^*).
Label-expressions. Let label/[ /a; m] be a label-expression, a name of a function, m lambda expression. Then,
label/[ /a; m ]^* = (LABEL,a^*,m^*).

For example,

/label/[f; λ[[e]; [atom[e] → e; T → f[car[e]]]]]

is translated into S-expression

(LABEL,(F,(LAMBDA,(E), (COND,((ATOM,E),E), ((QUOTE,T),(F,(CAR,E))))))).

Somewhat larger M-expression

label/[ /subst; λ[[x; y; z]; [ /atom/[z] → [eq[z; y] → x; T → z]; T → cons[subst[x; y; car[z]]; subst[x; y; cdr[z]]]]]]

is translated into S-expression

(LABEL,SUBST, (LAMBDA,(X,Y,Z), (COND,((ATOM,Z),(COND,((EQ,Z,Y),X), ((QUOTE,T),Z))), ((QUOTE,T),(CONS,(SUBST,X,Y,(CAR,Z)), (SUBST,X,Y,(CDR,Z))))))).

McCarthy was reserved about readability of such, in S-expression translated M-expressions¹⁵⁹, partially perhaps because he still didn’t accepted Rochester’s formatting by indenting lines. For example, the above expression is written in original as:

(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, (EQ,Y,Z),X),((QUOTE, T),Z))),((QUOTE,T),(CONS,(SUBST,X,Y, (CAR,Z)),(SUBST,X,Y,(CDR,Z))))))).

9.19 REMARKS ABOUT M-EXPRESSION TRANSLATION

It seems reasonable to introduce notion of “symbolic expressions assigned to functions” about which McCarthy didn’t write, but which are natural and useful analogy to meta-expressions assigned to functions, and which will be needed in chapter about S-functions and computation theory. S-expression assigned to function h, denoted by h⁽s⁾ should be a translation of meta-expression assigned to function h. For example,

list1 = λ[[x]; cons[x; NIL]] list1⁽s⁾ = (LAMBDA,(X),(CONS,X,(QUOTE,NIL))).

Further, despite McCarthy not writing about it, not all meta-expressions can be translated into symbolic expressions in described way. A wide class of meta-expressions which McCarthy didn’t use while defining S-expressions, such as

[[∃y][ cons [y; y] = x] → T, T→ F] are not translatable, because instructions for their translation are not given. This restriction is not result of limit of the idea of meta-expression translation into S-expressions, but just of McCarthy being interested exclusively into translating only meta-expressions which define S-expressions. If some particular program needs to translate some other meta-expressions, it is possible to introduce new rules for translation.

Even meta-expressions which usually define functions, in form of

f/[x_1; …; x_n] = /e

can not be converted, since there is no rule to convert equality. But, meta-expression on the right side of the equality, e is usually convertible. Convertible are also meta-expressions in form of

λ[[x_1; …; x_n]; e] label[f, λ[[x_1; …; x_n]; e]]

for concrete variables x_1, …, x_n and e. Important exception is list which definition

/list/[e_1; …; e_n] = cons[e_1; cons[e_2; …; cons[e_n; NIL]…]]

is not convertible because the right side of equality, and thus belonging label-expression contain tre dots which are not possible to remove, for which also, a conversion rule is not given.

Meta-expressions which contain conjuctions are not convertible. If conjuctions are replaced with equivalent conditional expressions, obtained meta-expressions are convertible.

It is important to note that rules for converting meta-expressions can be broaden, and thus make it possible to convert larger class of meta-expressions into S-expressions. Truly, in later Lisp development, this was done. For example, definitions in form of f/[x_1; …; x_n] = /e were converted with (DEFINE,f^*,(x_1^*,…,x_n^*),e^*).

We can ask if it is possible to convert all meta-expressions (also, all mathemtical expressions), with some set of rules into symbolic expressions. It seems that it is; the author of this book does not know of any mathematical expression that couldn’t be translated into a symbolic expression.

Non-atomic S-expressions which are not “reducible” to list form or to a nested list, for example, (A·B), are not a translation of some meta-expression. The exception are S-expressions in which non-reducible parts are inside a list of form (QUOTE, e). For example, (QUOTE,(A·B)) is conversion of meta-expression (A·B).

9.20 MATHEMATICAL DEFINITION OF S-FUNCTION EVAL

Some meta-expressions have a value. For example cons/[A; (B)] has value (A,B). Meta-expression /f/[ /x; (B) ] has a value only if f and x have values. Implemented Lisp-system should compute values of meta-expressions instead of humans.

McCarthy defines S-function eval which, although, not computing values of meta-expressions, does something similar: it computes values of converted M-expressions.

S-function eval takes two arguments:

symbolic expression obtained by converting M-expression and
list of variable pairs and function names and their values. That list is in Lisp literature called association list.¹⁶⁰

Let, for example, x = (A) and y = (B). Then computing cons/[x;y] can be reduced to applying function /eval.

/cons/[x; y] = eval[(CONS,X,Y);((X,(A)),(Y,(B)))].

Computing value of meta-expression append/[x;y] is possible if we add to the list of pairs also definition of non-elementary S-function /append. That S-function “has M-expression”

label[append; λ[x; y][null[x] → y; T → cons[car[x]; append[cdr[x]; y]]]]

in which is also used S-function null “whose M-expression” is, if we eliminate conjuction ∧,

λ[[x]; [atom[x] → eq[x; NIL]; T → F]].

Then

append[x; y] = eval[(APPEND,X,Y); ((X,(A)), (Y,(B)), (APPEND, (LABEL,APPEND, (LAMBDA,(X,Y), (COND,((NULL,X),Y), ((QUOTE,T), (CONS,(CAR,X), (APPEND,(CDR,X),Y)))))), (NULL,(LAMBDA,(X), (COND,((ATOM,X),(EQ,X,NIL)), ((QUOTE,T),(QUOTE,F))))))].

Generally, let e be a convertible meta-expression, x_1, …, x_n are “free variables” whose values are S-expressions s_1, …, s_n, and f_1, …, f_k are names of non-elementary functions whith meta-expressions, m_1, …, m_k. If, on basis of given data, it is possilbe to compute value e then that value is

/eval/[e^*; ((x_1^*,s_1),…,(x_n^*,s_n),(f_1^*, m_1^*),…,(f_n^*,m_k^*))].

Value eval/[e;a] is defined depending on the form of /e.

Symbols. S-function eval is reduced to assoc. For example,
eval[X; ((X,B))] = assoc[X; ((X,B))] = B.

Generally, if e is symbol, then

eval[e; a] = assoc[e; a].

Quote-expressions. S-functions eval and quote cancel each other. By example,
eval[(QUOTE,Y); ((Y,B))] = (Y).

Generally, if e = (QUOTE, e_0) then

eval[e; a] = eval[(QUOTE,e_0); a] = e_0.

Atom-expressions. Eval is reduced to S-function atom. For example,
eval[(ATOM,X); ((X,A))] = atom[eval[X; ((X,A))]].

Generally, if e = (ATOM e_0) then

eval[e; a] = eval[(ATOM,e_0); a] = atom[eval[e_0; a]].

Eq-expressions. For example,
eval[(EQ,X,(QUOTE,A));a] = eq[eval[X; a]; eval[(QUOTE,A); a]].

Generally, if e = (EQ, e_1, e_2), then

eval[e; a] = eval[(EQ,e_1, e_2); a] = eq[eval[e_1; a];eval[e_2; a]].

Cond-expressions. For example,
eval[(COND,((CAR,A),A),((CDR,B),B)); a] = = [eval[(CAR,A); a] → eval[A; a]; eval[(CDR,B); a] → eval[B; a]].

Generally, if e = (COND,(p_1, e_1),…,(p_n, e_n)) then

eval[e; a] = eval[(COND,(p_1, e_1),…,(p_n, e_n));a] = = [eval[p_1; a] → eval[e_1; a]; …; eval[p_n; a] → eval[e_n; a]].

Car-expressions. For example,
/eval/[(CAR,(QUOTE,(A,B)));a] = car[eval[(QUOTE,(A,B));a]

Generally, if e = (CAR,e_0) then

eval[e; a] = eval[(CAR,e_0); a] = car[eval[e_0; a]].

Cdr-expressions. For example,
eval[(CDR,(QUOTE,(A,B))); a] = cdr[eval[(QUOTE,(A,B)); a].

Generally, if e = (CDR,e_0) then

eval[e; a] = eval[(CDR,e_0); a] = cdr[eval[e_0; a]].

Cons-expressions. For example,
eval[(CONS,(QUOTE,(A,B)),(QUOTE,(C,D))); a] = = cons[eval[(QUOTE,(A,B)); a]; eval[(QUOTE,(C,D)); a]].

Generally, if e = (CONS,e_1, e_2) then

eval[e;a] = eval[(CONS,e_1, e_2); a] = cons[eval[e_1; a];eval[e_2; a]].

S-expressions whose car is a lambda expression. For example,
eval[((LAMBDA,(X),(APPEND,X,X)),(QUOTE,(Y)));()] = = eval[(APPEND,X,X); ((X,(Y)))].

Generally, if e = ((LAMBDA,(x_1, …, x_n), e_0), e_1, …, e_n) then

eval[e; a] = eval[((LAMBDA,(x_1, …, x_n),e_0),e_1, …, e_n); a] = = eval[e_0; append[((x_1, eval[e_1; a]),…,(x_n, eval[e_n; a])); a]].

S-expressions whose car is a label-expression. For example,
eval[((LABEL,F,(LAMBDA,(X),(F,X))),Y); ()]= = eval[((LAMBDA,(X),(F,X)),Y);((F,(LAMBDA,(X),(F,X))))].

Generally, if e = ((LABEL,f,l),e_1, …, e_n) then

eval[e; a] = eval[((LABEL,f,l), e_1, …, e_n); a] = = eval[(l, e_1, …, e_n); append[((f,l)); a]].

S-expression whoce car is a symbol. For example,
eval[(F,A);((F,(LAMBDA,(X),X)))] =

= eval[((LAMBDA,(X),X),A);((F,(LAMBDA,(X),X)))].

Generally, if e = (s,e1,…,en), where s is a symbol, then

eval[e; a] = eval[(s, e_1, …, e_n); a] = eval[(assoc[s; a], e_1, …, e_n); a].

9.21 S-FUNCTION EVAL

Previous description is enough for mathematically correct definition of function eval. Anyway, McCarthy defined eval same as most of other non-elementary S-functions, by meta-expression which uses conditional expression to include all different cases. Definition of eval function in the memo, and also in all other internal documents that preceded it, contains obvious, but non-important errors that were wrote about by Jordan^161, Stoyan^162 and Graham^163. Errors were corrected in definition

eval[e; a] = [atom[e] → assoc[e; a]; atom[car[e]] → [eq[car[e]; QUOTE] → cadr[e]; eq[car[e]; ATOM] → atom [eval[cadr[e]; a]]; eq[car[e]; EQ] → eq[eval[cadr[e]; a]; eval[caddr[e]; a]]; eq[car[e]; COND] → evcon[cdr[e]; a]; eq[car[e]; CAR] → car[eval[cadr[e]; a]]; eq[car[e]; CDR] → cdr[eval[cadr[e]; a]]; eq[car[e]; CONS] → cons[eval[cadr[e]; a]; eval[caddr[e]; a]]; T→ eval[cons[assoc[car[e]; a]; cdr[e]^164]; a]]; eq[caar[e]; LABEL] → eval[cons[caddar[e]; cdr[e]]; cons[list[cadar[e]; car[e]]; a]]]; eq[caar[e]; LAMBDA] → eval[caddar[e];append[pair[cadar[e];evlis[cdr[e]; a]]; a]]].

Used are also some “abbreviations” card, caddr, caddar, … as well as list. Helping S-functions evcon, which which serves for calculation of conditional expressions, and evlis which applies eval “inside a list” are defined as

evcon[c; a] = [eval[caar[c]; a] → eval[cadar[c]; a]; T → evcon[cdr[c]; a]]

evlis[m; a] = [null[m] → NIL; T → cons[eval[car[m]; a]; evlis[cdr[m]; a]]].

Function eval applies “computational strategy” today known as “call by value” for all function calls. Arguments to the function are calculated before function is applied. Quote-expressions and cond-expressions are calculated without previous calculation of the arguments.

9.22 REMARKS ALONG THE DEFINITION OF EVAL FUNCTION

Lisp defined inside eval function is different from the Lisp with which eval itself is defined. This is not just about syntax, symbolic expressions instead of meta-expressions. “Inside” Lisp has operator QUOTE, which is used when defining S-functions. “Outer” Lisp accepts a line of function definitions in implicit or explicit form, and then make them avialable for calculating expressions that use those functions. “Inside” Lisp requires all previously defined functions to be passed in the second argument, in the form of

(f^*,(LAMBDA,(x_1^*,…,x_n^*),e^*))

Where f is function name, x_1, …, x_n are symbols and e expression. Here, if function f is recursive, it is not needed to use label-expressions. For example, call to function

/eval/[(APPEND,X,Y); ((X,(A)), (Y,(B)), (APPEND,(LABEL,APPEND,(LAMBDA,(X,Y),…))), (NULL,(LAMBDA,(X),…))) ],

is, considering how computation of label-expression is defined, computed somewhat more complex, but has same value as

/eval/[(APPEND,X,Y); ((X,(A)), (Y,(B)), (APPEND,(LAMBDA,(X,Y),…))), (NULL,(LAMBDA,(X),…))) ].

There are some differences between McCarthy’s eval and one in most contemporary implementations of the language. A programmer probably does not expect that

/eval/[(P,(QUOTE,(A,B))); ((P,Q),(Q,CAR))] = = /eval/[(Q,(QUOTE,(A,B))); ((P,Q),(Q,CAR))] = = /eval/[(CAR,(QUOTE,(A,B))); ((P,Q),(Q,CAR))] = = /car/[(QUOTE,(A,B))] = = A.

In Mccarthy’s Lisp implementation, computing (P, (QUOTE, (A,B))) would surely ended by error repport such as “Q is not an operator.” Despite, it can not be stated that this is an error in original eval. If we reason about M-expressions as a special sort of mathematical expressions, then from p = q and q = car follows that p[x] = car[x].

McCarthy’s eval does not process correctly expressions in which a function argument is a lambda-expression or label-expression. For example,

/eval/[(ATOM,(LAMBDA,(X),X)); a] = = /atom/[eval[(LAMBDA,(X),X); a]] = = /eval/[cons[assoc[ LAMBDA; a]; ((X),X)]; a]].

While computing assoc/[ *LAMBDA*; /a ] there would be en error. McCarthy has simply forgotten lambda- and label-expressions in this place. He returned to that problem only after three years.^165

Another possible, and according to many important error in eval definition, is ignoring possibility of using lambda-expression parameters in association lists, among other responsible for the “funarg problem”.^166

It is often stated that eval defines “formal”^167 or “operational”^168 Lisp semantics.

To many readers, encounter with function eval represents a very plesant surprise. Enthusiasm about eval was expressed by, for example, Smalltalk author Alan Kay^169, Eiffel author Bertrand Meyer^170 and Paul Graham.^171 Despite this, it is not easy to understand why eval leaves this impression. Very respected Edsger W. Dijkstra denied the value of so defined interpreter.^172

9.23. UNIVERSAL S-FUNCTION APPLY

After exampel of universal Turing machine, McCarthy defined function apply which can substitute any other S-function, if it is given that other function as an argument. For example,

/cons/[A; (B,C)] = /apply/[CONS; (A,(B,C))].

λ[[x; y]; /cons/[y; x]][(A); B] = /apply/[ (LAMBDA,(X,Y), (CONS,Y,X)); ((A),B)].

Generally, let f be a name of S-function that “has meta-expression” m without abbreviations, logical conjuctions and calls to non-elementary functions. Then for all S-expressions e_1, …, e_n holds

f[e_1; …; e_n] = apply[m^*; (e_1 ,…, e_n)].

S-function apply can be defined with help of S-function eval. For example,

/apply/[CONS; (A,(B,C))] = /eval/[(CONS,(QUOTE,A), (QUOTE,(B,C))); ()].

Generally,

/apply/[f; args] = apply[f; (args1,…,argsn)] = = /eval/[(f,(QUOTE,args1),…,(QUOTE,argsn)); ()] = = /eval/[cons[f; appq[args]]; ()]

where

/appq/[l] = [null[l] → NIL; T → /cons/[list[QUOTE; car[l]]; /appq/[cdr[l]]]].

S-function apply does not allow for the use of “surrounding” as it is used by eval. If a function f is defined by a meta-expression m in which are used names of previously defined, non-elementary S-functions, apply will not work. For that reason it is necessary to eliminate calls to help functions.

9.24 LISP INTERPRETER

Programmer Russell realized that implementation of eval in machine language gives a simple and useful interpreter for Lisp. That idea surprised McCarthy himself who didn’t believe in it’s practical value.^173,174 McCarthy’s suspicion appeard to Stoyan as improbable.^175

An interpreter for a programming language written in the language itself is usually called “meta-cirkular evaluator”. That term, as it seems, was coined by John C. Reynolds, 1972.^176 McCarthy’s eval is not first meta-cirkular evaluator; it was preceded by Böhm’s^177, and even earlier by Turing’s machine.^178

At the time of creation of “pure Lisp”, McCarthy saw S-function apply as the interpreter.^179,180 Only, quite later did he started to call S-function eval the interpreter for Lisp.^181,182

Russel managed to implement eval which made possible for programmers to write programs in form of S-expressions.^183

9.25. S-FUNCTIONS AND COMPUTABILITY THEORY

McCarthy supported idea that S-functions are suitable basis not just for a programing language, but also as a mean for development of computability theory.^184 There are three reasons for this: simple expression of recursive functions on symbolic expressions as symbolic expressions, which renders “artificial” constructions like Turing machines and Gödel’s numbers unnecessary.^185 Second, simple and effective computations of interesting S-functions with help of a computer. Finally, use of conditional expressions significantly simplifies recursive functions.

Basic results of theory of computable functions are, according to McCarthy

Turing’s thesis, an argument about every effectively computable process representable by the Turing machine.
Existence of an universal Turing’s machine that can simulate work by all other Turing machines.
Proof of non-existence of a Turing machine that computes if every Turing machine will terminate.

The universal S-function was given in addendum; it is the S-function apply. Instead of claim that every effectively computable process can be represented by a S-function, McCarthy proofs that every Turing machine can be simmulated by S-function. Finally, he also gives an independent proof that there is not such S-function that computes if a S-function is defined for a given set of arguments.

9.26 SIMULATION OF TURING MACHINES WITH S-FUNCTION

McCarthy defines S-function turing^186,187 which “simulates” work of Turing machine. The definition is very direct, with just few help functions, presented here is the version from RLE QPR 053, with minor corrections and simplifications.

Definitions of Turing machines appear in literature with minor differences, McCarthy’s version being very typical.

IMAGE 11. Scheme of a Turing machine. State of machine is β. Value of tape field under the reading and writing head is C.

Turing machines have two kind of memory, s.c. machine state and tape. During the work, the machine is always in one of the finite number of states. The machine state changes according the “instructions” which are also part of the definition of a Turing machine.

The tape is one dimensional, infinite on both sides and divided into fields. At each field on the tape can be written one of finite many signs. Despite the tape being infinite, in every moment, a sign is written only on finite many fields. Other fields are empty. By agreement, an empty field can be understood as if a special sign, “blank”, is written on it. Turing machine has a “head” which is mounted over only one field and can read and write signs only on the field below the head, and thus the tape can be moved only left or right on the track. The head of the machine can be moved only one field left or right, in accordance to instructions.

Functioning of a Turing machine is defined by a finite, unchengable stream of instructions in form of

“If state of machine is x_1 and sign under the reading head is y_1 the change state of the machine in x_2 write sign y_2 on the tape and move the head in direction d.”

The machine stops the execution if there is no such instruction that describes what to do for a given combination of machine state and the sign under the head. The tape content after the execution ends, is the result of machine execution.

S-function that simulates Turing machines. To show that all functions computable by a Turing machines are also computable by S-functions, McCarthy defines S-function turing. Call to function

/turing/[machine; tape]

is defined for S-expression machine which represents a Turing machine and S-expression tape that represents the tape of Turing machine. the value of the call is S-expression that represents tape configuration in moment of stopping, if the Turing machine terminates.

The representation of a Turing machine. A Turing machine is represented by a Symblic expression

(initial-state,instruction_1, …, instruction_n),

where initial-state is a symbol representing the initial state of the machine, and instruction_i, i = 1, …, n, n≥0, are quintuples representing instructions of a Turing machine.

Representing instructions of Turing machines. Quintuple instruction_i in form

(current-state_i, current-symbol_i, new-symbol_i, direction_i, new-state_i)

represents instruction

“If the state of a machine is current-state_i and current-symbol_i is under the head then write new-symbol_i to the tape, move the head in direction direction_i and change the state of the machine to new-state_i.”

For example, the Turing machine that moves to the left-most field on the tape, and computes the parity of numbers 1 on the tape

ignoring zeros, until it encounters an empty field is represented by the S-expression

(0,(0,0,B,R,0),(0,1,B,R,1),(0,B,0,R,2), (1,0,B,R,1),(1,1,B,R,0),(1,B,1,R,2)).

Representating the tape of a Turing machine. Tape of a Turing machine is represented by a symbolic expression in form of

(current-symbol,left-part,right-part),

where current-symbol represents a sign written on the tape under the current position of head for reading, left-part is a list of symbols that represent the part of the tape to the left of the machine head, and right-part is a list of symbols representing the part of the tape to the left of the machine head. Rest of the fields on the tape are empty.

IMAGE 12. Example of a Turing machne tape.

For example, tape of the Turing machine in image 12 with highlighted place over which the reading and writing head resides is represented by symbolic expression (0,(1,0,1,1),(1,1,0)).

Help S-function find. Call to S-function

/find/[current-state; current-symbol; instructions],

is defined for symbols current-state which represents the state of the machine, current-symbol which represents the sign below the head of the Turing machine, and a list of instructions which represents a set of instructions. Call to S-function has value

(new-symbol,direction,new-state),

a triple which describes what given Turing machine has to execute next. Function find is defined by the meta-expression

find[current-state; current-symbol; instructions] = [null[instructions] → NIL; [first[first[instructions]] = current-state ∧ second[first[instructions]] = current-symbol] → third[first[instructions]]; T → find[current-state; current-symbol; rest[instructions]]].

where functions first, rest, second, third are equivalent to functions car, cdr, cadr, caddr.

Representing configuration of a Turing machine. Turing machine configuration consists of the changeable elements of Turing machine during the execution: the state of the machine, the tape and the position of the head on the tape. It is represented by the S-expression

(current-state,current-symbol,left-part,right-part),

where current-state represents the current state of the machine, current-symbol, left-part and right-part are same as in S-expression representing the tape of a Turing machine.

Help S-function successor. Call to function

/successor/[machine; configuration]

is defined for every S-expression machine in form

(initial-state,instruction_1, …, instruction_n)

which represents a Turing machine and every S-expression configuration which represents configuration of a Turing machine. Value of the function call is the following configuration created during the execution of Turing machine, NIL if such does not exist, i.e. if the machine is terminated. For clearer definition exposition, some abbreviations are used which McCarthy originally didn’t use; todo is an abbreviation for meta-expression

find[first[configuration]; second[configuration]; rest[machine]]

which has value (new-symbol, direction, new-state), a tripple which describes what machine should do next;

current-tape is an abbreviation for meta-expression

rest[configuration]

which has value (current-symbol, left-part, right-part) which represents the state of the tape. S-function successor is defined by meta-expression

successor[machine; configuration] = [todo = NIL → NIL; T→cons[third[todo]; [second[todo] = L → list[first[second[current-tape]]; rest[second[current-tape]]; cons[first[todo];third[current-tape]]]; second[todo] = R → list[first[third[current-tape]]; cons[first[todo];second[current-tape]]; rest[third[current-tape]]]]]].

If values for abbreviations are substituted in, the “real definition” is obtained, considerably more complex then this.

Help S-function tu. Call to function

/tu/[machine; configuration]

(current-state, current-symbol, left-part, right-part),

is defined for symbolic expression machine which represents a Turing machine and symbolic expression configuration which represents a configuration of the Turing machine, if that corresponding Turing machine terminate. The value of the call represents the state of the Turing machine after the termination. S-function tu is defined by meta-expression

tu[machine; configuration] = [successor[machine; configuration] = NIL → rest[configuration]; T → tu[machine; successor[machine; configuration]]].

S-function turing. Call to function

/turing/[machine; tape]

calculates end state of a Turing machine represented with S-expression machine applied to a tape represented with symbolic expression tape. S-function turing is defined by meta-expression

turing[machine; tape] = tu[machine; cons[first[machine]; tape]].

McCarthy show not only how individual Turing machines can be encoded into S-functions that simulates them, but he also defined S-function that simulates all Turing machines.

9.27 QUESTIONS ABOUT S-FUNCTIONS NON-DECIDABLE WITH S-FUNCTION

McCarthy proofs, similarly as in other computing theories, that some important questions about S-functions can not be decided by S-functions. His proof is in addendum slightly simplified and somewhat more precisely decribed then in the original.

Let denote h^(S) a translation of meta-expression assigned to a function h. For example,

list1 = λ[[x]; cons[x; NIL]] list1^(S) = (LAMBDA,(X),(CONS,X,(QUOTE,NIL))).

We can say for S-function h that it is a selfapplyable if the value h/[h^(s)] is defined. For example, /car is not selfapplyable; λ[[x]; car[x]] is. We could ask if selfapplyability can be described with a S-function. More precisely, does a S-function selfapplyable exists, with property

selfappliable[h(S)] = T if h[h^(S)] is defined F if h[h^(S)] is not defined

Let us suppose that it exists. Then we can also define S-function contra

contra[x]=[selfappliable[x] = T → car[NIL]; selfappliable[x] = F → ANYVALUE].

Function contra execute reverse from what selfapplyable execute. Is function contra selfappliable, i.e. is value contra/[contra^(s)] defined? Let us suppose that it isn’t. From definition of /contra follows that

/selfappliable/[contra^(S)] = T.

Then, from selfapplayble property, the value /contra/[contra^(s)] is defined, which is a contradiction to the assumption.

Let us suppose that contra/[contra^(s)] is defined. Then, according to definition of /contra, it holds that

/selfappliable/[contra^(S)] = F.

Then, by property of selfapplyable, value /contra/[contra^(s)] is not defined.

Also, the statement that contra is a S-function leads to a contradiction. But, definition of contra is correct, if selfapplayable is a S-function. Thus, selfapplayable is not a S-function.

It can be proofed same way that more general function,

/def/[h^(S); (args_1 ,…, args_n)]

which computes if S-function h is defined for arbitrary arguments args_1, …, args_n is not a S-function. If def would be a S-function, then also selfappliable could be defined

/selfappliable/[h^(S)] = /def/[h^(S); h^(S)],

which is correct definition for S-function. Since selfappliable is not a S-function, thus can def not be a function either.

9.26 PROGRAMS AS S-FUNCTION

McCarthy also wrote a small note about translation of other programming languages into S-functions. Idea is simple and didn’t raise bigger discussions.

“Machine configuration” is in every moment defined by value of all variables whose values are given in the program. Those variables and their values can be “combined” in a list in form

((variable, value),(variable, value),…).^188

“Program blocks”, parts of a program that have only one “input” and one “output” transoform the configuration. For example, program block

A = B + 1

transforms the configuration ((A,0),(B,1)) into ((A,2),(B,1)). Let X^(1), …, X^(n) be all possible “configurations” for the machine, and let Y^(1), …, Y^(n) be corresponding configurations after the execution of that program block. Then S-function given by

/f/[x] = [x = x^(1) → y^(1), …, x = x^(n) → y^(n)]

computes same configuration as the program block. An important restriction, during this, is that set of all possible configurations has to be finite. In many programs, number of configurations is almost infinite and is limited only by the computer memory.

A program block can also consist of parts which also are program blocks, as well as conditions that decide which block will continue the execution. Such sets of blocks and conditions can be represented by a so called flow chart.

IMAGE 13. A program described by a flow chart.^189

McCarthy states an example of translating the program given by a flow chart in Image 13. Let r, s, and t be S-functions which simulate part of the program between points R, S, and T and program exits, respectivly. Let π_11 and π_12 be possible choice decisions at place π_1. Then

r(x) =[π_11[x] → s[f_1[x]]; π_12 → s[f_2[x]]], s[x] = [π_21[x] → r[x]; π_21[x] → t[f_3[x]]], t[x] = [π_31[x] → f_4[x]; π_32[x] → r[x]; π_33[x] → t[f_3[x]]].

There is no essential difference if a program block has multiple exists.

9.29 REPRESENTING SYMBOLIC EXPRESSIONS IN COMPUTER MEMORY

Representation of symbolic expressions in computer memory is same as in “imperative Lisp”. Words are divided in two parts, address one and decrement one. Every part can contain addresses of symbols or other words. Set of all such connected addresses, of which one is distinguished as starting one McCarthy calls for a list structure. Thereby, for lots of consideration, real memory addresses are not important; only relations between addresses are. For this reason, list structures, just like in the first memo, can be easily represented graphically. Compared to Memo 1., graphical representations are improved: an arrow showing list start is added.

IMAGE 14. Graphical representation of a list structure corresponding to the expression (A,(B,C),(B,(D,E)),F).

List structures can grow or shrink as needed, and enable effective use of computer memory.

9.30 DIFFERENCES BETWEEN SYMBOLIC EXPRESSIONS AND LIST STRUCTURES

List structures are more general than symbolic expressions. Symbolic expressions in which same expression appears twice or more times can be represented as list structures in several considerably different ways.

IMAGE 15. Two different memory representations of expression ((A.B),(A.B)).

On the other side, a list structure that contains cycles, circular list structures are not at all representations of symbolic expressions.

IMAGE 16. Example of a list structure containing a cycle.

A language designer can design a language such that the programmer can process all list structures and accept all possible complications following from differences between list structures and symbolic expressions; maybe even take advantage from the more general structure. Alternativly, he could exclude list structures that does not represent symbolic expressions, and if symbolic expressions have multiple representations, support only one of those. McCarthy choose the middle way; he allowed different representations of same symbolic expression, but not for list structures containing cycles.^190

9.31 GARBAGE COLLECTION

Manipulating free memory with help of “free memory list” was introduced in FLPL and accepted in “imprative Lisp”. McCarthy realized very soon clumsiness of need to explicitly release occupied memory and expressed intention for automatic release.^191 Result of McCarthy’s intensive work^192 on this problem is a program in machine language, a part of Lisp which intern was called “garbage collector”, name that to McCarthy didn’t appear as serious enough for a scientific paper.^193

“Garbage collector” activates only when function cons tries to use a word from the free memory list and it appears that free memory list is empty. Then, “garbage collector”, starting with few basic words by consecutive use of car and cdr iterates through entire avialable memory and marks all words which it accesed by setting value of S (sign) bit to 1. If it during this iteration encounters a word in which S bit is already set to 1, the program assumes that word, and all words accessible from this word are already processed.

In second iteration through the memory, this time entire, “garbage collector” organizes all those words in which S bit has value 0 into a free memory list.

Finally, the program iterates for the third time through the memory, starting only from the basic words and sets value of S bit to 0.

Described technique is today known as “mark-sweep”. McCarthy thought about the other well-known, “reference counting” technique that was also used in some Lisp implementations, but not under McCarthy’s leadership.^194

Members of the project didn’t rush with “garbage collector” implementation, since first programs were just a testbed for the system and didn’t needed to be really effective.^195 Despite the memory being very small (free memory list had initially about 15 000 words) at the time of “garbage collector” development, the program was practically slower then McCarthy’s estimation (several seconds) and became a source of anecdots.^196

130 McCarthy, History of LISP, 1981., p. 173. 131 McCarthy, History of LISP, 1981., p. 178. 132 McCarthy, Recursive functions …, AIM-008, 1959. 133 McCarthy, Recursive functions …, AIM-011, 1959. 134 McCarthy, Recursive functions …, RLE QPR 053, 1959., p 124-152. 135 Faase, The origin of CAR and CDR in LISP, 2006. 136 McCarthy, LISP: A programming system for symbolic manipulation, 1990. 137 McCarthy, Recursive functions …, CACM, 1960., p. 193. 138 McCarthy, Recursive functions …, RLE QPR 053, 1959. 139 McCarthy, History of LISP, 1981., p. 178. 140 “And then, two years later came John’s paper … That changed the whole ball game, and it changed how people perceived LISP. Now all of a sudden, LISP was not merely a language you used to do things. It was now something you looked at: an object of beauty. It was something to be studied as an object in and of itself.” Abrahams, Transcript of discutant’s remarks in McCarthy, History of LISP, 1981., p. 193. 141 Woodward i Jenkins, Atoms and lists, 1961., p. 51. 142 McCarthy et al, LISP 1.5 programmer’s manual, 1962., p. 20. 143 Talcott, Rum. An intensional theory of function …, 1988., p. 15. 144 Personal communication with Abrahams., 2014. 145 “The Lisp programming system is the system for using the lBM 704 computer to compute with symbolic information in the form of S-expressions (…) The basis of the system is a way of writing computer programs to evaluate S-functions.” McCarthy, Recursive functions …, CACM, 1960., p. 191. 146 “The LISP programming system will be shown … to be based mathematically on a way of generating the general recursive functions of symbolic expressions.” McCarthy et al., The LISP programming system, 1959., p. 122. 147 McCarthy, Recursive functions …, CACM, 1960., p. 184. 148 We should differ betwen recursive definition from recursive activation of, for example, expression f(f(x)). 149 McCarthy, /Recursive functions …, CACM, 1960., p. 185. 150 See chapter in A Basis for a Mathematical Theory of Computation 151 “Since we regard the expressious with commas as abbreviations for those not involving commas, we shell refer to them all as S-expressions.” McCarthy, Recursive functions …, CACM, 1960., p. 187. 152 McCarthy, Recursive functions …, AIM-008, 1959., p. 3. 153 “We now define a class of functions of S-expressions. The expressions representing these functions are written in a conventional functional notation. However, in order to clearly distinguish the expressions representing functions from S-expressions, we shall use sequences of lower-case letters for function names and variables ranging over the set of S-expressions. We also use brackets and semicolons, instead of parentheses and commas, for denoting the application of functions to their arguments. Thus we write car[x], car[cons[(A∙B); x]]. In these M-expressions (meta-expressions) any S-expression that occur stand for themselves.” McCarthy, Recursive functions …, CACM, 1960., p. 187. 154 “Compositions of car and cdr give the subexpressions of a given expression in a given position. Compositions of cons form expressions of a given structure out of parts. The class of functions which can be formed in this way is quite limited and not very interesting. (…) We get a much larger class of functions (in fact, all computable functions) when we allow ourselves to form new functions of S-expressions by conditional expressions and recursive definition.” McCarthy, Recursive functions …, CACM, 1960., p. 187. 155 “… function whose M-expression is label[subst; λ[[x; y; z]; […]]] has the S-expression …” McCarthy, Recursive functions …, CACM, 1960., p. 189. 156 Slagle, A heuristic program …, Ph.D. thesis, 1961., p. 18. 157 “Another useful abbreviation is to write list[e_1; …; e_n] for cons[e_1; cons[e_2; …; cons[e_n; NIL]…]]. This function gives the list, (e_1, …, e_n) as a function of its elements.” McCarthy, Recursive functions …, CACM, 1960., p. 188. 158 “Some of the decisions made rather lightheartedly for the “Recursive functions … ” paper later proved unfortunate. These included the cond notation for conditional xpressions, which leads to an unnecessary depth of parentheses, and the use of the number zero to denote the empty list NIL and the truth value false.” McCarthy, History of LISP, 1981., p. 179. 159 McCarthy, Recursive functions …, CACM, 1960., p. 189. 160 In original RFSE, the term “association list” is used for what usually, including this book too, is called “property list”. 161 Jordan, A note on LISP universal S-functions, 1973. 162 Stoyan, The influence of the designer on the design — McCarty and Lisp, 1991. 163 Graham, Roots of Lisp, 2002. 164 In original paper, also in Lisp I. handbook here is, according to opinions by all commentators, a logical misstake: instead of cdr[e] it stated evlis[cdr[e];a]. 165 See chapter New Function eval 166 See chapter Lisp 1.5. 167 Gilmore, An abstract computer with a Lisp-like machine language…, 1963., p. 72. 168 Sebesta, Concepts of Programming Languages, 2012., p. 680. 169 “Yes, that was the big revelation to me when (…) I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over.” Kay, A conversation with Alan Kay, 2004., p. 26. 170 “… an unbelievable feat, especially considering that the program takes hardly more than half a page — an interpreter for the language being defined, written in that very language! The more recent reader can only experience here the kind of visceral, poignant and inextinguishable jealously that overwhelms us the first time we realize that we will never be able to attend the première of Don Giovanni …” Meyer, John McCarthy, 2011. 171 “So by understanding eval, you’re understanding what will probably be the main model of the computation well into the future.” Graham, Roots of Lisp, 2002., p. 11. 172 “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. … This unfortunate LISP-interpreter formulated in LISP has somehow given mechanistic (or “operational”) language definitions an undeserved aura of respectability …” Dijkstra, Trip report, Edinburgh and Newcastle, 1974., p. 0. 173 “… This EVAL was written and published on the paper and Steve Russell said, look, why don’t I program this EVAL and you remember the interpreter, and I said to him, ho, ho, you’re confusing theory with practice, this EVAL is intended for reading not for computing. But he went ahead and did it. That is, he compiled the EVAL in my paper in to 704 machine code fixing bugs and then advertised this as a LISP interpreter which it certainly was, so at that point LISP had essentially the form that it has today, the s-expression form …” Stoyan, Early LISP history (1956-1959), 1984., p. 307. 174 Stoyan, LISP history, 1979., p. 45. 175 Stoyan, Lisp 50 years ago, 2008. 176 Reynolds, Definitional interpreters …, 1972., p. 725. 177 Böhm, Calculatrices digitales …, 1954. 178 Turing, On computable numbers, with an application …, 1936. 179 McCarthy, Recursive functions …, RLE QPR 053, 1959., p. 144. 180 McCarthy, Recursive functions …, CACM, 1960., p. 193. 181 McCarthy, History of LISP, 1981., p. 173., 179. 182 McCarthy, Lisp − notes on its past and future, 1980., p. v. 183 McCarthy, History of LISP, 1980. 184 McCarthy, Recursive functions …, RLE QPR 053, 1959., p. 145. 185 McCarthy, Recursive functions …, RLE QPR 053, 1959., p. 124. 186 McCarthy, Recursive functions …, AIM-008, 1959., p. 9-12. 187 McCarthy, Recursive functions …, RLE QPR 053, 1959., p. 145-147. 188 McCarthy, Programs in LISP, AIM-012, 1959., p. 2. 189 According to McCarthy, Recursive functions …, RLE QPR, 1959., p. 150. 190 “The prohibition against circular list structures is essentially a prohibition against an expression being a subexpression of itself. Such an expression could not exist on paper in a world with our topology. Circular list structures would have some advantages in the machine, for example, for representing recursive functions, but difficulties in printing them, and in certain other operations, make it seem advisable not to use them for the present.” McCarthy, Recursive functions …, CACM, 1960., p. 192. 191 See chapters FLPL, Imperative Lisp and Elements of funkcional programming. 192 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 193 McCarthy, Recursive functions …, 1995., p. 27., bilješka 7. 194 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 195 McCarthy, History of LISP, 1981., p. 178. 196 McCarthy, History of LISP, 1981., p. 183.

10. Linear Lisp

In Memo 8.^197 and later documens^198,197 McCarthy states that there are several possible ways to define functions, “alternative formalisms” over symbolic expressions similar to “accepted system” and briefly describes two “Lisp variants”: “linear” and “binary Lisp”. “Linear Lisp” is described in all intern and published versions of the memo.

10.1. L-EXPRESSIONS

Symblic expressions, a basic kind of data in “pure Lisp”, are intended for processing mathematical and logic epxressions. The difference between symbolic expressions and general mathematical expressions is not small. For example, the equality called “difference of two squares”,

a^2 - b^2 = (a + b) · (a - b)

would be written in most programming languages as

a^2 - b^2 = (a + b) * (a − b).

The equivalent symblic expression has form

(= (− (^ A 2) (^ B 2)) (* (+ A B) (− A B))).

We can ask why Lisp does not process arbitrary sequences of signs. Beside answering the standing complain on Lisp account, of S-expressions being hard to read, the language would win on generality. McCarthy devoted a paragraph in a memo^200 to discussion of exactly such, “linear Lisp”, that process arbitrary sequences of characters, strings, or as he also calls them, L-expressions, defined by

Every individual character is an L-expression.

Any sequence of signs, including an empty sequence (notated: Λ) is an L-expression

10.2. ELEMENTARY FUNCTIONS

Defined are six elementary functions with L-expressions; three of which are predicates.

Elementary function first. For example,
/first/[AB] = A.

Generally, first/[x] is the first sign in a string /x. Specially, /first/[Λ] is not defined.

Elementry function rest. For example,
/rest/[ABC] = BC.

Generally, /rest/[x] is a sequence of signs obtained after eraisng the first sign. Specially, /rest/[Λ] is not defined.

Elementary function combine. For example,
/combine/[A; BC] = ABC.

Generally, combine/[x; y] is a sequence of signs formed by concatening L-expressions /x i y.

Elementary function char. For example,
/char/[A] = T, /char/[AA] = F.

Generally, if x is a sequence of only one chaacter then /char/[x] has value T. If x is a sequence of more then one character, then /char/[x] has value F.

Elementary function null. For example,
/null/[Λ] = T, /null/[A] = F.

Generally, vaue null/[x] is *T* if and only if /x = Λ. Otherwise, value /null/[x] is F.

Elementary function =. For example
value A = A is T, value A = B is F.

Generally, if x and y are same sequence of characters then x = y has value T. If x and y are different, then x = y has value F.

10.3 FACTORING OUT SUB-EXPRESSIONS

“Linear Lisp” is more regular and more general than “pure Lisp”. In “pure Lisp” parantheses and commas play special role. In “linear Lisp” there are no such, special signs. Every S-expression is an L-expression, but many L-epxressions are not S-expressions.

On the other side, factoring out sub-expressions in “linear Lisp” is a complex operation. Programs should have special rules for factoring out expressions, depending on opeartors used. McCarthy believed that majority of programmers would in linear Lisp implement support for symbolic expressions and used “linear Lisp” as ordinary Lisp, so to avoid implementing special functions for factoring out sub-expressions. Then “linear Lisp” would not have advantages over “pure Lisp”, and would be slower, because of more generality.

197 McCarthy, Recursive functions …, AIM-008, 1959., p. 16. 198 McCarthy, Recursive functions …, RLE QPR 053, 1959., p. 148. 199 McCarthy, Recursive functions …, CAMC, 1960., p. 194. 200 McCarthy, Recursive functions …, CAMC, 1960., p. 194.

11. Binary Lisp

Another “LISP variant”, “binary Lisp”, McCarthy descrbied only in Memo 8^201, but not in other documents. Description of “binary Lisp” is very brief.

Assymetric definition of functions car and cdr, according to McCarthy, can be “source of disscomfort”. Thus, “binary Lisp” allows only for lists made of exactly two elements. On such lists are defined functions first, rest and combine. For example,

/first/[(X,Y)] = X /rest/[(X,Y)] = Y /combine/[X; Y] = (X,Y).

More general, for all S-expressions e1 and e2 holds

/first/[(e_1, e_2)] = e_1 /rest/[(e_1, e_2)] = e_2 /combine/[e_1; e_2] = (e_1, e_2).

It is enough to define two predicates, symbol equality, eq and atom. In such Lisp, empty lists are not needed. McCarthy’s objection to such system is complexity of function representation.

Despite Memo 8. having same title as later documents, described symbolic expressions in that memo are different: there are no “dotted pairs”.^202 On the other side, functions car, cdr and cons in “pure Lisp” are identical to functions in “binary Lisp”, but are defined over dotted pairs. Thus it seems that “binary Lisp” is an important link in development of “pure Lisp”.

201 McCarthy, Recursive functions …, AIM-008, 1959., p. 17. 202 See discussion in chapter Pure Lisp.

12. Slagle’s language for manipulating symbols

In a 1961. work, Slagle also described briefly a “symbol manipulation language” “similar to McCarthy’s Lisp”.^203

Basic property of Slagle’s language is giving up on “dotted pairs”. While McCarthy introduces symbolic expressions as pairs in form (e_1 . e_2), and (e_1, …, e_n) only as abbreviation to (e_1 . (e_2 . (…(e_n . NIL)…)), Slagle introduces lists directly. To him (e_1, …, e_n) is a real symbolic expression, not just an abbreviation, while “dotted pairs” are not symbolic expressions at all. Function cons/[x;y] is defined just if /y is a non-atomic S-expressions or NIL.

Instead of T and F, Slagle uses TRUE and FALSE. Instead of car and cdr, he writes shortly f (from first) and r (from rest). Instead of caar, cadr, cdar, cddr, etc. he writed ff, fr, rf, rr, etc.

Important is innovation and operation of function composition, for example, f ◦ g.

Slagle, as difference to McCarthy, explicits that function can be defined with expressions in form

function = λ[[x1; …; xn]; form] function[x1; … ; xn] = form.

Slagle defined a collection of interesting functions, for example procedures for inserting elements in ordered lists and for sorting lists, as well as predicates forall and therex, as well as function depth which computes “maximal parantheses level” in an S-expression.

/forall/[s; p] = /null/[s] ∨ [p ◦ f[s] & /forall/[r[s]; p] /therex/[s; p] = ~forall[s; λ[[si]; ~p[si]]]

depth/[s] = [atom[s] → 0.0; *TRUE* → /max/[[1.0 + /depth ◦ f[s]]; depth ◦ r[s]]].

Slagle’s Lisp was never implemented.

203 Slagle, A heuristic program …, 1961., p. 16.

13 Symbolic expressions as the language syntax

Originally^204, Lisp syntax was similar to that of Algol and other higher level programming languages. In the first few months, that syntax gets the uniform shape of meta-expressions. Programmers translated programs into assembler personally, obtaining experiences necessary for writing a compiler. Unexpected consequence of definition and implementation of S-function eval is appereance of useful interpreter for programs represented in the computer memory in form of list structures. Maling and Silver implemented function READ that reads symbolic expressions and converts them into a list structure which made it possible for programmers to start writing programs in form of symbolic expressions.

The Lisp community didn’t accepted easily symbolic expressions as the language syntax. Already McCarthy deemed them as “hard to read”^205, “somewhat readable”^206, and M-expressions as “easier to read”.^207 Later he suggested marking parenthesis with arbitrary number of dots and commas, for example (.. and ..), where closing such parenthesis would close all others that were left open.^208 Also some other members of the Lisp project considered Lisp not practical because of the big number of parenthesis.^209,210 Lisp programmers, as noted by McCarthy, if a problem requires more significant work with symblic expressions gladly choose other data representations and implement their own, ad hoc translators. For that reason he considered that support for expressions in other forms should be

built into Lisp.^211 Maling and Silver also tried, beside never finnished^212 support for meta-expressions, to support “algebraic expressions” such as a*b+c*d.^213 There were thoughts about S-function eval accepting arguments in “usual notation”.^214 Programs in memoes and books were still long written in form of M-expressions. It is also less known that Lisp 1.5 also support expressions in form of

(IF (a THEN b ELSE c))^215

and similar form for FOR expression. After McCarthy’s leave from MIT some public criticism appears^216 as well as attempts to create alternative forms of syntax.^217,218

Despite, the community kept symbolic expressions as the language syntax and gradually stopped using M-expressions. In Lisp 1.5 manual, prog-expression is introduced as meta-expression and equivalent S-expression, but without explicit rules for the translation.^219 The first bigger document in which there are no mentioning of M-expressions is Handbook of LISP functions by a group of students from Baltimore, from August 1961.^220

204 see chapter Imperative Lisp. 205 “This notation is rather formidable for a human to read …” McCarthy, Recursive functions …, AIM-008, 1959., p. 14. 206 “This notation is writable and somewhat readable.” McCarthy, Recursive functions …, CAMC, 1960., p. 189. 207 McCarthy et al., LISP I programmer’s manual, 1960., p. 53. 208 McCarthy, New eval function, AIM-034, 1962., p. 2. 209 “I thought it was a marvelous sort of language, except that it was somehow impractical. You can’t ask people to do that; you need a translator. Such programs for LISP may exist now. I don’t know. A program you could give simple statements to that would be automatically be translated into the multiply-parenthesized code.” Fox, An interview with Phyllis A. Fox, 2005., p. 31. 210 “The task of writing out S-expressions to define programs is a tedious one, especially since the LISP notation seems to run counter to the natural way that people think of mathematical expressions.” Abrahams, Application of LISP to checking mathematical proofs, 1964., p.159. 211 McCarthy, LISP − notes on its past and future, 1980., str. vi. 212 McCarthy, History of LISP, 1981., str. 179. 213 Maling, The Maling-Silver read program, AIM-013, 1959. 214 McCarthy et al., LISP programmer’s manual, 1959., str. 3/1. 215 McCarthy et al., LISP 1.5 programmers manual, 1962., str. 98. 216 “… it has become evident that the general list processing languages (such as LISP) are not appropriate for processing complex mathematical data. This is due not only to the extreme complexity of the coding that necessarily ensues in the analysis of an intricate problem, but also to the fact that the input-output procedures most ideally suited for these languages are totally inadequate for the individual prlmarily interested in the analysis of a problem and not the underlying mathematical and input-output structure involved.” Morris, Models for mathematical systems, 1966., str. 1520. 217 Henneman, An auxiliary language for more natural expressions …, 1964. 218 Abrahams et al., The LISP 2 programming language and system, 1966. 219 McCarthy et al., LISP 1.5 programmer’s manual, 1962., str. 29. 220 Conrad et al., A handbook of LISP functions, 1961.

14 Fortran-like commands, function program, power and multiparadigmatism of LISP

McCarthy’s Memo 11.^221 was still introducing “pure Lisp”, but already Memo 12.^222 again introduces commands for assignement, or as McCarthy calls them, “Fortran-like” commands. For example, if “state of the machine” is defined by x that has value (A) and by y which has value (B,B), then after executing fortran-like commands

x = /append/[x; x] y = /cons/[x; y]

variable x will have value (A,A), and variable y will have value ((A,A),B,B). According to McCarthy, there are two reasons why fortran-like commands are good. First, many programs and functions can be written more concisely, with higher indenpendency between parts than in “pure Lisp”. Second, many programs and functions can be more efficient.

14.1 CODING THE STATE OF THE MACHINE AND FORTRAN-LIKE COMMANDS

At same time, fortran-like commands are, according to McCarthy, nothign more then just a convenience. Machine states can be encoded in pair lists, just like those used in definition of S-function eval. For example, starting and ending state of the machine from the previous example can be encoded into S-expressions

((X,(A)),(Y,(B,B))) and ((X,(A,A)),(Y,((A,A),B,B))).

Over encoded states of the machine, can be defined S-functions equivalent to the function of fortran-like commands on states of the machine.

Further, sequences of fortran-like commands can also be encoded into lists of pairs. For example,

x = /append/[x; x] y = /cons/[x; y]

can be encoded into ((X,(APPEND,X,X)),(Y,(CONS,X,Y))).

14.2 S-FUNCTION PROGRAM

It is possible to define S-function program that applies encoded sequence of fortran-like commands on encoded states of the machine. For example

/program/[((X,(APPEND,X,X)),(Y,(CONS,X,Y))); ((X,(A)),(Y,(B,B))) ] = = ((X,(A,A)),(Y,((A,A),B,B))).

Generally, if a sequence of fortran-like commands s_1, s_2, …, s_n changes machine state a_1 into machine state a_2, then

/program/[(s1^*, s2^*, …, sn^*); a1^*] = a2^*,

where s_1^*, s_2^*, …, s_n^*, a_1^* and a_2^* are respective codes. McCarthy defined S-function program with meta-expression

program[p; a] = [null[p] → a; T→ program[cdr[p]; change[a; caar[p]; eval[cadar[p]; a]]]].

Help S-function change defines or changes values of variables in represented state machine. For example,

change[(); Y; C]=((Y,C)), change[((X,A),(Y,B)); Y; C]=((X,A),(Y,C)).

Function change is defined by meta-expression

change[a; var; val] = [null[a] → list[list[var; val]]; caar[a] = var → cons[list[var; val];cdr[a]]; T → cons[car[a]; change[cdr[a];var; val]]]

In very same memo, McCarthy briefly describes also some other interesting possibilities. Equivalent of the famous GO TO command can be implemented with special interpretation of the symbol IL. Thus, the program /program2/[((IL,e)…); a] could be computed as /program2/[eval[e; a]; a].

14.3 SIMULTANEOUS EXECUTION OF FORTRAN-LIKE COMMANDS AND ORDERING BETWEEN SYMBOLS

Further, McCarthy defines function program3 so that fortran-like commands can be executed simultaneously, for example,

/program3/[((X,Y),(Y,X)); ((X,A),(Y,B))] = ((X,B),(Y,A)).

In the implementation of the last program, McCarthy used relation or ordering (<) between symbols and assumes that for every state vector in form

((var_1, val_1),(var_2, val_2),…,(var_n, val_n))

holds var_1 < var_2 < … < var_n.

14.4 MULTIPARADIGMATISM OF LISP

Memo 12. reveals more about McCarthy’s understanding of Lisp then what is visible at first sight. First Lisp version was pragmatic and imperative; the beauty of “pure Lisp” was accidental, and, even for the members of the AI group, a surprising result^223

which didn’t stimulate them on insisting on “pureness”, and for which Lisp was later sometimes hard criticized.^224 Moreover, the argument in favor of fortranlike commands^225 can be applied also on other language constructs that could be added to Lisp. Since “pure Lisp” is Turing-complete, then for every possible augmentation of “pure Lisp” exists an equivalent function in “pure Lisp” that to the machine state - such as defined by McCarthy or maybe somewhat different - assigns a new machine state, and then even that augmentation can be added to Lisp. For any programming language PL, it is possible to define S-function pl

[OBS! I CAN’T TRANSLATE THE REST OF THAT SENTENCE]

x’ = pl(p,x).

Such augmentation is, if we follow McCarthy’s reasoning, just a convenience. On contrary to Stoyan’s stance^226, it seems that McCarthy at the time of writing Memo 12. was very open towards augmentations of the language and thus closer to understanding of Lisp as expressed today in “multiparadigm” dialect of Common Lisp then in the “more elegant” dialect of Scheme. That stance, it seems, was held by McCarthy even later, distanciating himself only from the augmenations that would disturb the syntax of the language.^227

14.5 THE LANGUAGE POWER FROM A PROGRAMMERS POINT

In Memo 12., McCarthy highlights, similar as in Compiler suggestion that “power of a programming language” or “power of the system” from the programmer’s point of view is the most important goal in Lisp development.^228 Such enthusiastic standpoint of the langauge author, is surprisingly, rarely cited.

As an example, Lisp is more powerful then the assembler because a programmer does not need to introduce help concepts in Lisp such as addresses at which variable values are stored or those of the list of free storage. Similary, a programming language in which matrices A and B could be multiplied directly, by an expression such as A*B, would be more powerful then the language in which programmer has to explicitly compute value of each element of the result matrix. Generally, a programming system is more powerful then soem other programming system if functions that can be described directly in one system demands describing help calculations in the other system.^229 Help calculations are still done, but it is a compiler’s or interprretter’s responsibility.

Looking from a time distance, we could ask ourselves how would a language where help computations are minimized look like. It is evident that such a language must have large library of standard functions, towards which, all language designers gravitate. Especially, it would support “declarative programming” in which is describaed what to compute, not how to compute. Also, much later, McCarthy also worked for including a support for logical expressions^220 and connecting Lisp and Prolog.^231 On the other side, the language must be kept “open”, so that often repeated pattern compuations - regardless of how complex - could be described by simpler syntatic constructions. Already since Fortran, for such purpose were used functions. But, functions only, at least as defined in “pure Lisp” does not allow for avoiding of computing of all computing patterns.^232 Despite, the most ambitious later attempts to develop Lisp in that direction, for example, Carl Hewitt’s Planner or Brian Smith’s 3-Lisp did not make influence on the most popular language dialects.

McCarthy also recognizes some inneficiencies of Lisp. Supporting S-functions, Lisp always computes new values, old values are never changed. That problem is solvable in few different ways.^233 Another inneficiency is the necessity to search the association lists in search for values assigned to a variable.

221 McCarthy, Recursive functions …, AIM-011, 1959. 222 McCarthy, Programs in LISP, AIM-012, 1959. 223 “And then, two years later came John’s paper … That changed the whole ball game, and it changed how people perceived LISP. Now all of a sudden, LISP was not merely a language you used to do things. It was now something you looked at: an object of beauty. It was something to be studied as an object in and of itself.” Abrahams, Transcript of discutant’s remarks in McCarthy, History of LISP, 1981., p. 193. 224 “It needs to be said very firmly that LISP, at least as represented by the dialects in common use, is not a functional language at all. LISP does have a functional subset, but that is a rather inconvenient programming language and there exists no significant body of programs written in it. Almost all serious programming in LISP makes heavy use of side effects and other referentially opaque language features. I think that the historical importance of LISP is that it was the first language to provide garbage-collected heap storage. This was a very important step forward. For the development of functional programming, however, I feel that the contribution of LISP has been a negative one. My suspicion is that the success of LISP set back the development of a properly functional style of programming by at least ten years.” Turner, Functional programs as executable specifications, 1984., p. 387. 225 “Since all computable functions can be expressed in LISP without the program feature, this feature can only be regarded as a convenience. However, it is a convenience at which we cannot afford to sneer.” McCarthy, Programs in LISP, AIM-012, 1959., p. 1. 226 “As things stand, he must prefer SCHEME to Common LISP — a clear, understandable small diamond, to a messy, incomprehensible clump.” Stoyan, The Influence of the Designer on the Design…, 1991., p. 424. 227 “Steele: Let’s move up to the list to question no. 3. What would you add to Lisp if you could goback in time? What would you delete and what would you change? McCarthy: People have added some Englishy stuff and at least the syntax of that is not in the spirit of Lisp. I don’t have any objection to the content and generally I don’t have any objection to things being added to Lisp, because you can always not use them. I don’t have any particular ambitions to add anything in particular to Lisp right now. I’d like to add some direct logic, but I don’t know how to do that in a good way. Steele, Interview with John McCarthy, 2009. 228 “In developing LISP our first goal is to describe a language which is as powerful as possible from the point ot view of the programmer. More precisely, we wish to be able to describe the transformation between the input of a program and the desired output as directly as possible.” McCarthy, Programs in LISP, AIM-012, 1959., p. 4. 229 “We shall consider one programming system more powerful than another if functions which can be described directly in the one require the description of auxiliary computation in the other.” McCarthy, Programs in LISP, AIM-012, 1959., p. 5. 230 McCarthy, Beyond Lisp, 2006., img. 4. 231 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 232 See chapter Lisp 1.5, Special forms. 233 See chapter Lisp 1. 5 and Memoization.

15 Woodward-Jenkins arithmetics

If a programmer would like to implement arithemetic in “pure Lisp”, numbers should be represented as symbolic expressions, for example, 857 as (8,5,7) and then to implement algorithms such as those as used by humans when computing basic computing operations.

D.P. Jenkinks implemented 1960. or 1961. a Lisp on a computer TREAC in Royal Radar Establishment in Malvern. Jenkins and Phillip Woodward 1961.^234 described a program for addition of numbers. Numerals are symbols contained in a list tab that has value

(0,1,2,3,4,5,6,7,8,9).

Ingeres are represented as lists of tab sublists, written in reversed order. For example, number 857 is represented by the list

((7,8,9),(5,6,7,8,9),(8,9)).

Functions needed for list addition are

sum[x; y] = [null[y] → x; T → inc[x; y; tab]]

inc[x; y; b] = [eq[caar[y]; car[b]] →cons[car[x]; sum[cdr[x];cdr[y]]]; T → inc[step[x]; y; cdr[b]]] step[x] =[null[x] → cons[cdr[tab]; NIL]; null[cdar[x]] → cons[tab; step[cdr[x]]]; T → cons[cdar[x]; cdr[x]]].

McCarthy wrote later that even the original group at MIT made an attempt to represent numbers in similar fashion, but that this approach was abandoned due to slowness.^235 Author of this book did not found any document in which such attempts are described, and neither did the members of the original group with whom he consultated remember such attempts.

In Lisp I., and also in later Lisp 1.5, numbers were already implemented as special type of atoms. Such implementation certainly undermine the beauty of the language and brings suspicion to it’s usability, but it seems that it was unavoiadble. Even today, in all practical Lisp implementations, numbers are implemented as a special type of data.

234 Woodwards & Jenkins,/ Atoms and lists/, 1961., p. 52. 235 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 McCarthy, History of Lisp, 1981., p. 180.

16 Lisp 1.5

Despite the beauty, “pure Lisp” was innefficient and practically almost unusable.^236 Experience from a number of small problems convinced McCarthy that support for symbolic expression alone is not enough and that Lisp must make it possible to compute with other types of data.^237 Thus, further development of the language was directed towards practical aspects of the language. That period, unfortunately, is not that well docummented^238 such as previous, and it is possible that some interesting ideas are lost forever.

LISP programmer’s manual from March 1959. contains a list of functions and their definitions in LISP or IBM 904 Assembler. In that time, Lisp syntax was still similar to that from “imperative Lisp”.^239

Considerably more volymous Lisp preliminary programmer’s manual from January 1960.^241 brings many changes. Amongs other, the syntax from “imperative Lisp” is finally removed.

All important changes in Lisp I. found their place also in Lisp 1.5 which is mentioned in intern documents already in spring 1961.^242 LISP 1.5 programmer’s manual was published in August 1962. The manual was, as it seems, left more influnce than the paper from 1960. For example, Kay, Meyer and Dijkstra, when discussing about eval, talk about the version from the Manual.

The Manual leaves an impression of a collection of independent articles rather then a coherent book. It was sharply critized by Edsger W. Dijkstra.^243 Best addition to the manual is an article by Robert A. Saunders.^244

16.1 PURE LISP

First chaper in Manual brings a short resume of “pure Lisp”, with some small changes. Among others, instead of term “S-function” is used simply “function”.

Beside commas, whitespaces can also be used for delimiting list elements. For example instead of (CAR,X) it could be written (CAR X).

As pair lists, which are in Lisp 1.5 called also association lists, are no longer used ordinary lists with two elements, but “dotted pairs”. For example, instead of ((X (A B)) (Y C)) is used ((X . (A B)) (Y . C)). That small change was introduced probably to save some memory. Also, some functions are redefined, and some new are introduced.

Function member/[x;y] is a predicate which is true if and only if a symbolic expression /x is element in a list y. For example,

/member/[X; (A X)] = T, /member/[Y; (A X)] = F.

Function definition is

/member/[x; y] = [null[y] → F; /equal/[x; car[y]] → T; T → /member/[x; cdr[y]]].

Function pairlis/[x;y;a] creates corresponding pair list from lists /x and y and adds it to association list a. For example,

pairlis[(A B C); (U V W); ((D.X) (E.Y))] = ((A.U) (B.V) (C.W) (D.X) (E.Y)).

Definition of the function is

/pairlis/[x; y; a] = [null[x] → a; T → cons[cons[car[x]; car[y]]; /pairlis/[cdr[x]; cdr[y]; a]]].

Function assoc/[x;a] searches for symbol pair /x in the association a. Function definition is

assoc[x; a] = [equal[caar[a]; x] → car[a]; T → assoc[x; cdr[a]]].

Function sublis/[a;y] substitues values instead of variables into a symbolic pair /y. For example,

sublis[((X.S) (Y.(T T)); (X WROTE Y)] = (S WROTE (T T)).

Definition of the function is

/sublis/[a; y] = [atom[y] → sub2[a; y]; T → cons[sublis[a; car[y]] /sublis/[a; cdr[y]]]].

Help function sub2/[a;z] solved a special case in which which /z is atom. Definition of the function is

/sub2/[a; z] = [null[a] → z; eq[caar[a]; z] → cdar[a]; T → /sub2/[cdr[a]; z]].

Because of the new format for association lists, definition for the function sub2 is simpler then before.

Definitions of funtions eval and apply differ from those in documents from 1959-60. Function apply have additional third argument, a list of values which are substituted in place of free variables and thus has got a part of functionality that was previously done by eval.

apply[fn; x; a] = [atom[fn]→ [eq[n; CAR] → caar[x]; eq[fn; CDR] → cdar[x]; eq[fn; CONS] → cons[car[x];cadr[x]]; eq[fn; ATOM] → atom[car[x]]; eq[fn; EQ] → eq[car[x];cadr[x]]; T → apply[eval[fn; a]; x; a]]; eq[car[fn]; LAMBDA] → eval[caddr[fn]; pairlis[cadr[fn]; x; a]]; eq[car[fn]; LABEL] → apply[caddr[fn]; x; cons[cons[cadr[fn]; caddr[fn]]; a]]]

eval[e; a] = [atom[e] → cdr[assoc[e; a]]; atom[car[e]]→ [eq[car[e]; QUOTE]→ card[e]; eq[car[e]; COND]→ evcon[cdr[e]; a]; T → apply[eval[fn; a]; x; a]]; T → apply[car[e]; evlis[cdr[e]; a]]

Help functions evcon and evlis are defined as in paper Recursive functions … S-function that was in original presentation about “pure Lisp” called apply is here called evalquote and is defined by the expression

/evalquote/[fn; x] = /apply/[fn; x; NIL].

“Pure Lisp” is left as a mathematical idea, while the real interpretter worked somewhat differently. Introduced are many changes that made Lisp 1.5 more practical. More functions are defined, not just the basic five. Real eval and apply were much more complex. Beside the five elementary functions, defined are also many other functions.

16.2 USE OF PROPERTY LISTS

Property lists are intern representation of symbols. Property lists are similar to other lists, their maintance is done by the Lisp system, but a programmer can also manipulate them. It would be a misstake to think that property lists are symbol values. On contrary, a Lisp system can use property lists only to calculate a symbol value, if a programmer asks it to.

For example, intern representation of a symbolic expression (A B) is shown graphically in image 17.

IMAGE 17. Graphical representation of a symbolic expression (A B).

In those places in graphical representation were A and B are written, are addresses of property lists of symbols A and B respective. In crossed, decerement part in second part of the list is address of property list of symbol NIL.

IMAGE 18. Graphical representation of property list for symbol NIL.

In the example of property list of NIL symbol, it is also possible to see the general form of a property list. In address part of first element of a property list there is always a binary representation of number -1. In address part of next elements of property lists are addresses of indicators, here APVAL and PNAME. Indicators are symbols that denote kind of properties that immidiately follow. For example APVAL denotes that property that follows is the symbol value. Symbol NIL is a special case: value NIL is NIL itself.

Indicator PNAME denotes that the following property is name of the symbol, stored in one or more memory words in the, back then used, BCD code.

If a programmer with some expression defines a function then in the symbol list will be indicator EXPR after which will follow the address at which is representation of lambda-expression which defines the function. Lisp 1.5 allows also functions to be written in machine language. Then it is machine code for that function that is in the property list, after the indicator FSUBR.

Function deflist/[((u_1 v_1) … (u_n v_n));i] inserts indicator /i with it assigned property v_1 in property list u_1, …, indicator i and it assigned property v_n into list of properties u_n. For example with the expression

/deflist/[((IDENTITY (LAMBDA (X) X)));EXPR]

is defined identity function. If some symbol u_j already has indicator i and it assigned property, that property will be substituted with v_j.

Function get/[s;i] returns property of symbol /s assigned to indicator i. For example, after computing the above expression

/get/[IDENTITY; EXPR] = (LAMBDA (X) X).

Function /attrib/[x;e] concatenates two lists in computer memory changing last element of the first list so it points to the first element of the second list. Specially, if x is a symbol, then e will be added to the property list of that symbol. For example, function call

/attrib/[IDENTITY; (EXPR (LAMBDA (X) X))]

inserts indicator EXPR and associated symbolic expression (LAMBDA (X) X) in property list of symbol IDENTITY.

Function remprop/[x;i] removes indicator /i and assigned property from the property list of symbol x.

Programmer can insert any indicator and associated property into the property list of a symbol if he wishes. But, only some of indicators are used by the system.

16.3 PSEUDOFUNCTIONS

By utilizying property lists it is possible to store results obtained during the computation of symbolic expressions and then use them again later, for computations in other symbolic expressions. Functions that utilze that possibility - and which does not exist in mathematics - are called pseudo-functions. S-function deflist and attrib are obviously such functions.

Another reason for using pseudo-functions is connected to list structures that are introduced just as intern representation of symbolic expressions, but which also themselves cause problems that needs to be solved. In Lisp 1.5 is defined a number of function inspired by the need for more efficient use of list structures. Most important example are functions rplaca and rplaced. Function rplaca/[x;y] substitutes first element of symbolic expression /x with y. For example,

/rplaca/[((A) B); (C D)]=((C D) B).

It could be thought that

/rplaca/[x; y] = cons[y; cdr[x]].

It is true if we think only in terms of symbolic expressions. But, while computing expression cons/[y;cdr[x]] takes new list element from the free storage list and sets address and decrement parts of the list element to addresses of /y and cdr/[x], computing /rplaca/[x;y] writes address /y in address part of first list element of list x.

For example, let ((A) B) be value of symbol X and (C D) value of symbol Y. Call to function /rplaca/[x;y] will not just return ((C D) B), but the value of X will also be changed from ((A) B) into ((C D) B). Image 19. shows what exactly will happen.

IMAGE 19. Property lists of symbolx X and Y before and after call to function /rplaca/[x;y]

Dotted thin arrow denotes the value of addres part of a list element before computing /rplaca/[x;y] and thick full line denotes value after the computation of /rplaca/[x;y]. After finnishing /rplaca/[x;y] value of symbol X will be changed; after computing /cons/[y; cdr[x]] it will not.

Function rplacd/[x;y] on same way change decrement part of the first list element /x.

Functions rplaca and rplacd have analogous effect also on list structures that are not symbol values.

Other important pseudofunctions are /cset/[x;val] and /csetq/[x;val]. Those two functions are Lisp 1.5 equivalent of the command for assignement, or, as McCarthy wrote earlier, “fortran-like commands” x = val. Both psuedofunctions set value of symbol x to val by writing val in property list of symbol x, immidiately after the APVAL indicator. Letter c infront of set and setq comes from the word “constant”; symbols whose value is stored in property list are in Lisp 1.5 manual called constants.

16.4 SPECIAL FORMS

Differences between psuedofunctions cst and csetq can be seen from the meta-expressions, but they can also be seen in translation from meta-expressions into symbolic expressions.

meta-exression	translation into symbolic expression
cset[X; (A B C D)]	(CSET (QUOTE X) (QUOTE (A B C D))).
csetq[X; (A B C D)]	(CSETQ X (QUOTE (A B C D))).

In translation of csetq one QUOTE was not needed, and thus csetq was used more often than cset.

In function eval, function CSETQ must have different treatment than other functions because the first argument of the function must not be evaluated. For that reason CSETQ is not called a function or psuedofunction but “special form”, as was also COND and QUOTE.

More general, special forms are expressions in form (e_1 e_2 … e_n) computed without computing symblic expressions e_1, …, e_n before the execution control is transformed to symbolic expression e_1. In LISP 1.5 Manual expression e_1 itself was also called special form. Today e_1 in expression (e_1 e_2 … e_n) is usually called special operator.^245

Second important property of special forms is that they, for the difference from functions, can (but don’t have to) allow for variable number of arguments. For example, special form COND can have arbitrary number of arguments.

16.5 FEXPRS

In “pure Lisp”, special forms have special rules for computing in function eval and programmer can not define his own operators. In Lisp 1.5 special operatos can be defined with lambda-expressions as well as functions, and interpreter recognize them by the indicator FEXPR^246 in property list and computes them differently. With time it become accustomed to call such special forms for fexprs to differentiate them from other kinds of special forms which appeared during Lisp development. In Lisp 1.5, CSETQ is, for example, fexpr.

Fexprs are very powerful. For example, let fexpr Q2 be defined with

deflist[((Q2 (LAMBDA (V1 V2) (CAR V1))); FEXPR],

(Q2 X) is a simple symbolic expression that uses fexpr and ((X A)) is an association list. Then it holds

eval[(Q2 X); ((X Y))] = = eval[((LAMBDA (V1 V2) (CAR V1)) (QUOTE (X)) (QUOTE ((X Y)))); ((X Y))],

so from the definition of eval follows

= /eval/[(CAR V1); ((V1 (X)) (V2 ((X Y))) (X Y))] = = /car/[eval[V1; ((V1 (X)) (V2 ((X Y))) (X Y))]] = = /car/[(X)] = = X.

Also, fexpr Q2 can be used instead of special operator QUOTE. As it is seen from the previous equality, fexprs have access to the association list which is passed to eval that applies them.

More general, fexprs are defined by expressions of form

/deflist/[((fx (LAMBDA (v1 v2) e)));FEXPR]

where symbol fx is name of the special form, v_1 and v_2 are symbols, e is symbolic expression that probably contains v_1 and v_2. Let a be the association list. Then the value,

/eval/[(fx e_1 e_2 … e_n); a],

is equal to the value

/eval/[((LAMBDA (v_1 v_2) e) (QUOTE (e_1 e_2 … e_n)) (QUOTE a)); a].

Fexprs could, as functions, be defined in machine code too. Then in the property list they would be preceded by the indicator FSUBR. Almost all special operators in Lisp 1.5 system, including COND, QUOTE, AND, OR and LIST have indicator FSUBR.

In “pure Lisp” and Lisp 1.5 functions does not need to have name; it is enough to use lambda- or later label-expressions, for example (LAMBDA (X) X). Such functions are today called “anonymous functions”. Information that some lambda-expression should be used as fexpr can only be in the property list and thus in Lisp 1.5 anonymous fexprs are not possible.

Fexprs make it possible for a programmer to define elements of the language that seems more basic than functions. Despite this insight seeming exceptionally important and exciting^247, fexprs are only briefly described, without any examples. Also in other documents from that time, fexprs are barely even mentioned. McCarthy discussed fexprs in the memo from 1962.^248

16.6 PROGRAMS IN LISP

A program in Lisp 1.5 is a sequence of symbolic expressions pair. For example, program that defines S-function

append[x; y] = [null[x] → y; T → cons[car[x]; append[cdr[x]; y]]].

and afterwards computes /append/[(A B); (B C)] is

DEFINE (((APPEND (LAMBDA (X Y) (COND ((NULL X) Y) (T (CONS (CAR X) (APPEND (CDR X) Y)))))))) APPEND ((A B) (B C)) .

Interpreter calls in order function evalquote with arguments which are pairs of symbolic expressions in the program. In this example, the interpreter calculates, in the order

/evalquote/[DEFINE; (((APPEND …)))], /evalquote/[APPEND; ((A B) (B C))].

Function evalquote calls as needed function apply, function apply calls as needed function eval etc.

Lisp 1.5 interpreter “remembers” some symbol values and after the computation is finnished calls evalquote. In above example, interpreter wrote into property list for symbol APPEND in first call value (LAMBDA (X Y) …). In second call, evalquote computes

/apply/[APPEND; ((A B) (B C)); NIL].

Function apply then computes

/eval/[APPEND; NIL]

during which interpreter first searches for value APPEND in associated property list, and if it is not found there, then in the association list a. Also, once defined function APPEND can be used in entire program. Something like that was not possible in “pure Lisp” in which APPEND can be used only if the definition is in the association list, for example

/eval/[ (APPEND (QUOTE (A B)) (QUOTE (B C)); ((APPEND (LAMBDA (X Y) (COND … )))) ].

16.7 FUNCTIONAL ARGUMENTS

Functionals, functions which accepts other functions as arguments are already discussed in chapters Elements of functional programming and Pure Lisp. In fall 1959. Slagle run into unexpected problems, later called ”funarg problems”.^249 Such problems are barely noted in LISP 1.5 Manual^250 but Saunders^251 cites example similar to Slagel’s^252,253 which shows why naive use of functions as arguments to other functions does not render expected results. That example is here exposed in somewhat simplified form.

Let function TESTR be defined by lambda-expression

(LAMBDA (L FN) (COND ((NULL L) NIL) (T (TESTR (CAR L) (QUOTE (LAMBDA () (CONS (CDR L) (FN)))))))).

After call to

(CHANGE (LAMBDA (A) (MAPLIST A (FUNCTION (LAMBDA (J) (CONS (CAR J) (QUOTE X))))))) (TESTR (QUOTE ((A) (B) (C))) (QUOTE (LAMBDA (X) X)))

parameters L and FN would have following values:

L: ((A) (B) (C)) FN: (LAMBDA (X) X)

Since the condition (NULL L), is not satisfied, then the execution would follow the other branch of cond-expression

(TESTR (CAR L) (QUOTE (LAMBDA () (CONS (CDR L) (FN)))))

After repeated call to function TESTR, the value of parameters would be

L: (A) FN: (LAMBDA()(CONS (CDR L) (FN))).

In the expression that is value of FN appears symbols L and FN, but values of those symbols is now different from the values that they have at time when the gunction G is called. [OBS! Otkud funkcija G?]

McCarthy didn’t show interess for this problem, so the solution was developed by Russell, Edwards and Patrick Firsher.^254 For the Lisp interpreter to correctly compute such expressions, it is important to also save original values of variables with expressions. In Lisp 1.5 for this is used operator FUNCTION with wich functions can be used as arguments to other functions. Thus, TESTR should be defined as

(LAMBDA (L FN) (COND ((NULL L) NIL) (T (TESTR (CAR L) (FUNCTION (LAMBDA () (CONS (CDR L) (FN)))))))).

Then after the call

(TESTR (QUOTE ((A) (B) (C))) (QUOTE (LAMBDA (X) X)))

parameter values will be

L: ((A) (B) (C)) FN: (LAMBDA (X) X)

Since the condition (NULL L) is not met, execution would go to other branch of cond-expression

(TESTR (CAR L) (FUNCTION (LAMBDA () (CONS (CDR L) (FN)))))

After repeated call to function TESTR values of the parameters would be

L: (A), FN: (FUNARG (LAMBDA()(CONS (CAR L) (FN))) ((L . ((A) (B) (C))) (FN . (LAMBDA (X) X)))).

Lisp system thus have access to all data needed for the computation. More generally,

eval[(FUNCTION fn); q] = (FUNARG fn q) apply[(FUNARG fn q); x; p] = apply[fn; x; q].

The future would show that Lisp community was not satisified with this solution. Even McCarthy himself, after being not so interested in the start, expressed unsatisfaction with the solution.^255

16.8 SPECIAL OPERATOR PROG

Function program^256 as described in an earlier chapter, was introduced in Lisp 1.5 as a special operator prog and that in very developed form. For example, function length which computes length of a list, is defined with

length[l] = prog[ [u; v]; v := 0; u := l; A [null[u] → return[v]] u := crd[u]; v: = v +1; go[A]].

Translation of that definition into symbolic expressions is

DEFINE (((LENGTH (LAMBDA (L) (PROG (U V) (SETQ V 0) (SETQ U L) A (COND ((NULL U) (RETURN V))) (SETQ U (CDR U)) (SETQ V (ADD1 V)) (GO A) ))))).

First argument of prog-expression is a list of “program variables” which are treated same as parameters in lambda-expressions. If there are no program variables then it should be written either () or NIL.

Rest or arguments to prog-expression are commands and atomic symbols. Prog-exression is computed by executing commands in the order as they are written in the prog-expression. Terms “command” and “execution” as opposed to “term” and “computing” show an important difference: obtained value is ignored.

Variables can be “installed” inside a prog-expression. Variables are installed by M-expressions such as a := b.

Command return/[e] is executed so that /e is computed after which prog-expression ends computing with the value obtained by computing e. If prog-expression runs out of commands to execute, it ends the computation with value NIL.

Command go/[s] causes continuation of prog-expression execution from the command directly after symbol /s. Translation of prog-expressions into S-expressions is somewhat more complex and is not at all described in the literature. From examples is obvious that M-expressions a := b translates into (SETQ a^* b^*), pseudo-functions SET and SETQ are behaving like in CSET and CSETQ, minor the difference they are applied on variables. Command /go/[s] is translated into (GO s) and command /return/[e] into (RETURN e^*). Inside the prog-expressions, symbols that serve as names of commands are translated directly, without QUOTE.

16.9. GENSYM AND OBLIST

One of most interesting functions in Lisp 1.5 is /gensym/[] which every time it is called generates a new symbol, previously not used in the program. In Lisp 1.5 those symbols had names G00001, G00002, G00003, …

The Manual does not describe how the function gensym could be used. From only few documented examples of usage it can be observed two, somewhat different usage patterns.

Generating new, previously unused symbols is often needed operation while processing logic formulas. For example, first two axioms of propositional calculus, written in symbolic expressions form are:

(→ A A)
(→ B (→ A B))

If axiom 1. is substituted into axiom 2. instead of B into axiom 2. it is obtained

(→ (→ A A) (→ A (→ A A)))

From 1. and 3. follows after modus ponens

(→ A (→ A A))

That theorem is weaker then theorem (→ A (→ G00001 G00001)) which would be obtained if all symbols used in 1. theorem were substituted with new, previously unused symbol. Expression

sublis[cons[cons[A; gensym[ ]]; NIL]; (→ A A)]

is computed into (→ G00001 G00001), if G00001 is first unused symbol. Function gensym was used in such way in Abrahams’ program PROOFCHECKER.^257,258

Second reason for which function gensym was used is processing of Lisp code. For example^259, recursive function search/[l;p;h;u] in list /l searches y for which is p/[y] = *T*; if it is found, value of the function is /h/[y]; if it is not, value of the function is /u. The function is defined with expression

search[l; p; h; u] = [null[l] → u; p[car[l]]→ h[car[l]]; T·→ search[cdr[l]; p; h; u]].

Such defined function is slow because during the every call, are used arguments p, f and u which are not changed. A possible solution is exchanging function search with function compsearch/[l;p;h;u] which for every argument quadruple defines and calls a new, similar to function /search, but more efficient function searchf. Definition of searchf has form

searchf[g] = [null[g]→ u; pf → hf; T·→ searchf[cdr[g]]],

where g is some generated symbol, for example G00001, and pf and hf are M-expressions which has same effect as p/[car[g]] and /h/[car[g]], which are not applications of functions /p and h, but are constructed from the definitions of functions p and h. For example, if

h[y] = [y = NIL → NIL; T → λ[[r]; cons[r; y]][cons[y; y]]]

then in place of hf it should be

[car[g] = NIL → NIL; T → λ[[r]; cons[r; car[g]]][cons[car[g]; car[g]]]].

Generated symbol g is needed because any other symbol could already be in use in the body of function h, just like in previous example symbol r was used. Similar holds also for pf.

The system keeps a list oblist which holds all symbols used by the programmer. Generated symbols are not stored into oblist, which makes them different from symbols used by the programmer, even if the programmer on purpose uses symbols with same names.

16.10 SYMBOLS T, **T** AND NIL

Some of the changes in Lisp 1.5 are motivated completely practically. Symbolic expression (QUOTE T) was used so often in programs, specially in the last part of cond-expression, that a trick was often used. Instead with the symbol T, the truthness was represented with the symbol **T** and symbol T had the value **T**. Likewise, as example, an expression from “pure Lisp”

(COND,((EQ,Z,Y),X), ((QUOTE,T),Z))

was not correct in Lisp 1.5. Instead, it should be written

(COND ((EQ Z Y) X) (T Z)).

Value of the symbol **T** is **T**.

Analogous, the falsehood was represented with the symbol NIL. Value of F is NIL. Value of the symbol NIL is NIL.

Predicates are defined as functions for which values has at most two values: **T** and NIL.

In functions of Lisp 1.5 which as arguments expect T or NIL every other value is processed equally to **T**.

In conditions from conditional expressions any value different from NIL can be used instead of **T**.

Those decisions, beside shortening programs, made the language at same time more complex and less beautiful. The authors of the manual described the mentioned definitions with the phrase “Humpty Dumpty semantics”.^260

In similar, pragmatic, but not so elegant way are redefined also some functions from “pure Lisp”. For example, function eq in Lisp 1.5 is defined also on non-atomic expressions and value of that function is true if function arguments have same representation in computer memory.

16.11 ARTITHEMTIC

McCarthy wished from the early beginning for Lisp to also be suitable for numerical computations.^261 Unfortunately, the arithmetic implementation in style of Woodwards and Jenkins was not efficient enough for practical applications so Lisp 1.5 supports the arithmetic similar to Fortran and other programming languages. For example, the epxression 123 + 456 is in Lisp 1.5 represented with meta-expression

/plus/[123;456]

which is computed into value 579, while 123, 456 and 579 are symbols. Those symbols are different from others, so they are called “pseudo-atomic symbols”.^262 Values of symbols 123, 456 and 579 are in order 123, 456 and 579 and can not be assigned other values. For that reason meta-expressions containing numbers translate into symbolic expressions without symbol QUOTE. For example, meta-expression /plus/[123;456] is translated into symbolic expression (PLUS 123 456). Same numbers written in different way, for example, 123 and 123.00 are considered to be same symbol.

Lisp 1.5 supported numbers with fix and floating comma. Defined is about twenty basic functions on numbers.

16.12 FIELDS

Fields are defined with pseudo-function array. For example after definition

array[((ALPHA (7 10) LIST) (BETA (3 4 5) LIST))]

alpha and beta are functions that behave in a specific way. Value alpha at coordinates 5 and 6 is set to value 8 by expression

/alpha/[SET;8;5;6]

after which expression /alpha/[5;6] has value 8. Symbol LIST is obligatory, and from the manual it is clear only that authors were thinking also about other fields, in which some other symbol would be used.

16.13 LOGIC

Considering the purpose of Lisp and relative maturity of the language in time when Manual was published, support for logical operations, specially for processing logic expressions was surprisingly weak.

There is no special logical type. NIL denotes non-truth and all other values represent truth. Number of supported propositional opeators is small: OR, AND and NOT, and there exist versions to be applied on bits: LOGAND, LOGOR, included is also LOGXOR (“exclusive or”). Other propositional operators could be easily defined; for example,

implies[x;y]=~x∨y,

but same argument holds for many other arithmetic functions which still were supported in the language.

Only two functions which can be useful during processing logic expressions (and not just logic values) are already described SUBST and GENSYM.

Much later, McCarthy advised to augment Lisp with support for processing logic expressions^263 which existed only in experimental dialects of the language.

236 “LISP 1 was characterized by great elegance, but in practice it turned out to be a language in which it was impossible to write useful programs. This situation led to many additions to LISP 1, and the result of these additions has become known as LISP 1.5 (since it was believed to be halfway between LISP 1 and LISP 2).” Abrahams pod LISP 1. misli na “čisti LISP” − private communication Abrahams, Symbol manipulation languages, 1968., p. 69. 237 “Experience with the present LISP system on a number of small problems has shown the importance of being able to compute with other quantities than symbolic expressions, and a revised version of LISP is being considered which will allow computation of recursive functions of a wide variety of kinds of information.” McCarthy, The LISP programming system, RLE QPR 056, 1960., p. 159. 238 “… they never documented or wrote down anything, especially McCarthy. Nobody in that group ever wrote down anything. McCarthy was furious that they didn’t document the code, but he wouldn’t do it, either.” Fox, An interview with Phyllis A. Fox, 2005., p. 30. 239 McCarthy et al., LISP programmer’s manual, 1959. 240 McCarthy et al., LISP preliminary programmer’s manual, 1960. 241 McCarthy et al., LISP I. programmer’s manual, 1960. 242 Levin, Arithmetic in LISP 1.5, AIM-024, 1961. 243 Dijkstra, Trip report, Edinburgh and Newcastle, EWD 448., 1974. 244 Saunders, LISP — on the programming system, 1964. 245 Pitman, Special forms in Lisp, 1980. 246 Term fexpr is probably abbreviated form for the term “functional expression”. Former term was used for meta-expressions in McCarthy, RFSE, MIT AIM-008, 1959., p. 4. in meta-expressions, as well as in expressions whose first element is an fexpr symbol QUOTE is not needed. 247 “… pure language was supposed to be based on functions, but its most important components — such as lambda expressions, quotes, and conds — were not functions at all, and instead were called special forms. (…) In the practical language things were better. There were not just EXPRs (which evaluated their arguments), but FEXPRs (which did not). My next questions was, why on Earth call it a functional language? Why not just base everything on FEXPRs and force evaluation on the receiving side when needed? I could never get a good answer (…)” Kay, Early history of Smalltalk, 1996., p. 534. 248 See chapter New function eval. 249 Stoyan, The influence of the designer on the design, 1991., p. 420. 250 “We also need a special rule to translate functional arguments into S-expression. If fn is a function used as an argument. then it is translated into (FUNCTION fn*). Example An examination of evalquote shows that QUOTE will work instead of FUNCTION provided that there are no free variables present.” McCarthy et al., LISP 1.5 programmers manual, 1962., p. 21. 251 Saunders, LISP — on the programming system, 1964. 252 Stoyan, LISP history, 1979., p. 47. 253 McCarthy, History of LISP, 1981., p. 180. 254 “And I never understood the complaint very well, namely, I said : ‘oh, there must be a bug somewhere, fix it!’ And Steve Russell and Dan Edwards said, there is a fundamental difficulty and I said, there can’t be, fix it, and eventually they fixed it and there was something they called the funarg device. He tried to explain it to me but I was distracted or something and I didn’t pay much attention so I didn’t really learn what the funarg thing did until really quite a few years later. But then it turned out that these same kinds of difficulties appeared in ALGOL and at the time, the LISP solution to them, the one that Steve Russell and Dan Edwards had simply cooked up in order to fix this bug, was a more comprehensive solution to the problem than any which was at that time in the ALGOL compiler.” McCarthy, Talk about LISP history, 1974., cited from Stoyan, History of Lisp, 1979., p. 47. 255 “Thus the system eval will accept functional arguments only when they are preceded by FUNCTION, which is both a theoretical and practical nuisance.” McCarthy, New eval function, AIM-034, 1962., p. 8. 256 See chapter Fortran-like commands and function program. 257 Abrahams, Application of LISP to checking mathematical proofs, 1964., p.141. 258 Abrahams, The proofchecker, AIM-021, 1961., p. 9. 259 McCarthy et al., LISP I manual, 1960., p. 139. 260 The phrase is used in the context of “corrupted and irredeemable”. McCarthy et al., LISP 1.5 programmer’s manual, 1962., p. 22. 261 McCarthy, Notes on improving Lisp, 1986., p. LP-I.2.3. 262 McCarthy et al., Lisp 1.5 programmer’s manual, 1962., p. 14. 263 McCarthy, Beyond Lisp, 2005., img. 4.

17 Mathematical Theory of Computing

During 1961. and 1962. McCarthy gave several presentations about mathematical theory of computations on scientific gatherings. During the midterm 1961., at Western Joint Computer Conference in Los Angeles, McCarthy held the presentation A basis for a mathematical theory of computation - preliminary repport. Same year, presentation with same theme was given on a seminarium in IBM’s school in Blaricuum, Netherlands. The presentation was published first in 1963. in book Computer programming and formal systems, but it was also contained in a much older AIM-031 from january 1962. It seems that in the article from 1963, the name LISP appears for the first time in form Lisp.^264 Second presentation, Towards a mathematical science of computation was held at second IFIP congress in München, Germany and was published in the congres’s journal,^265 as published on McCarthy’s Web pages. Those two publications cover and complement each other in many parts.

McCarthy suggests development of “mathemtical theory of computation”. One element of the computing theory is the development of a universal programming language. McCarthy claims that formalism he describes, very similar to generalized “pure Lisp” is not a suitable candidate for universal programming language but the reason he cited was not very strong.^266

A mathematical theory of computation would be very useful in practice. Programming languages cold be developed systematically, and proofing the correctness of a program could almost completely substitute “debugging”.^267 Amongst goals of the mathematical theory of computation, is also representation of an algorithm with symbolic expressions so that important changes in algorithm behavour can be represented with small changes in symbolic expressions. He also states a bold claim that the consciousness of algorithm representation is also accessible and suitable for processing by another algorithm.^268

17.1 FUNCTIONS DEFINED BY BASIC FUNCTIONS

There are five basic functions in “pure Lisp” defined over symbolic expressions, and from them could other functions be defined according to certain rules. Here, McCarthy allows any set of “basic functions” F defined over any arbitrary set, and then defines functions computable on basis of those functions. Set of all computable functions over basis F is denoted C{F}. Means with which functions can be defined are same as those in “pure Lisp”.

For exampl⋜e, using only two basic functions over non-negative numbers, succ(n)=n’, for example, succ(8)=9 and eq (n_1, n_2) = T if and only if n_1 and n_2 are equal, it is possible to define function pred (n) inverse to function succ, addition, multiplication, relation ≤ and many other functions. All those functions are defined relatively naturally, for example,

m ≤ n = (m = 0) ∨ (~ (n = 0) ∧ (pred(m) ≤ pred(n))).

17.2 FUNCTIONALS

Specially, rules for defining functions allow use of functions as arguments to functions. For example, functions map and apply are functionals. McCarthy introduces a hierarchy, separation of functionals into “orders”. First order functionals are functions which take arguments from a base domain (in case of Lisp, symbolic expressions). Second order functionals take arguments from the base domain or first order functionals, etc.

Some functionals are not in this hierarchy. For example, functions can be defined so that they accept themselves as arguments. Unfortunately, McCarthy stayed on a remark and didn’t ever try to describe more sophisticated classification of functionals.

17.3 REMOVABILITY OF LABEL-EXPRESSIONS

Functions that accepts themselves as arguments are used for proof that label-expressions are not necessary for defining recursive functions. The proof is based on substitution of a function f(x) with more abstract function p(x,ϕ) which can be defined non-recursively, applied on itself, p(x,p). McCarthy shows that with suitably defined function p, for every x for which f(x) is defined, holds

f(x) = p(x,p).

During the computation p(x,p) calls itself, despite that call was not necessary while defining p. Specially, f = λ((x), p(x, p)). It is left to show how to define p. For example, let

fact(n) = (n = 0 → 1, T → n·fact(n − 1)).

Function fact can be defined with a label-expression

fact = label(f, λ((n), (n = 0 → 1, T → n· fact(n − 1)))).

Function p can be defined as a function that computes factorials directly by computing only base case, n = 0, and for all others, more demanding cases, by calling some other function.

p(n, ϕ) = (n = 0 → 1, T → n · ϕ(n − 1)).

Function p is not a recursive function. Specially, if second argument of function p is function fact then also p computes factorials, i.e. p(n,fact)=fact(n).

Application of function p on any other function gives correct results for n = 0. For example p(0,sin)=fact(0).

Since p is a function of two variables, if application of function on itself will have sense, the definition has to be slightly changed

p(n, ϕ) = (n = 0 → 1, T → n· ϕ(n − 1, ϕ)). (*)

Function p is still not recursive. Specially, it holds

p(n, p) = (n = 0 → 1, T → n· p(n − 1, p)). (**)

It follows that

p(n, p) = fact(n).

We could think that p(n), after the expression (***) is anyway a recursive functon. But, equality (**) is not a definition of function p, but only a result of substitution of p for ϕ, and function definition (*) is not recursive, and thus it is possible to define function p also with lambda-expression

p = λ((n, ϕ), (n = 0 → 1, T → n· ϕ(n − 1, ϕ))).

Function p is still a function of two variables, and is not identical to function fact. But, function

λ((n), p(n, p))

is also not recursively defined, and can be defined with label-expression

fact2 = λ((m), p(m, p))

and for every n = 0, 1, … holds fact_2(n)=fact(n).

Same technique McCarthy applies also in general case. Let f be a recursive function defined by label

f(x) = E(x,f)

where E is an expression in which x and f appears. Fucntion f can be defined with a label-expresison which we wish to avoid. Let p be a function defined with expression

p(x, ) = E(x, λ((y), ϕ(y, ))).

Function p is not recursive so

p = λ((x, ϕ), E(x, λ((y), ϕ(y, ϕ))).

Function f_2 is defined with expression

f_2(x) = p(x, p).

Function f_2 is not recursive, so it can be defined with lambda-expression

f_2 = λ((x), p(x, p)).

Then for every x holds

f_2(x) = p(x, p) = E(x, λ((y), p(y, p)) = E(x, f_2).

Function f_2(x) defined exclusively with lambda-expessions is identical to f(x) for all x = 0, 1, 2, … Definition itself is, if unfolded, unusually conplex:

f = f_2 = λ((x), p(x, p)) = = λ((x), λ((z, ϕ), E(z, λ((y), ϕ(y, ϕ))) (x, λ((v, ψ), E(v, λ((w), ψ(w, ψ)))) )

McCarthy’s derivation holds, with some unsignificant changes, also for functions of several variables.

17.4 CONDITIONAL EXPRESSIONS ARE NOT FUNCTIONS

It could be thought it is possible to define function cond_n in 2n varibables for a given natural number so that

(p_1 → e_1, …, p_n → e_n) = condn(p_1, …, p_n, e_1, …, e_n).

According to McCarthy, it is not possible because “normally” all function agruments must be defined. For conditional expessions though, it is important that some of p_i and e_i are not defined. For example, in definition of factorial

n! = (n = 0 → 1, T → n ∙ (n − 1)!)

sub-expression n ∙ (n − 1)! is not defined for n = 0.

17.5 NON-COMPUTABLE FUNCTIONS

Beside lambda- and label-expressions, McCarthy develops new expressions with which functions could be defined. Let e be an exression which can have values T and F, and which contains variable x. We can define new form

T if e has value T for all x ∀((x), e = F if e has value F for at least one x undefined otherwise

With help of that form we can define other functions that are not S-functions, i.e. they can not be defined in Lisp because ∀((x), e)=F is defined even in case when e i computed infinitely for some expression x.

17.6. Multivalued functions [OBS! Viseznacne = multivalued?]

Multivalued functions have for avery argument a given set of valid values, and during the execution one of those values is chosen. Basic v function is amb(x,y) which at execution chooses one of values x,y. Other functions can be defined by using function amb, for example

less(n) = amb(n − 1, less(n − 1)), ult(n) = (n = 0 → 0, T → ult(less(n)))

Then holds

∀((n), ult(n) = 0) = T.

17.7 RECURSIVE DEFINITION FOR SETS OF SYMBOLIC EXPRESSIONS

Some results described in presentations are interesting foremost to Lisp community. In original Lisp, symbolic expressions are sequences of symbols; for example ((A.B).C). Lists, such as (A,B,C) were abbreviations, in this case (A.(B.(C.NIL))). Here McCarthy defines symbolic expressions as ordered n-tubles over some such base set.

Let A be a set of symbols {A,B,C,AA,…}. Let (a · b) be a notation for an oredered pair. Then, for example, (((A · B) · C) is an element of set (AXA)XA. Set of al symbolic expressions over A is denoted sexp(A). Then recursive definition of a set of symbolic expressions holds

sexp(A) = {Λ} ∪ A ∪ (sexp(A) × sexp(A)).

Set of all lists over A is a set of all symbolic expressions in form

(a_1, …, a_n) = (a_1 · (a_2 · … (a_n· Λ)))

where a_1, …, a_n are symbolic expressions. That set is the solution for the equation

seq(A) = {Λ} ∪ A × seq(A).

Over those sets can usual Lisp functions such as car, cdr, cons, atom, eq be defined.

17.8 RECURSIVE INDUCTION

In usual mathematical induction, if we wish to proof the equality in which variable n appears holds for every natural number n≥0, it is enough to proof that

equality holds for n = 1;
if equality holds for n-1 then it also holds for n.

McCarthy introduces analogous method for proofing equality of functions over symbolic expresions which he calls recursive induction.

Let g(x_1, …, x_n) and h(x_1, …, x_n) be functions over symbolic expressions and it needs to be shown that for all x_1, …, x_n holds

g(x_1, …, x_n) = h(x_1, …, x_n).

Then it is enough to proof that there exists i such that

if /null/[x_i] then g(x_1, …, x_i, …, x_n) = h(x_1, …, x_i, …, x_n);
if g(x_1, …, cdr[x_i], …, x_n) = h(x_1, …, cdr[x_i], …, x_n) then
g(x_1, …, x_i, …, x_n) = h(x_1, …, x_i, …, x_n).

For example, let x*y be concatenation of lists x and y. For example,

(A B) * (B (C D)) = (A B B (C D)).

Function x*y is defined with

x * y = [null[x]→ y; T → cons[car[x];cdr[x]*y].

McCarthy shows that concatenation is associative operation, i.e. that for all symbolic expressions x, y and z holds

[x * y] * z = x * [y * z].

For the left side of the equality holds

[x * y] * z = [null[x] → y; T → cons[car[x]; cdr[x] * y]] * z = [null[x] → y * z; T → cons[car[x]; cdr[x] * y] * z] = [null[x] → y * z; T → cons[car[x]; [cdr[x] * y] * z]].

For the right side of equalith holds

x * [y * z] = [null[x] → y * z ; T → cons[car[x]; cdr[x] * [y * z]]].

From the last two equality follows

if /null/[x] then [x*y]*z = x*[y*z];
if [cdr[x] * y] * z = cdr[x] * [y * z] then [x * y] * z = x * [y * z]

what was necessary to proof.

McCarthy’r student Lewis M. Norton proofed in early 1962. about twenty lemmas and theorems about equality of expressions that contain applications of function subst.^269

17.9 ABSTRACT SYNTAX OF PROGRAMMING LANGUAGES

In volumnous litterature prevailes the concensus that McCarthy introduced the idea of abstract syntax of programming languages.^270 Abstract syntax is defined with functions which (1) recognize the kind of term, symbolic expressions legal in a programming language, (2) analyze terms and (3) synthetize terms.

For example, let there be a given programming language in which only arithmetic expressions exist and the only operations are addition and multiplication of two arguments. The abstract syntax of that language is described with following sequence of functions:

Predicates that recognize the term kind: isconstant(t), isvariable(t), issum(t) and isproduct(t). Predicate equalvariable(t,u) which checks if two symbols are repetition of same variable.
Functions that factor out members of sum and product: augment(t) and addend(t), multiplier(t) and multiplicand(t).
Funkcije koje synthetize expressions: makesum(t,u), makeproduct(t,u)/.

If an implementation of a programming language make use only of above stated functions during the processing of a term, then it does not effect the implementation if terms are in form of a+b, +ab, (PLUS A B) or even Gödel’s numbers.

Abstract syntax has two advantages over back then popular Backus normal forms. First, Backus’ normal forms are synthetic; they don’t give rules for subdivision of a program in parts. McCarthy’s abstract syntax is synthetic, but also analytic, it makes it possible to subdivide a program in parts. Second, abstract syntax is independent of the concret syntax of a programming language.

McCarthy didn’t tried to connect Lisp with abstract syntax, but the way in which Lisp is defined - with functions applied on symbolic expressions - it makes it almost the language of the abstract syntax. McCarthy’s definition of eval, in “pure Lisp” and Lisp 1.5, still though, contain complex M-expressions used for factoring out parts of S-expressions, which means they are not written with abstract syntax in mind.^271 Later, McCarthy held that every language, including Lisp should also include functions that support it’s abstract syntax, and that languages should have several different syntaxes, for different purposes.^272

The idea of abstract syntax allows for generalizations about which McCarthy didn’t speak: defining language by more complex data structures than symbolic expressions alone, for example, list structures.

17.10 SEMANTICS

To define a semantic of the described arithmetic programming language, i.e. the meaning of the language terms, according to McCarthy we should define

function valueconstant(t) whose value is a number denoted by t.
function valuevariable(t,x) whose value is equal to number assigned to symbol /t in association list x.
function makeconstant(n) whose term denotes number n

Function valuvariable is identical to already known function assoc. Finally, it is possible to define value(t,x), the meaning of term t for given vector of machine states x:

value(t, x) = (isvariable(t) → valuevariable(t, x), isconstant(t) → valueconstant(t), issum(t) → value(addend(t), x) + value (augend(t), x), isproduct(t) → value(multiplier(t), x) · value(multiplicand(t), x))

Function value(t,x) in arithmetic language is analogous to function eval(e,a) in Lisp.

More generally, program meaning is defined by result of applying the program to a machine state vector. Entire programming language can be defined as a function, for example

x’=algol(p,x)

Where p is any program and x’ and x are machine state vectors, associative lists of variables and values.

McCarthy’s thoughts are generalizations of concepts known from Lisp. Scientific community stand divided about importance of McCarthy’s presentations. For example, while Dines Bjørner sees them as a “great classics of computer science”^273, Martin Davis left “unconvinced of any of McCarthy’s ideas presented in first presentation.”^274

264 McCarthy, A basis for a mathematical theory of computation, 1963., p. 52 265 McCarthy, Towards a mathematical science of computation, 1962. 266 “We believe that this goal has been written off prematurely by a number of people. Our opinion of the present situation is that ALGOL is on the right track but mainly lacks the ability to describe different kinds of data, that COBOL is a step up a blind alley on account of its orientation towards English which is not well suited to the formal description of procedures, and that UNCOL is an exercise in group wishful thinking. The formalism for describing computations in this paper is not presented as a candidate for a universal programming language because it lacks a number of features, mainly syntactic, which are necessary for convenient use.” McCarthy, A basis for a mathematical theory of computation, 1963., p. 34. 267 McCarthy, Towards a mathematical science of computation, 1996., p. 6. 268 “Programs that are supposed to learn from experience change their behavior by changing the contents of the registers that represent the modifiable aspects of their behavior. From a certain point of view, having a convenient representation of one’s behavior available for modification is what is meant by consciousness.” McCarthy, A basis for a mathematical theory of computation, 1963., p. 34. 269 Norton, Some indentities concerning the function subst[x; y; z], AIM-037, 1962. 270 Bjorner, Software engineering 2, 2006., p. 87. 271 “Lisp is close to its abstract syntax, but needs it anyway.” McCarthy, Beyond Lisp, 2006., sl. 2. 272 McCarthy, Guy Steele interviews John McCarthy, father of Lisp, 2009. 273 Bjorner, Software engineering 2, 2006., p. 87. 274 Davis, Review of John McCarthy, A basis for a mathematical theory …, 1968.

18 Gilmore’s lisp-like language

In same book as McCarthy’s article A basis for a mathematical theory of computation, is also published an article by Paul C. Gilmore, An abstract computer with Lisp-like machine language without label operator, probably the first “independent” attempt to improve Lisp and the only such attempt in the period which is the subject of this book.

Gilmore considers more generally defined Lisp, defined by a class of primitive functions F over some given set U, “universe”, which does not necessary need to be the set of all symbolic expressions. It is necessary, though, that the elements of the universe, primitive functions and operator cond can be represented as strings. With C(F) is denoted a class of all functions that can be defined as in McCarthy’s paper Recursive funcions over symbolic expressions.

18.1 CONDITIONAL EXPRESSIONS

McCarthy’s Lisp has, according to Gilmore, two deficiencies. One is in the definition of the condition expression, (p_1 → e_1, …, p_n → e_n), where p_1, …, p_n are propositional expressions with “logical values”, T or F. Because of that, symbols T and F have to be elements of the universe U and at least some of the primitive functions have to have them as values. Gilmore defines conditional expressions in form

cond(x, y, z, w) = z if x and y are equal w otherwise

for which T and F does not have to be elements in the universe. McCarthy’s conditional expression can be defined as a composition of Gilmore’s conditional expressions. For example, for n = 2 holds

(p_1 → e_1, p_2 → e_2) = cond(p_1, T, e_1, cond(p_2, T, e_2, e)),

where e is any expression.

18.2 QUOATE AND LABEL

Second, bigger problem is in operators quote and label which do not belong “naturally” into the theory of computable functions. McCarthy’s elimination of label-expressions does not satisfy Gilmore because he searches for additional assumption that functions can accept themselves as arguments, and alternative, non-recursive definitions are significantly more complex from starting ones.

The need for operators quote and label is, to Gilmore, a consequence of not recognizing that symbols in Lisp are used in different ways, as:

elements of universe U which can be arguments to funcitons or operators;
names of elements of universe U; for example, truth and false can be elements in U, and their names are T and F;
name for functions or operators, primitive or defined ones.

Gilmore succeeds in avoiding operators quote and label by introducing the ”initial load operation”, for example

!: (lambda, x, cond(x, 1, 1, x · (x − 1)!).

He held that this does not violate “drastically” the simple structure of Lisp. Initial command is very similar to operators cset or csetq from Lisp 1.5. Since Gilmore does not compare those two commands, at the time he wrote the article, he probably wasn’t familiar with the Lisp 1.5 about which first articles were published first in 1962.

18.3 ABSTRACT MACHINE

The semantics of lisp-like language is described with a virtual abstract machine with an infinite number of memory places denoted with characters (wihout “:”). In every memory place can be stored a sequence of characters (again, without “:”) of arbitrary length. Initial load command s_1:s_s is executed by writing the string s_2 into memory location s_1. Since s_1 and s_2 must not contain character “:” load commands could not be nested. Since now every expression could be loaded into some address, and if needed used, there is no need for the operators quote and label in the lisp-like language.

Gilmore considered the virtual machine as a useful tool which simplifies the language implementation, described in details in the article, and at the same time indicate some possible problems when implementing it on real computers. To simplify presentation, Gilmore assumes there are no “clashes of bound variables”, in expressions like

(lambda, x, (lambda, x, x))

where it is not clear if the last appereance of x is bound to first or second lambda. That problem can be avoided, for example, if computation of lambda expression is preceded by variable renaming, or if it is left to programmers to take care of avoiding variable clashes.

The advantage of the “lisp-like” language is the possibility to use not just symbols, but also symbolic expressions as variables, even if it is not easy to find an example where such generalisation would be useful. New syntax, even if it is not, as Gilmore writes, “drastically different”, does not seem necessary.

Gilmore’s articles almost had no echo in the Lisp community. But, it was cited by Landin, 1965., in an important paper A generalisation of jumps and labels as an early exmaple of introducing imperative elements into a “purely functional” or a “referencially transparent” language. Since Landin introduced several abstract machines, he was probably influenced by Gilmore. Overheu^275 developed an alternative abstract machine which keeps the advantages of Gilmore’s machine - removal of quote, label and more general cond-expressions.

275 Overheu, An abstract machine for symbolic computation, 1966.

19 Memoization

Memoization discovery is usually described to Richard Bellman^276 and the idea was named and popularized by Donald Michie.^277 McCarthy’s memo On efficient ways of evaluating certain recursive functions from 1962.^278 is one early example of using memoization.

Naive recursive implementation of some algorithms is innefficient because some functions are computed needlessly for same argument values. Most simple example is the example for computing Fibonacci numbers

fibonacci[n] = [n ≤ 1 → 1; T → fibonacci[n − 1] + fibonacci[n − 2]].

Computing function value of fibonacci for big n is slow, because the function call itself many times with same arguments and repetedly calculates the function value. For example, /fibonacci/[n − 2] is computed twice, /fibonacci/[n − 4] four times, /fibonacci/[n − 6] eight times etc.

Similar example is computing number of partitions of natural number. For example partitions of number 5 are 5, 4+1, 3+1+1, 3+2, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

McCarthy defines function q/[m;n] which computes number of partitions for number /m, such that any of addends is not bigger then n. Function is defined by the expression

/q/[m; n] = [m = 1 ∨ n = 1 → 1; m ≤ n → /q/[m; m − 1] + 1; T → /q/[m − n; n] + q[m; n − 1]].

Computing this function is innefficient because function q is called many times with same arguments. To avoid that, McCarthy defines function so that results of computations are stored in a list of form ((m,n,q[m; n]), …). If some of defined functions expects that list as an argument, corresponding parameter is called known.

Help function /present/[m; n; known] is a predicate whose value is T if an element of the list in form of (m,n,qmn) is in the list known.

present[m; n; known] = ~ null[known] ∧ [[eq[caar[known]; m] ∧ eq[cadar[known]; n]] ∨ present[m; n; cdr[known]]]

Help function /val/[m; n; known] is defined only for those values m, n and known for which is /present/[m; n;known] = T and has then value qmn.

val[m; n; known] = [eq[caar[known]; m] ∧ eq[cadar[known]; n] → caddar[known]; T → val[m; n; cdr[known]]]

Help function prob/[m; n; known] has as a value list /known, if it needs it needs the augmented, so it includes (m,n,qmn).

prob[m; n; known] = [present[m; n; known] → known T → λ[[v];cons[list[m; n; v]; known]] [[m = 1 ∨ n = 1 ∨ m = 0 → 1; m ≤ n → val[m; n − 1; prob[m; n − 1; known]] + 1; T → λ[[p]; val[m − n; n; p] + val[m; n − 1; p]] [prob[m; n − 1; prob [m − n; n; known]]]]]]

The tehnique which avoids multiple calls of function s with same arguments is in the last two rows. If McCarthy wrote

T → val[m − n; n; prob[m − n; n; known] + val[m; n − 1; prob[m; n − 1; known]

some calls of function prob, including prob/[m; n; NIL], would call function /prob twice and would be equally inneffective as calls to function /q/[m; n].

Generally, if we wish to avoid computing of expression e twice in

g/[…, /e, …] + h/[…, /e, …]

we can use

λ[[p]; g[…, p, …] + h[…, p, …]][e].

Association lists obtained by computing

/prob/[m − n; n; known] and /prob/[m; n − 1; known]

are not equal. Despite, in this context both can be substituted with

/prob/[m; n − 1; /prob/[m − n; n; known]].

While computing that expression function prob is called twice, but the value obtained by computing the inner call to the function is used for computing the outer call to the function. Finally,

/q/[m; n] = /val/[m; n; /prob/[m; n; NIL]].

Still, q is computed relatively slowly becuase functions present and val search list known lineary. McCarthy observes that it would be more effective to use hash tables.

McCarthy gave assignement to students to write a function to transform any S-function into equivalent function which is not computed multiple times for the same argument and to proof by induction the corretness of the function.

McCarthy’s example was published 1968. by D.W. Barron.^279

276 Bellman, Dynamic programming, 1957. 277 Michie, Memo functions and machine learning, 1968. 278 McCarthy, On efficient ways of evaluating certain recursive functions, AIM-032, 1962. 279 Barron, Recursive techniques in programming, 1968., p. 18-19.

20 New function eval

McCarthy’s memo MIT AIM-034, New eval function written 1962.^280, latest 6. March^281, is a late unswer on unsasisfying processing of functions as arguments, in “theoretic” as well as in “system” Lisp.

McCarthy introduces several changes in notation. As in memoes about computability theory, he used round parenthesis in meta-expressions instead of rectangular. He denotes parenthesis with arbitrary number of dots or commas. For example, ..) closes parenthesis (.. and also all other parenthesis opened between those two signs. In conditional expressions he writes t instead of T and thus conditional expressions are translated in the form of Lisp 1.5, i.e. (COND … (T …)) instead of (COND … ((QUOTE T) …)) as in “pure Lisp”.

20.1 AUGMENTED LISP

For difference from “pure Lisp”, “system” or “augmented Lisp” stores symbol values in a property list. Expressions of “augmented Lisp” or E-expressions are built from atomic symbols and a pointer (orig. full word pointer), address in memory. Definition of E-expression is

Atomic symbol is E-expression
Pointer is E-expression
if e_1 and e_2 are E-expressions then (e1 . e2) is also an E-expression.

Elementary function car and cdr are not defined for pointers.

Predicate /atom/[x] is true only for symbols, and false for all other E-expressions.

Predicate eq/[x;y] is true if all /x and y are same addresses in memory.

Predicate fullword/[x] is true iff /x is a pointer.

Function value/[x] is defined if and only if /x is a symbol. If x has a vlue v stored in a property list, then

/value/[x] = (VALUE . v).

20.2 NEW EVAL

McCarthy tried to write funciton eval which would enable usage of functions as arguments and was correct commputed reagrdless if values of symbols were given in an associative or a property list.

If e is a symbol, then eval searches for a value of e first in the property list, and if it is not found there then in the associative list a.

If e has form (fn arg_1 … arg_n) then the function fnval is defined first as a result of computing fn.

If fn is a function, then fnval is the address of a function in machine language (which is tested by condition fullword/[fnval]), a lambda- or a label-expression.Then /eval applies (by using app1) fnval over computed values of the arguments.

If fn is fexpr, then fnval has form (fx . FEXPR) where fx is an lambda- or label-expression. Then eval applies fx on a list (args a) where args=(arg_1 … arg_n).

For applying the function over a list, function app1/[f-nval;args;a] is used, similar to function /apply from Lisp 1.5 programmer’s manual. For the difference from apply, function app1 does not compute values of symbols in operator place automatically.

app1/[ /eval [fn; a]; args; a] = /apply/[fn; args; a].

This is how suggested eval looked like, using usual rectangle parantheses and somewhat shorter variable names:

/eval/[e; a] = [atom[e] → /search/[e; λ[[j]; [eq[car[j]; VALUE]]]; cadr; λ[[ ]; /assoc/[e; a]]]; t → prog/[[fnval]; /fnval = eval[car[e]; a] /return/[[fullword[fnval] ∨ eq[car[fnval]; LAMBDA] ∨ eq[car[fnval]; LABEL] → app1[fnval; maplist[cdr[e]; λ[[j]; eval[car[j]; a]]]]; a]; t→ app1[car[fnval]; list[cdr[e]; a]; a]]]]]

New function eval does not have special rules for computing of usage for basic functions car, cdr, cons, atom, eq, nor operators COND or QUOTE but searches for their values just like for any other function of fexprs.

20.3 AUTONOMOUS LAMBDA AND LABEL

Problem that was left was computing lambda- and label-expressions themselves, for example /eval/[(LAMBDA (X) X);a].

McCarthy wasn’t fond of using QUOTE or FUNCTION. Instead, he suggests that lambda- and label-expression should be autonymes, expressions that computes themselves. That stance is consistent: lambda-expressions are introduced into “imperative Lisp” for the purpose of avoiding the computing. McCarthy achieves that by defining LAMBDA and LABEL as fexprs. For example, value LAMBDA can be defined in a property list as

((LAMBDA (E A) (CONS (QUOTE LAMBDA) E)) . FEXPR).

McCarty was still ignoring then already two and a half year old funarg problem. Lisp implementers didn’t accepted McCarthy’s suggestions.^282

280 McCarthy, A basis for a mathematical theory of computation, AIM-031, 1962., p. 1. 281 Norton, Some identities concerning function subst[x;y;z], AIM-037, 1962., p. 1. 282 McCarthy et al., LISP 1.5 Programmer’s manual, 1962., p. 70.

21 First applications of Lisp

In early period, Lisp development absorbed that much time and energi from members of AI project that they joked that Lisp is a language for writing Lisp.²⁸³ Soon, Lisp was though used. First programs used largely capability to represent mathematical and logical expressions as S-expressions.

The earliest descrbied Lisp program - if we don’t take into count examples put together to describe possibilities of Lisp in ealier memoes - is Rochester’s program for deriving expressions of one variable.²⁸⁴ Program searches for derivations of S-expressions containing variable x, constants and operations times, plus and minus. First, instead of x in entire expression is substituted (plus, x, (Δ,x)). Such obtained expressions are converted after sequence of about tenth or so rules which Rochester derived, including symbolic division with (Δ,x), as well as symblic search for the limit. During the processing, expressions are simplified, for example (times, 0, x) is simplified to 0. Program was written in very early Lisp version. Similar program was soon also developed by Maling²⁸⁵ whose diff function is similar to McCarthy’s.^286

Tim Hart implemented during 1961. function simplify, which simplified 45 cases of algebraic expressions.^287

Rochester, Goldberg, Rubentein, Edwards and Markstein studied properties of electric circuits and nets and wrote several programs. They considered Lisp a good choice because of the purpose for which it was designed: to express mathematical and logical algorithms and processing symbolic expressions.^288 McCarthy and others noticed^289 in April 1959. that there is a need to organize data in matrices and for effiecient matrix inversions in that project.

MIT’s first chess program, despite McCarthy and Abrahams taking part in the development, was written in FORTRAN.^290

McCarthy described^291,292,293 a program which uses Wang’s algorithm^294 to check if “sequent” is a tautologi in propositional calculus. Formulas were defined in a following way: Symbols P, Q, R, M, N, etc are formulas. If φ and ψ are formulas then are also ~φ, φ & ψ, φ ∨ ψ, ⊃ ψ, φ ≡ formulas. “Sequents” are expressions in form

φ_1, …, φ_n → ψ_1, …, ψ_m

and they are true if for every value of propositional variables holds: if all formulas φ_1, …, φ_n are true, then at least one of formulas ψ_1, …, ψ_m is true. Propositional formulas are converted into S-expressions as usually. Sequent φ_1, …, φ_n → ψ_1, …, ψ_m is converted into symbolic expression

(ARROW,(φ_1^*,…,φ_n^*),(ψ_1^*,…,ψ_m^*)).

During 1960. or 1961. S. R. Petrick wrote a program for simplification of propositional logic expressions in “pure Lisp”.^295

During 1960. Anthony Valiant Phillips wrote a program that answers on questions in english language on basis of a given text, in hope that program could understand text on a level of a six year old child. For example, based on text

((AT SCHOOL JOHNNY MEETS THE TEACHER) (THE TEACHER READS BOOKS IN THE CLASSROOM))

the program answered the question

(WHERE DOES THE TEACHER READ BOOKS)

with answer

(((IN THE CLASSROOM) (THE TEACHER READS BOOKS IN THE CLASSROOM))).

Despite the program not reaching the desired level, Phillips considered the goal as reachable, and he was also satisfied with Lisp and saw it as important for the success of the project.^296

Slagle developed during his studies at MIT program SAINT for solving indefinite integrals. The subject was chosen, among other reasons, because it includes “manipulations with symbolic expressions” which will probably be fundament for future problem solutions.^297 He graded quality of program himself as on “approximately a level of a good college freshman.”^298

Student Louis Hodes wrote a simple program for “pattern recognition” under leadership of Minski.^299

McCarthy used Lisp for solving simple problems in graph theory.^300

Paul W. Abrahams developed program Proofchecker^301,302 with which he tested proofs in II. chapter of Russell’s and Whitehead’s book Principia Mathematica. All theorems from that chapter belongs to propositional logic. Conversion, even of exceptionally formal language into a form that computer understands posed a problem. Formulas from Principia Mathematica were translated into S-expressions, for example

p ∨ q → q ∨ p

is converted to

(IMPLIES (OR P Q) (OR Q P)).

Already while converting, there were some errors discovered in Principia Mathematica. Substitution operation showed to be especially demanding, for example p → q for ~ p ∨ q and vice versa. Tests of steps in proofs often came down to constructing of a symbolic expression and applying function eval. Proofchecker created and maintained a list of previously proofed theorems, and in start, that list contained only axioms. Every theorem were a list of three elements: theorem name, a list of “substitutable” variables and the proposition of the theorem. For example, theorem

p ∧ q → q

named CONJ was written in list of theorems in form

(CONJ (P Q) (IMPLIES (AND P Q) Q)).

Steps in the proof were saved in a form of list of three elements: number of steps, text of proofed theorem and a list of numbers of formulas used in the proof. The program often needed new variables that were not used in previous formulas for which purpose Lisp function gensym was used.

283 Personal communication with Abrahams, 2014. 284 Rochester, AIM-005, 1958. 285 Maling, The LISP differentiation demonstration program, AIM-010, 1959. 286 McCarthy, Recursive functions…, CACM, 1960. 287 Hart, Simplify, AIM-027, 1961. 288 Rochester et al., Machine manipulation of algebraic expressions, RLE QPR 055, 1959., p. 132. 289 McCarthy et al., Artificial intelligence, RLE QPR 053, 1959., p.123. 290 Norberg, Paul W. Abrahams interview, 2006., p. 10. 291 McCarthy, The Wang algorithm for propositional calculus …, AIM-014, 1959. 292 McCarthy et al., LISP I. programmer’s manual, 1960., p. 25-36. 293 McCarthy et al., LISP 1.5 programmer’s manual, 1962., p. 44-55. 294 Wang, Toward mechanical mathematics, 1960. 295 Petrick, Use of list processing language in programming simplification procedures, 1961. 296 Phillips, A question-answering routine, AIM-016, 1960. 297 Slagle, A heuristic program …, 1961., p. 10. 298 Slagle, A heuristic program …, 1961., p. 7. 299 Hodes, Some results from pattern recognition program using LISP, AIM-018, 1960. 300 McCarthy, Puzzle solving program in LISP, AIM-020, 1960. 301 Abrahams, The proofchecker, AIM-021, 1961. 302 Abrahams, Application of LISP to checking mathematical proofs, 1964.

Images

Image 1. Graphical representation of a word in IBM 704 computer. → 21 Image 2. A list element → 22 Image 3. A List (0.71412, 2.71828, 3.141259) at adress 1001. → 23 Image 4. Two list elements containing same data. Lower list element “borrows” data. The lower list element “borrows” the data. → 24 Image 5. Graphical view of a list. → 30 Image 6. Graphical view of list structure representing the symbolic expression (a, (b,c),(b,(d,e)),f). → 46 Image 7. Graphical vew of a list that modells the sequence 2, 3, 5, 7, 11 and whose external representation is (2,3,5,7,11). → 47 Image 8. Putting symbol x in third place in list L. → 49 Image 9. Result of applying maplist(list(1,2,3),x,x*x). → 52 Image 10. The result of computing maplist(list(1,2,3),car). → 55 Image 11. Scheme of a Turing machine. State of machine is β. Value of the tape field under the reading and writing head is C. → 109 Image 12. Example of a Turing machne tape. → 111 Image 13. A program described by a flow chart. → 117 Image 14. Graphical representation of a list structure corresponding to the expression (A,(B,C),(B,(D,E)),F). → 118 Image 15. Two different memory representations of expression ((A.B),(A.B)). → 118 Image 16. Example of a list structure containing a cycle. → 119 Image 17. Graphical representation of a symbolic expression (A B). → 147 Image 18. Graphical representation of property list for symbol NIL. → 147 Image 19. Property lists of symbolx X and Y before and after call to function /rplaca/[x;y] → 150

BIBLIOGRAPHY

704 electronic data-processing machine − manual of operation. (1955). New York: International Business Machines Corporation. Abrahams, P. (1961). Character-handling facilities in the Lisp system, AIM-022. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Abrahams, P. (1961). The proofchecker, AIM-021. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Abrahams, P. (1964). Application of LISP to checking mathematical proofs. U E. C. Berkeley, & D. G. Bobrow (Ed.), The programming language LISP: its operation and applications (P. 137-159). Cambridge, Massachusetts, USA: The M.I.T. Press. Abrahams, P. W. (1968). Symbol manipulation languages. Advances in computers, 9, 51-111. Abrahams, P. W., Barnett, J. A., Book, E., Firth, D., Kameny, S. L., Weissman, C., i dr. (1966). The LISP 2 Programming language and the system. AFIPS ‘66 (Fall) Proceedings of the November 7-10 1966, fall joint computer conference (p. 661-676). New York: ACM. Andresen, S. L. (October 2002). John McCarthy: Father of Lisp. IEEE Intelligent Systems, 17(5), 84-85. Backus, J. W., Beeber, R. J., Best, S., Goldberg, H., Herrick, H. L., Hughes, R. A., et al. (1956). The FORTRAN automatic coding system for the IBM 704 EDPM. New York: International Business Machines Corporation. Barendregt, H., & Barendsen, E. (2000). Introduction to Lambda calculus. Taken 5. June 2014 from The Programming Logic Group in Göteborg: http://www.cse.chalmers.se/research/group/ logic/TypesSS05/Extra/geuvers.pdf Bellman, R. (1957). Dynamic Programming. Princeton: Princeton University Press. Berkeley, E. C., & Bobrow, D. G. (Ur.). (1964). The programming language LISP: its operations and applications (1st ed.). USA: Information International Inc. Bjørner, D. (2006). Software engineering 2 − specification of systems and languages. Berlin, Germany: Springer Verlag. Bobrow, D. A. (1963). METEOR: A LISP interpreter for string transformations, AIM-051. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Böhm, C. (1954). Calculatrices digitales. Du déchiffrage des formules logico-mathématiques par la machine même dans la conception du programme. Annali di Matematica Pura ed Applicata, 37(4), 1-51. Brayton, R. (1961). LISP error stops as of may 10, 1961, AIM-025. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Brayton, R. (1961). Trace-printing for compiled programs, AIM-023. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Burger, A. (n.d.). PicoLisp reference. Taken 23. February 2014 from http://software-lab.de/doc/ref.html Burger, A. (n.d.). The PicoLisp Reference. Taken 5. June 2014 from Software Lab. Alexander Burger: http://software-lab.de/doc/ref.html Church, A. (1941). The calculi of lambda conversion. Princeton, New Jersey, USA: Princeton University Press. Conrad, T., Conrad, P., Hartline, P., Schlessinger, J., Yates, B., Evans, R., et al. (1961). Handbook of LISP functions. Technical report, RIAS, Baltimore. Davis, M. (March 1968). Review of John McCarthy, A basis for a mathematical theory of computation, preliminary report. The Journal of Symbolic Logic, 33(1), 117. Davis, M. (March 1968). Review of John McCarthy, Recursive functions of symbolic expressions and their computation by machine. The Journal of Symbolic Logic, 33(1), 117. Dezani-Ciancaglini, M., & Hindley, J. R. (2008). Lambda Calculus. U B. Wah (Edt.), Wiley encyclopedia of computer science and engineering. John Wiley & Sons, Inc. Dijkstra, E. W. (1974). Trip report, Edinburgh and Newcastle. Edwards, D. (1963). Secondary storage in Lisp, AIM-063. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Edwards, D. J. (1960). Lisp II garbage collector, AIM-019. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. Edwards, D. J., & Hart, T. P. (1961). The alpha-beta heuristics, AIM-030. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Evans, T. G. (1962). A heuristic program to solve geometric analogy problems, AIM-046. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Faase, F. J. (2006). The origin of CAR and CDR in LISP. Taken

June 2014 from I write, therefore I am: http://www.iwriteiam.

nl/HaCAR_CDR.html Fox, P. A. (7-8. June 2005). An interview with Phyllis A. Fox. (T. Haigh, interviewer) Philadelphia, PA. Gelernter, H., Hansen, J. R., & Gerberich, C. L. (1960). A FORTRAN-compiled list-processing language. Journal of the ACM (JACM), 7(2), 87-101. Giles, H. A. (Edt.). (1889). Chuang Tzu − Mystic, moralist and social reformer. (H. A. Giles, Prev.) London: Bernard Quaritch. Gilmore, P. C. (1963). An abstract computer with a Lisp-like machine language without a label operator. U P. Braffort, & D. Hirschberg (Edt.), Computer programming and formal systems (p. 71-86). Amsterdam: North Holland. Graham, P. (2002). Roots of Lisp. Taken 5. June 2014 from Paul Graham: http://lib.store.yahoo.net/lib/paulgraham/jmc.ps Hart, T. (1961). Simplify, AIM-027. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Hart, T., & Levin, M. (1962). The new compiler, AIM-039. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Henneman, W. (1964). An auxiliary language for more natural expressions − the A-language. U E. C. Berkeley, & D. G. Bobrow (Edt.), The programming language LISP: its operation and applications (p. 239-248). Cambridge, Massachusetts, USA: The M.I.T. Press. Hodes, L. (1960). Programs with common sense, AIM-018. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. Jordan, C. R. (1973). A note on LISP universal S-functions. The Computer Journal, 16(2), 124-125. Kay, A. (prosinac/January 2004-2005). A conversation with Alan Kay. Queue, 20-30. Kay, A. C. (1996). The early history of Smalltalk. U History of programming languages II (p. 511-598). New York, NY, USA: ACM. Landin, P. J. (March 1966). The next 700 programming languages. Communications of the ACM, 9(3), 157-166. Levin, M. (1961). Arithmetic in LISP 1.5, AIM-024. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Levin, M. (1961). Errorset, AIM-026. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Levin, M. (1961). LISP 1.5 Programmer’s manual, AIM-028. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Levin, M. (1963). Primitive recursion, AIM-055. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Levy, S. (2010). Hackers (1st ed.). Gravenstein Highway North, Sebastopol, CA, USA: O’Reilly Media, Inc. Lord, T. (25. October 2011). John McCarthy has passed. Taken

May 2014 from Lambda The Ultimate: http://lambda-the-

ultimate.org/node/4387 Mac Lane, S. (1988). Group extensions for 45 years. The mathematical intelligencer, 10(2). Maling, K. (1959). The LISP differentiation demonstration program, AIM-010. M.I.T., Artificial Intelligence Project. Maling, K. (1959). The Maling-Silver read program, MIT AIM-013. McCarthy, J. (1956). The Inversion of function defined by Turing machines. U C. E. Shannon, & J. McCarthy (Edt.), Automata studies (Svez. 267). Princeton, New Jersey: Princeton University Press. McCarthy, J. (1957). A proposal for a compiler, CC-56. Massachusetts Institute of Technology, Computation Center. McCarthy, J. (1958). A revised definition of maplist, AIM-002. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1958). An algebraic language for the manipulation of symbolic expressions, AIM-001. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1958). Notes on the compiler, AIM-007. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1958). Revisions of the language, AIM-003. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1958). Revisions of the language, AIM-004. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (10. June 1958). Some proposals for the Volume 2 (V2) language. letter. Cambridge, Massachusetts, USA. McCarthy, J. (1959). LISP: a programming system for symbolic manipulations. Proceedings ACM ‘59 Preprints of papers presented at the 14th national meeting of the Association for Computing Machinery. New York: ACM. McCarthy, J. (August 1959). On conditional expressions and recursive functions. Communications of the ACM, 2(8), 2-3. McCarthy, J. (1959). Programs in LISP, AIM-012. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1959). Programs with common sense. Symposium on Mechanization of Thought Processes, Teddington, England,

I, p. 75-92. London: Her Majesy’s Stationary Office.

McCarthy, J. (1959). Recursive functions of symbolic expressions and their computation by machine. Research Laboratory of Electronics, Quarterly progress report, 053, 124-152. Cambridge, MA, Massachusetts, USA: MIT. McCarthy, J. (1959). Recursive functions of symbolic expressions and their computation by machine, AIM-008. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1959). Recursive functions of symbolic expressions and their computation by machine, AIM-011. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1959). The LISP programming system. Research Laboratory of Electronics, Quarterly progress report, 053, 122. Cambridge, MA, Massachusetts, USA: MIT. McCarthy, J. (1960). Programs with common sense, AIM-017. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. McCarthy, J. (1960). Puzzle solving program in LISP, AIM-020. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. McCarthy, J. (1960). Recursive functions of symbolic expressions and their computation by machine. Part I. Communications of the ACM, 3(4), 184-95. McCarthy, J. (1960). The LISP programming system. Research Laboratory of Electronics, Quarterly progress report, 056, 158-

Cambridge, MA, Massachusetts, USA: MIT.

McCarthy, J. (1961). A basis for a mathematical theory of computation − preliminary report. U P. Braffort, & D. Hirschberg (Edt.), Papers presented at the May 9-11, 1961, western joint IRE-AIEE-ACM computer conference (p. 225- 238). New York: ACM. McCarthy, J. (1962). A basis for a mathematical theory of computation, AIM-031. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1962). New eval function, AIM-034. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1962). On efficient ways of evaluating certain recursive functions, AIM-032. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. McCarthy, J. (1962). Towards a mathematical science of computation. U C. M. Popplewell (Edt.), Proceedings of IFIP Congress 62, Munich, Germany, August 27 − September 1, 1962 (p. 21-28). Amsterdam: North-Holland. McCarthy, J. (1963). A basis for a mathematical theory of computation. U P. Braffort, & D. Hirschberg (Edt.), Computer programming and formal systems (p. 33-70). Amsterdam: North Holland. McCarthy, J. (1963). Situations, actions and causal laws. Stanford University, Stanford Artificial Intelligence Project. Springfield: Stanford University. McCarthy, J. (1980). LISP − notes on its past and future. LFP ‘80 Proceedings of the 1980 ACM conference on LISP and functional programming (p. .5 − viii). New York: ACM. McCarthy, J. (1981). History of Lisp. U R. L. Wexelblat (Edt.), ACM SIGPLAN History of Programming Languages Conference, June 1-3, 1978 (p. 173-198). New York: Academic Press, Inc. McCarthy, J. (June-srpanj 1987). Notes on improving Lisp. ACM SIGPLAN Lisp pointers, 1(2), 3-4. McCarthy, J. (1988). The logic and philosophy of artificial intelligence. Taken 31. May 2014 from Kyoto Prize: http:// emuseum.kyotoprize.org/sites/default/files/4kA_e.pdf McCarthy, J. (2. March 1989). An interview with John McCarthy. (W. Aspray, interviewer) Palo Alto, CA, USA: University of Minnesota. McCarthy, J. (1995). Recursive functions of symbolic expressions and their computation by machine. Taken 6. June 2014 from John McCarthy’s home site: http://www-formal.stanford.edu/ jmc/recursive.pdf McCarthy, J. (1996). Towards a mathematical science of computation. (C. M. Popplewell, Ur.) Taken 7. June 2014 from John McCarthy’s Home Page: http://www-formal.stanford.edu/ jmc/towards.pdf McCarthy, J. (2002). John McCarthy: father of AI. 84-85. IEEE. McCarthy, J. (19. June 2002). Some Lisp history and some programming languages ideas. Taken 7. June 2014 from John McCarthy’s Home Page: http://www-formal.stanford.edu/jmc/ slides/lisp/lisp-sli.dvi McCarthy, J. (22. June 2005). Beyond Lisp. Taken 7. Juni 2014 from John McCarthy’s Home Page: http://www-formal.stanford. edu/jmc/slides/lisp/beyond-sli.pdf McCarthy, J. (November 2006). Dartmouth and beyond. Taken 1. Juni 2014 from John McCarthy’s Home page: http://www-formal. stanford.edu/jmc/slides/dartmouth/dartmouth-sli/ McCarthy, J. (12. November 2007). What is artificial intelligence? Taken 31. May 2014 from John McCarthy’s Home Page: http://www-formal.stanford.edu/jmc/whatisai.pdf McCarthy, J. (2008). The philosophy of AI and AI of philosophy. U P. Adriaans, & J. van Benthem (Edt.), Handbook of the philosophy of science − volume 8: philosophy of information (1st ed., Book. 8). North Holland. McCarthy, J. (1. May 2009). Guy Steele interviews John McCarthy. Taken 4. August 2013 from InfoQ: http://www.infoq.com/ interviews/Steele-Interviews-John-McCarthy McCarthy, J. (n.d.). Examples of proofs by recursion, AIM-015. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. McCarthy, J. (n.d.). Progress and its sustainability. Taken 5. March 2014 from John McCarthy’s Home Page: http://www- formal.stanford.edu/pub/jmc/progress/ McCarthy, J. (n.d.). The Wang algorithm for the propositional calculus programmed in LISP, AIM-014. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. McCarthy, J., & Minski, M. (1959). Artificial intelligence. Research Laboratory of Electronics, Quarterly progress report, 052, 129. Cambridge, MA, Massachusetts, USA: MIT. McCarthy, J., & Minski, M. (1959). Artificial intelligence. Research Laboratory of Electronics, Quarterly progress report, 053, 122-

Cambridge, MA, Massachusetts, USA: MIT.

McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P., & Levin, M. I. (1962). Lisp 1.5 Programmer’s manual. Cambridge, Massachusetts, USA: The M.I.T. Press. McCarthy, J., Brayton, R., Edwards, D., Fox, P., Hodes, L., Luckham, D., et al. (1960). Lisp I programmer’s manual. Cambridge, Massachusetts, USA: manuscript. McCarthy, J., Brayton, R., Edwards, D., Fox, P., Hodes, L., Luckham, D., et al. (1960). Lisp preliminary programmer’s manual − draft. Cambridge, Massachusetts, USA: manuscript. McCarthy, J., Minsky, M., Rochester, N., & Shannon, C. E. (31. August 1955). A proposal for the Dartmouth summer research project on artificial intelligence. McCarthy, J., Rochester, N., Maling, K., & Russell, S. (1959). LISP programmer’s manual. MIT, Artificial Intelligence Project, Cambridge. McCarthy, S. (25th. March 2012). What your dentist doesn’t want you to know. Taken 31st. May 2014 from Celebration of John McCarthy: http://cs.stanford.edu/jmc McJones, P. (n.d.). History of LISP. Taken 6th. June 2014 from Software Preservation Group: http://www. softwarepreservation.org/projects/LISP/ Meyer, B. (7th. November 2011). John McCarthy. Taken 5th. Juni 2014 from Bertrand Meyer’s technology+ blog: http://bertrandmeyer.com/2011/11/07/john-mccarthy/ Michie, D. (1968). Memo functions and machine learing. Nature, 218, 19-22. Minski, M. (1963). Artificial intelligence. Research Laboratory of Electronics, Quarterly progress report, 068, 159-161. Cambridge, MA, Massachusetts, USA: MIT. Minsky, M. (1983). Introduction to the COMTEX microfiche edition of the early MIT AI memos. AI Magazine, 4(1), 19-22. Moore, C., & Martens, S. (2011). Nature of computation. New York: Oxford University Press. Morris, A. H. (1966). Models for mathematical systems. SYMSAC ‘66 Proceedings of the first ACM symposium on Symbolic and algebraic manipulation (p. 1501-1524). New York: ACM. N., N. (1962). LAP (LISP assembly program), AIM-035. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Newell, A., & Shaw, J. C. (1957). Programming the Logic Theory Machine. IRE-AIEE-ACM ‘57 (Western) Papers presented at the February 26-28, 1957, western joint computer conference: Techniques for reliability (p. 230-240). New York: ACM. Newell, A., & Simon, H. A. (1956). The logic theory machine − a complex information processing system. Santa Monica: Rand Corporation. Nilsson, N. (2012). John McCarthy 1927-2011. Washington: National academy of science. Norberg, A., & Abrahams, P. W. (15-17. Oktober 2006). Paul W. Abrahams interview: October, 15, 16 and 17, 2007; Deerfield, MA. Proceeding ACM Oral History interviews. New York: ACM. Norton, L. M. (1962). Some identities concerning the function subst[x; y; z], AIM-037. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Overheu. (June 1966). An abstract machine for symbolic computation. Journal of the ACM, 13(3), 444-468. Perlis, A. J. (1978). The American side of the development of Algol. ACM SIGPLAN Notices − Special issue: History of programming languages conference. 13, p. 3-14. New York: ACM. Petrick, S. R. (1961). Use of a list processing language in programming simplification procedures. 1st and 2nd Annual Symposium on Switching Circuit Theory and Logical Design, (p. 18-24). Detroit, MI. Phillips, A. V. (1960). Examples of proofs by recursion, AIM-016. RLE and MIT Computation Center, Artificial Intelligence Project. M.I.T. Pitman, K. M. (1980). Special forms in LISP. LFP ‘80 Proceedings of the 1980 ACM conference on LISP and functional programming (p. 179-187). New York: ACM. Raphael, B. (1961). Introduction to calculus of knowledge, AIM-029. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Raphael, B. (1963). Computer representation of semantic information, AIM-049. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Reynolds, J. C. (1972). Definitional interpreters for higher-order programming languages. ACM ‘72 Proceedings of the ACM annual conference. 2, p. 717-740. New York: ACM. Robnett, R. A. (1963). Suggested conventions for LISP time-sharing system, AIM-050. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Rochester, N. (1958). AIM-005. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Rochester, N., Goldberg, S. H., & Edwards, D. J. (1959). Machine manipulation of algebraic expressions. Research Laboratory of Electronics, Quarterly progress report, 055, 132-134. Cambridge, MA, Massachusetts, USA: MIT. Russell, S. (1958). Writing and debuging programs, AIM-006. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Russell, S. (1959). Explanation of BIG “P” as or march 20, AIM-009. Internal memoranda, M.I.T., Artificial Intelligence Project, Cambridge, MA. Russell, S. (25th March 2012). Adventures and pioneering with John. Taken 31. May 2014 from Celebration of John McCarthy: http://cs.stanford.edu/jmc Saunders, R. (1964). LISP − on the programming system. U E. C. Berkeley, & D. G. Bobrow (Ed.), The programming language LISP: its operation and applications (p. 50-72). Cambridge, Massachusetts, USA: The M.I.T. Press. Sebesta, R. W. (2012). Concepts of programming languages (10th ed.). Boston: Pearson Education Inc. Shasha, D., & Lazere, C. (1995). Out of their minds: the lives and discoveries of 15 great computer scientists. New York: Copernicus/ An Imprint of Springer-Verlag. Slagle, J. R. (1959). Formal integration on a digital computer. ACM ‘59 Preprints of papers presented at the 14th national meeting of the Association for Computing Machinery (p. 36-1 − 36-2). New York: ACM. Slagle, J. R. (1961). A heuristic program that solves symbolic integration problems in freshman calculus, Symbolic Automatic Integrator (SAINT). Cambridge, MA, USA: Massachusetts Institute of Technology. Stoyan, H. (December 1979). Lisp history. (P. Greussay, & J. Laubsch, ed.) LISP bulletin(3), 42-53. Stoyan, H. (1980). LISP, Anwendungsgebiete, Grundbegriffe, Geschichte. Berlin: Akademie-Verlag. Stoyan, H. (1984). Early history of LISP (1956-1959). Stoyan, H. (1984). Early LISP History (1956-1959). 1984 ACM Symposium on LISP and functional programming (p. 229-310). ACM. Stoyan, H. (1988). Programmiermethoden der Künstlichen Inteligenz (1st ed.). Berlin Heidelberg, Germany: Springer. Stoyan, H. (1992). List processing. U A. Kent, & J. G. Williams (Ed.), Encyclopedia of computer science and technology (Svez. 25, p. 143-158). New York: Marcel Dekker Inc. Stoyan, H. (2008). Lisp 50 years ago. Proceeding LISP50 Celebrating the 50th Anniversary of Lisp. New York: ACM. Stoyan, H. (n.d.). The influence of the designer on the design − J. McCarthy and LISP. U Artificial intelligence and mathematical theory of computation (p. 409-426). San Diego, CA, 1991: Academic Press Professional, Inc. Talcott, C. (1988). Rum − an intensional theory of function and control abstractions. U M. Boscarol, L. Carlucci Aiello, & G. Levi (Edt.), Foundation of logic and functional programming, workshop, Trento, Italy, December 15-19, 1986 (p. 3-44). Berlin: Springer-Verlag. Turing, A. M. (1936). On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2). Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59(236), 433-460. Turing, A. M. (1986). Lecture to the London Mathematical Society on 20 February 1947. U A. M. Turing, B. E. Carpenter, & R. W. Doran (Edt.), A. M. Turings ACE report of 1946 and other papers. Cambridge, Massachusets, USA: Massachusetts Institute of Technology. Turner, D. (1984). Functional programs as executable specifications. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 312(1522), 363-388. von Neumann, J. (1951). The general and logical theory of automata. U L. A. Jeffress (Edt.), Cerebral mechanisms in behavior; the Hixon Symposium. 5, p. 1-41. Oxford, England: Wiley. Wang, H. (January 1960). Toward mechanical mathematics. IBM Journal of Research and Development, 4(1), 1-22. Weizenbaum, J. (April 1967). Rev. of The LISP 2 programming language and system, by P. W. Abrahams and C. Weissman. IEEE Transactions on Electronic Computers, EC-16(2), p. 236-238. Woodward, P. M., & Jenkins, D. P. (1961). Atoms and lists. The Computer Journal, 4(1), 47-53.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

As Powerful as Possible by Majorincs Kazimir.org

As Powerful as Possible by Majorincs Kazimir.org

Cover

Title

Licence info

As Powerful as possible - Major ideas of Lisp in McCarthy’s period

Contents

1. Introduction

2 Early influences on McCarthy

3. Darthmouth Project

4. FLPL

5. A proposal for a compiler

6. Suggestion for a programing language

7 Imperative Lisp

8. Elements of functional programming

9. Pure Lisp

10. Linear Lisp

11. Binary Lisp

12. Slagle’s language for manipulating symbols

13 Symbolic expressions as the language syntax

14 Fortran-like commands, function program, power and multiparadigmatism of LISP

15 Woodward-Jenkins arithmetics

16 Lisp 1.5

17 Mathematical Theory of Computing

18 Gilmore’s lisp-like language

19 Memoization

20 New function eval

21 First applications of Lisp

Images

BIBLIOGRAPHY

Files

As Powerful as Possible by Majorincs Kazimir.org

Latest commit

History

As Powerful as Possible by Majorincs Kazimir.org

File metadata and controls

Cover

Title

Licence info

As Powerful as possible - Major ideas of Lisp in McCarthy’s period

Contents

1. Introduction

2 Early influences on McCarthy

3. Darthmouth Project

4. FLPL

5. A proposal for a compiler

6. Suggestion for a programing language

7 Imperative Lisp

8. Elements of functional programming

9. Pure Lisp

10. Linear Lisp

11. Binary Lisp

12. Slagle’s language for manipulating symbols

13 Symbolic expressions as the language syntax

14 Fortran-like commands, function program, power and multiparadigmatism of LISP

15 Woodward-Jenkins arithmetics

16 Lisp 1.5

17 Mathematical Theory of Computing

18 Gilmore’s lisp-like language

19 Memoization

20 New function eval

21 First applications of Lisp

Images

BIBLIOGRAPHY