Python で作る Prolog 処理系

2006.6.6 - 2006.7.14 (鈴)

1. Prolog とは

フランス語の programmation en logique (英語の programming in logic) の略。 1972 年に Marseilles (マルセイユ) で作られたプログラミング言語。 １階述語論理をもとに事実とルールから一種の自動推論を行うことから， 1980 年代に人工知能実現のための基礎技術として日本で脚光を浴びた。

「アダムは男だ」という命題は， 述語「男だ」を１引数の man で表すと man(アダム) と記述できる。 述語論理は命題に∀,∃の限定記号により変数を導入した論理である (例えば ∃X man(X) は，man を満たす X が存在することを意味する)。 １階述語論理は変数の値として命題や述語を許さないものである。

現在，定番といえる処理系は，自由なソフトウェアとして公開されている SWI-Prolog といえるだろう。Unix 類と Windows (ネイティブおよび Cygwin) に移植されている。 例えば，下記のテキストファイル test.pl を用意して， 

man(adam).
parent(adam, cain).
parent(adam, abel).

father(P, C) :- man(P), parent(P, C).

次のように実行することができる (下記は Cygwin での実行例。 ただし便宜上キー入力を水色で示す)。 

$ pl -s test.pl
% test.pl compiled 0.00 sec, 2,684 bytes
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- father(X, Y).

X = adam
Y = cain ;

X = adam
Y = abel ;

No
?-

man(adam). は「adam は男だ」という事実， parent(adam, cain). は「adam は cain の親だ」という事実， father(P, C) :- man(P), parent(P, C). は， 「なんであれ P, C について father(P, C) が成り立つためには， man(P) かつ parent(P, C) が成り立てばよい」，つまり 「誰か P が男であって，P が誰か C の親ならば，P は C の父だ」， 要するに 「男親ならば父だ」というルールだと言える。

*1 正確にいえば， 関数が引数として関数をとるか，結果として関数を返すならば， その関数は高階 (higher-order) である。 この定義を再帰的に適用すると，Ling が舌をかみそうになった説明になる。

2. クラス定義で構成する Prolog 構文

Python については Life with Cygwin の該当章などを参照されたい。

ここで作る Prolog 処理系では，Prolog 構文の終端記号のうち， 数や文字列などの定数には Python の定数をそのまま使う。 

>>> 1
1
>>> "adam"
adam

Prolog の変数と述語には Python の変数を使う。 ただし，それらの Python 変数は それぞれ Var クラス，Pred クラスのインスタンスとする。 

>>> man = Pred("man")
>>> X = Var("X")

変数と述語は，Lisp でいうシンボルと同じく唯一性が要求される。 つまり，同一の名前が同一の実体を指さなければならない。 ここでは，それを Python 変数の唯一性に肩代わりさせる。 したがって，Var インスタンスや Pred インスタンス自体に名前は必要ない。 しかし，表示の便宜のため，コンストラクタの引数として与えることにする。

述語と引数からなる述語項は，_Goal クラスのインスタンスで表す。 このインスタンスは， Pred クラスの関数呼び出し演算子 __call__ によって構成する。 

>>> man("adam")
man("adam")
>>> isinstance(man("adam"), _Goal)
True

Prolog の節 (clause) は， _Goal クラスの左シフト演算子 __lshift__ で表現する。 

>>> man("adam") << ()
>>> father, parent, Y = Pred("father"), Pred("parent"), Var("Y")
>>> father(X, Y) << (man(X), parent(X, Y))

普通の表記方法でいう
  man(adam).
は
  man("adam") << ()
と表される。
  father(X, Y) :- man(X), parent(X, Y).
は
  father(X, Y) << (man(X), parent(X, Y))
と表される。

左シフト演算子は述語 (Pred インスタンス) に節を定義として追加する。 節は処理系内部で頭部と本体のペアで表される。 節の本体は Lisp のリストのような入れ子のペアで表される。 defs メソッドで述語に定義された節のリストを得ることができる。 

