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
2012/01/19
ピアノレッスン32回目
ベルガマスク組曲、通しで。細かいミスが取れないのだけれど、「曲毎に音の質の弾き分けが出来ていて良かった」とのこと。
もうちょいpolishして録音したいなあ。
次回からバッハを始める。英語では「ばーっく」だ。
Tag: Piano
2012/01/18
SICPは死なず
Hacker News経由で。SICPを使うコース6.001が帰って来た?
どうもMITにはIndependent Activities Periodという期間があって(1月の4週間)、学生や教官が独自のクラスやイベントを企画できるっぽい。単位が出るコースを設けることもできる。その枠でもって、4週間でSICPをやっちまおうというコースらしい。東大でやってた自主ゼミみたいなものだと思うが、MITの方は数も多いしバリエーションもたくさんあるなあ。短い決まった期間に全学でぐわっとやるのがエネルギーを集中できて良いのかもしれん。
東大が秋入学にするとかなんとかニュースになってたけど、希望者がブランクの期間にこういう短いゼミをいくつか取れたりしたら面白そうだなあ。
2012/01/17
That's a good question
らむ太の質問が徐々に進化しているので、その傾向を励ますべく、 これはと思う質問には「それはいい質問だね」と言うようにしている。
らむ太は確かに学習したようだ。最近では質問をする時にこう言うようになった。
「ねえねえとうさん、いい質問があるよ」
そう来るか。
Tag: 生活
2012/01/17
失敗に学ぶこと
色々なプログラミング言語を学んでおくことは、単に多くのパラダイムに 触れられて視野が広がるから、というだけでなく、 他の言語の失敗に学ぶという効果があるかもしれない。
ループ変数を破壊的に変更するのは、レキシカルクロージャと相性が悪い。 伝統的なLispのdoはこの点で失敗していて、Schemeのdoはそれを直した。 (Common Lispのdoは伝統的なdoの失敗を引きずっているが、それは仕方ない。 Common Lispの全てはkludgeだから)。
C#も同じ間違いをしてて、C# 5で直すそうだ。 互換性を破っても直す、というのはえらいと思うが、 クロージャを導入した時に誰かが気づいてたらもっと良かったのに、と思わないでもない。 (尤も、選択はその時点で見えていたいろいろな要素に重み付けをした結果で、 もしかするとその時クロージャとの相互作用について気づいてはいたけれど for文との一貫性の方を重く見た、ってだけかもしれないから、 後知恵でとやかく言えることではないけど。)
とはいえ、自分がよく知っているもの以外の言語について「失敗」を探すのは難しいよなあ。 それがおかしな機能に思えても、 実は自分が知らないだけでそれが有用な場面があったり、 その言語特有の別の機能と合わさるとものすごく強力だ、とか見えない理由があるかもしれない。 正しく判断するには、その言語の歴史も知らないとならないし。
むしろ、みんなが自分のよく知っている言語についての失敗点を挙げておけば 今後の言語開発者の参考になったりしないだろうか。
Tag: Programming
Comments (6)