(没)→書き直し
継続を使ったambの実装
この章は難しい。難しい理由を考えてみた。
- 継続の説明がない。
この章は継続を利用してamb を実装することを説明しているだけであって、継続自体の説明はない。 - 継続を実装しているが、どうやって実装しているかの説明がない。
この章では、ambの実装に先立って、継続を実装している。しかしその実装方法とか実装方針とか実装の肝についての説明がない。いつのまにかうまいこと実装されてしまっている。
こんな感じではないだろうか。ということで、本文に入る前にまず継続とは何かについて、および継続の実装方針について自力で理解しとかないといけない。
では継続とは何か。それは、ある関数の継続とは、その関数の次に実行する関数のことである。
合成関数を考える。
この中の関数 h の継続とは、
のことである。h に続いて実行されるのは、f・g だからである。
普通の逐次処理を考える。
(a ...) (b ...) (c ...)
というプログラムについて、(a ...) の継続とは、(b ...) (c ...) のことである。(a ...)に続いて実行されるのは、(b ...) (c ...) だからである。、、、以上で継続自体の説明は終わりである。
次に継続の実装であるが、まず、何のために継続を実装するのか。継続が上のようなものなら、特になにもしなくても元々Schemeはそういう風に動作しているではないか。これ以上なにが必要なのか。
ところが必要はあるのである。amb を使ったプログラムを見てみよう
(let ((x (amb 1 2 3 4 5 6 7 8 9 10))) (require (= (modulo x 2) 0)) (sqrt x))
このソースに対して、我々が期待する処理は、
(define x 1)
(if (= (modulo x 2) 0)
(sqrt x))
(define x 2)
(if (= (modulo x 2) 0)
(sqrt x))
...
(define x 10)
(if (= (modulo x 2) 0)
(sqrt x))
というようなものである。amb評価器は、amb式の継続 (require...) と (sqrt ...) を 10回繰り返さないといけない。つまりこの例では、継続を書いた順に実行するだけでは不十分で、それを繰り返さないといけなかった。
これを Scheme で実現しようとするとどうなるか。2つの方法が考えられる。
- ループとかストリームに置き換える
- 継続を操作して、書いた順の継続を、繰り返し継続に変換する
もちろんこの章では、2番目の方法を採用している。しかし元々Schemeには、継続を操作する能力がない。従って、ここで、「継続を操作する機能」を実装する必要が出てくるのである。
では継続を操作するにはどうすればいいか？ずばり、各関数をλで包んでしまえばいいのである。 例えば、上の (a ...) という関数は、
(λ1 (f) (a ...) ← a を実行する (f) ) ← 引数で渡された f を実行する
とするのである。(b ...) と (c ...) も同様に
(λ2 (f) (b ...) (f)) (λ3 (f) (c ...) (f))
とλで包んでしまう。引数 f は、次に実行する関数、つまり継続を渡す。たとえば、(a ...) のあとで、(b ...) を実行するというのは、
(λ1 (λ2 nil-f) ) ← nil-f は、何もしない関数
となる。λ1は a を実行し、λ2は、bを実行するからだ。次に (b ...) (c...) という2文の継続は、
(λ4 (f) (λ2 (λ3 nil-f)) (f))
と表現できる。次に（a ...） の継続を、(b...)(c...) にしたければ、
(λ1 （λ4 nil-f))
とすればよい。各関数 a, b, c を直接使わず、いったん λ で包んでから使うというのが味噌である。このように各関数を λ 包みにしてしまえば、amb評価器は、これらを自由に組み合わせることができる。継続を操作することができる。
というような感じで、継続の操作はメタ関数だけで実現できる。call/cc や、プログラムカウンタの操作は必要ない。この章の amb評価器もメタ関数だけで実装されている。関数もif 文も、set 文も、amb文も何もかも一旦 λで包んで、継続を操作している。
図にするとこんな感じ
関数 a, b, c を直接使わず、いったん λ でパッケージしてから使うという発想である。
ここで x は関数なので、λ1, λ2, λ3 はメタ関数である。図にするとこんな感じ
これを、次のように接続する。
(λ1 (λ2 (λ3)))
図にすると。
この (λ2 (λ3)) の部分をまとめてλパッケージ化する。
(λ4 (x) (λ2 (λ3))
(x))
結局、a の継続 b, c は、λ4 という一つのλパッケージにまとめることができる。
(λ1 (λ4))
c の継続を a の継続に戻したい場合は、このようにする。
(λ1 (λ4 (λ4)))
処理を戻すために、プログラムカウンタを操作する必要はない。 同じ処理をもう一度呼び出せば良いことである。ここでは、同じλ4パッケージをもう一度接続すれば良い。
このような感じで、関数をλパッケージにしてから使うことで、継続をプログラマブルにすることが可能になることが分かった。SICPの第4章も同様な方法で、継続の切り替え、amb の実装を行っている。そこでは、関数のみならず if式、quote式、複文...と、ありとあらゆる式を λパッケージにして、継続の切り替えを実施している。
次は、第4章のamb評価器の実装を詳しく調べよう。
[1]
第4章で使う λ パッケージは、上のものに比べて、さらに3つの工夫が追加されている。
第1の工夫は、引数で取る継続が2つになっていることである。
(λ (s f) (a ...)
(s ...) or (f ...)
)
図にするとこんな感じ。
もちろん s は、成功継続で f は失敗継続である。 なんらかの条件によって、接続先を切り替えることができるようになっている。 ただし、この切り替え機能を使っているのは amb式 だけである。 他の式は、上のλパッケージと同じく1つの継続(成功継続)しか使っていない。
第2の工夫は、失敗継続を伝播することである。
失敗継続は、上記のようにamb以外の式では実行されることはないが、成功継続を通じて継続先に伝播される。
失敗継続を、使いもせずひたすら伝播させるだけ、というあまり意味のない工夫のようにも見えるが、amb式のバックトラック機能は、上の継続の切り替えと、この失敗継続の伝播を利用して実装される。
第3の工夫は、(a...)の実行結果を成功継続sで使えるようにすることである。
これを実現するために、成功継続s に、(a...)の結果を引数で渡すことにしている。 この工夫が役にたつのは、合成関数を λパッケージにするときである。 下位の関数の結果を上位の関数に引き渡すのに、この工夫を使っている。
[2]
あらゆる式をλパッケージに変換する。というのを実装しないといけないのだが、 うまい具合に、4.1.7節で作った評価器が、あらゆる式をλ式化するものであった。 これは少しの修正でλパッケージの実装として使える。
なお、子Schemeの式を親Schemeのλ式でパッケージするのであって、 子Schemeの式を子Schemeのλでパッケージするというのではない。
[3]
構文ごとにのλパッケージ化の詳細が異なる。 引数で貰った成功継続をそのまま実行したり、処理を変えてから実行したり。 失敗継続もそのまま伝播したり、処理を追加して伝播したり。
各構文のλパッケージの様子を確認しよう。 図中の四角で囲っているのはλパッケージで、 s は成功継続である。
analyze-self-evaluation
即値式
analyze-quoted
quote式
analyze-variable
変数式
analyze-lambda
λ式
図には出てこないが、解析されたλ式の本文は、下のanalyze-sequence を使ってλパッケージになっている。
analyze-if
if式
analyze-sequence
複文
例として4つの文の場合を考える。
analyze-definition
define式
analyze-assignment
set!式
失敗継続に、旧値を復元する処理を追加して伝播させる。
analyze-application
関数式
get-args
引数評価
関数の各引数を評価して引数リストを作成する。 analyze-application の補助関数。
引数2個の場合の図
λパッケージを作る関数ではないが、 各引数がλパッケージになっているため、評価がλパッケージ用になっている。