>>> man.defs()
[(man('adam'), None)]
>>> father.defs()
[(father(X, Y), (man(X), (parent(X, Y), None)))]

Prolog のカット演算子は Python のグローバル変数 CUT で表す。 CUT は述語項と同様に節の本体に含めることができる。 便宜のため，変数の値は "!" とする。ただし，is 演算で CUT かどうかを 判定するため，文字列定数 "!" で CUT を代用した場合の動作は保証されない。 

>>> CUT
'!'

ここまでの範囲の Python プログラムを下記に示す。 

# -*- coding: utf-8 -*-

CUT = "!"

class Var:
    u"変数 (variable)"
    def __init__(self, name):
        u"name は repr() による表示にだけ使用される。"
        self.name = name

    def __repr__(self):
        return self.name

class Pred:
    u"述語 (predicate)"
    def __init__(self, name):
        u"name は repr() による表示にだけ使用される。"
        self.name = name
        self.__defs = []

    def __repr__(self):
        return self.name

    def __call__(self, *args):
        u"述語項を構成する。"
        return _Goal(self, args)

    def defs(self):
        u"節 (head と body からなるタプル) からなるリスト"
        return self.__defs

    def add_def(self, head, body):
        u"節 (head と body) を追加する。"
        self.__defs.append((head, body))

class _Goal:
    u"述語項"
    def __init__(self, pred, args):
        assert isinstance(args, tuple)
        self.pred = pred
        self.args = args

    def __lshift__(self, rhs):
        u"節を定義する。self が節の頭部，rhs が節の本体となる。"
        if not isinstance(rhs, tuple):
            rhs = rhs,
        if __debug__:
            for t in rhs:
                assert t is CUT or isinstance(t, _Goal)
        self.pred.add_def(self, pair(rhs))

    def __repr__(self):
        if len(self.args) == 1:
            return "%s(%r)" % (self.pred, self.args[0])
        else:
            return "%s%s" % (self.pred, self.args)

def pair(x):
    u"x1,..,xN の列から，入れ子のペア (x1, (...(xN, None))) を作る。"
    x = list(x)
    x.reverse()
    return reduce(lambda a, b: (b, a), x, None)

上記の内容のファイルをp1.pyとして用意した。 シェルのコマンド行から 

$ python -i p1.py

のようにして Python の対話セッションを開始するか， あるいは Python の対話セッションから 

>>> from p1 import *

とすれば，これまで述べた例を実験できる。 ただし，後者の方法では，下線ではじまる名前 (ここでは _Goal) がじかには見えないことに注意されたい。

3. 環境とユニフィケーション

この処理系では， 環境を表す Env クラスのインスタンスに変数の値を保持する。 変数自体を表す Var インスタンスには保持しない。 変数値を参照するときは， 入れ子になった Env インスタンスをたどって値を取り出す。

環境は初期状態では空である。 環境の内部データは属性 _Env__table に保持される (この属性は Python スクリプトでは self.__table と表記されている。 下線２個で始まる private 属性は，不用意なアクセスを防ぐため， 実行時，名前に下線１個とクラス名が接頭されることを思い出されたい)。 

>>> e1 = Env()
>>> e1
<__main__.Env instance at 0x5cdc8>
>>> e1._Env__table
{}

変数に値を定義するときは，変数と，値と環境のペアを put メソッドに与える。 

>>> V1 = Var("V1")
>>> e2 = Env()
>>> e1.put(V1, ("poi", e2))
>>> e1._Env__table
{V1: ('poi', <__main__.Env instance at 0x5ce40>)}
>>> e2
<__main__.Env instance at 0x5ce40>

このように環境は， 変数から，値と環境のペアへのマッピングを保持している。

get メソッドで値と環境のペアを取り出すことができる。 

>>> e1.get(V1)
('poi', <__main__.Env instance at 0x5ce40>)

