(没)→書き直し
継続を使ったambの実装
この章は難しい。難しい理由を考えてみた。
- 継続の説明がない。
この章は継続を利用してamb を実装することを説明しているだけであって、継続自体の説明はない。 - 継続を実装しているが、どうやって実装しているかの説明がない。
この章では、ambの実装に先立って、継続を実装している。しかしその実装方法とか実装方針とか実装の肝についての説明がない。いつのまにかうまいこと実装されてしまっている。 - ついでに言うと、継続をうまいこと実装する際に call/cc を使ったり、スタックを弄ったりはしていない。メタ関数のみで実装している。
- さらに言うと、amb評価器を実装するのに継続を使う必然性はない。forループに置き換えるだけでも十分実装できる。教育のためにわざわざ難しい継続を使っているのであろう。
なので、本文に入る前に①継続とは何か、および②継続の実装方針について自力で理解しとかないといけない。
【1】
①継続とは何か。
ある式の継続は、その式の次に実行する式のことである。
合成関数を考える。
f(g(h(0)))
例えばh(0)=1とすると、式 h(0) の継続とは
f(g(1))
のことである。h(0) に続いて実行されるのは、f(g(1)) だからである。
純粋な関数型言語なら、すべての処理は結局、合成関数として表現される。従って継続は明確に定義できる。つまり合成関数の残りが継続である。
純粋でない関数型言語なら、すこしややこしい。
これが、C言語ならもっと面倒くさい。
例えば、複文であるが、
a(0) b(0) c(0)
これを合成関数で表現すると
A(x):=a(0) B(x):=b(0) C(x):=c(0) C(B(A(x)) (記号 := は関数の定義という意味)
となる。この場合、A(x)の継続がC(B(x))になっている。これは複文において、a(0)のあとで、b(0) と c(0) が実行されることに整合している。
【2】
つぎに②継続の実装を考える。
と、その前に、誰が継続を実装するのか？を確認しておこう。
継続を実装する主体は、親言語である。
例えば、子言語で書かれたプログラム
a(0) b(0) c(0)
これを順番どおりに実行する責任を負っているのは親言語である。
子言語というのは、amb評価器のことで、親言語というのはamb評価器を実装しているSchemeのことである。
では、継続の実装の方針を考えよう。
1つ目は、子言語で書かれたプログラムを、単純に頭から順番に実行するだけという実装。第4章の前半の評価器はそのようにしている。この場合、継続を取り出したり、操作したりはできない。頭から終わりまで、1方向に流れるだけの継続である。
2つ目は、子言語のプログラムを一旦すべて親言語の中で合成関数に置き換える。という実装。これがamb評価器の方針である。
合成関数化すると、継続を操作することができる。つまりある時点の継続とは合成関数の残りであり、合成関数の残りというのは単なる関数だから、これを取り出して変数に代入したり、他の関数の引数にしたりすることは簡単である。
次にプログラム全体を合成関数に置き換える方法を考えよう。
繰り返しになるが、また複文を合成関数化してみよう。
a(0) b(0) c(0)
このままでは合成関数にするもなにもどうしようもない。そこで、各式を関数でラッピングすることにしよう。
①「a(0) という式」を「「a(0)という式」を実行する関数A(x)」→ A(x):=a(0) という風にラッピングする。 ②「b(0) という式」を「「b(0)という式」を実行する関数B(x)」→ B(x):=b(0) という風にラッピングする。 ③「c(0) という式」を「「c(0)という式」を実行する関数C(x)」→ C(x):=c(0) という風にラッピングする。
こうすると、複文は、合成関数
C(B(A(x)))
と表現することができる。xに適当な値を入れて実行する。例えば a(0) = b(0) = c(0) = 1 として
C(B(A(0))) = C(B(a(0))) ・・・①より。ここでa(0)が実行される。 = C(B(1)) = C(b(0)) ・・・ ②より。ここでb(0)が実行される。 = C(1) = c(0) ・・・ ③より。ここでc(0)が実行される。 = 1
複文を頭から実行するのと同じように、a(0), b(0), c(0) が順番に実行されることが確認できる。
要するに、子言語のプログラムの各式を関数でラッピングすれば合成関数化できるということである。
【3】
ここで、継続を取り出して、他の関数に渡すというのをやってみよう。
まずA(x)の継続を取り出してみる。
④ A(x)の継続 s1(x) := C(B(x))
このように継続というのは、単なる関数である。
この継続を引数として受け取る関数を作ってみよう。例えば
⑤ L(s) := s(a(0))
こんな感じ。L は関数を引数にとるのでメタ関数である。
メタ関数Lに④の継続を与えて実行してみよう。
L(s1) = s1(a(0)) ・・・ ⑤より。ここでa(0) が実行される。 = s1(1) = C(B(1)) ・・・④より。 = C(b(0)) ・・・ ②より。ここでb(0)が実行される。 = C(1) = c(0) ・・・ ③より。ここでc(0)が実行される。 = 1
驚いたことに、この L(s1) は、先の C(B(A(0))) とまったく同じようにa(0), b(0), c(0)を順番に実行している。
これを継続渡しという。
これなら、L(s)をA(x)の代わりに使えるのではないか。合成関数化に継続渡しが使えそうではないか。という考えが出てくる。
試してみよう。
まず、a(0)、b(0)、c(0) を継続渡しの関数でラッピングする。
⑥ a(0) の継続渡しの関数ラッピング L(s) := s(a(0)) ⑦ b(0) の継続渡しの関数ラッピング M(s) := s(b(0)) ⑧ c(0) の継続渡しの関数ラッピング N(s) := s(c(0))
次に、M(s) と N(s) の合成関数 O(s) を作る。
⑨ s1(x, t) := N(t) ⑩ O(s) := M(s1(x,s))
こんな感じになる。ここで⑨の左辺の s1 の引数 t は t(x) という関数である。⑩の右辺の s1(x,s) は、s1 の引数 t に O(s) の引数 s を与えたものである。だから⑩の右辺の s はすでに自由変数ではない。s1(x, s) は単に x の関数である。
さらに、O(s) と L(s) の合成関数 P(s) を作る。O(s) のときと同様に作ればよい。
⑪ s2(x, t) := O(t) ⑫ P(s) := L(s2(x, s)) ← L、M、N の合成関数
これで、L、M、Nの合成関数ができた。
では、実際に s に適当な関数
⑬ s0(x) := x
を与えて、P(s) を実行してみよう。
P(s0) = L(s2(x, s0)) ・・・⑫より = s2(a(0), s0)) ・・・⑥より。ここで a(0) 実行 = s2(1, s0) = O(s0) ･･･⑪より = M(s1(x, s0)) ・・・⑩より = s1(b(0), s0)) ・・・⑦より。ここで b(0) 実行 = s1(1, s0) = N(s0) ・・・⑨より = s0(c(0)) ・・・⑧より。ここで c(0) 実行 = s0(1) = 1 ・・・⑬より
うまく、a(0)、b(0)、c(0) が順番に実行されていることが確認できる。
注意点は、
× L(s2(x, s0)) = L(O(s0)) ・・・間違った変形
と変形しないことである。s2(x, s0) のx はまだ自由変数だから実行してO(s0)になることはないのである。s2(x, t) が x について定数関数になっているため紛らわしくなっている。 また、間違った変形の右辺をみると、Lの引数が値O(s0)になっている。Lはメタ関数だから引数は関数でないといけない。というように引数の整合性からも変形の間違いに気付くことができる。
ということで、継続渡しを利用しても、複文を合成関数化できることが分かった。
合成関数化の方式として、A(x), B(x), C(x) とL(s), M(s), N(s)の２つの方法を得た。
どっちでもいいと思うが、本文では、継続を利用するL,M,Nのやり方を採用している。
以上、複文の例を見たが、ラムダ式、代入、if, amb ... amb評価器で必要なすべての式を継続渡しで合成関数化しないといけない。