> Once we decided on garbage collection, its actual implementation could be postponed, because only toy examples were being done.

> McCarthy J. History of LISP [^McCa78]

Early Lisp programmers did not want to manage memory manually as in IPL, and chose between reference counting and garbage collection. They chose garbage collection because they wanted a `cons` cell to fit into a single word. On the IBM 704, this was 36 bits. An address was 15 bits. Two groups of three bits were too small for a reference count [^McCa78].

This was a rather fortunate coincidence for functional programming, which often creates cyclic references. But this fortunate coincidence was probably not critical for the emergence of functional languages. For example, the authors of SIMULA eventually abandoned reference counting in favor of garbage collection because they conducted experiments and compared the performance of reference counting combined with garbage collection for collecting heap cycles with that of a compacting garbage collector. At least, they recall this [^Dahl78]. But perhaps it was still beneficial that Lisp programmers began working on garbage collection earlier.

Having chosen garbage collection over reference counting, Lisp programmers postponed its implementation because they were writing only toy programs for the time being. But they did not postpone it for long. Dan Edwards wrote a garbage collector in June–July 1959 [^Stoy84].

The first public demonstration of Lisp, in 1960 or 1961, also became the first public demonstration of garbage collection—although this was not planned. It didn't trigger during the rehearsal, but the rehearsal took up enough memory that the garbage collector started working during the demonstration and ran for the rest of the time allotted to it, printing statistics [^McCa78]. It is hard to say why Lisp programmers did not want to show off what was, in Turner's opinion [^Turn12], their greatest achievement. But fortunately, everything ended well and they did show it.

In the printed statistics, the collector is already proudly called a garbage collector, but in the first Lisp paper [^McCa60] they are still shy about calling it that. McCarthy is too serious there, but this is compensated by other Lisp programmers in other papers.

McCarthy writes that the "reclamation" process takes "a few seconds." This is true when memory is 8192 words. But by the time of the collector demonstration, it was already 32768 words, and the process took at least four times "a few" seconds. Not great.

The main problem [^Wilk92] with McCarthy's collector: even if almost no live objects remain at the time of collection, the entire heap must still be traversed; the collector's run time depends on the size of the heap.

Proponents of reference counting criticized McCarthy’s method almost from the very beginning [^Coll60] for the fact that the collector’s running time does not depend on how much memory is freed. But the fact that the running time does not depend on how much memory is freed is actually a good thing. What is bad is that the running time depends not only on the number of live objects.

It turns out that memory growth brings not only new opportunities but also new challenges. More time passes before the next collection—time that can accommodate not just a demonstration (but not along with its rehearsal), but some more interesting work. But the break in work also becomes increasingly painful.

Of course, such a view of the problem is entirely unsuitable for functional programming. Functional code allocates enough to quickly fill memory. Functional programming can benefit from memory growth only if collection time does not grow as fast as memory size.

McCarthy's collector has another problem that is very important for functional languages. Since the work of a functional program boils down to allocation to such a significant extent, allocation must be fast. And searching for memory in a free-list is not the fastest way to allocate.

And Lisp programmers thought less about how to make garbage collection more efficient, and more about how to reduce heap allocations, reducing the load on the collector.

Abandoning garbage collection and keeping Lisp as it was was practically impossible. But if one allocates less on the heap, reuses data structures by modifying them in place, one can preserve this illusion of a solution—pushing collection into the future, where perhaps the computation will already be finished and no collection will be needed at all.

Thus, for functional programming and for use as a basis for implementing functional languages, Lisp compilers were not yet suitable.

In the summer of 1962 McCarthy left MIT and went to work at Stanford [^Stoy79]. And however indifferent he may have been to functional programming, the Lisp programmers remaining at MIT seem to have been even more indifferent. This marked the end of the first unsuccessful attempt to implement a functional language.