続・C# で作る Prolog 処理系

2007.1.26 - 2007.2.9 (鈴)

1. 処理系 三訂版 とベンチマーク結果

C# で Prolog を実装するライブラリ 三訂版 の特徴は次の4点である。

  1. スタックフレームによる変数束縛。 スタック上にフレームを設け, 変数名の文字列をハッシュ表で引くかわりに, 節の定義時に算出しておいた整数インデックスで変数を参照する。 これにより,ベンチマーク・テストで約2倍の高速化が達成された。 その一方,複数の問い合わせの並列的な求解も妨げない。
  2. 改良されたデバッグ用動作トレース。 インタープリタの動作をより系統的にデバッグ出力する。 この出力から内部でどのように推論を進めているのか分かるため, Prolog の学習にも有用である。 コンパイル時のオプションによって省いたとき,実行速度への影響はない。
  3. IronPython のためのシンタックス・シュガーのサポート。 本ライブラリを IronPython から利用したとき, Python 版処理系 と同じく, 述語の関数適用演算で述語項を構築でき,述語項の左シフト演算で節を定義できる。 実行速度に対する実質的な影響はない。
  4. より広汎なデータ構造への対応。 一般に IEnumerable を実装するデータ構造を単一化の対象にできる。 これには IronPython のリストやタプルが含まれる。 このような一般化は実行速度の低下をもたらすが, 典型的な型に対して専用のコードを用意することで悪影響を抑えた。

次節以降,これらの特徴について順に解説する。 本節の残りでは,ベンチマーク・テストの結果を簡単にまとめて, おおまかな性能の目安を示す。

残念ながら,Mono 1.2.2.1 の C# コンパイラ gmcs が生成するコードは, yield return を含む try 文の finally 節を必ずしも適切に実行しない。 このバグは,三訂版のソース tiny_prolog.cs 424 行の Trace.Assert() で検出された。 同種のバグは前回 第5節 でも null 参照例外として発現している。 三訂版ではフレームがスタックを共用するため,バグの影響が深刻である。

ただし,Mono の実行時処理系はこの件について問題ない。 したがって,コンパイル時だけ .NET Framework を使えば,バグを回避できる。 ここでは下記のように Windows XP SP2 上の .NET Framework 2.0 の csc コマンドでコンパイルした tiny_prolog.dll を用意した。 csc にオプションとして /d:TRACE も /d:DEBUG も与えていないため, デバッグ用動作トレースは完全に省かれている。

$ make CSC=csc CSFLAGS=/o
csc /o /doc:tiny_prolog.xml /t:library tiny_prolog.cs
Microsoft(R) Visual C# 2005 Compiler version 8.00.50727.42
for Microsoft(R) Windows(R) 2005 Framework version 2.0.50727
Copyright (C) Microsoft Corporation 2001-2005. All rights reserved.

バイナリ互換性により,Mono 1.2.2.1 でも,この DLL ファイルを利用できる。 前回 第5節 と同一マシン (MacBook Pro, 2GHz Core Duo, 1GB, OS X 10.4.8),同一 Makefile, path.cs でベンチマークを実行した例を示す。

