2007/03/07

call/ccは「引数を1つとる関数」である。
call/ccは「引数を1つとるプロシージャを1つ引数にとる関数」である。
ということは、call/ccにcall/ccを引数として与えられる。
(call/cc call/cc)
これは何か。

おさらいから。call/ccは引数を1つとるプロシージャを引数にとる。
(call/cc (lambda (k) ...))    ; (A)
これをなんとなく評価してみると、内側の(lambda (k) ...)に適当な引数を与えて評価されたかのような結果が得られる。
gosh> (call/cc (lambda (k) 1))
1
gosh> (call/cc (lambda (k) (odd? 1)))
#t
このときの適当な引数が継続である。つまり、(A)を評価するとそのときの継続を引数にして内側の(lambda (k) ...)が評価される。これがcall/ccという名前の関数の動作だ。

では、そのときの継続適当な引数)ってのが具体的に何であるかを考えよう。実際に内側の(lambda (k) ...)でkを返すようにしてみても、あまり有効なヒントは得られない。
gosh> (call/cc (lambda (k) k))
#<subr continuation>
そこで、call/ccの引数であるプロシージャのなかで、kを適当なグローバル変数に代入してみる。
gosh> (define c '())
c
gosh> (call/cc (lambda (k) (set! c k) k)) ; (B)
#<subr continuation>
gosh> (c 100 "abc" (odd? 1) (display (/ 5 2)) (display "\n"))
2.5
100
"abc"
#t
#<undef>
#<undef>
どうやらcは、任意の引数をとってそれを評価するプロシージャみたいに機能している。しかしcはプロシージャではない。cとeq?の意味で同じオブジェクトであり、かつ(B)が返すはずのkも、やはりプロシージャではない。だから、こんなふうに適用することはできない。
gosh> ((call/cc (lambda (k) (set! c k) k)) 1)    ; (C)
ERROR: invalid application: (1 1)
(C)からは、kがプロシージャでないことを納得する以上に興味深いことがわかる。もしcall/ccが内側のlambdaを評価しているだけなら、(C)のように実行してエラーが返ったところで、cには(B)を評価したときと同じような動作をするオブジェクトが代入されているはずだ。ところが結果は次のとおり。
gosh> (c 100)
ERROR: invalid application: (100 1)
どうやらc(つまりk)は、外側のcall/ccがどういう文脈で評価されたかを知っている。そしてSchemeでは、そういうオブジェクトを継続と呼んでプロシージャ並みに自由に扱うことができる。

(C)の場合、call/ccの返すオブジェクトは、引数の位置に数字の1をともなって評価されようとしている((call/cc ...) 1)、引数自身(lambda (k) ... k))だ。
だから、(C)は「引数の位置に数字の1をともなって評価されようとしている数字の1」だし、(c 100)は「引数の位置に数字の1をともなって評価されようとしている数字の100」だ。いずれもエラーになって当然。

ちなみに、cは「引数の位置に数字の1をともなって評価されようとしている……」なので、次のようにcを評価すればエラーにならない。
gosh> (c (lambda (x) 1))
1
gosh> (c (lambda (x) 100))
100
もちろん最初から同様にやることもできる。
gosh> ((call/cc (lambda (k) (set! c k) k)) (lambda (x) 1))    ; (D)
1
(lambda (x) 1)とかを引数にしている限り、cの動作もあんまり変わらない。
gosh> (c (lambda (x) 1))
1
gosh> (c (lambda (x) 100))
100
しかし、この見た目に惑わされると道を見失う。(D)の結果cは「引数の位置に数字の1を返す1引数プロシージャをともなって評価されようとしている……」になるので、先のcとはまったく異なるものだ。今度のcには、「1引数プロシージャを引数にするプロシージャ」を適用できる。
gosh> (define apply100
(lambda (proc)
(proc 100)))

apply100
gosh> (c apply100)
1
くどく書けば、(c apply100)は「引数の位置に数字の1を返す1引数プロシージャをともなって評価されようとしているapply100」だ。だから1が返る。

ところで「1引数プロシージャを引数にするプロシージャ」は、わざわざapply100みたいなのを定義しなくても身近にある。call/ccだ。ということは、次の式もきちんと評価されるし、その結果もここまでくれば明らかだよね。
gosh> (c call/cc)
1


さて。

冒頭に書いたように、call/ccは引数を1つとるプロシージャを引数にとる。そこで今度は、さっき定義したapply100を使って次の式について考えてみよう。
(call/cc apply100)    ; (E)
apply100は、「引数を1つとって、その引数をプロシージャとして、そのプロシージャの引数には数字の100を束縛する」。したがってcall/ccから見ると、「call/ccを呼んだときの継続に数字の100を適用する」。トップレベルで(E)を呼べば、そのときの継続は「評価して返す」というREPLの基本動作だけなので、100が返る。
gosh> (call/cc apply100)
100


ところで「引数を1つとるプロシージャ」は、わざわざapply100を使わなくても身近にある。call/ccだ。ということは、次の式もきちんと評価される。
(call/cc call/cc)    ; (F)
call/ccは、「引数を1つとって、その引数をプロシージャとして、そのプロシージャの引数にはそのときの継続を束縛する」。したがって左のcall/ccから見ると、「左のcall/ccを呼んだときの継続に右のcall/ccを呼んだときの継続を適用する」。トップレベルで(F)を呼べば、そのときの継続は「評価して返す」というREPLの基本動作だけなので、右のcall/ccを呼んだときの継続が返る?
gosh> (call/cc call/cc)
#<subr continuation>


右のcall/ccを呼んだときの継続って何?(結局疑問形で時間切れ……)

0 件のコメント: