Rubyで作るProlog処理系

複数のクラスから構成されるRubyプログラムの実例

環境と単一化

　これまでイテレータresolveがブロックに与える値として環境（environment）を見てきました。環境は、単一化（unification）と一体となって、Prologの内部動作の基礎を形作っています。

　本処理系は環境をクラスEnvのインスタンスで表します。resolveがブロックに与える値もEnvのインスタンスです。

　Envのインスタンスは、変数をキーとし、変数値と環境（Envのインスタンス）のペアを値とするハッシュ表を保持します。変数に対して、変数値だけでなく環境もペアにしてハッシュ表に格納するわけは、Prologの変数が必ずしも具体的な値にセットされるとは限らないからです。

　例えば、次のゴール、

mortal[:A]

　が与えられたとき、述語mortalの定義として、

mortal[:X] .si human[:X]

　があったとすると、まずmortal[:A]とmortal[:X]がパターンマッチされて、:Aと:Xが単一化されます（実際には、:Aが:Xにセットされるか、:Xが:Aにセットされます。どちらになるかは実装次第ですが、どちらにせよ一方の変数が未セットで、もう一方の変数が他方にセットされた状態になります)。ただし、具体的な値はこの時点では決まりません。

　さらに、human[:X]に対し、:Xが'socrates'とパターンマッチしたとすると、その時点で、:Xと単一化されている:Aも'socrates'になります。

human['socrates'] .si

　つまり、もし:Aが:Xにセットされていて、:X自身が未セットだったならば、:Xが'socrates'にセットされます。一方、もしも、:Xが:Aにセットされていて:Aが未セットだったならば、:Xを'socrates'にセットしようとするとき、:Xの値である:Aが取り出され、:Aが'socrates'にセットされます。

　このように処理を進めるには、変数を変数にセットするとき、それがどんな状況のもとでの変数なのかという情報が必要になります。これが変数値と環境をペアにして保持する理由です。

　Envクラスのdereferenceメソッドは、このように具体的な値または未セットの変数が得られるまで延々と環境をたどります。dereferenceメソッドの本体にある式Symbol === tは、tがシンボルであるか否か、つまりProlog変数であるか否かを判定します。

list9

class Env
    def initialize
        @table = {}
    end
    def put(x, pair)
        @table[x] = pair
    end
    def get(x)
        return @table[x]
    end
    def delete(x)
        @table.delete(x) {|k| raise "#{k} not found in #{inspect}"}
    end
    def clear
        @table.clear
    end
    def dereference(t)
        env = self
        while Symbol === t
            p = env.get(t)
            break if p.nil?
            t, env = p
        end
        return [t, env]
    end
    def [](t)
        t, env = dereference(t)
        return case t
            when Goal then Goal.new(t.pred, env[t.args])
            when Cons then cons(env[t[0]], env[t[1]])
            when Array then t.collect {|e| env[e]}
            else t
            end
    end
end

　これまで環境envからProlog変数:Xの値を取り出すとき、クラスEnvの配列要素参照演算であるenv[:X]を使ってきました。上記のdef [](t)から分かるように、このメソッドは実は、配列などの入れ子になったデータ構造のなかに現れる変数を、再帰的にできる限り展開した値を返す関数です。引数には一般のProlog式（正確には「項」term）が可能です。

　従って、前節のappend述語のスクリプトは、最後の3行を次のように書くこともできます。

t = append[:A, :B, list(1, 2, 3)]
resolve t do |env|
  print env[t].inspect, "＼n"
end

　この場合、次のような実行結果が得られます。

実行結果

append[nil, (1 2 3), (1 2 3)]
append[(1), (2 3), (1 2 3)]
append[(1 2), (3), (1 2 3)]
append[(1 2 3), nil, (1 2 3)]

　下記の関数unifyが、パターンマッチないし単一化を実現しています（名前を下線で始めているのは、内部的な関数である、という気持ちを表すためです）。環境x_env, y_envのもとで、項x, yを単一化します。単一化に成功したときtrueを返します。単一化の対象が未セットの変数ならば、他方の変数値にセットします。

list10

