星田さんの記事に対するコメント。
えっ(・_・;) なぬーっ！？lambdaって後ろに続くシンボル？を引数に取るんではないの？
そう。「マトモに」ラムダ式の構成を考えるとその通りだし、機能的にはそうならなきゃいけない筈だ。
しかし、CPSで書く場合、「機能はそう」な筈なんだけど、事実上、情報は次の図の矢印ように「伝搬してる」。
fib (- n 2) と言う情報はあたかもラムダ式のuに伝わり、fib (- n 1) と言う情報はあたかもラムダ式のvに伝わってるように「見える」。
もちろん、通常の関数で考えると、例えば
(f a b)
と言う関数があったとして引数aの情報が引数bに「手渡されてる」なんつー事はない筈だ。
ところがCPSだとあたかもこういう現象が起きてる「ように」見えるんだよな。
「SchemeとActor理論」が伝えたかった事は端的に言うとそこで、また歴史的にSchemeが誕生した「理由」もこの辺なんだわ。
まずちと整理してみよう。
世の中に最初に「オブジェクト指向」と言う考え方を広く知らしめたのは1972年に登場したSmalltalkと言うプログラミング言語だ。
発案者のアラン・ケイって人はコンピュータ内で小さなコンピュータ同士が「メッセージを送り合って」計算を成し遂げるモデルを想像してたらしい。この「小さなコンピュータ」を「オブジェクト」って読んでたわけだね。ここではその実態は問わないけど(まぁ、データと考えて良い・・・その「データ」が何か、と言うのは取り敢えず棚上げにしておこう)。
もちろん、全部が全部、アラン・ケイが発明したわけじゃない。この辺の発想の引き金を引いた人の1人に、MITに所属してたカール・ヒューイットって人がいる。この人が1969年に作ったプログラミング言語がPlannerだ。そしてその言語のバックグラウンドにあったのがActor理論だ。
それまでのプログラミング言語には、関数型言語ではないけども「returnを伴う」関数と言うモデルがあった。Actor理論はかいつまんで言うと、「returnを止めようぜ」と言う事(笑)。全ての計算モデルはActorとして表現出来る。Actor同士がメッセージを送り合うようにモデル化すれば良いだろう、と。そういう提案をしたわけだな。
ところが、実験言語Plannerは使うのが難しかった。特に腹を立ててたのがSICPの著者の1人で、Schemeを作った(うちの1人である)サスマンと言う人。そしてこの人に後輩のガイ・スティールと言う人が加勢する。
「ちょっとよぉ。PlannerもActor理論も分かりづれぇしよ。ヒューイットの論文を基にMacLisp(Emacs Lispの先祖)で簡単なLisp処理系使って何が起きてるんだか調べてみねぇ?」
っつーんで、Actor理論の肝、alpha構文、と言うのを基にしてLisp処理系をMacLisp上に作るわけだ。それでActor理論を徹底検証しようとしたわけだ。
alpha構文ってのは「SchemeとActor理論」で書かれてる通り、メッセージを送る為だけに存在する構文だ。この2人組はオリジナルのLisp処理系のコンパイラをヒューイットの論文を基にして作り、実際使ってみた。そしてコンパイラが一体どういう機械語を吐き出すんだか徹底検証したわけだな。
その結果分かった事は・・・「あれ、フツーにreturnするのと何も変わんなくね?」っつーのを発見するわけだ。
と言う事は、特殊なalpha構文なんつーものは必要ない、って事が分かった。要するにレキシカル・スコープ前提のラムダ式を使えば、ふっつーに「メッセージ送信」が行える事をこの2人は発見したわけだよ。
この2人は、それでLambda: The Ultimate Imparativeと言う論文を発表する。結論は「ラムダ式さえあればいい」と言うモノだ(笑)。そしてActor理論を検証する為だけに作った自作Lispを、Planner(企画者)にあやかってSchemer(企てる者)と名付けようとする。残念ながら当時の字数制限のせいで6文字が上限だったんでSchemeと言う名前になる。
alpha構文は
(alpha (u k) ...)
と記述した際に、uを使って作られた情報は次の引数kに転送される、と言う性質を持っていた。
一方ラムダ式にはそういう約束事はない、と言うのは星田さんが考えてる通りだ。
(lambda (u k) ...)
ところが、引数で調整するのが問題ではない。ラムダ式の場合、例えば一番簡単なケースだと
(lambda (u k) (k u))
と記述すれば「アクターkに情報uを転送する」と言う事が表現出来る。引数が問題じゃなく、本体が問題なわけだ。
今、現代の目で見ると「何を当たり前の事言ってんの」と思うんだけど、それでも1970年代半ばだとある意味「大発見」だったんだよな。
んで、確かに真っ当に考えると例えばfib (- n 1)と言う再帰部分は
(lambda (u)
(fib (- n 1) (lambda (v)
(k (+ u v)))))
と言う無名関数を「受け取ってる」のは事実なんだけど、それじゃあ分かりづらいわけだ。CPSに於いては逆にuがfib (- n 1)と言う情報を「受け取ってる」って「解釈」した方が見通しが良い。「そう考えた方が分かりやすい」と言うのを、「SchemeとActor理論」での論が保証してるわけだな。
実はこの解釈はもう1つの事も保証してる。
- u = fib (- n 2)
- v = fib (- n 1)
が成り立つ、って事は言い換えると、このCPSは
(define (fib n)
(if (< n 2)
n
((lambda (u)
((lambda (v)
(+ u v)) (fib (- n 1)))) (fib (- n 2)))))
と同じ事をやってるんだ、って事が保証されている。
多分上のコードを見たら「え?何やってんの?」って思うだろう。
しかし走らせてみればキチンとフィボナッチ数列になってる、って事が分かると思う。一体何が起きてるのか?
もう一度言おう。
- u = fib (- n 2)
- v = fib (- n 1)
が成り立ってる、ってのが前提。Lisp系言語ではこれは
- (let ((u (fib (- n 2))))
- (let ((v (fib (- n 1))))
と表現出来て、かつ、letはラムダ式の構文糖衣、つまりマクロである、と言うのは再三指摘している。
つまり、実はCPSは
(define (fib n)
(if (< n 2)
n
(let ((u (fib (- n 2)))
(v (fib (- n 1))))
(+ u v))))
と書くのと全く同じ事をしてる、って意味になるんだ。
言われてみれば当たり前でしょ?これならuは明示的に(fib (- n 2))を束縛されてるし、vも明示的に(fib (- n 1))が束縛されている。
つまり全く同じモノを「いくつか違う表現で」記述出来るんだ、って事を表しているんだ。
これがルールなんだって事なら覚えるだけだから楽でいいけど。
機械的に変換する部分で悩むのは無駄
そう、極論そうなんだ。「SchemeとActor理論」ってのはテクニカルな結論は上の通りで「機械的に変換して構わない」と言う事を保証する為の話なのね。言わば数学で言うトコでの「証明」だ。
一端証明されたモノは疑問を挟まず機械的に適用していって構いません。理論的に怪しくなってくれば、もう一回、いや、何度でも「SchemeとActor理論」に立ち返って読み直せば良いです。それだけの話、になる。
