R.I.P. John McCarthy


J. McCarthyといえば「GCの父」ですよね。
私が調べた限り、最初にGCという単語が出たのは以下の論文(略: RFSE)。

We already called this process “garbage collection”, but I guess I chickened out of using it in the paper - or else the Research Laboratory of Electronics grammar ladies wouldn’t let me.

Recursive functions of symbolic expressions and their computation by machine, Part I


我々はこの機能をGarbage Collectionと呼んでいる。



A further important concept which is mentioned in the paper is the garbage collection idea under the heading `Free-Storage List'.
In this section McCarthy describes the way how free registers are managed.
The difference to the IPL-solution is condensed in the sentence: `No provision need be made for the user to program the return of registers to the free-storage list.
The return takes place automatically ...'. If we look at the short and elegant functions for copying or applying a function to every element of a list then we become aware that an explicit erasing of list structures would have obscured the notation.
McCarthy had provided functions for list erasure but never really used them.
This worked for a while but when the interpreter was implemented the situation must have happened that all registers were exhausted.
To overcome this bottleneck, the idea of garbage collection emerged.
As far as Abrahams and Maling remember, R. Silver first came out with this proposal.
However, McCarthy - after a discussion with R. Silver, convinced us that he conceived this.

In (19) McCarthy describes the idea as follows:
"Nothing happens until the program runs out of free storage.
When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts ...".
Then he gives a description of the now well known steps of garbage collection.
He concludes:
"This process, because is is entirely automatic, is more convenient for the programmer than a system in which he has to keep track of lists and has to erase unwanted lists.
Its efficiency depends upon not coming close to exhausting the available memory with accessible lists.
This is because the reclaming process requires several seconds to execute, and therefore must result in the addition of at least several thousand registers to the free-storage list if the program is not to spend most of its time in reclamation."

This was pure theory then because the first garbage collector was implemented by Dan Edwards during June/July of 1959.
At the end of April Dan Edwards was one of the first users of the LISP-system.

LISP History


論文(訳注1)内で述べられているさらに重要なコンセプトは見出し「Free-Storage List」の下にある Garbage Collection というアイデア。
このセクションで、McCarthyは free registers の管理方法を示している。
IPL-solution との違いはこの文に要約される:
  “供給はレジスタのfree-storage listに対する返却をユーザがプログラミングすることは必要としない。
このボトルネックを克服するために、Garbage Collectionのアイデアがでてきた。
Abrahams と Maling は、*R.Silverがこの提案をはじめに言った*と記憶している。
また一方、McCarthy(R. Silverとの対話後)は彼が提案したことを、我々に確信させた。

    これは再利用プロセスが実行に数秒を必要とするからであり、ひいては、プログラムの大部分が再利用に使われないのならば、少なくとも数千のレジスタのfree-storage listへの追加を終えなければならないからだ。」

はじめのGCは1959年6〜7月に*Dan Edwardsによって実装された*ため、これはまだ、全くの理論でしかなかった。
その4月の終わり、Dan EdwardsはLISPシステムの最初のユーザであった。

訳注1: 1959年4月にMcCarthyによって書かれた公開する前のRFSEの短い版らしい。

R.SilverとDan Edwardsも父だよね。さて、彼らはご存命なのでしょうかね…。