R.I.P. John McCarthy

GC本書いたときに「おぉ、まだご存命でらっしゃる」と認識したのだけど、ついにこの時が。

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と呼んでいる。
しかし、この論文にその名前は使わないことにした。
もし使おうとすれば、言葉遣いにうるさい研究所の女性達が私を止めただろう。

さて、コンピュータ業界においてXXの父、というのは無妻多夫制度(なにこれ)っぽくて、父というのは複数人いるものです(例えばAI)。
GCについても、これは例外ではない。

実は、これまたGC本を書いているとき、竹内先生にその辺りのいきさつを教えていただいたのだった。
以下はその話のソースとなった(と思われる)論文。

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に対する返却をユーザがプログラミングすることは必要としない。
  返却は自動で行われる...”
われわれが短くて簡潔な複製、もしくはリストのすべての要素に対する関数適用、を見た時に、リスト構造の明示的な消去は記述から隠されていることに気づかされる。
McCarthyはリストの消去を行う関数を提供していましたが、それらは使うことはなかった。
これはしばらく動いていたが、インタプリタが実装されたとき、すべてのレジスタが枯渇した状態が起こったに違いない。
このボトルネックを克服するために、Garbage Collectionのアイデアがでてきた。
Abrahams と Maling は、*R.Silverがこの提案をはじめに言った*と記憶している。
また一方、McCarthy(R. Silverとの対話後)は彼が提案したことを、我々に確信させた。

(19)で以下のようなアイデアをMcCarthyは述べた:
  「このプロセスは、完全に自動なので、プログラマがシステムの中でリストの跡を保持するのを知るのと、もう見ないリストを消すことを知るよりも、便利である。
    その効率は、アクセス可能なリストで利用可能なメモリが消耗することに親密に依存している。
    これは再利用プロセスが実行に数秒を必要とするからであり、ひいては、プログラムの大部分が再利用に使われないのならば、少なくとも数千のレジスタのfree-storage listへの追加を終えなければならないからだ。」

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

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

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