$ make path
make tiny_prolog.dll
make[1]: `tiny_prolog.dll' is up to date.
gmcs /d:TRACE /r:tiny_prolog.dll path.cs
MONO_TRACE_LISTENER=Console.Out mono path.exe
solve(p(2, 2), L)
1/22/2007 3:00:33 PM
solve(p(2, 2), [p(1, 1), p(2, 1), p(3, 1), p(4, 1), p(5, 1), p(6, 1), p(7, 1), p
(8, 1), p(8, 2), p(7, 2), p(6, 2), p(5, 2), p(4, 2), p(4, 3), p(4, 4), p(5, 4), 
p(6, 4), p(7, 4), p(8, 4), p(8, 5), p(7, 5), p(6, 5), p(5, 5), p(4, 5), p(3, 5),
 p(2, 5), p(1, 5), p(1, 4), p(2, 4), p(2, 3), p(1, 3), p(1, 2), p(2, 2)])
1/22/2007 3:00:47 PM
$ 

3回繰り返した結果, 三訂版に対するこのベンチマークの所要時間はいずれも 14 秒だった。 前回の二訂版をこれと同じ条件で再計測したところ, 所要時間は 24 秒だった。 java 1.5.0_06 上の XProlog 1.3 を測ったところ, 前回と同じく所要時間は 17 秒だった。 XProlog から派生した YProlog 20060421 (http://wwwhome.cs.utwente.nl/~schooten/yprolog/) では 15 秒だった。 有効桁数2桁として結果を下記の表にまとめる。

path ベンチマーク: solve(p(2, 2), L)
処理系 所要時間[秒] 速度比
tiny_prolog 二訂版  24 1.0
XProlog 1.3 17 1.4
YProlog 20060421 15 1.6
tiny_prolog 三訂版 14 1.7

速度は CPU の種類や Java や Mono 自体の実装等に依存するが, この結果による限り,三訂版は Prolog インタープリタとして一応満足できる性能である。

2. スタックフレームによる変数束縛

述語項の並びを表すクラス Goals の主要部を下記に示す。 Debug 関連の記述は省略した。 二訂版と比較すると,trail が Env の1メンバになったこと, Resolve メソッドの try 文 finally 節のバックトラック処理が, Env の Dispose メソッドで実装され,暗黙裏に using 文から呼び出されること, 以上の2点が主な変更点である。 しかし,これらの変更は Env をスタック実装に替えたことと直接の関係はない。

スタック実装と関係があるのは, GetEnumerator メソッドの中で,述語項の変数を Core.ScanVars を使って走査し,変数の配列 (vars) を得ている点である。 この配列は Env のコンストラクタに渡される。 同様に,Resolve メソッド内で節の定義に対する環境を構築するときも, あらかじめ節の定義時に走査しておいた変数の配列 (def.vars) が Env のコンストラクタに渡される。

/// <summary>述語項の並び</summary>
public class Goals: IGoals, IEnumerable<Env> {
    internal readonly Goal goal;
    internal readonly Goals rest;

    […略…]
    /// <summary>空の環境のもとで述語項の並びを解決する。</summary>
    /// <remarks>Prolog の事実上の主ルーチン</remarks>
    public IEnumerator<Env> GetEnumerator() {
        List<Var> vv = new List<Var> ();
        Core.ScanVars(this, vv);
        Var[] vars = vv.ToArray();
        using (Env env = new Env (vars, null)) {
            foreach (int q in Resolve(env)) {
                if (q != 0) {
                    break;
                }
                yield return env;
            }
        }
    }

    /// <summary>GetEnumerator() の実質的な本体</summary>
    public virtual IEnumerable<int> Resolve(Env env) {
        foreach (Def def in goal.pred.defs)
            using (Env dv = new Env (def.vars, env)) {
                if (Core.Unify(goal, env, def.head, dv, dv.trail, dv)) {
                    foreach (int q in def.body.Resolve(dv)) {
                        if (q == 1) { // カットされたならば
                            yield return 2; // カットを伝播する。
                            yield break;
                        } else if (q == 2 || q == 3) { // 伝播はここまで。
                            yield break;
                        }
                        foreach (int r in rest.Resolve(env)) {
                            if (r == 2) {
                                yield return 3; // さらにカットを伝播する。
                                yield break;
                            }
                            yield return 0;
                        }
                    }
                }
            }
    }
    […略…]
}

2.1 Env クラスの実装

Prolog 変数の環境を表すクラス Env のメンバ変数とコンストラクタを示す。

/// <summary>Prolog の環境</summary>
/// <remarks>同じ寿命だから,trail を部品とする。</remarks>
public class Env: IDisposable {
    private readonly Var[] vars;
    private readonly List<Pair<object, Env>> stack;
    private readonly int[] top;
    private readonly int frame;
    internal readonly Trail trail;

    private static readonly Pair<object, Env> NONE
        = new Pair<object, Env> (null, null);

    /// <summary>vars の変数を格納できるスタックフレームを作る。</summary>
    /// <remarks>
    /// もしも env 引数が null ならば,スタック自体を新しく作る。
    /// そうでなければ,env のスタックトップにフレームを載せる。
    /// </remarks>
    public Env (Var[] vars, Env env) {
        this.vars = vars;
        if (env == null) {
            stack = new List<Pair<object, Env>> ();
            top = new int[] {0};
            frame = 0;
            trail = new Trail (null);
        } else {
            stack = env.stack;
            top = env.top;
            frame = top[0];
            trail = new Trail (env.trail);
        }
        int sp = frame + vars.Length;
        top[0] = sp;
        for (int i = stack.Count; i < sp; i++)
            stack.Add(NONE);
    }

例として,Prolog 変数 X, Y, Z をもった Env オブジェクトのメンバ変数の様子を左図に示す。 整数 frame と top[0] は stack の添字 (ゼロからはじまる) である。 frame が指す要素から top[0] が指す要素の直前までが, この Env オブジェクトのスタックフレーム (または単にフレーム) であり,その要素数は vars の要素数に等しい。

たとえば,変数 Y の束縛を参照するときは, 変数 Y に対するフレーム内のオフセット値 1 を得て,stack[frame + 1] を参照する。

変数 Y のオフセット値 1 は,普通は, 事前に計算されて変数オブジェクトの index メンバに直接格納されている。 これにより高速に変数の束縛にアクセスできる。

構築したままの,いわば生の変数オブジェクトを参照したとき, index メンバは設定されていない。 この場合は,vars での Y の出現位置をさがしてオフセット値とする。

    /// <summary>変数に対するフレーム内のオフセット値を得る。</summary>
    private int IndexOf(Var x) {
        int i = x.index;
        if (i != -1) {
            Debug.Assert(0 <= i && i < vars.Length);
            return i;
        } else {
            Debug.WriteLine("- " + x.name + " not indexed");
            Var id = x.identity;
            for (i = 0; i < vars.Length; i++)
                if (id == vars[i].identity)
                    return i;
            throw new KeyNotFoundException(x.ToString());
        }
    }

    internal void Add(Var x, Pair<object, Env> pair) {
        Debug.Assert(pair.Snd != null);
        int i = IndexOf(x);
        stack[frame + i] = pair;
    }

    /// <summary>変数が束縛されている項とその環境を返す。</summary>
    /// <remarks>戻り値の Snd が null ならば変数は未束縛である。</remarks>
    internal Pair<object, Env> Get(Var x) {
        int i = IndexOf(x);
        return stack[frame + i];
    }

    internal void Remove(Var x) {
        int i = IndexOf(x);
        stack[frame + i] = NONE;
    }

Env クラスの Dispose メソッドを示す。 このフレームに属するスタック要素 (stack[frame + 0] から stack[frame + (vars.Length - 1)] まで) に NONE を代入して (ガーベジコレクタのために) 参照を取り消した後, 現在のフレームの先頭を,新しいスタックトップにして (top[0] = frame), フレームをたたむ。

    /// <summary>束縛を取り消し,スタックフレームを解放する。</summary>
    /// <remarks>
    /// 高速化のため,底に着くまでスタック自体は縮めず,そのまま次の
    /// フレームのために再利用する。
    /// </remarks>
    public void Dispose() {
        trail.Dispose();
        // Mono 1.2.2.1 C# コンパイラのバグ(?)を下記の表明で常時検査する。
        Trace.Assert(top[0] == frame + vars.Length);
        for (int i = 0; i < vars.Length; i++)
            stack[frame + i] = NONE;
        top[0] = frame;
        if (top[0] == 0) {
            stack.Clear();
            Debug.WriteLine("- clear " + this);
        }
    }

前述のように Mono 1.2.2.1 の C# コンパイラにはジェネレータ内の try-finally 文やそれと等価な using 文の後処理コード生成に問題があり, Dispose メソッドが適切に呼び出されないことがある。 順序どおりにフレームをたたむ必要があるから,この不具合は深刻である。 問題の発生を検出するため, 事前条件として,たしかにフレームの末尾がスタックのトップであることを (Debug.Assert ではなく) Trace.Assert で常時検査する。

環境がスタック構造をとることは Env クラス内部のここまで述べた部分にだけ関係する。 プログラムの他の箇所はその事実に依存しない。 たとえ Env クラスのメソッドであっても, 上記以外の箇所, たとえば非変数または未束縛変数が得られるまで項の束縛値をたどる Dereference メソッドは,スタック構造という実装詳細に依存しない。

    public Pair<object, Env> Dereference(object t) {
        Env env = this;
        for (;;) {
            Var v =  t as Var;
            if (v == null)
                break;
            Pair<object, Env> p = env.Get(v);
            if (p.Snd == null)
                break;
            t = p.Fst;
            env = p.Snd;
        }
        return new Pair<object, Env> (t, env);
    }

ただし,たしかにスタック実装そのものは完全に隠蔽されているが,厳密に言えば, コンストラクタに与える vars 引数と,index 値を含む変数の表現の変更を経由して, Env の内部実装の変更が他の箇所に影響を与えている。

2.2 Var クラスの実装と変数の走査および単一化

Prolog の変数を表すクラス Var を示す。 今までの実装では Var オブジェクトは名前だけを保持し, オブジェクト自身の同一性がプログラム上で意味をもっていた。 いわば Ruby などにあるシンボルと同じである。 実際,Ruby 版実装では, Var クラスを定義せず,Ruby のシンボルで代用していた。

本実装では,スタックフレームで高速に変数束縛を参照するため, 各変数オブジェクトにあらかじめフレーム上でのオフセット値 index を持たせる。 ただし,コンストラクタに名前引数を与えて普通に変数オブジェクトを構築するときは, index を無効値 -1 にする。

/// <summary>Prolog の変数</summary>
/// <remarks>変数値はここには保持しない。</remarks>
public class Var {
    /// <summary>名前</summary>
    internal readonly string name;
    /// <summary>スタックフレームでのオフセット値,または -1</summary>
    internal readonly int index;
    /// <summary>この値が等しければ同一変数と判断する。</summary>
    internal readonly Var identity;

    /// <summary>名前を与えて変数を構築する。</summary>
    /// <remarks>index を -1, identity を this にする。</remarks>
    public Var (string name) {
        this.name = name;
        index = -1;
        identity = this;
    }

節を定義したり,述語項の並びを解決するときに Core.Scanvars を使って対象を走査し,Env への vars 引数を用意するとともに, 対象に出現する各変数オブジェクトを (もしも対象が書換え可能ならば) 下記の2引数コンストラクタで構築した index 設定済み変数オブジェクトに置換する。

    /// <summary>同一と判断される変数を index を与えて構築する。</summary>
    internal Var (Var reference, int index) {
        name = reference.name;
        this.index = index;
        identity = reference.identity;
    }

    /// <summary>名前を返す。</summary>
    public override string ToString() {
        return name;
    }
}

はじめに述べたように,今までは変数オブジェクトの同一性によって Prolog 変数の同一性を判定していた。 本実装では,もともとの変数オブジェクトと,置換した index 設定済み変数オブジェクトが,同じ Prolog 変数を表現していると判定できるように,メンバ変数 identity を設ける。

このとき,Prolog の二つの項を単一化する Core.Unify 関数は, 変数の自分自身への束縛を避けるための判定基準として, 変数オブジェクトそのものではなく,その identity を使う必要がある。 下記で xvar と yvar の identity を == で比較している箇所に注目されたい。 (また,ここでは Env オブジェクト xenv, yenv の使用方法が,内部実装のスタック化の影響を受けていないことも確認されたい)

public class Core {
    /// <summary>単一化関数</summary>
    internal static bool
    Unify(object x, Env xenv, object y, Env yenv, Trail trail, Env tmpenv)
    {
        for (;;) {
            Var xvar = x as Var;
            if (xvar != null) {
                Pair<object, Env> xp = xenv.Get(xvar);
                if (xp.Snd != null) {
                    xp = xp.Snd.Dereference(xp.Fst);
                    x = xp.Fst;
                    xenv = xp.Snd;
                } else {
                    Pair<object, Env> yp = yenv.Dereference(y);
                    Var yvar = yp.Fst as Var;
                    if (! (yvar != null &&
                           xvar.identity == yvar.identity &&
                           xenv == yp.Snd)) {
                        xenv.Add(xvar, yp);
                        if (xenv != tmpenv)
                            trail.Add(xvar, xenv);
                    }
                    return true;
                }
            […略…]

Core.ScanVars 手続きを示す。 補助関数 ScanVars1 は,Var の2引数コンストラクタ Var (Var reference, int index) で index 設定済み変数オブジェクトを構築する。 Core.ScanVars は,対象が IList xx ならば xx[i] = e で index 設定済み変数オブジェクトへの置換を試みる。 List<> や ArrayList だけでなく (狭義の) 配列も IList であることに注意されたい。

IList は必ずしも書換え可能ではなく, xx[i] = e という操作がサポートされているとは限らない。 しかし,サポートされていなかった場合,特に何もしない。 もしも IList 以外の列挙可能 (IEnumerable) オブジェクトだったならば,はじめから走査だけ行い,置換はしない。 これらの場合,変数オブジェクトの index が設定されないままになる。 しかし,その場合でも前述したように, Env オブジェクトの vars メンバを使って参照時にそのつど index 値が算出されるから,処理系は低速ながら正常に動作する。

    /// <summary>変数の走査</summary>
    /// <param name="x">この中の変数が Index 付きに置換される。</param>
    /// <param name="vars">x 内の変数が Index 付きで追加される。</param>
    internal static void ScanVars(object x, List<Var> vars) {
        Goals gg = x as Goals;
        if (gg != null) {
            ScanVars(gg.goal, vars);
            ScanVars(gg.rest, vars);
        } else {
            Goal g = x as Goal;
            IList xx = (g != null) ? g.args : (x as IList);
            if (xx != null) {
                for (int i = 0; i < xx.Count; i++) {
                    object e = ScanVars1(xx[i], vars);
                    try {
                        xx[i] = e; // ←置換を省いても低速ながら動作する。
                    } catch (NotSupportedException) {}
                }
            } else if (! (x is string)) {
                IEnumerable ee = x as IEnumerable;
                if (ee != null)
                    foreach (object e in ee)
                        ScanVars1(e, vars);
            }
        }
    }

    private static object ScanVars1(object x, List<Var> vars) {
        Var xv = x as Var;
        if (xv != null) {
            Var id = xv.identity;
            foreach (Var v in vars)
                if (id == v.identity)
                    return v;
            Var v1 = new Var (id, vars.Count);
            vars.Add(v1);
            Debug.Assert(vars.IndexOf(v1) == v1.index);
            return v1;
        }

        Cons c = x as Cons;
        if (c != null) {
            object car = ScanVars1(c.Car, vars);
            object cdr = ScanVars1(c.Cdr, vars);
            return new Cons (car, cdr);
        }

        ScanVars(x, vars);
        return x;
    }

節の定義を表す構造体 Def を示す (この構造体は Goals クラス の Resolve メソッドの最外 foreach 文の制御変数の型として出現している)。 構造体の構築時に,節の頭部と本体を Core.ScanVars で走査し, その結果を vars メンバに格納していることに注目されたい。

/// <summary>節の定義</summary>
internal struct Def {
    /// <summary>節の頭部</summary>
    internal readonly Goal head;
    /// <summary>節の本体</summary>
    internal readonly IGoals body;
    /// <summary>節に含まれる変数の並び</summary>
    internal readonly Var[] vars;

    /// <summary>節の頭部と本体を与えて構築する。</summary>
    /// <remarks>
    /// 頭部 (head) と本体 (body) を走査して vars を構築する。
    /// vars は節に対するスタックフレームのひながたとなる。
    /// 高速化のため,head と body に出現する各変数オブジェクトを,
    /// 同一 identity だが vars での位置をその index 値とする変数
    /// オブジェクトに置換する。
    /// </remarks>
    public Def (Goal head, IGoals body) {
        this.head = head;
        this.body = body;
        List<Var> vv = new List<Var> ();
        Core.ScanVars(head, vv);
        Core.ScanVars(body, vv);
        vars = vv.ToArray();
    }

    […略…]
}

*1: David H D Warren, Luis M Pereira and Fernando Pereira: Prolog - the language and its Implementation compared with Lisp, Proceedings of the 1977 symposium on Artificial Intelligence and programming languages, 1977, pp.109-115

*2: Python 版実装の 環境とユニフィケーション の節で説明したように, Prolog では従来の言語でいう関数の変数引数が, 関数内部のローカル変数に束縛されることがあるから, 一見するとスタックを安全にたためないように思われるかもしれない。 しかし,ここで読者は yield 文をもつ Resolve が一種のコルーチンとして動作することに注意されたい。 変数引数の束縛値を参照する時点では環境のスタックはたたまれない。 スタックがたたまれるのは,参照し終わってバックトラックが行われる時点である。 本処理系のように外部イテレータとして与えた場合, Goals に対するイテレーションは多数並行できるから, 可能性として多数のスタックが必要になる。 したがって実装上,ヒープが必要である。 しかし,その割り付けと解放のタイミングは明確であり,たとえば C 言語の malloc と free に相当する機能だけで十分である。

3. 改良されたデバッグ用動作トレース

三訂版はインタープリタの動作をより系統的にデバッグ出力する。 内部でどのように推論を進めているのか (どのような入れ子の状態で,どの節定義とゴールをつきあわせているのか) 分かるため,Prolog の学習にも有用である。 初版以来の例題である test_append.cs で例を示す。

$ make clean
rm -rf xml html tiny_prolog.xml tiny_prolog.dll *.exe
$ make CSFLAGS="/d:TRACE /d:DEBUG"
gmcs /d:TRACE /d:DEBUG /doc:tiny_prolog.xml /t:library tiny_prolog.cs
$ make test_append
make tiny_prolog.dll
make[1]: `tiny_prolog.dll' is up to date.
gmcs /d:TRACE /r:tiny_prolog.dll test_append.cs
test_append.cs(15,29): warning CS0612: `TinyProlog.Goal.if(params TinyProlog.IGoal[])' is obsolete
test_append.cs(16,44): warning CS0612: `TinyProlog.Goal.if(params TinyProlog.IGoal[])' is obsolete
Compilation succeeded - 2 warning(s)
MONO_TRACE_LISTENER=Console.Out mono test_append.exe
-- ! :- TinyProlog.Core+cut_Body.       %
-- fail :- TinyProlog.Core+fail_Body.   %
-- not(VAR1) :- TinyProlog.Core+not_Body.       % VAR1
-- apply(VAR1, VAR2, VAR3) :- TinyProlog.Core+apply_Body.       % VAR1 VAR2 VAR3
-- append([], A, A) :- true.    % A
-- append([A | X], Y, [A | Z]) :- append(X, Y, Z).      % A X Y Z
append(X, Y, [1, 2, 3, 4])
    ?- append(X, Y, [1, 2, 3, 4])
    - append(X, Y, [1, 2, 3, 4]) ~ append([], A, A)
