依然として「継続」と格闘中だ。そして連敗中だ(笑)。
あんまり頭に来てるんで、ちと基本に戻ろうと思う。
ところで、以前、「Schemeは元々の開発目的としてマクロは重要視されてなかった」と書いた。実はSchemeの本懐はむしろ「継続」と言うアイディアだ。
ANSI Common Lispの場合、「マクロを制する者がANSI Common Lispを制す」わけだが、一方、Schemeの場合、「継続を制する者がSchemeを制す」だ。
従って、僕は結果のところ、Schemerではない。継続がよく分かってないから、だ。
と同時にその辺に付いてはあんま心配もしてないんだ。「継続がよく分かってない」人はたくさんいる。だから安心してるわけ(笑)。
ところで、Schemeは継続絡みでデザインされた言語だが、初版にはcall/ccと言う関数は無かった。call/ccと言う関数の登場は初版(実装は1975年頃登場)から約10年後の1985年頃に発表されたScheme第2版から、だ。なお、前年の1984年に草の根仕様のCommon Lisp第1版がリリースされている。
表面的には、call/ccは単に脱出の為の関数に過ぎない。しかし、Schemeの初版(仕様・1978年)には古典的Lispのcatchとthrowが備わっていて、call/ccは無かったわけだ(※1)。しかし、R2RSでcatchとthrowは姿を消し、「表面的にはそれらと同等の機能を有する」call/ccが取り入れられたわけだ。
この辺の話も後述するが、いずれにせよ、call/ccは元々脱出の為の機能だ。付随する事は色々あるが(それも後で見るが)、そこをまず押さえておこう。
しかし、call/ccの「奇妙な挙動」はSchemeを使ってる人全員が把握してるわけでもないんだ。例えば1999年、次のようなコードが「今まで想像もしなかった」ような挙動を示す事が「発見」された。
(let ((yin
(let ((cc
(call/cc
(lambda (c)
c))))
(display #\@)
cc))
(yang
(let ((cc
(call/cc
(lambda (c)
c))))
(display #\*)
cc)))
(yin yang))
このプログラムは何故か無限ループするが、@と言う文字は一種区切り文字を表し、一周期毎に*と言う文字が一つづつ増えていく。
結果、ある意味、このプログラムは抽象的な「無限長の整数列」を表すわけだ。
繰り返すが、これが発見されたのが1999年。Schemeにcall/ccが導入されたのが1985年。つまり、15年にも渡って「call/ccがこんな挙動を示す」と言う事を誰も知らなかったんだ。
また、この「挙動」を説明出来る人も殆どいないだろう。これは今はyin-yang-puzzleとして知られている(※2)。「題意を実装しろ」ではなく「このcall/ccの挙動を説明せよ」と言うクイズだ。これも後で見てみよう。
call/ccにはまだまだ謎が多い。上の例だけじゃなくってまだ「知られてない」挙動を示すプログラムが書ける可能性が常にあるわけだ。
結果、「call/ccがよく分からない」っつっても気にする必要がない、と個人的には思っている。一つの「不思議な挙動を起こすプログラム」が発見されるまでハッカー達でさえ15年もかかってる。僕如きが他のプログラムを「思いつく」事が出来なくてもそりゃ当然だろう、とか思ってるわけだ。
そしてそれくらいcall/ccは「難しい」(※3)。
ところで、日本語では通常、call/cc(call-with-current-continuation)は「継続」と呼ばれるが、原語から見ると実際は「現在の継続付き(関数)呼び出し」と言った方が正しい。
ここで「継続」とは一体何だろうか。単純に言うと「今から行われる計算」の事を指す。つまり、単なる「続き」だ。"to be continued"が「(今の話から)続く」の意図なら、continuation(続き)の意味自体は分かると思う。
言い換えると、call/cc「自体」は継続そのものではなく、あくまで継続を利用した「関数呼び出し」だと言う事だ。
ところで、「継続を丁寧に説明しよう」とする国内外のサイトに於いて、call/ccの話を書くより先に「継続受け渡し方式」(CPS)で継続と言う「概念」を説明しようとする事が多い(※4)。
確かに「継続と言う概念」を説明するにはCPSは外せないだろう。しかし、困った事に、CPSを理解するのとcall/ccを使いこなす、ってのは表層的には全く関係がない、と言わざるを得ないんだ。そもそもCPSとcall/ccと言う「実装」が全く結びつかないだろう。
結びつく?僕は全く結びつかなったんだよな。「何の関係があるのこれ」ってのがそれらの解説を読んだ時の感想だった。
継続がオブジェクト指向に関係する、と言う話も聞いたし、SICPで取り扱われていないcall/ccを知りたい(※5)、ってぇんでSchemeを学び始めた当初、「SchemeとActor理論」と言う文書を見つけて何度も読み直してみた。
しかし、CPS自体に付いては理解は出来たが、
- オブジェクト指向と一体何の関係があるの?
- 結局、call/ccと何の関係があるの?
ってのは分からずじまいだった。
結果、この文書を何度も読み返してはふて寝する毎日だった(笑)。
実は1.に関しては「大した事が無かった」のを後に知る事になる(笑)。
オブジェクト指向の「原理的な実装」に付いてはSICPに記述されているが、そこではアクター理論の「メッセージ送信」に付いては何も触れられていない。
これは当然で、SICPでは「オブジェクト指向に於けるデータ設計」に付いて記述してるだけで、メッセージ送信に付いては事実上全く触れてないんだ。
ここでアクター理論に於ける「アクター」は実は何でも良くって、オブジェクト指向に於ける「オブジェクト」あるいは「インスタンス」でも構わない。
例えばSICPの3.1.1の例に対し、次のような関数を定義してみる。
(define (send object message . args)
(apply (object message) args))
これは語順が「アクター理論」で扱われるブツと違うが、メッセージ送信なんだ。objectが継続アクター、そしてmessageとargsが送信されるメッセージとなる。
語順が違うのは、平たく言うと、SICPの「オブジェクト指向的データ設計」の形式に合わせているから、だ。一般的なCPSの記法だと
(send message arg0 arg1 ... object)
となるが、objectが可変長変数を受け取る、と言った場合、関数の引数の末尾に置くと面倒くさくなったりするわけだ。従って、継続をkとすると、
(send k message . args)
と言うような書き方をした方が都合がいい。
また、この場合、「継続」として使われるブツ、つまり送信先の「アクター」はオブジェクト指向的に設計されたデータ型で構わない。データ型がメッセージを「受け取った」時点で、データ型側が「正しいメソッド」を実行してくれるわけだ。
結果、SICPの例だとsendを使って次のように書けば例示と同じ結果が得られる。
> > (define acc (make-account 100))
(send acc 'withdraw 50)
50
> (send acc 'withdraw 60)
"Insufficient funds"
> (send acc 'deposit 40)
90
> (send acc 'withdraw 60)
30
繰り返すが、確かに形式的にはこれはCPSで、継続を受け渡してるんだけど、まぁ、大げさな言い回しだよな、ってのが分かって、3日くらい寝込んでいた(笑)。
ホント、コンピュータ・サイエンスって持って回った言い回しをするんで嫌いだ(怒)。
じゃあ2番はどうなのか。CPSとcall/ccは「どのくらい」関係があるんだろう。
実は、call/ccにまつわる伝説としては、「誰かが偶発的に発見した」と言われている。しかしながら、その「誰か」は明らかにされてない、んだ(※6)。
恐らく次のような話だったんだろう。
上にも書いたけど、初版のSchemeにはcall/ccはなかった。そして初版のSchemeはCPS(翻ってアクター理論)を検証する為の処理系で(※7)、Lisp古来のラムダ式を使っていけば特殊な構文は必要なく、アクター理論を「行える」と言う事が発見された。
このCPSの優秀なトコは高級言語の文脈で「関数の制御」を簡単に別の関数に移せるところだった。つまり、「ジャンプ」を自然と記述している。
そこで、初版のSchemeでは、この性質を利用して、ある特殊なスタイルの再帰だと「効率が良い再帰になる」事を示したわけだな。そうだな、末尾再帰最適化だ。
しかし、初版のSchemeはそれ以上CPSにツッコむ気は無かったらしい。ラムダ式があればCPSは書ける。そしてCPSの成果物として末尾再帰最適化がある。
ところが、初版のScheme(1975年)から第二版のScheme(1985年)の間の10年間に、どっかの誰かがこんな事を思いついたんだろう。
「あれ、Scheme実装のevalをCPSで書けばどないなるんや」
と。
つまり、インタプリタとしては基本は
(loop (print (eval (read))))
なんだけど、これを
(loop (eval (read) print))
と組み立てるような処理系を思いついたんだな。言い換えると、evalが
(define (eval x cont)...
と定義されてるような処理系だ。
そうすると、CPSにより、変数contには「現在evalが行ってる計算」の情報全てが入ってる事となる。
また、eval内で使われてるcontはローカル変数なんで引数のcontを参照可能、つまり「現在の継続を取り出せる」事となる。
この「eval内のcont」を自由に取り出せるようにしたプリミティヴな関数が、call/ccだ。eval内で定義されている以上、evalの「状態」がCPSプログラミングスタイルでは常にキャプチャされている。
またそのため、call/cc自体はユーザーが直接「プログラミング」するわけにはいかないんだ(※8)。
いずれにせよ、CPSとcall/ccの「直接の関係」ってのはSchemeインタプリタの「実装」に於いて出てくるモノで、実の事を言うとユーザーレベルではさほど関係はない、ってのが実際なんだ。
と言うわけで、名もなき誰かのインタプリタ実装上のイタズラで「発見された」call/ccはLispの古典的なcatch/throwを置き換えるようにして登場し、通常の言語で言うreturnやbreakの代替物のようなカンジの機能だとは言える。
しかし、それでもピンと来ない機能ではある。と言うのも「関数型言語」Lispは、そもそも「明示的なreturnが無くても自然と値を返す」言語だからだ(※9)。
例えば「フツーの言語」Pythonで、再帰で階乗関数を書く場合、当然returnのお世話にならないといけない。
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
もちろん、Schemeでもcall/ccを用いて同様の形式で関数を書くことは可能と言えば可能だ。
(define (fact n)
(call/cc
(lambda (return)
(if (zero? n)
(return 1)
(return (* n (fact (- n 1))))))))
しかし、誰もこんな風には書かないだろう。なぜならSchemeではプロシージャじゃない限り必ず値を返すわけで、明示的にcall/ccを使う必要性がないから、だ。
つまり、こんな例だと「何の為にcall/ccがあるの?」になってしまう。大域脱出でさえcall/ccは無用の長物と化し、あまり説得力がない例になってしまう。
それでもcall/ccは強力なんだ。
第一に、通常、returnやbreakの類は構文だ。関数ではないんだ。一方、call/ccは関数で、いつぞやも見せたが、高階関数の引数にさえ出来てしまう。
> (map call/cc (map (lambda (x)
(lambda (return)
(return x))) '(1 2 3 4 5)))
'(1 2 3 4 5)
この簡単な例も実用的には説得力がないかもしんない。ただし、こんな事はフツーのプログラミング言語だと実は不可能なんだよ。
# Pythonで同じ事をやろうとしたら怒られる。>>> [return x for x in [1, 2, 3, 4, 5]]
SyntaxError: invalid syntax
そもそも、脱出のような制御機構が関数になってる、なんつーのは異常なんだ。
この、高階関数とcall/ccの組み合わせの典型例と言えば、Lispでお馴染みの「多値」はSchemeでは原理的にはcall/ccで実装されている。
> (define (my-values . args)
(call/cc (lambda (return) (apply return args))))
> (my-values 1 2 3)
1
2
3
可変長引数argsのリストに対して「脱出」をapplyすると、あら不思議、「同時に複数の値を返す」事になるわけだ。
当然こんな挙動は、他の「return/breakが関数じゃない」言語では不可能、って事になる。
# Pythonだと単にタプルが返るだけ、だ。# もっともPythonだとタプルが多値代わりなんで、正しい結果だ、と言えば正しい。>>> def values(*args):
return args
>>> values(1, 2, 3)
(1, 2, 3)
また、call/ccは脱出を司るが、「大域脱出」「局所脱出」を区別しない。単に「どこをcall/ccで包むのか?」が問題になるだけ、だ。
一方、通常のプログラミングだと、returnは大域脱出、breakは局所脱出、と用途が分かれている。
例えばPythonでの次の例を見てみよう。
これはSchemeで書くと次のようになる(※10)。
(dolist (n (range 2 10))
(call/cc
(lambda (break)
(dolist (x (range 2 n))
(when (zero? (modulo n x))
(printf "~a equals ~a * ~a~%" n x (quotient n x))
(break #f))))))
ここでは、継続breakを用いて内側のdolistの外側へと脱出してるが、大域脱出ではなく局所脱出だ。
もちろん、コンテクストが変われば表現が変わるべきだ、と言う意見も一考に値するが、call/ccは「脱出」と言う事象に於いて、returmもbreakも統一的に扱う立場を取っている。
また、通常の言語では、returnは値を返すが(※11)、breakは単に脱出するだけ、だ。
一方、継続は「一引数関数になる」と言う縛りがあるが、これは本当に便利なんだ。
例えば、何度か例に挙げてるが、数値リストの要素全部を掛け合わせる関数list-productを考える(※12)。
これは正常に動くが、一方、リストsに0を見つけた場合、残りの計算は無駄になってしまう。
必要なのは、リスト内に0を見つけた際に即座にfoldlの計算を止めて0を持って脱出しちまう事だ。
(define (list-product s)
(call/cc
(lambda (exit)
(foldl (lambda (y x)
(if (zero? x)
(exit 0)
(* x y))) 1 s))))
こういう、イテレータを強制的に停止させる、なんつー事はフツーの言語では出来ない。また、Pythonなんかのbreakはループから脱出する為の機能なんだけど、reduceなんかでは使えないんだ。
他にも、継続は一引数関数なんで、局所脱出で「持ち出した」値に対して更に加工する、と言うような事もやってのけられる。
とまぁ、「脱出」って事だけに絞って考えてみても、call/ccは破格の強力さを備えている。そしてその強力さを何が支えてるのか、と言うと、半分くらいはcall/ccが関数である、と言う事だと思う。脱出なのに構文じゃない。「制御機構を表現する関数」なんつーのは、フツーの言語では考えられない事だ。
結果、フツーの関数で出来る事はcall/ccにも出来、関数型プログラミングの枠組みで自在に扱う事が可能となるわけだ。
と。ここまでは良い。
問題が出てくるのは、継続がファーストクラスオブジェクトであり、代入なぞが可能だ、って辺りから、なんだ。
曰く、
「callccを使えばゲームなんかのセーブも簡単に出来るんだよ!」
と。
ゲームをセーブする機能を書く事は結構難しい。今現在「進行中」の事柄に於いて、色んな「状態」を記憶しとかなきゃならないから、だ。低レベルで言うと、メモリの状態もともかくとして、コールスタック、と言われる「現在実行してる関数を保持する領域」なんかも逐一記録しておかないとならない。
思い返してみれば、ファミコン/スーファミなんかでも「自由にプレイ途中の状態」ではセーブ出来なかったんじゃないか?特殊なセーブ地点だとか、区切りが良いトコ、しかセーブ出来なかっただろ?
そう、今やってるゲームの「あらゆる情報を」全部プログラマ側がカウントして適切に「保存する」ってのは難しいんだ。
ところが、理論的な話をすると、「継続」ってのは「今実行中の事柄」を自然と全部把握出来る機能なんだ。把握できなければ「続き」が実行出来ないからな。
そういう機能を尖ったRubyのプログラマはコーフンして話していた。
一方。
じゃあ、Schemeのcall/ccが同等の事が出来るのか、と聞かれると一般的には「出来ない」といえるだろう。少なくとも、当時のMzScheme(Racketの前身)では不可能だった。
話を聞いた僕は、「じゃあ、"継続"はファイルに書き出せるのか？」とやってみたんだ。
(define cc #f)
(* 3 (call/cc (lambda (k)
(set! cc k)
(+ 1 2))))
(with-output-to-file "cont.rkt"
(lambda ()
(display cc)))
ところがファイルに書き出された結果は「これ」だ。
#<procedure>
「関数」と言うデータ形式でしたよ、と書き出されるだけで情報は全部消失してやがった(笑)。「クソも役に立たねぇ!」って怒り心頭だったんだ(笑)。
ちなみに、川合史朗さんに拠ると、「継続を書き出して保存出来る処理系もある」らしい(※14)。しかし、これは実装依存、と言う事になり、そもそも仕様上、「継続」が「これだ」っつーデータ形式を持ってない、って事を意味する。
そして、あっちこっちで「継続は保存出来ます」って言い回しをしてるけど、「オンメモリ」って意味なんだ。通常の意味で言うと「セーブ」は出来ない。従って、一般的には、Schemeでなんかのソフトウェア(ワープロでもいいし、表計算でもいい)を書いたとしても「保存」機能に継続は使えない。古典的に「データこれこれを書き出して・・・」ってプログラマ側がやらなアカンので「その辺諸々の面倒くささを解決出来る」夢溢れた機能ではない、ってこった。
あまりにもガッカリして7日間くらい寝込んでた。
そして、ここまでは関数型プログラミングで来た。しかし、継続の応用の本懐は「変数への代入」だ。そう、Schemeプログラミングで排されて来た「破壊的変更」がいきなり出てくるんだ。
と言うか、Schemeのset!は殆ど継続の束縛の為にある、って言って過言じゃない。
とは言っても、やっぱ気持ち悪いんだよ(笑)。関数型プログラミングをずーっとやってきてるのにいきなり「破壊的変更の要請」とは(※15)。
第二の問題として、call/ccの「キャプチャ範囲が何なのか」がハッキリしない辺りだ。これも「解説」は割にワンパターンで書かれてるんだが例示が少なくて結果、いまいちピンと来ない、と言う話になる。
取り敢えず「キャプチャ範囲」の話から始めよう。
例えば良くある例に次のようなモノがある。
> (define cc #f)
> (+ 2
(call/cc
(lambda (k)
(set! cc k)
(* 5 4))))
22
> (cc 1)
3
本質的には、このコードは(+ 2 (* 5 4))と言う計算をしてるだけ、で答えは見た通り22だ。ただし、途中にcall/ccを挿入して「(何かに)2を足す」と言う「継続」を大域変数ccへと保存している。結果、ccはそのまま「(何かに)2を足す」と言う効果を獲得して、引数に1を与えて呼び出せば(+ 2 1)が実行されて3と言う結果を得るわけだ。
文字通り、call/ccは「内側に何があるか」には全く興味がなく、call/ccが置かれた「外側の環境」をキャプチャしている。
以前も書いたけど、「スコープが反転してる」のが分かるだろう。call/ccが興味があるのは「常に外側」なんだ。
ところが、これはいわゆる「良くある用例」なんだけど、これ「だけ」の用例だと一体「どこまでがキャプチャ範囲なのか」ってのがユーザーには分かりづらい、と言う問題が生じる。
例えば次のような式を考える。
(/ (* 6/7 7/2) (- 4.5 1.5))
ここで、適当にcall/ccを置いて「継続」を大域変数に代入した、とする。果たして一体「何」がキャプチャされるんだろうか。
> (define cc #f)
> (/ (* (call/cc
(lambda (k)
(set! cc k)
6/7)) 7/2) (- 4.5 1.5))
1.0
> (cc 1)
1.1666666666666667
call/ccは置かれた環境「全て」をキャプチャしている。ccでの計算を見ると、これはつまり6/7以外の全部がキャプチャされてる、って事だ。
> (/ (* 1 7/2) (- 4.5 1.5))
1.1666666666666667
位置は関係ないのだろうか、ってぇんで実験してみよう。
> (/ (* 6/7 (call/cc
(lambda (k)
(set! cc k)
7/2))) (- 4.5 1.5))
1.0
> (cc 1)
0.2857142857142857 ;; (/ (* 6/7 1) (- 4.5 1.5)) と同じ計算結果> (/ (call/cc
(lambda (k)
(set! cc k)
(* 6/7 7/2))) (- 4.5 1.5))
1.0
> (cc 1)0.3333333333333333 ;; (/ 1 (- 4.5 1.5)) と同じ計算結果> (/ (* 6/7 7/2) (- (call/cc
(lambda (k)
(set! cc k)
4.5)) 1.5))
1.0
> (cc 1)
-6.0 ;; (/ (* 6/7 7/2) (- 1 1.5)) と同じ計算結果
> (/ (* 6/7 7/2) (- 4.5 (call/cc
(lambda (k)
(set! cc k)
1.5))))
1.0
> (cc 1)
0.8571428571428571 ;; (/ (* 6/7 7/2) (- 4.5 1)) と同じ計算結果
> (/ (* 6/7 7/2) (call/cc
(lambda (k)
(set! cc k)
(- 4.5 1.5))))
1.0
> (cc 1)
3 ;; (/ (* 6/7 7/2) 1) と同じ計算結果
見た通り、どこにcall/ccを置こうが、問答無用に、その「外側」をキャプチャする。位置なんざ関係ない。
また、次のような式を考える。
(+ (+ 2 2) (+ 2 2))
これに対して、次のようなcall/ccの使用を考えよう。
> ((call/cc
(lambda (k)
(set! cc k)
+)) (+ 2 2) (+ 2 2))
こんな風に書いて、「引数"だけ"をキャプチャ出来るのか?」と問えば、何と、これもO.K.なんだ。
> (cc -)
0
> (cc *)
16
> (cc /)
1
(+ 2 2) と (+ 2 2) と言う2つの引数情報「のみ」がcall/ccの「外側」としてキチンとキャプチャされてる。抜けてるのはcall/ccの内側にある+、つまり「使用した関数の情報だけ」だ。
恐ろしい(笑)。
つまり、基本的には、
(ex1 ex2 ... (call/cc f) ... exn)
と言う表現があった場合(fは1引数関数とする)、(call/cc f)は次の式に置き換えて考える事が出来る、って事だ。
(lambda (k)
(ex1 ex2 ... k ... exn))
ホント、文字通り、「外側丸ごと」がキャプチャ対象になってる、って事だ。
バカバカしく思えるんだけど、「そういう事」にならざるを得ない。
ところが、call/ccは「その外側のデータを全てキャプチャする」とすると、次のような不可思議な動作が分からなくなる、ってのも事実なんだ。
> (begin (call/cc
(lambda (k)
(set! cc k)))
(+ 3 3))
6
大域変数ccに(+ 3 3)と言う情報が保存されるのか?と思うと「そうじゃない」結果が返ってくる。
> (cc #f)
#f
> (cc 1)
1
単純に言うと、「なんかを返す」と言う「挙動」だけが保存されるが、(+ 3 3)と言う情報は消えてしまったようだ。
おかしい。何故なんだ、と。
一つその前の例示との違いを言うと、ここで使われてるbeginは関数ではなくマクロ、なんだ(※16)。call/ccでマクロを扱う場合は解釈がややこしくなる。
つまり、その前の「(call/cc f)の一般化」で解釈するにはちと納得が行かない結果となってるだろう。
;; こう考えられる?(lambda (k)
k
(+ 3 3))
beginだけ、ではなく、例えば次のようなマクロでも同様だ。
> (if (null? '())
(call/cc
(lambda (k)
(set! cc k)))
'(b c))
> (cc #f)
#f
> (cc 1)
1
> (and (> 3 2) (call/cc
(lambda (k)
(set! cc k))))
> (cc #f)
#f
> (cc 1)
1
「返る」と言う「事象」だけが記録されていて、「call/ccが置かれた外側」は記録されていない。
じゃあ、マクロ全部がそうなのか、と言うとそうじゃない、って辺りが問題を複雑化する。
例えば、Racketのbegin0と言うマクロを見てみよう。
> (begin0 (+ 3 3)
(call/cc
(lambda (k)
(set! cc k))))
6
> (cc #f)
6
これは「6と言う情報」を確かに記録してるんだ。「なんでやねん?」となるだろう。
実はbegin0と言うマクロは定義的には次のようなモノだ。
(define-syntax begin0
(syntax-rules ()
((_ first-form form ...)
(let ((val first-form))
form ...
val))))
これで伺い知れるのは、letと言うマクロは継続がその外側をキャプチャ出来るマクロだ、と言うことだ。
> (let ((x 2))
(call/cc
(lambda (k)
(set! cc k)))
(+ x 3))
5
> (cc #f)
5
そして理論的には、letと言うマクロはlambdaと言うマクロで記述されている(※17)。
つまり、lambdaと言うマクロは「関数と言うデータ型を作成する」が、「その実行」に於いてはcall/ccが「その外側の環境」をキャプチャ出来る、ってことだ。
> ((lambda (x) (call/cc
(lambda (k)
(set! cc k)))
(+ x x)) (* 3 4))
24
> (cc #f)
24
続く。
※1: Scheme自体の登場は1975年だが、これもMITのAI研ローカルの「私的処理系」だと言ってよく、また、実装もMITのMACLISP(Emacs Lispの前身)で作られた、Pythonのような「仕様 = 実装」言語だった。
3年後に出版されたR1RS(Revised Report on Scheme)は35ページしかない「文書」だが、この時点だと実は「仕様」と言うより、ちと論文よりであって、「こんな処理系を作りましたよ」と言うのを「発表した」だけに近い。
そういう意味では、初めて「誰でもSchemeを実装可能」な「仕様」となったのはR2RSから、であり、R1RSを読んで「見様見真似で」Schemeを作った実装者が各自、R1RSで生じた問題等を持ち寄って会議し、現在のRnRSに見られる「仕様の形式」を整えた最初の版だ、と言う事ができる。
※2: yin-yangとは恐らく、陰陽道の「陰陽」の事だ。中国(簡体字)では「阴阳 」(yīnyáng)と記述するらしい。
毛唐が名付けた割にはシャレている(笑)。
※3: この「難しさ」の大半は、繰り返すが、実装上、デバッガ自体が継続が「何を抱えてるのか」示せないトコに負うと思う。結果、暗中模索のプログラミングにならざるを得ない。
「見えないデータ相手にプログラムする」と言う事が想像できれば、これがどれくらい「難しい事か」よく分かると思う。
※4: CPS自体は以前、このブログでも扱った事がある。
そこではPythonを用いたが、CPS自体はPythonやLispに限らず、ラムダ式を持った言語(JavaScriptやC++等でも)なら書けるプログラミング・テクニックで、「継続」自体を取り出す事は可能だ。
反面、ラムダ式を持たないCやPascalなどの言語ではCPSは書けないし、継続自体は基本的には取り出せない。
※5: SICPではマクロと共に、call/ccに付いては一つも書かれていない。
信じられない事に、SICPはMITの新入生向けの「初めてのコンピュータ・サイエンス」を意図して書かれたモノだが、難解な同書でさえ「call/ccはより上級生向けの機能」として省かれている。
言い換えると、call/ccが難解なのはMITのお墨付きだ、と言う事だ。
※6: 理論的な話では、イギリスの計算機学者、ピーター・ランディンが1965年に提唱したJオペレータがcall/ccそのもの、と言ったような話がある。ただし、1965年はまだSchemeは生まれていない。
※7: 話によると、「アクター理論」、及びそれを備えたプログラミング言語、PlannerとPlasmaがあまりにも使うのが難しくて、開発者のヒューイット教授と大喧嘩したのが、SICPの著者、ジェリー・サスマンだと言われている。
彼がMITの後輩、ガイ・スティールを誘って、アクター理論を検証する為に作り出したのが初代Schemeとなる。
※8: この辺の「実装法」に付いては、実用Common Lisp(PAIP)が詳しい。
 | 実用Common Lisp ピーター・ノーヴィグ 翔泳社 |
また、call/ccの基礎的な実装に付いては「ラムダ式を持ったインタプリタならではのモノ」と言うのも分かると思う。
一方、Schemeをコンパイラとして実装したり、あるいはC言語なんかのコンパイラ実装を利用してcall/ccを実装するのはかなりメンドイ、って事も想像に難くない。スタックを一々気にして「まとめなきゃならない」ってのはかなり手間がかかる。
※9: もっとも、厳密に言うとSchemeはその定義には当てはまらない。Lispの流れから外れて「値を返さない」プロシージャがSchemeには含まれているから、だ。
※10: 厳密にはRacketで書いている。
また、ここではANSI Common Lispから移植したdolistマクロを用いている。
※11: 一般に言うとreturnは単独で使えて、後続に値が無い場合はプロシージャとして解釈される、と言うケースが多い。
※12: これも厳密にはRacketで書いている。
foldlが無い処理系ではSRFI-1のfoldを用いればいい。
※13: RubyユーザーはPythonユーザーと違って保守的じゃない、ってのが特徴だった。限りなくハッカーに近い層がユーザーだったんで、「どんな難解な機能」でも割に喜んで受け入れる土壌がある。
※14: 冷静に考えてみると、「計算を中断した状態をファイルに書き出す」となると、フツーのテキストファイル相手じゃ無理で、最低でもバイナリファイル形式にならざるを得ないし、半分コンパイラのような機能になるんじゃないか。
また、少なくとも当時(R5RS)のSchemeだと仕様上バイナリファイルの読み書きも出来ないし、「継続の存在」の割には出力周りが単に貧弱だった、って事が言えるんじゃなかろうか。
※16: Schemeの仕様上、マクロ、と言う用語は使われてはいるが、同時にシンタックス、も用いられていて、かなり曖昧だ。
ANSI Common Lispでは、プリミティヴなシンタックスを「特殊形式」と呼び、プリミティヴなシンタックスを組み合わせて作り上げたシンタックス(構文)をマクロと呼ぶ。
一方、現行のScheme仕様書では、プリミティヴ(原始式系)なシンタックスはそのままシンタックス、でいいが、プリミティヴなシンタックスを組み合わせて作り上げたシンタックスを「派生式系」、と呼称してるようだ。
一方、「ライブラリ構文」と言う呼び方もあり、しかしここに含まれるのが必ずしも「派生式系」ではない、と言う辺りが混乱する。
この辺の「整理」はどう見てもANSI Common Lispの方がスッキリとしてる。
※17: あくまで「理論的には」だ。
Schemeの現行仕様上、letもlambdaも単なる「構文」であり、しかしletは「派生式」なんで、「プリミティヴとして実装しなさい」と言われてるANSI Common Lispのletと比するとどう解釈していいのか分かりづらい。
ここでは一応、letはlambdaの構文糖衣だとしておこう。