環境が変数に対して値と環境のペアを保持する理由は， Prolog の変数が必ずしも具体的な値に束縛されるとは限らないからである。

たとえば，ゴール 

p(A)

が与えられ， 述語 p の定義として節 

p(X) << q(X)

があると仮定する。 まず p(A) と p(X) がパターンマッチされて，A と X が同一のものとされる (実際には，A が X に束縛される， あるいは X が A に束縛される。 いずれになるかは実装による。 いずれにせよ一方の変数が未束縛で，もう一方の変数が他方に束縛された状態になる)。 ただし，具体的な値はこの時点では決まらない。

つぎに節の本体である q(X) に対し X が 8 とパターンマッチしたと仮定する。 X と同一になっている A もまた 8 になる。 

q(8) << ()

このとき実際には，X が未束縛ならば，X が 8 に束縛される。 あるいは，X が A に束縛されていて A が未束縛ならば，A が 8 に束縛される。

最終的な結果として A の値を取り出すとき， 前者のシナリオでは，A から変数 X が取り出され，変数 X から 8 が取り出される。 後者のシナリオでは，A から 8 がじかに取り出される。

これを実装するには，変数を変数に束縛するとき， それがどの文脈のもとでの変数なのかという情報， つまり「環境」も込みで束縛しなければならない。 そこで，たとえば前者のシナリオではじめに A が X に束縛されるとき，実装上は 

Aの環境 . put (変数A, (変数X, Xの環境))

のようなメソッド呼び出しが行われ， A に対して (X, Xの環境) のペアが保持される。

このシナリオでは，この後，サブゴール q(X) において Xの環境 のもとで未束縛の X が 8 に束縛される。 最終的な結果として A の値を Aの環境 から取り出すとき， (変数X, Xの環境) が取り出されるが， Xの環境 では変数 X は 8 に束縛されているから， 結局，A の値として 8 が得られる。

Env クラスの dereference メソッドは， このように具体的な値または未束縛の変数が得られるまで延々と環境をたどって， (値, 環境) のペアを取り出す関数である。 

Aの環境 . dereference (変数A)

class Env:
    u"環境 (environment)"
    def __init__(self):
        self.__table = {}       #  {Var: (term, Env)}

    def put(self, x, (t, env)):
        u"変数 x を，項 t とその環境 env のペアに束縛する。"
        assert isinstance(x, Var)
        assert isinstance(env, Env)
        self.__table[x] = (t, env)

    def get(self, x):
        u"変数 x が束縛されている項とその環境のペア (なければ None) を返す。"
        return self.__table.get(x)

    def delete(self, x):
        u"変数 x の束縛を取り消す。"
        del self.__table[x]

    def clear(self):
        u"束縛をすべて取り消す。"
        self.__table.clear()

    def dereference(self, t):
        u"""非変数または未束縛の変数が得られるまで項 t の値を参照する。
        得られた値とその環境のペアを返す。
        """
        env = self
        while isinstance(t, Var):
            p = env.get(t)
            if p is None:
                break
            (t, env) = p
        return (t, env)

    def __getitem__(self, t):
        u"項 t に含まれる変数を再帰的にできる限り展開し，その値を返す。"
        (t, env) = self.dereference(t)
        if isinstance(t, _Goal):
            return _Goal(t.pred, env[t.args])
        elif isinstance(t, list):
            return [env[a] for a in t]
        elif isinstance(t, tuple):
            return tuple([env[a] for a in t])
        else:
            return t

述語項の引数について，これまで定義してこなかった。 Prolog で述語項の引数は一般に項 (term) と呼ばれる。 この処理系では項を次のように定義する。 この定義は Env クラスの __getitem__ メソッドの処理を規定する。

  1. 項とは，定数 (数や文字列など) であるか，
  2. 変数 (Var インスタンス) であるか，
  3. 述語項 (_Goal インスタンス) であるか，または
  4. 項を要素とする tuple または list である。

