> We suspect that McCarthy simply had forgotten the functional arguments – a mistake of lasting importance.

> Herbert Stoyan. Early LISP history [^Stoy84]

The problem was first discovered in 1959 by James Slagle—the same one who took notes on "Fortran with lambdas." Slagle worked with the first Lisp implementation. In his history of Lisp [^McCa78], McCarthy even gives pseudocode corresponding to Slagle’s code, while debugging which Lisp programmers first realized that something was not working as expected:

```haskell

testr[x, p, f, u] <- if p[x] then f[x] else if atom[x] then u[] else

testr[cdr[x], p, f, λ:testr[car[x], p, f, u]].

```

Yes, as was customary in the first couple of decades of Lisp’s existence, code examples were usually pseudocode. After all, you wouldn’t publish all those parentheses in a paper.

Slagle thought he had written something like this:

```haskell

data Lisp = Atom String | Cons Lisp Lisp deriving (Show, Eq)

testr x p f u | p x = f x

testr (Atom _) p f u = u ()

testr (Cons h t) p f u = testr t p f $ \() -> testr h p f u

```

but in reality he had written something more like this:

```haskell

testr x p f u | p x = f x

testr h@(Atom _) p f u = u h p f u -- <==

testr (Cons h t) p f u = testr t p f testr -- <==

```

But why? Slagle tried to find out from the programmers, but they did not know why. So Slagle and the programmers turned to McCarthy. But that did not help either—at least not immediately. Let us give the floor to McCarthy himself [^Stoy79]:

“…naturally he complained. 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.”

What can one say? This is rather unexpected.

In his talks and articles on the history of Lisp in the 1970s, McCarthy said that he had not fully read Church’s work on the lambda calculus, and that what he had read he had not fully understood. Lisp historian Herbert Stoyan initially thought this was a joke [^Stoy79], but later reconstructed McCarthy’s path to mastering lambda [^Stoy84].

Remember the strange higher-order functions from the first report? When that report came out in the fall of 1958, McCarthy had only a vague idea of what lambda was. After unsuccessful attempts to write such a `maplist` in assembly, McCarthy decided to read about lambdas and entered the state he himself described as “not fully read, not fully understood.” But that was already enough for the appearance of HOFs in later reports to stop looking suspicious.

Stoyan finds it strange that McCarthy had only a vague understanding of lambda, yet months earlier spoke of dreaming of FORTRAN with lambdas and recommended adding them to the international algorithmic language. Stoyan suggests something might be wrong with the dates. But if the code from the first report was written earlier, it is still strange that no one noticed the suspicious HOFs.

Stoyan discussed this with McCarthy, and McCarthy himself was surprised, certain that only an unsuccessful attempt to implement such a `maplist` led him to using lambda. Why, then, did he recommend adding lambda to other languages long before that moment?

We are not inclined to treat this as a mystery and see no reason why one should not recommend that other programming language designers pay attention to lambdas, even if one only knows of their existence and does not yet properly understand them before attempting implementation.

So, the obviously incorrect lambda first became non-obviously incorrect. What was wrong with this one?

A not-so-obviously wrong lambda is a metaprogramming tool. It creates a description of function code that the interpreter can execute using the environment at the call site. The function code description has a free variable named `x`; the interpreter goes through a list of pairs and looks for the first key `"x"`. And which pair will be found first when executing Slagle's code? The one added during the function call, corresponding to one of its parameters. This is so-called "dynamic scope."

Functional programming, however, requires lexical scope. Lambda must construct a closure over the environment at the point where the lambda expression is evaluated. The Haskell code above works because closures form a stack for traversing the tree. But the Lisp interpreter did not construct closures. Closures as an implementation technique for functional languages had not yet been invented. The interpreter was looking in the wrong list of pairs—and it did not even have the right one.

Today one might assume that a metaprogramming “lambda” makes sense in Lisp, known for its use of metaprogramming. But “lambda” as a code fragment and an object of metaprogramming, rather than as a function, was not the result of careful design. Stoyan came to this conclusion by studying the process of its emergence. McCarthy wrote an interpreter for S-expressions of proto-Lisp in M-pseudocode. Russell or another programmer tried to rewrite it in assembly, discovering errors. The process repeated. Stoyan believes that during these iterations, at some point McCarthy simply forgot about functional arguments. And one of the programmers—most likely Russell—invented the metaprogramming “lambda” when he could not find a corresponding implementation in the pseudocode specification written by McCarthy. It seems that not all components of the language for programming artificial intelligence were equally important. Conditional expressions occupied McCarthy more than first-class functions.

It turned out that Russell most likely created the problem with the non-obviously incorrect lambda. But he also fixed it in the same year, 1959—with some help from Patrick Fischer. Russell added closures to Lisp: a pair of code and the very list in which linear search by variable name finds the correct variable from the environment at the point where the closure is constructed. At the point of lambda application, this list is added to the front of the environment list at the application site. After that, the interpreter interprets the lambda code as Slagle—or anyone else familiar with lambda calculus—would expect.

Technically, the error was not fixed. The error was classified as a feature, and the fix as another feature that one could choose not to use. The default scoping did not change, and closure construction was made explicit.

It is not entirely clear why the default behavior was not changed. It was not as if enough Lisp code had been written by then to worry about backward compatibility. Perhaps performance was the issue. Perhaps the fix was not considered important. Russell could not explain either the solution or the problem even to McCarthy, according to McCarthy himself.

Fortunately, for someone translating a functional language into Lisp, this does not matter: one can explicitly specify that a closure should be constructed for a lambda. And so—is the problem solved? Alas, no.

Unfortunately, this explicit construction of closures is only one manifestation of the indifference of Lisp programmers of that time to functional programming. Another, more important issue for compiling functional languages by translation into Lisp, was that advances in Lisp compilation and performance optimization were usually not applied to these closures.

Remember the caveat that the compiler compiles different Lisp code with varying degrees of success? Lambdas are precisely such code. In the case of selected functions like `map` and a known lambda, an advanced compiler can inline both, solving both the scoping and performance problems. But in the case of an unknown function, as in Slagle’s example, compilation will not occur at all. The lambda code will be interpreted, and the interpreter will traverse a singly linked list of pairs in search of a string with the desired name. This is not merely an explanation of semantics—it is, for the time being, the actual implementation.

Instead of working on an implementation that would execute Slagle’s code better, Lisp programmers abandoned functions that handled errors by calling a passed-in handler, in favor of functions that reported errors by returning the empty list.

All right—perhaps Lisp programmers did not yet want to create a practical implementation of first-class functions themselves. Still, Lisp implementations could be useful to a functional language implementer. Functional language implementers can implement functions by themselves, provided there is garbage collection. And Lisp was the first language with garbage collection.