Prolog でメモ化
ちょっと前に，「メモ化」なるものがそこかしこで話題になっていました．
んで，すっかり乗り遅れてますが，Prolog でちょっとやってみようかと．
でもでも，メモ化はともかく不動点の方は脳みそがとけちゃうので無理っぽい．何言ってるか分からないんだもの．(;_;)
ともあれ (JW)，ある述語をメモ化する述語は結構簡単に書けます．
memoize(P, M) :- P =.. [_ | Arg], P2 =.. [M | Arg], asserta((P2 :- P, asserta(P2))).
これは述語 P をメモ化した述語を M という名前で作成します．
例．
14 ?- memoize(fib(N, F), mfib). N = _G338 F = _G339 Yes 15 ?- mfib(10, F). F = 89 Yes 16 ?- trace. Yes [trace] 16 ?- mfib(10, F). Call: (7) mfib(10, _G442) ? creep Exit: (7) mfib(10, 89) ? creep F = 89 Yes
ここでは fib/2 をメモ化した述語を mfib という名前で作成しています．ちなみに 3 引数の述語でも 4 引数の述語でもメモ化できます．
そして 2 度目の呼び出しをトレースしていますが，再帰呼び出しなどすることなく，一撃で結果を得ています．
これは，mfib(10, 89) という事実が Prolog データベースに登録されているから．
Prolog データベースの乱用はどうかと思うのだけど，これは有効な使い方という気がするから不思議．(^^;
しかし，このメモ化述語には欠陥があります．
というのも，上でメモ化している fib/3 はこんな定義なのですが，
fib(0, 1). fib(1, 1). fib(N, F) :- N1 is N - 1, N2 is N - 2, fib(N1, F1), fib(N2, F2), F is F1 + F2.
メモ化されたのはあくまでも mfib/2 であって fib/2 ではないので，この fib/2 の再帰呼び出しはメモ化の恩恵を受けることができないのです．
この間盛り上がっていた方面はここから不動点関数とやらに向かっていきましたが，そういう素養のないおいらは別の手段でこれに対処するのだ．
要するに，メモ化した述語を別途作成するのではなく，その述語自身の新しい節として Prolog データベースに登録しちゃえばいいんじゃないかと．
つまり，Prolog データベースに登録されている節は最初こうなっているわけですが．．．
fib(0, 1).fib(1, 1).fib(N, F).
これをメモ化すると
fib(N, F).← これはメモ化する節．fib(0, 1).fib(1, 1).fib(N, F).← これは値を求める節．
となって，例えば fib(2, F). を求めた直後には
fib(2, 2).← 登録された節fib(N, F).← これはメモ化する節．fib(0, 1).fib(1, 1).fib(N, F).← これは値を求める節．
という具合に，新たな値が求められるたびに，その値を事実として持つ節を上に追加していけばいいはず．
そうすると，値を計算する節が再帰呼び出しをしてもちゃんとメモされた節が使われます．
問題は，メモ化する節が値を求める節を呼び出す方法．
普通に再帰呼び出しすると，また自分に来ちゃいます．
といってバックトラックすると，計算された結果を得ることができません．
うーみゅ．．．
基本はこの二つの組み合わせしかないはず．
つまり，値をメモするために再帰呼び出しして，そこではバックトラックして値を計算する述語に向かう．
そのためには，メモ化する節はバックトラックすべきかどうかを判断できなければならないわけで．．．
「Prolog ユーティリティライブラリ」ならここで Prolog データベースを使うに違いない！！
し・か・し
おいらにはもっとモダンになった Prolog 処理系があるのだ．
実は先の乱数で使った when/2 なんですが，これって内部では変数のアトリビュートというものを使います．
今時の Prolog の変数というのは，変数自身のインスタンス変数としてマップ (Java の Map) を持っているようなものなのです．
つ・ま・り
変数にアトリビュートがあるかどうかをチェックすれば，再帰呼び出しかどうかを判断できるはず．
結局副作用というか論理プログラミングの範疇から外れるわけですが．心より恥じる．
ともあれ (JW)，こうなりました．
memoize(P) :- asserta((P :- (mark(P), P, asserta(P)))). mark(P) :- P =.. L, get_var(L, X), \+get_attr(X, memoize, _), put_attr(X, memoize, memoize). get_var([X | _], X) :- var(X), !. get_var([_ | L], X) :- get_var(L, X). attr_unify_hook(memoize, _).
mark/1 が再帰呼び出しかどうかを示すマークを変数に付けます．
既にマークが付いていたら失敗します．つまりバックトラックを引き起こします．
get_var は述語の引数から変数を探します．変数がなければ失敗します．つまりバックトラックを引き起こします．
これがあるので，fib(1, 5) みたいな呼び出しをした場合にはメモ化しようとしないで値を計算しようとします．もし間違った値をメモ化しちゃダメだからね．
ともあれ (JW)，使ってみます．
3 ?- memoize(fib(N, F)). N = _G296 F = _G297 Yes 4 ?- fib(10, F). F = 89 Yes 5 ?- trace. Yes [trace] 5 ?- fib(11, F). Call: (7) fib(11, _G430) ? creep Call: (8) mark(fib(11, _G430)) ? creep Call: (9) fib(11, _G430)=.._L203 ? creep Exit: (9) fib(11, _G430)=..[fib, 11, _G430] ? creep Call: (9) get_var([fib, 11, _G430], _L204) ? creep Call: (10) var(fib) ? creep Fail: (10) var(fib) ? creep Redo: (9) get_var([fib, 11, _G430], _L204) ? creep Call: (10) get_var([11, _G430], _L204) ? creep Call: (11) var(11) ? creep Fail: (11) var(11) ? creep Redo: (10) get_var([11, _G430], _L204) ? creep Call: (11) get_var([_G430], _L204) ? creep Call: (12) var(_G430) ? creep Exit: (12) var(_G430) ? creep Exit: (11) get_var([_G430], _G430) ? creep Exit: (10) get_var([11, _G430], _G430) ? creep Exit: (9) get_var([fib, 11, _G430], _G430) ? creep Call: (9) get_attr(_G430, memoize, _L230) ? creep Fail: (9) get_attr(_G430, memoize, _L230) ? creep Call: (9) put_attr(_G430, memoize, memoize) ? creep Exit: (9) put_attr(_G430{memoize = ...}, memoize, memoize) ? creep Exit: (8) mark(fib(11, _G430{memoize = ...})) ? creep Call: (8) fib(11, _G430{memoize = ...}) ? creep Call: (9) mark(fib(11, _G430{memoize = ...})) ? creep Call: (10) fib(11, _G430{memoize = ...})=.._L220 ? creep Exit: (10) fib(11, _G430{memoize = ...})=..[fib, 11, _G430{memoize = ...}] ? creep Call: (10) get_var([fib, 11, _G430{memoize = ...}], _L221) ? creep Call: (11) var(fib) ? creep Fail: (11) var(fib) ? creep Redo: (10) get_var([fib, 11, _G430{memoize = ...}], _L221) ? creep Call: (11) get_var([11, _G430{memoize = ...}], _L221) ? creep Call: (12) var(11) ? creep Fail: (12) var(11) ? creep Redo: (11) get_var([11, _G430{memoize = ...}], _L221) ? creep Call: (12) get_var([_G430{memoize = ...}], _L221) ? creep Call: (13) var(_G430{memoize = ...}) ? creep Exit: (13) var(_G430{memoize = ...}) ? creep Exit: (12) get_var([_G430{memoize = ...}], _G430{memoize = ...}) ? creep Exit: (11) get_var([11, _G430{memoize = ...}], _G430{memoize = ...}) ? creep Exit: (10) get_var([fib, 11, _G430{memoize = ...}], _G430{memoize = ...}) ? creep Call: (10) get_attr(_G430{memoize = ...}, memoize, _L247) ? creep Exit: (10) get_attr(_G430{memoize = ...}, memoize, memoize) ? creep Fail: (9) mark(fib(11, _G430{memoize = ...})) ? creep Redo: (8) fib(11, _G430{memoize = ...}) ? creep ^ Call: (9) _L204 is 11-1 ? creep ^ Exit: (9) 10 is 11-1 ? creep ^ Call: (9) _L205 is 11-2 ? creep ^ Exit: (9) 9 is 11-2 ? creep Call: (9) fib(10, _L206) ? creep Exit: (9) fib(10, 89) ? creep Call: (9) fib(9, _L207) ? creep Exit: (9) fib(9, 55) ? creep ^ Call: (9) _G430{memoize = ...}is 89+55 ? creep wakeup(att(memoize, memoize, ), 144, ) Saved wakeup to 024F8418 ^ Exit: (9) 144 is 89+55 ? creep Restore wakeup from 024F8418 wakeup(att(memoize, memoize, ), 144, ) Call: (13) attr_unify_hook(memoize, 144) ? creep Exit: (13) attr_unify_hook(memoize, 144) ? creep ^ Exit: (9) 144 is 89+55 ? creep Exit: (8) fib(11, 144) ? creep ^ Call: (8) asserta(fib(11, 144)) ? creep ^ Exit: (8) asserta(fib(11, 144)) ? creep Exit: (7) fib(11, 144) ? creep F = 144 Yes
ちょっとトレースが長くて見にくいですが，青字になっているところが再帰呼び出しされたメモ化する節で最後は失敗してます．
赤字になっているところが値を計算している節で，きちんと結果を求めています．
その中で，fib(10, F). と fib(9, F). の呼び出しが計算をすることなく求まっていることが分かります．
つまり，元の述語 fib/2 に手を加えることなくメモ化すると同時に，それ自身もメモ化された述語を利用することができるようになりました．
「手を加えることなく」というのはソースにメモ化の対応をする必要がないという意味で，Prolog データベース的には思い切り，しかも直接手を加えていますけど．
そんなわけで (どんなわけで？)，あんまり格好良くないけど，まぁいいや．
そのうち不動点関数とやらが理解できたらそれにも挑戦したいと思います．
いつの日か．．．