これまでパターンマッチと呼んでいた操作は，Prolog では普通 ユニフィケーション (unification) と呼ばれる。 この処理系では，環境 x_env, y_env のもとでの 項 x, y のユニフィケーションを下記の関数 _unify で行う。 この関数はユニフィケーションに成功したとき True を返す。 ユニフィケーションの対象が未束縛の変数ならば， 他方の (間接参照した) 変数値に束縛する。 ここで (x, x_env) と (y, y_env) の二つの組が交換可能であることに注意されたい。 変数どうしのユニフィケーションでどちらをどちらに束縛するかは， この関数を呼び出している側がどちらを第１引数にするかで決まる。 

def _unify(x, x_env, y, y_env, trail, tmp_env):
    u"""x_env 下の x を y_env 下の y と unify する。バックトラックに備えて，
    その過程でおこなった変数束縛を trail に記録する。ただし，最適化のため
    tmp_env への束縛は記録しない。
    """
    while True:
        if isinstance(x, Var):
            xp = x_env.get(x)
            if xp is None:   #  x が未束縛ならば x を y の値に束縛する
                (y, y_env) = y_env.dereference(y)
                if not (x is y and x_env is y_env): # 自己代入チェック
                    x_env.put(x, (y, y_env))
                    if x_env is not tmp_env:
                        trail.append((x, x_env)) # 束縛を記録する
                return True
            else:               # X の束縛値を取り出す
                (x, x_env) = xp
                (x, x_env) = x_env.dereference(x)
        elif isinstance(y, Var):
            x, x_env, y, y_env = y, y_env, x, x_env
        else:
            break

    if isinstance(x, _Goal) and isinstance(y, _Goal):
        if x.pred is not y.pred:
            return False
        x, y = x.args, y.args
        assert isinstance(x, tuple) and isinstance(y, tuple)

    if ((isinstance(x, list) and isinstance(y, list)) or
        (isinstance(x, tuple) and isinstance(y, tuple))):
        if len(x) != len(y):
            return False
        for i in range(len(x)):
            if not _unify(x[i], x_env, y[i], y_env, trail, tmp_env):
                return False
        return True
    else:
        return x == y

ここまでの内容のファイルをp2.pyとして用意した。 使い方は p1.py と同様である。

4. ゴールをめざして

１個のゴールまたはゴールの並びに対し， それを満たす変数束縛からなる環境をかえすジェネレータ resolve() を下記に示す。 

def resolve(*goals):
    u"述語項 (の並び) を解決した変数束縛からなる環境をかえすジェネレータ"
    if __debug__:
        for t in goals:
            assert t is CUT or isinstance(t, _Goal)
    env = Env()
    for r in _resolve_body(pair(goals), env, [False]):
        yield env

resolve() は，ゴールに対する解決つまり変数束縛を求めるため， 下記のジェネレータ _resolve_body() を利用する。 _resolve_body() がかえす値に意味はない。つねに None である。 求める変数束縛は，引数として渡した env に副作用として与えられる。 resolve() は env の値をかえす。

_resolve_body() は渡された body を， 先頭１個のゴール goal と残り rest に分ける。 分けられず None のときは再帰の底である。

goal の述語に定義された節の並び goal.pred.defs() に対し， for 文を使ってループし， それぞれの節の頭部 d_head と goal の _unify() を試みる。 成功した場合は節の本体 d_body に対して _resolve_body() を試みる。 そのおのおのの解決に対し，残り rest の _resolve_body() を試みる。

_unify() に失敗したとき， または d_body と rest に対する入れ子の _resolve_body() の解決が尽きたときは， _unify() で設けた変数束縛を取り消してから， for 文の次のループに進み，別の節の d_head, d_body を試みる。 これにより，いわゆるバックトラックが実現される。