append([], [1, 2, 3, 4], [1, 2, 3, 4])
    - clear TinyProlog.Trail
    - append(X, Y, [1, 2, 3, 4]) ~ append([A | X], Y, [A | Z])
        ?- append(X, Y, Z)
        - append(X, Y, Z) ~ append([], A, A)
append([1], [2, 3, 4], [1, 2, 3, 4])
        - append(X, Y, Z) ~ append([A | X], Y, [A | Z])
            ?- append(X, Y, Z)
            - append(X, Y, Z) ~ append([], A, A)
append([1, 2], [3, 4], [1, 2, 3, 4])
            - append(X, Y, Z) ~ append([A | X], Y, [A | Z])
                ?- append(X, Y, Z)
                - append(X, Y, Z) ~ append([], A, A)
append([1, 2, 3], [4], [1, 2, 3, 4])
                - append(X, Y, Z) ~ append([A | X], Y, [A | Z])
                    ?- append(X, Y, Z)
                    - append(X, Y, Z) ~ append([], A, A)
append([1, 2, 3, 4], [], [1, 2, 3, 4])
                    - append(X, Y, Z) !~ append([A | X], Y, [A | Z])
    - clear TinyProlog.Trail
- clear TinyProlog.Trail
- clear TinyProlog.Env
$ 