def _unify(x, x_env, y, y_env, trail, tmp_env)
    loop {
        if Symbol === x
            xp = x_env.get(x)
            if xp.nil?
                y, y_env = y_env.dereference(y)
                unless x == y and x_env == y_env
                    x_env.put(x, [y, y_env])
                    trail << [x, x_env] unless x_env == tmp_env
                end
                return true
            else
                x, x_env = xp
                x, x_env = x_env.dereference(x)
            end
        elsif Symbol === y
            x, x_env, y, y_env = y, y_env, x, x_env
        else
            break
        end
    }
    if Goal === x and Goal === y
        return false unless x.pred == y.pred
        x, y = x.args, y.args
    end
    if Array === x and Array === y
        return false unless x.length == y.length
        for i in 0 ... x.length
            return false unless _unify(
                x[i], x_env, y[i], y_env, trail, tmp_env)
        end
        return true
    else
        return x == y
    end
end

　引数trailは、この単一化でセットされた変数とその環境を記録します。この記録は、後で同じ述語の別の定義を試す前に今の単一化を取り消す（いわゆるバックトラックをする）ために使われます。引数tmp_envは、すぐに廃棄される予定の環境です。これについては無駄ですからtrailに記録しません。

　前述のappend述語でリストの分離／連結操作が可能なのは、ここでArrayの各要素について再帰的に単一化しているからです。

　文字列定数や数値定数は、末尾のreturn x == yで等価性が判定されます。

ゴールをめざして

　イテレータresolveの定義をlist11に示します。

　与えられたゴールの並びがnilならば再帰の底です。そうでなければ、先頭のゴールgoalと残りrestに分割します(goal, rest = body)。

注

　ゴールが:CUTだった場合は後述します。

　ゴールの述語定義の配列goal.pred.defsの各要素について、for文ループでゴールと定義左辺d_headの単一化を試みます（_unify呼び出し）。ふつうのプログラミング言語になぞらえると、ここで関数の実引数と仮引数を結合するわけです。

注

　定義右辺d_bodyがProcだった場合は後述します。

　単一化に成功したとき、定義右辺d_bodyを、その環境d_envのもとで解決します（外側の_resolve_body呼び出し）。ふつうのプログラミング言語になぞらえると、実引数と結合した仮引数のもとで関数本体を実行するわけです。

　外側の_resolve_bodyの呼び出しが解を一組見つけたとき、仮引数と結合している実引数にその解がもたらされています。もとのゴール並びの残りrestを、実引数の環境envのもとで解決します（内側の_resolve_body呼び出し）。

　すべてに対して解決したら、yieldします。

　for文で次のループに入る前に、単一化前の状態に変数値を戻します（trailに対するfor文と、d_env.clear）。いわゆるバックトラックです。

list11

def resolve(*goals)
    env = Env.new
    _resolve_body(list(*goals), env, [false]) {
        yield env
    }
end

def _resolve_body(body, env, cut)
    if body.nil?
        yield
    else
        goal, rest = body
        if goal == :CUT
            _resolve_body(rest, env, cut) {
                yield
            }
            cut[0] = true
        else
            d_env = Env.new
            d_cut = [false]
            for d_head, d_body in goal.pred.defs
                break if d_cut[0] or cut[0]
                trail = []
                if _unify(goal, env, d_head, d_env, trail, d_env)
                    if Proc === d_body
                        if d_body[CallbackEnv.new(d_env, trail)]
                            _resolve_body(rest, env, cut) {
                                yield
                            }
                        end
                    else
                        _resolve_body(d_body, d_env, d_cut) {
                            _resolve_body(rest, env, cut) {
                                yield
                            }
                            d_cut[0] ||= cut[0]
                        }
                    end
                end
                for x, x_env in trail
                    x_env.delete(x)
                end
                d_env.clear
            end
        end
    end
end

コールバック

　list11で、もしもd_bodyがProcだったならば、d_body[]呼び出しをします。これによりProlog内部からRuby関数を呼び出せます。このときコールバック用の環境を構築し、引数として渡します。コールバック用環境のクラスCallbackEnvの定義は次のとおりです。実装詳細にかかわるtrailと複雑な仕様の_unifyを隠蔽して、単純で使いやすいメソッドを提供します。

