SCBM-Prolog：天啓――なんだ、簡単じゃないか

この数日、税務会計の仕事に追われています。

日本では中間決算が集中する時期です。日本の税法や会計は極めて緻密です。「そこまでやるのか？」と思うくらいです。

さらに追い打ちをかけるように、解釈通達、判例、実務指針……。

これを本当に人間が正確に実施できるのだろうか？

そんなことを考えながら仕事をしていたところ、突然ひらめきました。

先日考えていたSCBM-Prologの改良方法は、無意味に複雑だったのではないか？

もっと簡単にできそうです。

いつもの例

SCBM-Prologのデバッグで何度も使っている例です。

select1(X,[X|Xs],Xs).
select1(X,[Y|Ys],[Y|Zs]) :-
    select1(X,Ys,Zs).

perm1([],[]).
perm1(Xs,[X|Ys]) :-
    select1(X,Xs,Zs),
    perm1(Zs,Ys).

問題になるのは、select1 がバックトラックした場合です。

たとえば、

perm1(Xs,[X|Ys]) :-
    select1(X,Xs,Zs),
    perm1(Zs,Ys).

では、select1 が成功した後に

perm1(Zs,Ys)

を実行しなければなりません。

SCBMではこれを「成功継続」として保持しています。

ところが select1 がバックトラックして別解を求めた場合、その後に続く perm1 に対して、どの変数ポインタを復元すればよいのかが問題になっていました。

ここ数日、この問題についてずっと考えていました。

しかし、そもそもの発想が間違っていたのかもしれません。

SLDではどうなっているか

通常のSLD resolutionでは証明木があります。

select1 がバックトラックして別解を探しても、その後に証明すべきゴールそのものが別物になるわけではありません。

概念的には、

select1(X,Xs,Zs)
        |
        | success
        v
perm1(Zs,Ys)

です。

select1 が別の解を返しても、その後に実行するものは相変わらず

perm1(Zs,Ys)

です。

ここで気がつきました。

なぜSCBMでは、バックトラックするたびに成功継続を作り直そうとしているのだろう？

解決案

バックトラックした場合には、次の述語への成功継続を新たに生成しないことにします。

代わりに、

バックトラックする前に存在していた成功継続をそのまま再利用します。

実はSCBMでは、失敗継続を生成するときに、その時点の成功継続ポインタ np を保存しています。

つまり失敗継続は、もともとの成功継続がどこにあるのかをすでに知っています。

概念的には次のようになります。

最初の実行

        perm1
          |
          | success生成
          v
   +------------------+
   | success A        |
   | -> perm1(Zs,Ys)  |
   +------------------+
          ^
          |
        np
          |
       select1
          |
          | failure continuation生成
          v
   +------------------+
   | failure B        |
   | saved np = A     |
   +------------------+

その後 select1 が失敗してバックトラックするとします。

これまでは、

backtrack
    |
    v
select1を再実行
    |
    v
新しいsuccessを生成
    |
    v
正しい変数ポインタを復元？
    |
    v
perm1

という方向で考えていました。

この「正しい変数ポインタをどうやって復元するのか？」が非常に厄介でした。

しかし、新しい方法ではこうします。

backtrack
    |
    v
select1を再実行
    |
    v
別解を得る
    |
    v
保存してあったnpを復元
    |
    v
元のsuccess A
    |
    v
perm1(Zs,Ys)

つまり、

成功継続を作り直さない。

これだけです。

なぜこれでよいのか

成功継続は通常の実行ではスタックに上積みされていきます。

バックトラックしない限り、以前に生成された成功継続は残っています。

そして重要なのは、元の成功継続が正しい呼び出し側の環境で生成されていることです。

もう一度、

perm1(Xs,[X|Ys]) :-
    select1(X,Xs,Zs),
    perm1(Zs,Ys).

を考えます。

後半の

perm1(Zs,Ys)

への成功継続は、最初の perm1 の節を実行している時点で生成されています。

したがって、そこに保存されている変数ポインタは、本来の perm1 の環境のものです。

その後 select1 が内部でどれだけ深く再帰したとしても、その環境を改めて構築する必要はありません。

すでに正しいものが残っているからです。

成功継続の意味を考え直す

これまで私は成功継続を、

成功したときに、次に実行する処理

として考えていました。

もちろん、それ自体は間違いではありません。

しかし、もう少し違う見方ができそうです。

現在の述語へ入る前に、すでに決まっていた「残りの計算」

です。

これはSLDにおける「残余ゴール」とよく似ています。

select1 がバックトラックすると、select1 の解は変わります。

しかし、

perm1(Zs,Ys)

を次に実行するという事実は変わりません。

だったら、なぜそれを作り直す必要があるのでしょう？

これまで考えていた複雑な仕組み

ここ数日は、バックトラック時に正しい環境を復元するために、いろいろな方法を考えていました。

たとえば、

述語のクロージャを抜けたか判定
        ↓
nestを調べる
        ↓
successを調べる
        ↓
gotoポインタを比較
        ↓
親に相当する失敗継続を探す
        ↓
そこから変数ポインタを復元

といった方法です。

一つ一つには理由があります。

しかし、どうにも複雑です。

今回の方法なら、

failure continuation
        |
        | saved np
        v
original success continuation
        |
        v
remaining computation

これだけです。

失敗継続には、すでに np が保存されています。

元の成功継続も残っています。

ならば、それを使えばいい。

KISS

私はプログラムを書くとき、KISSをとても大切にしています。

単にコードが短ければよいという意味ではありません。

必要な複雑さは当然あります。

しかし、

「なぜこの機構が必要なのか？」

を説明できない複雑さは、できるだけ排除したい。

今回の問題も、複雑な仕組みを追加して解決するのではなく、

そもそも、その問題を解く必要があるのか？

と考え直したことで、ずっと単純な構造が見えてきました。

バックトラックしても残余ゴールは変わらない。

だから元の成功継続を再利用する。

それだけです。

天啓

ニコラ・テスラは、素晴らしいアイデアについて、自分で考え出したというより、どこか外から突然もたらされたように感じることがあった、という趣旨のことを語ったといわれています。

今回、少しだけその気持ちが分かったような気がしました。

何日も、

「正しい変数ポインタをどうやって復元する？」

と考え続けていました。

ところが税務会計の仕事をしている最中に、突然、

「待てよ。元の成功継続が残っているじゃないか」

と思ったのです。

正しい環境を復元する方法を考えるのではない。

正しい環境は最初からそこにある。

だったら、それを使えばいい。

まだ実装して検証する必要はあります。

まず select1/3 の全別解を確認し、次に

perm1([1,2,3],X).

で6個の順列が正しく生成されるかを確認します。

さらに再帰が深くなるケースについてもテストする必要があります。

しかし、原理としてはこれまで考えた方法よりずっと自然です。

難しい問題に出会うと、つい難しい解決方法を考えてしまいます。

でも、ときには問題そのものを疑った方がよい。

「なぜ復元する？　元のものがまだそこにあるじゃないか」

なんだ、簡単じゃないか。

さて、実験です。