C# コンパイラへのオプションとして /d:DEBUG を与えることでデバッグ出力が有効になる。 普通は,つねに /d:TRACE も与えるようにする (三訂版では 2.1 節で述べた Env.Dispose の Trace.Assert だけが TRACE に関係する)。 オプションを省いたときは,デバッグ出力関連のコードは生成されないから, 実行速度への影響はない。 Mono では環境変数 MONO_TRACE_LISTENER を Console.Out にすることで標準出力にデバッグ出力が書かれる。

述語が定義されたとき,処理系は "-- " に続けて定義 (の内部表現) を下記の Debug.WriteLine で出力する。このとき,"%" に続けて,2.2 節で述べたように 定義を走査して見つかった変数の列を書く。たとえば上記で "% A X Y Z" は, 節の定義から A, X, Y, Z の四つの変数が見つかったことを示している。

ちなみに上記で test_append.cs のコンパイル時に Goal.if メソッドが obsolete と警告される理由は,下記でそれを [Obsolete] としていることによる。

/// <summary>述語項</summary>
public class Goal: IGoal {
    /// <summary>述語</summary>
    internal readonly Pred pred;
    /// <summary>引数</summary>
    internal readonly object[] args;

    […略…]

    /// <summary>引数を頭部の述語の定義に追加する。</summary>
    internal void DefineAs(IGoals goals) {
        Def def = new Def (this, goals);
        pred.defs.Add(def);
        Debug.WriteLine("-- " + def);
    }

