あるいは、なぜcall/ccがプリミティブなのか、に関する一考察
(Shiro: 「なんでも継続」に入れようかと思ってたネタだけど、 あっちがいつ書けるかわからんので、忘れないようにこっちにまとめとく)
(話の流れがあるので、誤りの修正以外のコメントは途中ではなく、一番下にお願いします)
Aliceは、リストlisと述語手続きpredを取り、lisの各要素に順にpredを適用して、 predが真の値を返したら直ちにその要素を返すような関数findを 書くことを考えた。 (findは便利なので、実はsrfi-1に定義されてるけど、 Aliceはまあ自分の勉強のために書いてみることにしたと思いねえ)。
AliceはPerlなら良く知っている。Perlならこんな感じで書けるはず。
sub find
{
($pred, $lis) = @_;
foreach $elt (@$lis) {
return $elt if $pred->($elt);
}
}
find(sub { (shift()%2) == 0 }, [1, 3, 5, 4, 2]) ==> 4
Schemeにもfor-eachってあった。じゃあこんな感じ?
;; Alice-1
(define (find pred lis)
(for-each (lambda (elt) (if (pred elt) (return elt)))
lis)
#f)
ところが、動かしてみると怒られる。
gosh> (find (lambda (x) (zero? (modulo x 2))) '(1 3 5 4 2)) *** ERROR: unbound variable: return Stack Trace: _______________________________________
困ったAlice、近くのScheme使い、Bobに聞いてみて、驚愕の事実を知る。
ああ、Schemeにはreturnってのは無いんだ。
じゃあどう書けばいいの、というAliceに、Bobはふたつの方法を 教えてくれた。
普通のイディオムとしては、こういう場合は明示的に再帰で書くね。
;; Bob-1 (define (find pred lis) (let loop ((lis lis)) (cond ((null? lis) #f) ((pred (car lis)) (car lis)) (else (loop (cdr lis))) )))でも、どうしてもfor-eachからreturnを使いたいなら、call/ccってのを 使ってこうも書けるよ。
;; Bob-2 (define (find pred lis) (call/cc (lambda (return) (for-each (lambda (elt) (if (pred elt) (return elt))) lis) #f)))(call/cc (lambda (return) ...)) は説明すると長くなるけど、まあ、 returnってラベルを定義してるもんだと思ってくれればいい。 疑似コードで書けば、概念的にはこんな感じだね:
{ for-each ... ( goto return ) ... return: }
うーん、でもAlice、どうも納得できない。だって、Alice-1みたいな コードって、PerlでもCでも、すごく良く出てくるパターンでしょ。 どう見たってBob-1やBob-2よりわかりやすいと思うけどなあ。
Aliceはその疑問をBobにぶつけてみた。
うん。それは確かにそうなんだけども、Schemeっていうのは、 なるべく少ないプリミティブでなるべく多くのプログラミングパラダイムを なるべく簡潔にサポートする、ってのがポリシーでさ。 例えば再帰があればループ構文は要らない、とかね。 それと同じで、call/ccってのがあると、returnとかbreakとかcontinueみたいな 構文要素は全部表現できるし、さらにもっとすごいこともできるんだ。 それなら、call/ccだけをプリミティブで持ってればいいって考えなのさ。
もっとすごいことって何よ。
それは、うーんと、実はぼくも良くしらないんだけれども、 なんか色々できるらしいよ。
そんなの説明になってないわ。だいたい、最小の要素なんて突き詰めたら、 チューリングマシンになっちゃうじゃないの。絶対、変。
納得いかないなら、comp.lang.schemeあたりで質問してみれば?
だってあそこ、わけわからない細かいことについて延々と議論するような 人達がたくさんいて恐いんだもの。 最近だって、引数の評価順序を決めるのがいいとかわるいとか…
そうだ。いつもカッコつけて話してるClaudeなら何か知ってるかもしれない。
(私のことを)(呼んだかね?)
ああちょうど来たわ。あの人の話、ちょっと聞きづらいんだけど、 我慢して聞いてみましょう。
(うん)((良い 質問)だね)
(じゃあ)(逆に ((私から Aliceに)質問 するが))(もし ((Alice-1 の ように) 書けた) として)
((return は) どこに 戻れば いいかな?)
それは、findから抜ければいいんじゃない。
(define (find pred lis) ...) は (define find (lambda (pred lis) ...) の (短縮形) だった よね。
つまり (Alice-1 は) (こんなふうに) 書ける わけだ;; Alice-1' (define find (lambda (pred lis) (for-each (lambda (elt) (if (pred elt) (return elt))) lis) #f))lambda は (二重に) なっている。
(ところで (この return) は (内側の lambda) の 中に あるんだけれども) return は どうやって (抜けるのが (内側の lambda) ではなく (外側の lambda) である)ことを 知るのかな。
えっとそれは… 一番外側のlambdaから抜けることにすれば…
そう単純じゃないのさ。
Schemeでは(関数を生成する関数)なんてものを普通に使う。
((findみたいな関数) を生成する関数) を定義している場合、 (一番外側のlambda)ってどこになる? (こういうコード)だとしてさ。
;; Claude-1 (define make-find (lambda () (lambda (pred lis) (for-each (lambda (elt) (if (pred elt) (return elt))) lis) #f)))(実際のコードでは)、関数はいくらでもこんなふうにネストし得る。 だから、少なくとも、(どのレベルの関数を抜けるのか)を明示的に 示してやらなくちゃ、(returnは意味を持たない)。
(breakやcontinue)も同じことになるのさ。Schemeには ((構文上のブロック)って概念)は無いからね。 あるのは(for-eachに渡されるような)lambdaだけだ。
(何をbreakするのか)、(何をcontinueするのか)、 それは文脈からだけじゃ決定できないわけさ。
それが理屈の上では綺麗だってのはわかるわ。 でも、コモンイディオムをサポートするって考え方はあるでしょ。 理屈の綺麗さを重視して、普段書くプログラムの負担が増えたんじゃ、 言語としての意味がないんじゃないかしら。
ふふ。(Schemerとして言わせてもらうと)、それは逆なんだね。 (return, break, continue等の構文は)、ブロックなり 外側の関数なりを特別扱いしているから意味を持つ。 一方Schemeでは、(全てはlambda)だ。関数も、ブロックも、変数束縛さえも。
それによって、Schemerはプログラムを自由自在に(分解して)(再合成する) ことができる。
(for-eachがブロックではなくクロージャを取るから)、 ブロックの中身をパラメタライズしたくなったら、 それを外から与えることができる。 2つの変数が束縛されるブロック(lambda (x y) ...)があって、 yの束縛だけをパラメタライズしたくなったら、 (lambda (x) (lambda (y) ...)) みたいに分解したりとかね。 関数をいくつか書いて、共通するパターンに気づき、 リファクタリングして 異なる部分だけをクロージャでパラメタライズするような、 (関数を生成する関数)を書くことは、 Schemerなら空気のように自然に行っているんだ。
特別扱いする構造を導入することは、その自由を奪うことになる。 (for-eachの中身の一部分だけをクロージャにして分離したら、 プログラムの意味が変わってしまう)、というような言語構造は、 ちょいと困るんだ。
ふーん、Alice、まだ根本的に納得したわけじゃないけれど、 少なくともただreturnじゃまずいってことはわかったわ。 でも、行き先を示せばいいのなら、例えばラベルみたいなものじゃ だめなのかしら。Perlもブロックにラベルをつけて、 深いところから一気に脱出! って出来るわよね。そんな感じで。
;; (脱出は必ずしも副作用を伴わないから、脱出! っていうのは正しくないね。)
(あ、今のは独り言さ)(気にしないでね)
なるほど、確かに、(飛び先を明示してやる)という手はある。 実は、(CommonLispはじめ)、ほとんどのLispはそういう機能を持っている。 例えばCommonLispではblockという構文で(脱出すべきブロック)を示してやる ことができる。
;; Claude-2 (define (find pred lis) (block label (for-each (lambda (elt) (if (pred elt) (return-from label elt))) lis) #f)))実際、(CommonLispでは)(関数を定義するdefun構文)が暗黙にblockを作るんで、 (上のように明示的にblockを使う)必要の無いことも多い。
Schemeでは、(関数の定義)と(変数の束縛)とを区別せず、(関数の定義)とは (無名関数を作ってそれを変数に束縛すること)という、 (非常にシンプルなモデル)を採用した。しかし、そのモデルでは、 (トップレベルの関数定義だけ特別扱いする)ということは不自然だ。 トップレベルであろうが、他の関数の内部であろうが、lambdaはlambdaだからね。
暗黙のブロックがやりにくいことはわかったけど、 Claude-2みたいな明示的なblockはあってもいいんじゃない?
確かにその通り。 実は、((SussmanとSteeleによる)(1975年の)Schemeの最初の論文)には、 (catchという構文)があったんだ。こんなふうに使うことができた。 (当時はまだ、(define (find pred lis) ...) のような短縮形は無かったし、 #fではなくLispのようにNILを使っていたけれども)。
;; Claude-3 (define (find pred lis) (catch label (for-each (lambda (elt) (if (pred elt) (label elt))) lis) #f))(Claude-2のblock)とそっくりだろう。 ブロックとの違いは、脱出に(return-fromのような)構文を用いるのではなく、 catch構文の最初の引数に与えたシンボルには(catchを抜けるための継続)が 束縛されていて、それを関数のように呼び出すことでcatchを抜けることが できるようになっていた。
出たわね、継続。
そんなに身構えなくてもいい。Claude-3の例で言えば、 labelに引数を渡して関数のように呼び出すと、 まるで(catch式からその引数が帰って来たかのように)動作するってことさ。
Cのsetjmp/longjmpを考えてみるといい。 longjmpを行うと、プログラムからはまるで (setjmpの呼び出しから戻ってきたように)見えるだろう。
実際、Cのsetjmp/longjmpと継続とは非常に近い関係がある。 ただ、Schemeの場合、オブジェクトのエクステント(有効範囲)は原則として無限だ。 setjmpで捕まえたjmp_bufは、それより下位の関数呼び出しの中でしか使えないけれども、 Schemeの継続にはそういう制限がない。まあ、言ってしまえば違いはそれだけさ。
Claude-3のコードに戻ろう。Schemeは(なんでもファーストクラスオブジェクト) というポリシーがあるから、labelも単なる記号ではなく、 それは(継続を値として持つローカル変数)なんだ。
ちょうど、関数も引数や戻り値で自由に受渡しできるように、 継続も自由に受渡しでができるってことさ。 なるべく特別扱いするものを少なくしようという方針だ。
だから、labelはcatchの内部で直接呼び出す以外にも使える。 例えば、次のコードでは、for-eachの中身を(find-bodyという 別の関数で)定義している。脱出するための継続は、 最初(catchによって)labelに束縛され、 引数を通じて(find-bodyのreturn)へと渡されているわけだ。 こんなふうに、(関数の境界を越えて受渡しができる)ことも、 setjmp/longjmpに似ているね。
;; Claude-4 (define (find-body pred elt return) (if (pred elt) (return elt))) (define (find pred lis) (catch label (for-each (lambda (elt) (find-body pred elt label)) lis #f))
うーん、setjmp/longjmpとの類似性はわかるけれど、 find-bodyなんかを作ることに意味はあるのかしら。
上でちょっとリファクタリングについて触れたけれど、 例えば、ループの中身に関わらない、 (脱出可能なループ)という抽象構造を取り出すことを考えてみよう。
次のコードでは、walkerが受け取るbodyは、 (ループを脱出するための継続を取って、ループの中身となる関数を返す) という関数だ。
findは、抽象構造walkerを使って、 (自分の目的のために特化したbody)を渡してやればいい。
;; Claude-5 (define (walker body lis) (catch label (for-each (body label) lis) #f)) (define (find pred lis) (walker (lambda (return) (lambda (elt) (if (pred elt) (return elt)))) lis)このくらいの構造なら、わざわざwalkerを括り出す必要はないのだけれども、 ずっと複雑なロジックになった時に、(ロジックのメタな構造だけを 別関数に括り出せる)という機能は、実用的なコードを書く上でとても便利なんだ。
そして、(こんなふうに作った継続を引数や返り値で渡して行くためには)、 ラベルのような文法上特別な識別子よりも、 (継続というファーストクラスオブジェクト)が、 (普通にローカル変数に束縛されている)と考える方がシンプルだ。
(継続オブジェクトは自分自身が継続であることを知っている)のだから、 return-fromみたいな特別な構文を使う必要もない。 関数のように呼び出してやれば、望みの場所に飛んで行くというわけさ。 (実は、プログラムにCPS conversionという操作を行うと、 継続の呼び出しと関数の呼び出しは結局同じメカニズムになってしまう、 という背景もあるのだけれどね)。
さて、議論を振りかえってみよう。
- return、break、continueなどをSchemeで実装するためには、 それの飛び先を示すことが必要だ。
- 飛び先を示すには、ブロックにラベルをつけてやればいい
- ラベルに継続を束縛するようにすれば、ラベルだけ特別扱いすることもないし、 そこに飛ぶための特別な構文も必要としない。
なるほどね。そういう流れなら、Claude-3くらいの構文は 受け入れられるわ。
でも不思議ね。もともとあったcatchじゃなくて、それより冗長に見える call/ccが導入されたのはなんでかしら。
(実は私も、call/ccが導入された前後の流れというのをはっきり把握している わけじゃないんだ)。 (私がSchemeに触れた時には既にcall/ccがあったしね)。 (ただ、その理由をいくつか想像することはできる)。
まず、(catchがlabelに対する束縛を導入する)、という点だ。 Schemeでローカル変数を束縛する方法というのは原則としてひとつしかない。 lambda式だ。letもlambdaの構文糖衣にすぎないからね。 (トップレベルの束縛はちょっと厄介なんだが、 インタラクティブな環境でなければ、プログラム全体がletrecで 囲われているようなモデルで説明できる)。
それなのに、catchだけ特別扱いするのは気持ち悪いだろう。
まあ、その気持ち、わからないでもないわ。
letに関しては、次のようにしてlambdaに書き換えることができた。
(let ((var val)) ...) => ((lambda (var) ...) val)それなら、catchについても、何かのメカニズムを使って、 束縛の部分をlambdaに任せたいね。
(catch var ...) => (??? (lambda (var) ...) ???)
つまり、変数束縛っていうのは本質的にはlambdaである、 っていうところに持っていきたいのね。
そうだ。そうすることで、前に言った、 (プログラムを自由自在に分解・再合成できる)という特徴が実現できる。
さっき、(脱出可能なループ)というのを抽象化するwalkerという 関数を導入したよね。その考えをもうひとつ進めてみよう。 つまり、(任意の構造に対して、そこから脱出することを許す関数)という 抽象化をしてみるんだ。その関数をbreakerと呼ぼう。
;; Claude-6 (define (breaker block) (catch label (block label))) (define (find pred lis) (breaker (lambda (return) (for-each (lambda (elt) (if (pred elt) (return elt))) lis) #f)))
ええと、breakerはひとつの引数を取る関数blockを受け取って、 「これを呼べば(breakerの外に)脱出できるよ」っていうオブジェクトを blockに渡すのね。
そして、findの方は、本体をlambdaで囲んで、 それをblockとしてbreakerに渡してやると。 本体のlambdaに渡されたreturnは、breakerの作ったラベル(ええと、継続、ね)だから、 それを呼んでやれば、breakerから直接戻ることになる、と。
ふぅ。追うのは大変だけれど、何が起きてるかはわかったわ。
Claude-6を(ずーっと上の)Bob-2と比べてごらん
あら。call/ccとbreakerが置き換わっているだけ?
そう。(catchという特殊構文)のかわりに、(breakerみたいな関数)がひとつあれば、 変数の束縛はlambdaに任せられる。 それが、call/ccというわけだ。
(catch var ...) <=> (call/cc (lambda (var) ...))両者は相互に変換可能なので、どっちを基準にしてもいいのだけれど、 (変数束縛はlambda)という原則を保つなら、(call/ccを基本にして catchはマクロで実装)、というふうに落ち着いたんじゃないかな。
もちろん、変数束縛の全てをlambdaで書くのは不便だから、 普通はみんなletを使う。それと同じように、call/ccで書くのは面倒だから 構文糖衣が欲しいっていう話はあっていい。例えばPLT Schemeには、 let/ccっていうマクロがあるね。
(call/cc (lambda (var) ...)) => (let/cc var ...)これは便利だから、SRFIレベルで標準にしたっていいくらいだ。 ただ、(こういうマクロを)書こうと思えばすぐ書けるし、 let程には頻繁に使わないから、まだ標準にしようという声があがらないだけだと 思うよ。
なるほどねえ。言語の利用者としては、let/ccくらい標準で ついていて欲しいけれど、背景に関してはなんとなくわかったわ。 ところでClaude、最初はあなたのセリフ、カッコつけてばかりだったけれど、 だんだん読みやすくなったわね。
魚は、自分が水の中にいるっていつも意識してるかな。 Alice、君がカッコがだんだん気にならなくなっただけかもよ。
(深みにはまってゆく気がするわ…)
(define (find pred lis)
(and (not (null? lis))
(if (pred (car lis))
(car lis)
(find pred (cdr list)))))
(define find
(lambda (pred lis)
((lambda not-define-me
(call-with-current-continuation
(lambda (return)
(apply (lambda (pred lis)
(for-each (lambda (elt) (if (pred elt) (return elt)))
lis)
#f)
not-define-me))))
pred lis)))
Alice-1'の代わりにdefineがこう展開したらいいのかなと。
(lambda (return)
(lambda (pred lis)
(for-each (lambda (elt) (if (pred elt) (return elt)))
lis)
#f)
からfindが作れそうな気がするけど、
;; Clause-4
(define (find-body pred return)
(lambda (elt) (if (pred elt) (return elt)))
(define (find pred lis)
(catch label
(for-each (find-body pred label))
lis
#f))
(define (walker body)
(catch label
(body label)))
(define (find pred lis)
(walker (lambda (return)
(for-each (lambda (elt)
(if (pred elt) (return elt)))
lis)
#f)))
walkerがfor-eachに特化せず、受け取る関数が何でもよくなると
call/ccになるって話の方がラベルの順番より分かりやすいと思う。
(return, break, continue等の構文は)、ブロックなり外側の関数なりを特別扱いしているから意味を持つ。