以前、Pythonでは継続を一応取り扱う事が出来る、と言う話を書いた。Pythonでも計算途中の「状態」を切り出す事自体は可能である、と。
でもそんなモン取り出したから、っつってどーすんだよ、と言う話がある。全くその通り。
そこで、ここでは、「継続」を使った、不完全ながらも面白いモノを紹介しようと思う。バックトラッキングと非決定計算、である。
まずambと言われるモノを実装する。
正直言って、ambってのが何の略称なんだか知らない。これが英語サイトを探し回っても見つからないのだ。
可能な候補としてはAdvanced Memory Bufferの略だ、ってのがある。まぁ、ハードウェアの用語らしいんだけど、それをもじったのだろうか。確かにメモリの使い方の高度な応用と言えばその通りなのだ。
しかし与太話はそれくらいにしておいて。
良くある継続を使ったambの実装はPythonで書くと次のようになる。
fail = lambda : False
def amb(choices, cc):
global fail
def foo():
global fail
nonlocal fail0
fail = fail0
amb(choices[1:], cc)
if choices == []:
fail()
else:
fail0 = fail
fail = foo
cc(choices[0])
うげ。非決定計算とか。ややこしいコードじゃないか、とか思うかもしれない。
確かにぱっと見そう感じるかもしんない。僕も最初はそうだった。
しかし、本質的にはこのコードは単なる再帰関数なだけ、である。
def bar(ls):
if ls == []:
return False
else:
print(ls[0])
bar(ls[1:])
再帰にちょっとでも慣れてれば上のbarのコードの意味はすぐ分かるだろう。単純にリストの要素を先頭から一個づつ出力するだけ、である。そしてその前に書いたambのコードも本質的なルーティンはこの再帰関数barと全く同じなのだ。
違う点は以下の通りである。
- 継続を利用している。
- 大域変数falseを用意している。
- 大域変数falseをコード内でローカル変数false0に退避させている。
- 大域変数falseには新しく定義したローカル関数fooを代入している。
- fooはfalse0の内容をfalseに戻した後、ambを再帰呼び出しするだけである。
- しかし大域変数falseには関数名fooを代入してるだけで、foo自体は実行されていない。つまり、fooは遅延評価の役目をしてて、この時点ではfooに拠る再帰は行われていないのだ。
1番に付いては取り敢えず後回しにしておこう。2番から見ていく。
結局、2〜6で何が行われているのか。
ambは本質的には再帰関数だ、と言った。しかしポイントとしては
- 再帰関数だが再帰を「する」のではなく、未評価のままで大域変数failに束縛してる。
- 同時に、その再帰関数が実行される前のfailの値も未評価値として大域変数failに束縛する。
と言う事である。結果、failの値をある意味再帰関数の残りで肥大化させてる、と言うのがambの仕組みである。
で残り1番。継続、とはambが得た情報をambの状態と共に(※1)別の関数に渡す仕組みである。こういうのを継続渡しとかメッセージ送信(※2)と呼ぶ。ambは継続渡し/メッセージ送信を前提に書かれた関数となっている。
さて、実際にambを実行するとどうなるのか見てみよう。単純な例だ。
>>> amb([1, 2, 3], print)
1
ambにリスト[1, 2, 3]を与え、それらの継続をprint関数に手渡す。
コードを見てみれば明らかだろうが、結果1を返すだけ、である。何ともつまらん結果だ。
ところが、この状態で、大域変数failには「実行されるべき残りの再帰部分」がすべて詰め込まれている。ちょっと見てみよう。
>>> fail
<function amb.<locals>.foo at 0x7f8f5e50c790>
字面通り解釈すると、amb関数のローカル関数fooが詰め込まれている。大域変数はいつの間にか複雑な関数になっていたのだ。
と言う事はfailは実行可能だ、と言う事である。
>>> fail()
2
>>> fail()
3
>>> fail()
>>>
これもambのコードを見れば当たり前だろう(※3)。いずれにせよリストの先頭を順次返していく、ってのは予想の範疇ではある。あまりにつまらないと言えばつまらない。
が、非常に重要な示唆が4つ程ある。
- 非決定性計算、と言いながら実は決定論的に、つまりフツーに計算している。名前に反して特にランダム性があるわけではない。
- ambが呼ばれた時点で与えられたリストchoicesに関しては、コードに従って実は終端までキチンと計算されている。
- ただし、2.で言う「計算」と言うのは遅延評価前提で、リストchoicesの[1:]の各部分に関して最後まで計算してるわけではない。言わば計算する為の「条件」を表現しているだけ、である。
- 大域変数には結果、「未計算部分」あるいは「計算をする為の条件」の経路が詰め込まれている。
良く、非決定性計算に於いて、「未来を予知するような計算が出来る」とか書かれているが、んな事あるわけがないのだ。実際は、それら計算「過程」が隠されているだけ、と言った方が正しい。あるいは遅延評価的に計算条件だけは引数の全てに於いて行われている。それをユーザーに見せないようにしてる、って言うのがこの「非決定性計算」のキモであって、別にプログラム自体が何かを予言してる、と言うようなオカルト染みた行為があるわけではない。
もう一度言うが、ambは本質的には単なる再帰関数なんだけど、その再帰部分を「計算を止めて」「大域変数に保存してる」と言うメカニズムがあるだけ、なのである。
さて、上のパフォーマンスは例としては簡単なんだけど、あまりにも面白くない。
かつ、これだけだと「何の為に大域変数failに前回のfailと計算過程を保存してるのか」サッパリ分からんだろう。
そこで次のような問題を考える。
数値、1、 2、 3、 4、 5、 6、 7、 8、 9、 10の中で三平方の定理を満たす組を探せ
まずは数値1〜10までのリストを作成する。
>>> choices = [i for i in range(1, 11)]
>>> choices
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
次に、ambを用いて、三平方の定理を満たす数値を探すコードを書くと結果は次のようになる。
>>> amb(choices, lambda i :
amb(choices, lambda j :
amb(choices, lambda k:
print(i, j, k) if i**2 + j**2 == k**2 else fail())))
3 4 5
ambにリストchoicesを与えて、継続受け渡しで変数i、j、kの間の関係を記述する。三平方の定理を満たす組を発見出来たらそれをプリントするが、そうじゃない場合は大域変数failを関数として呼び出す。
そうすると、上に見た通り、3、4、5と言う組が出力される。
確かに皆が知ってる通り、これは三平方の定理を満たす組である。
ただ、これだけだろうか？と言うと違う。これはambがfailに保存した経路から導かれる結果の一つでしかないのだ。
実はこの後、failをまたもや連続して呼び出すと、別の組を返してくるのである。
>>> fail()
4 3 5
>>> fail()
6 8 10
>>> fail()
8 6 10
これは凄くないだろうか？ぶっちゃけ、再帰関数をちょっと弄って作った関数ambがこういう機能を持っているのだ。
これをバックトラッキング(※3)と呼ぶ。秘訣は「前回のfailの値も保存している」事である。従って、fail、つまり計算の失敗をambに報告すると、既に計算された経路のウチから適した組み合わせを探し出してくるわけだ。
そしてここでPythonの限界に突き当たる。与えるリストを大きくしたりするとクソみたいなエラー報告を目にする事となる。
RecursionError: maximum recursion depth exceeded in comparison
再帰の限界値に達するわけだな。末尾再帰最適化を持たないPythonの限界にここでぶち当たるわけだ。
このambさえ作れれば、100だろうが10000だろうが、三平方の定理を満たす整数を探すコードを書くのは簡単だし、また、パズルを解くようなプログラムも比較的簡単に書ける。コードを書く事が簡単なだけ、ではなく、バックトラッキングの仕組みを一々明示的に書く必要がなくなるから、だ。
ただ、Battery Includedと謳われるPythonの最大の欠点のうちの一つが、この末尾再帰最適化、と言う素敵な機能を欠いてる、と言う事だ。従って、Pythonと継続を使った非決定性プログラミングの実験は唐突にここで敢え無く終了、となるわけである(※5)。
※1: つまり、これらは言い換えると「ambにおける計算途中の情報」と言う事になり、それを継続と呼ぶわけだ。フツーに考えると変数の状態、関数の計算過程における状態、等をどっかに保存しておいて、逐一参照せねばならないのに、継続はそれらを纏めて大雑把に管理してる、と言う事である。
※2: 元々のSmalltalkによるオブジェクト指向のアイディア、と言うのは実は理論的にはこれに支えられている。
※3: この辺の動作の見た目はPythonのジェネレータ/イテレータに近い。
※4: このバックトラッキングを基盤としてるのが、古のAI用言語、Prologである。
※5: 何故にSchemeのような実用性皆無な言語が言語研究者に愛されてるのか、と言う理由がここにある。Schemeは小さくて何も出来ないが、ベースがタフなのだ。と言うか理論的にRobustであるように設計されてる。Pythonは実用性に重きを置いてるがそれがない、のだ。
Schemeのこの強健性はすべての言語の中で、ANSI Common Lispを相手にしても群を抜いてると思う。