_unify() で設けた変数束縛を取り消すときは， _unify() が trail 引数に残した記録を利用する。 ただし，節に対する環境 d_env については， trail の記録に頼らずに d_env.clear() によって一括消去する。 _unify() でも d_env への束縛はいちいち trail に記録しない。 これにより若干の効率向上が得られる。

カット演算子 CUT が現れたときは，残り rest を試みてから， cut[0] = True でフラグを立てる。 ここで配列を使うのは，Python での変数引数の代用品としてである。 このフラグによりバックトラック時に別の節を試さずに終了する。 d_body と rest で入れ子にしている _resolve_body() の２重ループの 内側でカットが行われたとき，外側にフラグを伝播させるため， この箇所では仮引数 cut2 に実引数 cut を渡す。 

def _resolve_body(body, env, cut, cut2=[False]):
    if body is None:
        yield None
    else:
        (goal, rest) = body
        if goal is CUT:
            for r in _resolve_body(rest, env, cut):
                yield None
            cut[0] = True
        else:
            d_env = Env()
            d_cut = [False]
            for (d_head, d_body) in goal.pred.defs():
                if d_cut[0] or cut[0] or cut2[0]:
                    break
                trail = []
                if _unify(goal, env, d_head, d_env, trail, d_env):
                    for r in _resolve_body(d_body, d_env, d_cut, cut):
                        for s in _resolve_body(rest, env, cut):
                            yield None
                for (x, x_env) in trail:
                    x_env.delete(x)
                d_env.clear()

カット演算子 CUT は，いわゆる探索木の枝刈りをすることによって， バックトラックを制御する。 ゴール p(X) とサブゴール g1, g2, g3 が与えられたとき， p(X) << (g1, CUT, g2) と p(X) << (g1, g2) はほぼ同じ意味を持つ。 ただし， 

p(X) << (g1, CUT, g2)
p(X) << g3

で g1 が成功した (＝満たす解が見つかった) とき， CUT を通り過ぎた時点で g1 の別解， および p に対する他の節のサブゴール g3 への探索木が刈り取られる。 p(X) が成功するかしないかは，g2 によって決定される。 g2 の解がすべて失敗したとき，他の可能性をさがすことなく p(X) が失敗する。

ここで，この処理系が実現している Prolog の言語仕様をまとめる。 

この処理系で項 (term) とは，
1. 定数 (数や文字列など) であるか，
2. 変数 (Var のインスタンス) であるか，
3. 述語項であるか，
4. 項を要素とする tuple または list である。
項での定数の等価性は == 演算で判定される。 
      変数の等価性は is 演算で判定される。
      tuple および list の等価性は各要素の等価性で判定される。

この処理系で述語項とは，
0 個以上の項を引数とした述語の呼出しである。
述語 (Pred のインスタンス) の等価性は is 演算で判定される。

この処理系で節 (clause) の定義とは，述語項を左辺とする << 演算である。
左辺が頭部を，右辺が本体を表す。
右辺は述語項，CUT，またはタプル (ただし各要素は述語項または CUT) である。
空の本体は空のタプルで表す。

たとえば，標準的な Prolog での
  man(adam).
  parent(adam, cain).
  father(F, C) :- man(F), parent(F, C).
は次のように表現される。

man, parent, father = Pred('man'), Pred('parent'), Pred('father')
F, C = Var('F'), Var('C')
man('adam') << ()
parent('adam', 'cain') << ()
father(F, C) << (man(F), parent(F, C))

>>> man, parent, father = Pred("man"), Pred("parent"), Pred("father")
>>> P, C, X, Y = Var("P"), Var("C"), Var("X"), Var("Y")

>>> man("adam") << ()
>>> parent("adam", "cain") << ()
>>> parent("adam", "abel") << ()
>>> father(P, C) << (man(P), parent(P, C))

>>> for env in resolve(father(X, Y)):
...     print env[X], env[Y]
...
adam cain
adam abel
>>>

