2007-08-30

私の苦手な単語である継続とやらについて調べてみた。

定義: 『プログラミング言語 SCHEME』のおまけの R5RS 6.4. 制御機能より抜粋

procedure: (call-with-current-continuation proc)
proc には1引数を受け取るプロシージャを指定する。プロシージャ call-with-current-continuation は現在の継続を「脱出プロシージャ」としてパッケージ化し、proc に引数として引き渡す。
継続とは、(デフォルトの)計算処理終了後の将来像を表現したものである。

将来像を表現したものって酷い言葉だ。関数の機能としては、とりあえず引数は一引数の関数で、その引数に継続が入るらしいので何が入るか試してみる。

gosh> (call/cc (lambda (c) print c))
#<subr continuation>

特に何も面白い事は起こらない。説明を読むと、引数の関数の引数(なんてややこしい)は特別な関数らしいので、その関数を呼ぶとどうなるかやってみる。

gosh> (call/cc (lambda (c) (c "hello")))
"hello"

引数と同じ値が返るだけだ。次に、式の途中で使うとどうなるかやってみた。

gosh> 
(call/cc (lambda (c)
           (begin (print "hop,")
                  (print "step,")
                  (c 'exit)
                  (print "jump!"))))
hop,
step,
exit

hop, step, と来て jump! の前に中断される。なーんだ。これだけか。という事で、式の途中で中断して返す関数の事を継続と言うらしいという事が分かった。という事でこれは最強の言語であるところの Smalltalk で書くとこうなる。

thisContext in: [ :c |
    Transcript show: 'hop,'.
    Transcript show: 'step,'.
    c return: #exit.
    Transcript show: 'Jump!'].

これが大騒ぎするほど凄い概念か？？？と疑問は残るが、意味は分かった。

-- 階乗の Haskell 再帰版 fact 0 = 1 fact n = n * fact (n - 1) -- CPS 版で書くとこうなる。(fact_cps 10 id => 3628800) fact_cps 0 cont = cont 1 fact_cps n cont = fact_cps (n - 1) (\a -> cont (n * a))

!Number methodsFor: 'factorial' stamp: 'tak 8/30/2007 00:50'! fact "10 fact" self = 0 ifTrue: [^ 1]. ^ self * (self - 1) fact! ! !Number methodsFor: 'factorial' stamp: 'tak 8/30/2007 00:54'! factCPS: aBlock "10 factCPS: [:a | a]" self = 0 ifTrue: [^ aBlock value: 1]. ^ self - 1 factCPS: [:a | aBlock value: self * a].! !

言語ゲーム

とあるエンジニアが嘘ばかり書く日記

継続とは何か？

継続渡し形式(CPS)変換とは何か？