> Without any doubt it is hard to imagine that this program could ever run correctly. However, McCarthy himself had this feeling, too.

> Herbert Stoyan. Early LISP history [^Stoy84]

In the summer of 1958 McCarthy met a student from the University of Michigan who was looking for a programming job—Klim Maling. McCarthy hired Russell and Maling for his new joint project with Minsky in September 1958. As part of this project, the first LISP was designed and implemented.

What did McCarthy end up with after combining all the components of his language for programming artificial intelligence? In the very first report [^McCa58] of the MIT AI Laboratory, we see code with lists, conditional expressions, recursion, FORTRAN with its `goto` and mutability, as well as something resembling higher-order functions—but looking rather strange. The function `maplist` is applied like this:

```

maplist(cdr(J),K,diff(K))

```

and like this:

```

maplist (cdr(J),L,(L = K → diff(K), L ≠ K → copy (L)))

```

which means roughly:

```haskell

maplist (tail j) (\l -> if l == k then diff l else copy l)

```

but the “lambda” is somehow passed to `maplist` via two parameters: the bound variable separately and the body of the lambda separately. How does that even work? You need to know which variables are bound and which are free at the point of function construction.

But such oddities did not last long. In later reports, `map` looks like this:

```

maplist(L,f)=(L=0→0,1→consls(f(L),maplist(cdr(L),f)))

```

and is applied as:

```

maplist (cdr(J),λ(L,(L = K → diff(L), L ≠ K → copy (L))))

```

which is perfectly normal.

In McCarthy’s article “Recursive functions of symbolic expressions and their computation by machine” [^McCa60], Lisp looks like this:

```haskell

maplist[x; f] = [null[x] → NIL;

T → cons[f[x]; maplist[cdr[x]; f]]]

maplist[(1,2,3); λ[[x]; x + y]]

```

This `maplist` differs from the more familiar `map` function in the standard libraries of today’s functional languages in that the function passed to it is applied not to the elements of the list but to its tails. But this is not a fundamental difference.

Naturally, this article made an indelible impression on future authors and implementers of functional languages.

Does this Lisp look unlike modern Lisp? It does not resemble the Lisp that actually existed at the time either. This is pseudocode for articles about Lisp—more or less resembling M-expressions, which looked like this [^LISP61]:

```

MAPCON(L,F)=

(L=0 YIELDS 0,

1 YIELDS NCONC(F(L),MAPCON(CDR(L),F)))

```

M-expressions were intended to be implemented, but nobody knew how. No one in McCarthy’s group knew how to write a compiler. The example of FORTRAN was not particularly inspiring—it took 30 man-years to write its compiler, which was quite a lot for that time, and especially for McCarthy’s group. Clearly, creating your own language has disadvantages compared to adding features to existing ones.

So M-expressions remained only pseudocode—not in articles, but in comments to real code written in assembler and Lisp. And the real Lisp code—S-expressions—looked [^McCa62] much the same as they do today:

```lisp

(MAPLIST (LAMBDA (X FN) (COND

((NULL X) NIL)

(T (CONS (FN X) (MAPLIST (CDR X) FN))))))

```

But for those who wanted to use Lisp implementations to create implementations of functional languages in the narrower sense, this was not a problem. Translating code into S-expressions is even easier. The main thing was that such implementations existed—and they did.

In 1958, to gain experience with translation, programmers Russell and Maling began rewriting simple programs from proto-Lisp into IBM assembler. By early April of the following year, they had rewritten 20 functions. McCarthy wrote programs in the M-expression language, and the two programmers wrote the corresponding assembler code.

The naive Lisp interpreter was initially a specification in M-expressions, and Russell, on his own initiative, made this specification executable. Naturally, the first specification executed incorrectly, but after several iterations of writing new specifications and manually translating them, the interpreter began to work.

For writing real programs, a naive interpreter is not enough, but more serious implementations were not long in coming.

No later than April 1959, Klim Maling began writing a Lisp compiler in Lisp, but the project was abandoned. Lisp programmers considered that a compiler written in assembly was obviously more practical.

Robert Brayton and David Park, who assisted him, wrote the LISP 1 compiler in assembly. This compiler became operational in January 1960. The code it generated ran 50 times faster than the interpreter [^Stoy79].

But in 1960 Brayton left MIT, and without him the Lisp programmers could no longer understand or develop the compiler [^Blai70]. McCarthy briefly described this experience as “unsuccessful” [^McCa78].

So the Lisp programmers decided to try writing a Lisp compiler in Lisp after all. This experiment ended in success, which became clear no later than August 1962. Timothy P. Hart and Michael Levin, better known for their other work, wrote the LISP 1.5 compiler, which is considered the first compiler to compile itself [^Hart62] [^McCa62]. The Lisp programmers were able to develop this Lisp-in-Lisp compiler.

The Hart and Levin compiler produced code that ran 40 times faster than the interpreter [^Hart62], or from 10 to 100 times faster depending on the program [^McCa62]. Depending on which properties of the program? A good question.

Bootstrapping took only 5 minutes, despite the fact that most of the time most of the compiler was still being interpreted.

McCarthy writes that the speed of compiled Lisp code is 10–100 times slower than FORTRAN code on numerical tasks. But there is no comparison with list processing written in a more traditional programming language, such as FORTRAN with appropriate extensions. Such a comparison would have been more interesting.

However, a compiler is a real application, so it can be concluded that Lisp programming existed in 1962.

And if already in 1962—or even in 1960, if you were brave enough—it was possible to compile a language with first-class functions, then functional programming in the broad sense existed from the early 1960s. And for functional programming in the narrow sense, on the languages of the Edinburgh research program, it remained only to invent and implement pattern matching and parametric polymorphism. After all, Lisp is a functional language with first-class functions, right?

That’s what David Turner, an important hero of our story, thought when he began studying Lisp in 1972. But he quickly noticed that the code was not doing what he would expect from a language that has lambda [^Turn12]. Turner read the documentation [^McCa62] and realized that LAMBDA does not construct a function.