2012/01/22

継続の起源

時々「継続ってSchemeが最初に作った概念なの?」みたいな疑問を見かけるのだけれど、 「Schemeは継続をプログラマが触れる言語機能として表舞台に登場させた最初の言語」というだけで、 継続の概念自体はSchemeよりかなり前からあったものだ。 1975年のSchemeの最初の論文 (pdf) には、「catch(call/ccの前身)は識別子をその式の継続に束縛する」とさらりと書いてあって、継続という用語については説明も参考文献も示してないので、1975年の時点で既に継続という概念はCS界隈では常識であったと思われる。

でも実際に、どういう経緯で継続という概念が産まれて来たのか知らなかったので調べてみたら、John Reynolds, "The discoveries of continuations", Lisp and symbolic computations, 6, 233-247, 1993 (pdf) という論文に詳しく書いてあった。以下はそれを踏まえた与太話。

タイトルが "Discoveries" となっているように、継続というのは誰かがある日「新しい概念を発明した」というようなものじゃなくて、むしろ最初からそこにあったものが「発見」された (それも複数回) というのがふさわしい。誰もが自分で気づかぬうちに、いろんな形で既に継続を実装していて、後からそれらを統合する意味が見出された、って感じ。

話は1960年前後に遡る。まだFORTRANが幼稚園児で、LISPのオムツがとれてなかった頃だけれど、 研究者達は、実装に規定されないプログラミング言語の姿を求めてAlgol60を設計していた。つまり、「こう実装すればこういう機能が出来るからこの機能を入れる」っじゃなくて、「詳しい実装のことはおいといて、言語にあるべき仕様ってどんなかね」って流れでまず仕様が考えられて、それを実装するにはどうするかって研究がたくさん出てきたわけだ。(LISPはFORTRANほど計算機のハードウェアには密着していなかったけれど、特定のEVALの実装から出発しているという点で、やっぱり実装に縛られていたと言えよう。実際、funarg問題などは初期のeval実装の欠陥というか見過ごしが表面化したものとも考えられる)。

「継続」という用語自体は、継続を陽に扱ってどうこうしようという話より前に出てきたものらしい。Algolは再帰呼び出しありなので、プログラムは手続きを呼び出す時に「その時点での環境と、戻りアドレス」を何らかの形でパッケージにしてどっかにとっとかないとならない。C言語みたいな単純なモデルではそれは要するに呼び出し時点でのスタックの状態なんだけど、再帰呼び出しに連続したスタックを使うのは当たり前でしょ、という時代ではなかった。そもそもハードウェアスタックなんて無かったし。Lispの当初の実装では、連続したスタックのためだけにメモリを割り当てるなんて贅沢だし遅かったので、呼び出し履歴はリンクトリストとしてヒープに確保されてたって話だ。Dijkstraも再帰呼び出しの実装戦略として、「プログラムの実行を継続するために必要な全て」を保持するデータ構造を「リンク」と呼んでいる。さらに、「リンク」も手続きに渡されるパラメータであると考えられる、とまで言ってて、これは現在からみればまさに継続渡しのことを言ってるんだけど、まだそれと意識していなかった様子。

同じ頃、Landinが適用順評価のラムダ演算のための仮想マシンとしてSECDマシンを考えてて、SECDマシンの最後のD (dump) はこれも後から考えれば継続そのものだった。LandinはAlgol60のgotoをSECDマシンへとコンパイルするためにJオペレータというのを導入して、それはdumpレジスタの状態をパッケージ化するものだったんだけれど、意味的にそれはSchemeのcall/ccと同じものだ。

で、どうやらAlgol60のgotoをどうコンパイルするか、ってのがこの頃のホットな話題のひとつだったらしい。gotoは機械語レベルでは単にプログラムのアドレスへのジャンプなんだけど、環境がネストしたりしてると、ジャンプと同時に環境をジャンプ先に合わせたりしなくちゃならない。となるとジャンプ先の「ラベル」は単なるアドレスではなく、環境を含んだ何かで、それは手続き呼び出しの「リンク」と同じようなものになる。

そんな中で、1964年にWijngaardenがAlgol60のgoto文をコンパイルする戦略として「継続渡しに変換しちゃえばgotoは消えて全部関数呼び出しになるじゃん」ってなことを発表する。ちなみにReynoldsによる上の論文によれば、DijkstraはWijngaardenのこの講演にインスパイアされてあの"Goto considered harmful"を書いたらしい。

そんで1970年前後までには、 継続渡し形式で考えれば末尾呼び出しと継続呼び出しって同じじゃん、とか、 継続使えば評価順序を陽に記述できるんじゃん、とか、そういう話は普通にあったようで、 Reynolds自身も"Definitional interpreters for higher-order programming languages", Proc. ACM Annual Conf. (1972) 717--740.で 継続を使ったインタプリタの抽象実装を示している。escapeという、 評価機の中の継続を陽に取り出すオペレータも示されてて、それを素直に実装したのが Schemeのcall/cc、って感じだ。

Scheme自体は、SteeleとSussmanが Actorモデルの実装中に「アクターにメッセージを送ることと 関数の末尾呼び出しは実装上全く同じものである」という発見をしたことから産まれた。 その発想も、こういう時代の文脈の中で出てきたもの、と言えそうだ。

継続自体は、言語実装を触ってればそう特別な話でもないのだけれど、 最初に目にした時のあの「わけのわからなさ」は何なんだろうね。 C言語やUnixがぐわーっと広まって、ハードウェアスタックがどんどん安くなり、 プログラミングの入門者はまずスタックのプッシュとポップで手続き呼び出しを理解するから、 なのかなあ。

自分もSchemeを知って継続の話を読んだ時に「うわなんだこれさっぱり分からん」と 思ったのを覚えてる。確か「情報処理」あたりで簡単なSchemeの記事があって、 Lispで簡単なSchemeインタプリタの実装が紹介されてたんじゃなかったかな。 当時Lispは知ってたんで「lambda式はクロージャに評価される」ってのはまあ 何とかわかったんだけど、「call/ccの実装はこうです」って出されて、 すげー簡単に書いてあるんだけど何やってるんだか全然わからなかった。 でも今説明しろと言われたらやっぱり実装を示して「これが継続です」って言っちゃいそうだ。 だってそれが継続なんだもん。それ以外にどう説明したらいい?

関連するかもしれない記事: なんでも継続 (まだ下書き)

Tags: Programming, Algol, Scheme, Lisp