resolve ジェネレータは，Prolog の結果を Python プログラムから利用するためには適切なインタフェースといえるが， 単に Prolog の計算結果を見るためには手軽さに欠ける。 下記の便宜関数を追加する。 

def query(*goals):
    u"""述語項 (の並び) に対するすべての解を印字する便宜関数。
    解の通番 (失敗ならば 0) を，各解決結果の前につけて印字する。
    """
    g = (len(goals) == 1) and goals[0] or goals
    count = 0
    for env in resolve(*goals):
        count += 1
        print count, env[g]
    if count == 0:
        print 0, g

>>> query(father(X, Y))
1 father('adam', 'cain')
2 father('adam', 'abel')
>>>

ここまでの内容のファイルをp3.pyとして用意した。 使い方は p2.py と同様である。

4.1 カット実装の訂正

訂正したジェネレータ _resolve_body を示す。 本体 (body) の残り (rest) でカットが行われ， rest の探索木が尽きて終了フラグ cut[0] が立ったとき， 述語定義に対する終了フラグ d_cut[0] に True を代入して， 述語定義本体 (d_body) の探索を終了させる。 

def _resolve_body(body, env, cut):
    if body is None:
        yield None
    else:
        (goal, rest) = body
        if goal is CUT:
            for r in _resolve_body(rest, env, cut):
                yield None
            cut[0] = True
        else:
            d_env = Env()
            d_cut = [False]
            for (d_head, d_body) in goal.pred.defs():
                if d_cut[0] or cut[0]:
                    break
                trail = []
                if _unify(goal, env, d_head, d_env, trail, d_env):
                    for r in _resolve_body(d_body, d_env, d_cut):
                        for s in _resolve_body(rest, env, cut):
                            yield None
                        if cut[0]:  # 終了フラグを内から外へ伝播させる
                            d_cut[0] = True
                for (x, x_env) in trail:
                    x_env.delete(x)
                d_env.clear()

ここで終了フラグの伝播が単方向であることに注意されたい。 d_body でカットが行われ， その探索木が尽きて終了フラグ d_cut[0] が立っても， それだけでは body の終了フラグ cut[0] は立たない。 現在の goal の前にバックトラックして， 新たな変数値のもとで body が再試行される可能性が残されている。

訂正版のファイルをp4.pyとして用意した。 使い方は p3.py と同様である。

5. コールバックとトレース

下記は Prolog でリスト連結を行う述語の定義である。 ここでは，第１引数と第２引数を連結したものが第３引数に等しい， ということを再帰的に表現している。 

$ python -i p4.py
>>> append = Pred("append")
>>> A, X, Y, Z  = Var("A"), Var("X"), Var("Y"), Var("Z")
>>> append(None, A, A) << ()
>>> append((A, X), Y, (A, Z)) << append(X, Y, Z)

下記のように実行できる。 最初の例は， (1, (2, None)) と (3, (4, None)) の連結結果を第３引数に求めている。 次の例は，連結結果が (1, (2, (3, (4, None)))) に等しいような第１引数と第２引数を求めている。 最初の例は解が１個，次の例は解が５個ある。 

>>> query (append(pair([1,2]), pair([3,4]), A))
1 append((1, (2, None)), (3, (4, None)), (1, (2, (3, (4, None)))))
>>> query (append(X, Y, pair([1,2,3,4])))
1 append(None, (1, (2, (3, (4, None)))), (1, (2, (3, (4, None)))))
2 append((1, None), (2, (3, (4, None))), (1, (2, (3, (4, None)))))
3 append((1, (2, None)), (3, (4, None)), (1, (2, (3, (4, None)))))
4 append((1, (2, (3, None))), (4, None), (1, (2, (3, (4, None)))))
5 append((1, (2, (3, (4, None)))), None, (1, (2, (3, (4, None)))))
>>>