    /// <summary>節の定義を頭部の述語オブジェクトに追加する。</summary>
    public void If(params IGoal[] goals) {
        DefineAs(Core.goals(goals));
    }

    /// <summary>If と同義</summary>
    [Obsolete] public void @if(params IGoal[] goals) { If(goals); }

    […略…]
}

Debug 関連の記述を含めた Resolve メソッドを下記に示す (cf. §2)。 ループ突入前にまず "?- " に続けて解決すべきゴールの並び (this) を表示する。 ゴール (goal) と定義の頭部 (def.head) の単一化を試みたあと, "- " に続けて両者がマッチしたか ("~"),マッチしなかったか ("!~") を表示する。

どれだけ入れ子しているかをデバッグ出力の字下げで示すため, メソッド本体の最初に Debug.Indent を行い,最後に Debug.Unindent を行う。 確実さのため try-finally 文を用いるが,デバッグ以外には不要だから, DEBUG シンボルで陽に条件コンパイルを行う (しかし,陽に条件コンパイルしなかった場合でも,もともと DEBUG 未定義時には Debug.Indent, Debug.Unindent の呼び出しコードは生成されないから,finally 節は空になる。 したがって,最適化によって try 文のためのコストはゼロになり得る。 ここでの #if-#endif の用法は必ずしも模範的とはいえないかもしれない)。

public class Goals: IGoals, IEnumerable<Env> {
    […略…]
    public virtual IEnumerable<int> Resolve(Env env) {
#if DEBUG
        Debug.Indent();
        try {
#endif
        Debug.WriteLine("?- " + this);
        foreach (Def def in goal.pred.defs)
            using (Env dv = new Env (def.vars, env)) {
                if (Core.Unify(goal, env, def.head, dv, dv.trail, dv)) {
                    Debug.WriteLine("- " + goal + " ~ " + def.head);
                    foreach (int q in def.body.Resolve(dv)) {
                        if (q == 1) { // カットされたならば
                            Debug.WriteLine("- cut1");
                            yield return 2; // カットを伝播する。
                            yield break;
                        } else if (q == 2 || q == 3) { // 伝播はここまで。
                            Debug.WriteLine("- cut-" + q);
                            yield break;
                        }
                        Debug.Assert(q == 0);
                        foreach (int r in rest.Resolve(env)) {
                            if (r == 2) {
                                Debug.WriteLine("- cut2");
                                yield return 3; // さらにカットを伝播する。
                                yield break;
                            }
                            Debug.Assert(r == 0);
                            yield return 0;
                        }
                    }
                } else
                    Debug.WriteLine("- " + goal + " !~ " + def.head);
            }
#if DEBUG
        } finally {
            Debug.Unindent();
        }
#endif
    }
    […略…]
}

Mono と異なり .NET Framework は環境変数でデバッグ出力の出力先を指定できないし, 素の状態ではどこにも出力しない。 ただし,出力しないからといってコンパイル時のオプションで省かなければ, 出力用データの生成処理が内部で行われ,実行時間が無駄に消費される。

.NET Framework で出力先を指定する一つの方法として, アプリケーション名に対応する構成ファイルがある。 たとえば, test_qsort.cs をコンパイルして test_qsort.exe を実行するとき,同じディレクトリに下記のような構成ファイル test_qsort.exe.config があれば,デバッグ出力がコンソールに書かれる。 もちろん,この方法は Mono でも同様に有効である。

<?xml version="1.0" ?>
<configuration>
  <system.diagnostics>
    <trace autoflush="true" indentsize="1">
      <listeners>
        <clear />
        <add name="L1" type="System.Diagnostics.ConsoleTraceListener" />
      </listeners>
    </trace>
  </system.diagnostics>
</configuration>

ここで <clear /> は既存の出力先を取り消す。 これは Mono で環境変数が設定されているとき,2重にデバッグ出力されることを防ぐためだが, 一般には無くてもよい。Windows XP SP2 上の .NET Framework 2.0 での実行例を示す。 indentsize="1" の指定により,字下げ幅が 1 になっていることに注意されたい。

$ csc /d:TRACE /d:DEBUG /t:library tiny_prolog.cs
Microsoft(R) Visual C# 2005 Compiler version 8.00.50727.42
for Microsoft(R) Windows(R) 2005 Framework version 2.0.50727
Copyright (C) Microsoft Corporation 2001-2005. All rights reserved.

$ csc /d:TRACE /d:DEBUG /r:tiny_prolog.dll test_qsort.cs
Microsoft(R) Visual C# 2005 Compiler version 8.00.50727.42
for Microsoft(R) Windows(R) 2005 Framework version 2.0.50727
Copyright (C) Microsoft Corporation 2001-2005. All rights reserved.

$ ./test_qsort.exe
-- ! :- TinyProlog.Core+cut_Body.       %
-- fail :- TinyProlog.Core+fail_Body.   %
-- not(VAR1) :- TinyProlog.Core+not_Body.       % VAR1
-- apply(VAR1, VAR2, VAR3) :- TinyProlog.Core+apply_Body.       % VAR1 VAR2 VAR3

-- qsort([X | L], R, R0) :- partition(L, X, L1, L2), qsort(L2, R1, R0), qsort(L1
, R, [X | R1]). % X L R R0 L1 L2 R1
-- qsort([], R, R) :- true.     % R
-- partition([X | L], Y, [X | L1], L2) :- le(X, Y), !, partition(L, Y, L1, L2).%
 X L Y L1 L2
-- partition([X | L], Y, L1, [X | L2]) :- partition(L, Y, L1, L2).      % X L Y
L1 L2
-- partition([], Y, [], []) :- true.    % Y
-- le(X, Y) :- apply(TestQSort+le_Impl, [X | Y], True). % X Y
[3, 14, 1, 5, 926, 5, 35]
 ?- qsort([3, 14, 1, 5, 926, 5, 35], R, [])
 - qsort([3, 14, 1, 5, 926, 5, 35], R, []) ~ qsort([X | L], R, R0)
  ?- partition(L, X, L1, L2), qsort(L2, R1, R0), qsort(L1, R, [X | R1])
  - partition(L, X, L1, L2) ~ partition([X | L], Y, [X | L1], L2)
   ?- le(X, Y), !, partition(L, Y, L1, L2)
   - le(X, Y) ~ le(X, Y)
    ?- apply(TestQSort+le_Impl, [X | Y], True)
    - apply(TestQSort+le_Impl, [X | Y], True) ~ apply(VAR1, VAR2, VAR3)
    - VAR1 not indexed
    - VAR2 not indexed
    test if 14 <= 3
    - VAR3 not indexed
[…略…]

もう一つの方法はプログラムによるリスナの追加である。 IronPython での例 test_append1.py を示す (cf. test_append.py)。

#!/usr/bin/env ipy
import clr
clr.AddReference('tiny_prolog.dll')

from System.Diagnostics import Debug, ConsoleTraceListener
Debug.IndentSize = 1
Debug.Listeners.Add(ConsoleTraceListener())

from TinyProlog import *
c = Core

A = Var('A')
X = Var('X')
Y = Var('Y')
Z = Var('Z')
append = Pred('append')
append[None, A, A] .If ()
append[c.cons(A, X), Y, c.cons(A, Z)] .If (append[X, Y, Z])

gg = c.goals(append[X, Y, c.list(1, 2, 3, 4)])
for env in gg:
    print env[gg]

4. IronPython のためのシンタックス・シュガー

これまで 本ライブラリを IronPython から使うときは,C# と同じく,述語オブジェクトのインデクサで述語項を構築し, 述語項のメソッド If で節を定義していた。 これに加え三訂版では,Python 版処理系 と同じく, 述語の関数適用演算で述語項を構築し, 述語項の左シフト演算で節を定義することもできる。 たとえば,下記 test_append2.py のような書き方をしてもよい。

#!/usr/bin/env ipy
import clr
clr.AddReference('tiny_prolog.dll')
from TinyProlog import *
c = Core

A = Var('A')
X = Var('X')
Y = Var('Y')
Z = Var('Z')
append = Pred('append')
append(None, A, A) << ()
append(c.cons(A, X), Y, c.cons(A, Z)) << append(X, Y, Z)

gg = c.goals(append(X, Y, c.list(1, 2, 3, 4)))
for env in gg:
    print env[gg]

残念ながら,実現方法はそれほどエレガントではない。 C# にとって奇妙な名前にすぎない Python の特別なメソッド名を陽に定義しているだけである。 すなわち,述語クラス Pred はインデクサだけでなく Python の関数適用演算子メソッド __call__ でも述語項を構築する。

    /// <summary>述語項を構築する。(IronPython 用)</summary>
    public Goal __call__(params object[] args) {
        return new Goal (this, args);
    }

述語項クラス Goal は If メソッドだけでなく Python の左シフト演算子メソッド __lshift__ でも節を定義する。

    /// <summary>If と同義 (IronPython 用)</summary>
    public void __lshift__(params IGoal[] goals) {
        DefineAs(Core.goals(goals));
    }

このシンタックス・シュガーを使った例として前回 第4節第5節 の同名のファイルを書き直した test_write.py, test_range.py および path.py を用意した。 実行例を下記に示す。

$ ./test_write.py
123 None
hello world 
$ ./test_range.py
0 1 2 3 4 5 6 7 8 9
$ ./path.py
solve(p(2, 2), L)
2/6/2007 7:12:17 PM
solve(p(2, 2), [p(1, 1), p(2, 1), p(3, 1), p(4, 1), p(5, 1), p(6, 1), p(7, 1), p
(8, 1), p(8, 2), p(7, 2), p(6, 2), p(5, 2), p(4, 2), p(4, 3), p(4, 4), p(5, 4), 
p(6, 4), p(7, 4), p(8, 4), p(8, 5), p(7, 5), p(6, 5), p(5, 5), p(4, 5), p(3, 5),
 p(2, 5), p(1, 5), p(1, 4), p(2, 4), p(2, 3), p(1, 3), p(1, 2), p(2, 2)])
2/6/2007 7:12:33 PM
$ 

IronPython は Mono と .NET Framework にとって現在,動的・対話的な処理系として有用である。 しかし,そのためだけに他の言語にとって奇妙にみえるメソッド名を導入することには 議論の余地があるかもしれない。 ただし,いずれにせよ,実行時の効率に対する実質的な影響はない。

5. より広汎なデータ構造への対応

三訂版は,単一化可能なデータ構造として, Lisp のリスト風の二項組 Cons のインスタンス (前節の IronPython の例では c.cons 関数や c.list 関数の戻り値として現れている) と,オブジェクトの配列 object[] のインスタンスに加えて, より広汎に IEnumerable を実装するオブジェクトを可能にしている。 これには IronPython のリストやタプルも含まれる。

したがって,下記 test_append3.py のようなプログラムが可能である。 これは Python 版実装での append 述語の例 のように長さ 2 の Python タプルで "リスト" を表現した例である。

#!/usr/bin/env ipy
import clr
clr.AddReference('tiny_prolog.dll')
from TinyProlog import *
c = Core

A = Var('A')
X = Var('X')
Y = Var('Y')
Z = Var('Z')
append = Pred('append')
append(None, A, A) << ()
append((A, X), Y, (A, Z)) << append(X, Y, Z)

gg = c.goals(append(X, Y, (1, (2, (3, (4, None))))))
for env in gg:
    print env[gg]

実行例を示す。

$ ./test_append3.py
append([], (1, (2, (3, (4, [])))), (1, (2, (3, (4, [])))))
append((1, []), (2, (3, (4, []))), (1, (2, (3, (4, [])))))
append((1, (2, [])), (3, (4, [])), (1, (2, (3, (4, [])))))
append((1, (2, (3, []))), (4, []), (1, (2, (3, (4, [])))))
append((1, (2, (3, (4, [])))), [], (1, (2, (3, (4, [])))))
$ 

このような一般化,汎用化は,普通,実行速度を低下させる。 そこで単一化関数 Core.Unify のなかで IEnumerable の典型的な実装クラスに対し専用のコードを用意することで効率を維持する。 object[] は述語項の引数の並びとして頻出する。

IEnumerable 実装クラスのなかでも,述語項の並び (Goals) については,むしろ Prolog 意味論の維持のために専用コードを用意する。 もしも仮に Goals を IEnumerable.GetEnumerator メソッドの戻り値でイテレートした場合, 並びに対する求解 (Prolog プログラムの実行) が行われ,求解結果である環境を単一化することになる。 これは意味のある結果をもたらさない。

public class Core {
    /// <summary>単一化関数</summary>
    internal static bool
    Unify(object x, Env xenv, object y, Env yenv, Trail trail, Env tmpenv)
    {
        for (;;) {
            Var xvar = x as Var;
            if (xvar != null) {
                […略…]
            } else if (y is Var) {
                […略…]
            } else {
                break;
            }
        }

        Goal xg = x as Goal;
        if (xg != null) {
            Goal yg = y as Goal;
            if (! (yg != null && xg.pred == yg.pred))
                return false;
            x = xg.args;
            y = yg.args;
        }

        Cons xc = x as Cons;
        if (xc != null) {
            Cons yc = y as Cons;
            if (yc == null)
                return false;
            return (Unify(xc.Car, xenv, yc.Car, yenv, trail, tmpenv) &&
                    Unify(xc.Cdr, xenv, yc.Cdr, yenv, trail, tmpenv));
        }

        IEnumerable xx = x as IEnumerable;
        if (xx != null && y != null) {
            // 高速化のため IEnumerable 用の処理と別に扱う。
            object[] xa = x as object[];
            if (xa != null) {
                object[] ya = y as object[];
                if (ya == null || xa.Length != ya.Length)
                    return false;
                for (int i = 0; i < xa.Length; i++)
                    if (! Unify(xa[i], xenv, ya[i], yenv, trail, tmpenv))
                        return false;
                return true;
            }

            string xs = x as string;
            if (xs != null)
                return xs.Equals(y);

            Goals g = x as Goals;
            if (g != null) {
                Goals h = y as Goals;
                if (h == null)
                    return false;
                return (Unify(g.goal, xenv, h.goal, yenv, trail, tmpenv) &&
                        Unify(g.rest, xenv, h.rest, yenv, trail, tmpenv));
            }

            if (xx.GetType() == y.GetType()) {
                IEnumerable yy = (IEnumerable) y;
                IEnumerator xi = xx.GetEnumerator();
                IEnumerator yi = yy.GetEnumerator();
                for (;;) {
                    bool xb = xi.MoveNext();
                    bool yb = yi.MoveNext();
                    if (xb != yb)
                        return false;
                    else if (! xb)
                        return true;
                    else if (! Unify(xi.Current, xenv, yi.Current, yenv,
                                     trail, tmpenv))
                        return false;
                }
            }
        }

        return Object.Equals(x, y);
    }

スタックに基づく三訂版の実装では,単一化関数 Core.Unify とあわせて変数走査手続き Core.ScanVars も IEnumerable を適切に扱う必要がある。 2.2 節で示したように,Core.ScanVars は Goals, IList (これは object[] を含む), string を除外した最後の分岐として IEnumerable が列挙する各要素を走査する。

6. 処理系 四訂版

処理系 四訂版は, Trail クラスに発見されたメモリリークの改修を主眼としている。 三訂版から Trail クラスは Env クラス (2.1 節) と同じようなスタック構造として実装されている。 Env クラスの Dispose メソッドは,スタックをたたむとき,たたまれるスタック要素に NONE を代入して (ガーベジコレクタのために) 参照を取り消している。 しかし,三訂版の Trail クラスの Dispose メソッドは,スタックをたたむとき,このような取り消しをしていなかった。

Trail スタックのメモリは,Prolog プログラムの求解が終わってスタックが空になったとき, List<Pair<Var, Env>>.Clear メソッドで解放される。 したがって,取り消しをしなくても定常的にはメモリリークは起こらない。 しかし,求解中,使用済みの Env オブジェクトがガーベジコレクタにより回収されない という現象が過渡的に発生するおそれがある。

四訂版はこの欠陥を改修している。 四訂版の Trail クラスを,Debug 関連の記述を省略し,改修点を強調して下記に示す。

/// <summary>束縛履歴</summary>
/// <remarks>
/// バックトラックで束縛を取り消すための情報を保持する。
/// Env と似たスタック構造をとる。
/// </remarks>
internal class Trail: IDisposable {
    private readonly List<Pair<Var, Env>> stack;
    private readonly int[] top;
    private readonly int frame;

    private static readonly Pair<Var, Env> NONE
        = new Pair<Var, Env> (null, null);

    internal Trail (Trail trail) {
        if (trail == null) {
            stack = new List<Pair<Var, Env>> ();
            top = new int[] {0};
            frame = 0;
        } else {
            stack = trail.stack;
            top = trail.top;
            frame = top[0]; // 既存スタックのトップにフレームを載せる。
        }
    }

    internal void Add(Var v, Env env) {
        Pair<Var, Env> ve = new Pair<Var, Env> (v, env);
        int sp = top[0]++;
        if (sp < stack.Count) {
            stack[sp] = ve;
        } else {
            stack.Add(ve);
        }
    }

    /// <summary>記録している束縛を取り消す。</summary>
    public void Dispose() {
        int n = top[0];
        for (int i = frame; i < n; i++) {
            Pair<Var, Env> ve = stack[i];
            ve.Snd.Remove(ve.Fst);
            stack[i] = NONE;
        }
        top[0] = frame;
        if (top[0] == 0) {
            stack.Clear();
        }
    }
}

他の改訂点は,Core.Unify 関数で Goals クラスを特別扱いする理由 (第5節) のコメント追加と,波かっこの使用・不使用についてのスタイルの統一である。 外部仕様に変更はない。同条件で測定したところ,四訂版は三訂版と path ベンチマークの結果も変わらなかった。


$ make path
make tiny_prolog.dll
make[1]: `tiny_prolog.dll' is up to date.
gmcs /d:TRACE /r:tiny_prolog.dll path.cs
MONO_TRACE_LISTENER=Console.Out mono path.exe
solve(p(2, 2), L)
2/9/2007 8:26:13 AM
solve(p(2, 2), [p(1, 1), p(2, 1), p(3, 1), p(4, 1), p(5, 1), p(6, 1), p(7, 1), p
(8, 1), p(8, 2), p(7, 2), p(6, 2), p(5, 2), p(4, 2), p(4, 3), p(4, 4), p(5, 4), 
p(6, 4), p(7, 4), p(8, 4), p(8, 5), p(7, 5), p(6, 5), p(5, 5), p(4, 5), p(3, 5),
 p(2, 5), p(1, 5), p(1, 4), p(2, 4), p(2, 3), p(1, 3), p(1, 2), p(2, 2)])
2/9/2007 8:26:27 AM
$ mono --version
Mono JIT compiler version 1.2.3, (C) 2002-2006 Novell, Inc and Contributors. www
.mono-project.com
        TLS:           normal
        GC:            Included Boehm (with typed GC)
        SIGSEGV:       normal
        Architecture:  x86
        Disabled:      none
$ ipy
IronPython 1.1a1 (1.1) on .NET 2.0.50727.42
Copyright (c) Microsoft Corporation. All rights reserved.
>>> ^D
$ 

続々・C# で作る Prolog 処理系 へつづく



Copyright (c) 2007 OKI Software Co., Ltd.