list12

class CallbackEnv
    def initialize(env, trail)
        @env, @trail = env, trail
    end
    def [](t)
        return @env[t]
    end
    def unify(t, u)
        return _unify(t, @env, u, @env, @trail, @env)
    end
end

　例えば、第1引数から第2引数を減算した値と第3引数を単一化する述語は、次のように記述できます。

subt = pred 'subt'
subt[:A, :B, :X].calls {|env|
  a, b = env[:A], env[:B]
  env.unify(:X, a - b)
}

　ここで、subt[10, 2, :X]をresolveすると、:Xの値は8になります。

カット演算子

　cutとd_cutはカット演算子に対するフラグです。入れ子になった関数呼び出しの奥底でフラグを立てられるように、長さ1の配列を使って、変数引数の代わりにしています。

　カット演算子:CUTは、いわゆる探索木の枝刈りをすることによって、バックトラックを制御します。ゴールp[:X], g1, g2, g3が与えられたとき、p[:X] .si g1, :CUT, g2とp[:X] .si g1, g2はほぼ同じ意味をもちます。ただし、

p[:X] .si g1, :CUT, g2
p[:X] .si g3

　で、g1が成功した（つまり満たす解が見つかった）とき、:CUTを通り過ぎた時点でg1の別解、および述語pに対するもう一つの定義の本体g3への探索木が刈り取られます。p[:X]が成功するかしないかは、g2によって決定されます。g2の解がすべて失敗したとき、他の可能性を探すことなくp[:X]が失敗します。

　つまり、Ruby風に表現すると、次のような制御構造を表現できるわけです。

def p(X)
    if g1 then g2
          else g3 end
end

おわりに

　ここでは、Rubyの構文要素を利用して小さなProlog処理系を作成しました。バックトラックで次々と値を返すことがPrologの基本動作ですから、Prolog式の評価関数に相当するものをRubyのイテレータとして作りました。

　ただし、いわゆる内部イテレータですから、Pythonのジェネレータに比べ自由度が劣ります。JRubyでの実行をあきらめれば、Continuationクラスを使うことで外部イテレータにすることができます。あるいは､可読性を犠牲にして､イテレータの処理ステップを分解し、有限状態機械に構成し直すことによっても外部イテレータにすることができます。その実装や各方式の総合的な優劣の評価は読者への課題として残します。

　一般的な組込み述語は用意していませんが、カット演算子やRuby関数のコールバックなどの基本機能は備えていますから、必要に応じて定義していくことができます。

　ただし、コールバック述語は決定性のある演算しか表現できません（append述語のように可能な値の組み合わせを次々と返すことはできません）。この制限を取り除くことは読者への課題として残します。

　この処理系に、記号表などの隠された大域変数はありません。Rubyオブジェクトの有効範囲としてローカルに与えた述語はローカルに、グローバルに与えた述語はグローバルに使えます。Rubyプログラム内で同時に複数のPrologプログラムを使うこともできます。

参考資料

　本処理系は、沖ソフトウェア エンジニアリングソリューションセンタ（以下、沖ソフトウェアESC）の下記のPythonによるProlog実装をベースとしています。

• 『Pythonで作るProlog処理系』

　Lispについては、例えば下記を参照してください。

• 沖ソフトウェアESC 『やさしい Lisp の作り方』

　本格的なPrologの処理系としては下記を挙げることができます。

• SWI-Prolog

　Prolog自体についてはWikipediaなどを参照してください。

• Prolog - Wikipedia

追記

　おわりにで述べた二つの課題については沖ソフトウェアESCの下記ページの対話部分でそれぞれ説明しています。

• 『Rubyで作るProlog処理系 (補講)』
• 『Javaで作るProlog処理系』

　Mauricio Fernandez 氏が本処理系をより本格的な Prolog らしくする興味深い拡張と記号計算への応用を eigenclass.org で発表しています。

• Logic programming in Ruby: a tiny prolog interpreter and symbolic computation