query 関数や resolve ジェネレータは Python から Prolog を実行する。 ここでは逆に Prolog から Python の関数を呼び出す (＝コールバックする) 機構を示す。 まず，下記のメソッドを _Goal クラスに追加する。 

    def calls(self, callback):
        u"""コールバックを定義する。
        self が unify されたとき，それに対する CallbackEnv インスタンス
        を引数として関数 callback が呼び出されるようにする。
        callback は True (成功) か False (失敗) を返す。
        """
        assert callable(callback)
        self.pred.add_def(self, callback)

つぎにコールバック専用の環境クラスを定義する。 これを Env クラスとは別に設ける理由は， Prolog 変数への代入に必要なユニフィケーション操作の詳細を隠蔽するためである。 変数が変数に束縛されている可能性があるから，一般に， ユニフィケーションの手続きを省略して変数値を環境に直接設定することはできない。 

class CallbackEnv:
    u"コールバック用の環境 (実体は節の環境)"
    def __init__(self, env, trail):
        self.__env = env
        self.__trail = trail

    def __getitem__(self, t):
        u"項 t に含まれる変数を再帰的にできる限り展開し，その値を返す。"
        return self.__env[t]

    def unify(self, t, u):
        u"この環境で項 t, u を unify する。"
        return _unify(t, self.__env, u, self.__env, self.__trail, self.__env)

それから _resolve_body 関数を改造する。 _unify() に成功した後，節の定義本体が関数だったならば (つまり callable(d_body) が真だったならば)， コールバック専用の環境インスタンスを引数として定義本体を呼び出すようにする。 この呼び出しでの変数束縛は，_unify() での変数束縛とともに， ループ末尾での trail と d_env に対する操作で取り消される。 

def _resolve_body(body, env, cut):
    if body is None:
        yield None
    else:
        (goal, rest) = body
        if goal is CUT:
            for r in _resolve_body(rest, env, cut):
                yield None
            cut[0] = True
        else:
            d_env = Env()
            d_cut = [False]
            for (d_head, d_body) in goal.pred.defs():
                if d_cut[0] or cut[0]:
                    break
                trail = []
                if _unify_(goal, env, d_head, d_env, trail, d_env):
                    if callable(d_body):
                        if d_body(CallbackEnv(d_env, trail)):
                            for s in _resolve_body(rest, env, cut):
                                yield None
                    else:
                        for r in _resolve_body(d_body, d_env, d_cut):
                            for s in _resolve_body(rest, env, cut):
                                yield None
                            if cut[0]:
                                d_cut[0] = True
                for (x, x_env) in trail:
                    x_env.delete(x)
                d_env.clear()

ここで _unify() の呼び出しを 「_unify_」に変えていることにも注意されたい。 これは下記のような関数を使って， ユニフィケーションの結果をトレース表示するためである。 

_trace = False
def trace(flag):
    u"flag が真ならば unify した結果を表示するようにする。"
    global _trace
    _trace = flag

def _unify_(x, x_env, y, y_env, trail, tmp_env):
    if _trace:
        lhs, rhs = str(x_env[x]), str(y)
    unified = _unify(x, x_env, y, y_env, trail, tmp_env)
    if _trace:
        print "\t", lhs, ((unified) and "~" or "!~"), rhs
    return unified

ここまでの内容を総合して tiny_prolog.pyとして用意した。使い方は p4.py と同様である。

トレース表示の例を示す。 各表示の左辺がゴール，右辺が節の定義頭部である。 unify に成功したときは ~ が，失敗したときは !~ が間に置かれる。 

>>> trace(True)
>>> query (append(pair([1,2]), pair([3,4]), A))
        append((1, (2, None)), (3, (4, None)), A) !~ append(None, A, A)
        append((1, (2, None)), (3, (4, None)), A) ~ append((A, X), Y, (A, Z))
        append((2, None), (3, (4, None)), Z) !~ append(None, A, A)
        append((2, None), (3, (4, None)), Z) ~ append((A, X), Y, (A, Z))
        append(None, (3, (4, None)), Z) ~ append(None, A, A)
1 append((1, (2, None)), (3, (4, None)), (1, (2, (3, (4, None)))))
        append(None, (3, (4, None)), Z) !~ append((A, X), Y, (A, Z))
>>>

コールバックを使って画面出力を行う例を示す。 河内の塔を解く下記の hanoi.py では， write(A).calls(write_callback) を使って， 述語項 write(A) が write_callback(env) を呼び出すようにしている。 write_callback 関数は呼び出されると Prolog 変数 A の値を env[A] で取得し，print する。 

# -*- coding: utf-8 -*-
from tiny_prolog import *

def hanoi_pred(top):
    A, B, C, X, Y = Var("A"), Var("B"), Var("C"), Var("X"), Var("Y")
    hanoi, write_move, write = Pred("hanoi"), Pred("write_move"), Pred("write")

    def write_callback(env):
        print env[A],
        return True

    write(A).calls(write_callback)

    write_move(X, A, B) << (
        write("move"), write(X), 
        write("from"), write(A), write("to"), write(B), write("\n"))

    hanoi(top, A, B, C) << (    # 頂上 top を A から B に移すには
        write_move(top, A, B))  # top を A から B に移す。

    hanoi((X, Y), A, B, C) << ( # 底が X, 上部が Y の塔を A から B に移すには
        hanoi(Y, A, C, B),      # Y を A から C に移して
        write_move(X, A, B),    # X を A から B に移して 
        hanoi(Y, C, B, A))      # Y を C から B に移す。
    return hanoi

if __name__ == "__main__":
    hanoi = hanoi_pred("top")
    query (hanoi(("base",("2nd","top")), "Left", "Center", "Right"))

実行例を示す。 

$ python hanoi.py
move top from Left to Center 
move 2nd from Left to Right 
move top from Center to Right 
move base from Left to Center 
move top from Right to Left 
move 2nd from Right to Center 
move top from Left to Center 
1 hanoi(('base', ('2nd', 'top')), 'Left', 'Center', 'Right')
$

もう一つの例として， 整数の減算 (subtract) と比較 ≦ (less than or equal to) を挙げる (arith0.py)。 

from tiny_prolog import *

A, B, X = Var("A"), Var("B"), Var("X")
subt, le = Pred("subt"), Pred("le")

def subt_callback(env):
    a, b = env[A], env[B]
    assert not isinstance(a, Var)
    assert not isinstance(b, Var)
    return env.unify(X, a - b)

subt(A, B, X).calls(subt_callback)

def le_callback(env):
    a, b = env[A], env[B]
    assert not isinstance(a, Var)
    assert not isinstance(b, Var)
    return a <= b

le(A, B).calls(le_callback)

$ python -i arith0.py
>>> query (subt(10, 2, A))
1 sub(10, 2, 8)
>>> query (le(10, 2))
0 le(10, 2)
>>> query (le(2, 10))
1 le(10, 2)
>>>

参考文献

ある程度まとまった資料として，今は亡き雑誌 bit の連載記事を参考にした。 とりわけ変数束縛のための構造共有の方式はこの記事を参考にした。

Prolog の語源は下記によった。

Python で書かれた Prolog は本処理系のほかにもいくつかある。

「述語項」という語は，Prolog 用語としてはあまり一般的ではないが， "predication" の訳語として Prolog の国内規格 JIS X 3013:2001 に挙げられている (一般的には関数記号と述語記号を区別せずに「複合項」"compound term" と呼ぶ)。 なお，この規格の内容は実質的に訳語の定義のみであり， 構文や意味論，組込み述語等については国際規格 ISO/IEC 13211-1:1995 を参照先として示しているだけである。

Ruby で作る Prolog 処理系 (補講) へつづく


Copyright (c) 2006 Oki Software Co., Ltd.