C# で作る Prolog 処理系

2006.11.23 - 2007.1.6 (鈴)

1. Python/Ruby からの直訳実装

ソース・ファイルへのリンクを下記に示す。 Microsoft の .NET Framework 2.0 およびその互換実装である Mono 1.2 の C# 2.0 のためのプログラムである。 Windows 上の .NET Framework および Mac OS X "Tiger" 上の Mono で動作を確認した。

Mono での実行例を示す。 無引数で make を実行すると tiny_prolog.cs からライブラリ tiny_prolog.dll を作成する。 make file を実行すると, tiny_prolog.dll を参照して file.cs をコンパイルし,file.exe を実行する。 gmcs は Mono の C# 2.0 コンパイラである。 mono は exe ファイルを実行するためのコマンドである。 exe ファイル,dll ファイルは .NET Framework とバイナリ互換である。

$ ls
Makefile        test_append.cs  test_qsort.cs   tiny_prolog.cs
$ make
gmcs /d:TRACE /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
MONO_TRACE_LISTENER=Console.Out mono test_append.exe
append[X, Y, list(1, 2, 3, 4)]
append[null, list(1, 2, 3, 4), list(1, 2, 3, 4)]
append[list(1), list(2, 3, 4), list(1, 2, 3, 4)]
append[list(1, 2), list(3, 4), list(1, 2, 3, 4)]
append[list(1, 2, 3), list(4), list(1, 2, 3, 4)]
append[list(1, 2, 3, 4), null, list(1, 2, 3, 4)]
$ make test_qsort
make tiny_prolog.dll
make[1]: `tiny_prolog.dll' is up to date.
gmcs /d:TRACE /r:tiny_prolog.dll test_qsort.cs
MONO_TRACE_LISTENER=Console.Out mono test_qsort.exe
list(3, 14, 1, 5, 926, 5, 35)
        test if 14 <= 3
        test if 1 <= 3
        test if 5 <= 3
        test if 926 <= 3
        test if 5 <= 3
        test if 35 <= 3
        test if 5 <= 14
        test if 926 <= 14
        test if 5 <= 14
        test if 35 <= 14
        test if 35 <= 926
        test if 5 <= 5
list(1, 3, 5, 5, 14, 35, 926)
$ 

コンパイラへのオプションとして /d:TRACE を与えることにより, プログラム中の Trace.Assert() や Trace.WriteLine() の呼び出しが有効になる。

コンパイルされた exe ファイルを mono コマンドで実行するとき, 環境変数 MONO_TRACE_LISTENERConsole.Out にセットすることにより, Trace.Assert() や Trace.WriteLine() の出力を標準出力に印字できる。 Console.Error にすると標準エラー出力に印字できる。 それ以外にセットすると印字先のファイル名と解釈される。 環境変数をセットしない場合, プログラムで陽に Trace リスナーを用意しない限り,mono は Trace.Assert() や Trace.WriteLine() の出力をどこにも印字しない。 上記の例で test if 14 <= 3 等とあるのは, Trace.WriteLine() の出力である。 この環境変数の用法は Mono 固有であり,.NET Framework には適用されない。

Windows 上の Cygwin で .NET Framework 2.0 の C# コンパイラ等を使えるように設定してあれば,同じ Makefile を使って Cygwin から make できる。 下記に実行例を示す。 この Makefile の記述では exe ファイルをビルドした後, mono コマンドを実行しようとして (当然ながら) 失敗するが, 得られた exe ファイルを直接実行すればよい。 デフォルトでは Trace.Assert() は失敗時にダイアログを表示し, Trace.WriteLine() は (デバッガがアタッチされていなければ) 何もしない。

$ type csc
csc is /cygdrive/c/WINNT/Microsoft.NET/Framework/v2.0.50727/csc
$ ls
Makefile  test_append.cs  test_qsort.cs  tiny_prolog.cs
$ make CSC=csc
csc /d:TRACE /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.

$ make CSC=csc test_append
make tiny_prolog.dll
make[1]: Entering directory `/tmp/cs'
make[1]: `tiny_prolog.dll' is up to date.
make[1]: Leaving directory `/tmp/cs'
csc /d:TRACE /r:tiny_prolog.dll test_append.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_TRACE_LISTENER=Console.Out mono test_append.exe
/bin/sh: mono: command not found
make: *** [test_append] Error 127
$ ./test_append.exe
append[X, Y, list(1, 2, 3, 4)]
append[null, list(1, 2, 3, 4), list(1, 2, 3, 4)]
append[list(1), list(2, 3, 4), list(1, 2, 3, 4)]
append[list(1, 2), list(3, 4), list(1, 2, 3, 4)]
append[list(1, 2, 3), list(4), list(1, 2, 3, 4)]
append[list(1, 2, 3, 4), null, list(1, 2, 3, 4)]
$

処理系の内容は概ね Python 版Ruby 版 からの直訳である。 Prolog プログラムを実行する操作, すなわち与えられたゴールの解を検索する操作は, Java 版 と同じくホスト言語 (ここでは C# 2.0) の標準的なイテレータ・インタフェースに統合されている。 下記のリスティングは上記でコンパイルし,実行した test_append.cs の内容である。

using System;
using TinyProlog;

class TestAppend: TinyProlog.Core
{
    /// <summary>リスト連結の例題</summary>
    static void Main()
    {
        Var A = var("A");
        Var X = var("X");
        Var Y = var("Y");
        Var Z = var("Z");
        Pred append = pred("append");

        append[null, A, A].@if ();
        append[cons(A, X), Y, cons(A, Z)].@if (append[X, Y, Z]);

        Goals g = goals (append[X, Y, list(1, 2, 3, 4)]);
        Console.WriteLine(g);
        foreach (Env env in g) {
            Console.WriteLine(env[g]);
        }
    }
}

節を表現する構文は,ほぼ Ruby 版の処理系と同じである。 配列要素を参照する構文を借りて,述語項を表現する。 (メソッド si ではなく) メソッド if を使って節を定義する。 Lisp に準じた list 関数と cons 関数でリストを構築する。

Prolog プログラムの実行にあたる導出 (resolution) と単一化 (unification) の操作は,foreach 文で駆動されるイテレータの中で行われる。

イテレータ (C# の用語で,列挙子, enumerator) は Goals クラスの GetEnumerator メソッドによって foreach 文ごとにジェネレートされる。 GetEnumerator は Python 版の resolve ジェネレータ と同じく, yield return 文を利用したジェネレータとして作られている。

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

    […略…]

    /// <summary>述語項の並びを解決する。</summary>
    public IEnumerator<Env> GetEnumerator() {
        Env env = new Env ();
        bool[] cut = new bool[] {false};
        foreach (bool dummy in Resolve(this, env, cut)) {
            Trace.Assert(dummy);
            yield return env;
        }
    }
tiny_prolog.cs(229,27): warning CS0168: The variable `dummy' is declared but never used

1.1 コールバックと導出の統合

本処理系の (直訳ではない) 特徴は, 非決定性コールバックを可能にするため, コールバックのインタフェースとしてジェネレータを採用していること, そしてそれにより通常の導出と処理を統合していることである。 Goals クラスの内部メソッド Resolve を下記に示す。 太字で強調した箇所を Python 版の _resolve_body ジェネレータの該当部分 (if _unify_(goal, … の箇所) と比較されたい。

Resolve は,コールバック (callback) と節の定義本体である述語項の並び (d_goals) のどちらの場合でもイテレータ iter をジェネレートし, 同じ二重 foreach ループを実行する。 コールバックの実例については前述の例題の一つ test_qsort.cs を参照されたい (この例ではたまたま一つしか解を返さないが, 非決定性の基本的な実現方法は明らかであろう。 yield return true を1回だけでなく複数回繰り返せばよい)。

    /// <summary>述語項の並びを解決する内部実装メソッド</summary>
    /// <remarks>これが本処理系の実質的な主ルーチンである。</remarks>
    private static IEnumerable<bool>
    Resolve(Goals body, Env env, bool[] cut) 
    {
        Trace.Assert(! cut[0]);
        if (body == null) {
            yield return true;
        } else {
            Goal goal = body.goal;
            Goals rest = body.rest;
            if (goal == Core.cut) {
                foreach (bool b in Resolve(rest, env, cut)) {
                    Trace.Assert(b);
                    yield return true;
                }
                cut[0] = true;
            } else {
                Env d_env = new Env ();
                bool[] d_cut = new bool[] {false};
                foreach (Clause clause in goal.pred.defs) {
                    if (d_cut[0])
                        break;
                    Goal d_head = clause.head;
                    object d_body = clause.body;
                    List<Pair<Var, Env>> trail =
                        new List<Pair<Var, Env>> ();
                    if (Core.Unify(goal, env, d_head, d_env, trail, d_env))
                    {
                        IEnumerable<bool> iter;
                        if (d_body is Callback) {
                            Callback callback = (Callback) d_body;
                            CallbackEnv e = new CallbackEnv (d_env, d_cut);
                            iter = callback(e);
                        } else {
                            Goals d_goals = (Goals) d_body;
                            iter = Resolve(d_goals, d_env, d_cut);
                        }
                        foreach (bool b1 in iter) {
                            Trace.Assert(b1);
                            foreach (bool b2 in Resolve(rest, env, cut)) {
                                Trace.Assert(b2);
                                yield return true;
                            }
                            if (cut[0]) d_cut[0] = true;
                        }
                    }
                    foreach (Pair<Var, Env> ve in trail) {
                        ve.Snd.Remove(ve.Fst);
                    }
                    d_env.Clear();
                }
            }
        }
    }

    […略…]
}

2. もっとオブジェクト指向で…

改良したソースを示す。 他のファイルは 1. と共通である。

メソッド Resolve をもつ共通のインタフェースとして IGoals を設ける。

public interface IGoals {
    IEnumerable<bool> Resolve(Env env, bool[] cut);
}

Goals クラスを IGoals の実装クラスとし, 従来の Resolve をほぼそのまま Goals クラスの非静的メソッドとする。 従来の Resolve の第1引数が Goals 型だったことを思い出されたい。

public class Goals: IGoals, IEnumerable<Env> {
    internal readonly Goal goal;
    internal readonly Goals rest;

    public virtual IEnumerable<bool> Resolve(Env env, bool[] cut) {
        Trace.Assert(! cut[0]);
        if (goal == Core.cut) {
            foreach (bool b in rest.Resolve(env, cut))
                yield return b;
            cut[0] = true;
        } else {
            List<Pair<Var, Env>> trail = new List<Pair<Var, Env>> ();
            Env d_env = new Env ();
            bool[] d_cut = new bool[] {false};
            foreach (Pair<Goal, IGoals> def in goal.pred.defs) {
                if (d_cut[0])
                    break;
                if (Core.Unify(goal, env, def.Fst, d_env, trail, d_env))
                    foreach (bool b1 in def.Snd.Resolve(d_env, d_cut)) {
                        Trace.Assert(b1);
                        foreach (bool b2 in rest.Resolve(env, cut))
                            yield return b2;
                        if (cut[0])
                            d_cut[0] = true;
                    }
                foreach (Pair<Var, Env> ve in trail)
                    ve.Snd.Remove(ve.Fst);
                d_env.Clear();
                trail.Clear();
            }
        }
    }
    […略…]
}

Goals インスタンスは,goal と rest の二項組で列を表現している。 列の最後の要素の rest 値は,従来は null だった。 rest に対する Resolve メソッド呼び出しを常に可能にするため, null にかえて GoalsEnd インスタンスを用いる。

internal sealed class GoalsEnd: Goals {
    public override IEnumerable<bool> Resolve(Env env, bool[] cut) {
        yield return true;
    }
    […略…]
}

従来は下記のような Callback の値をコールバックの定義本体として直接格納していた。

public delegate IEnumerable<bool> Callback(CallbackEnv env);

Callback に対し,IGoals インタフェースを実装するラッパを設ける。 この Resolve メソッドは引数からコールバック用の環境を作成し, コールバックに引数として渡す。

/// <summary>コールバックを節の本体扱いするためのラッパ</summary>
internal class CallbackWrapper: IGoals {
    private readonly Callback callback;

    internal CallbackWrapper (Callback cb) {
        callback = cb;
    }

    /// <summary>節の解決のためにコールバックを呼び出す。</summary>
    /// <remarks>
    /// 便宜のためコールバックからの各 yield に対し,
    /// 事後に Backtrack() で変数束縛を取り消す。
    /// </remarks>
    IEnumerable<bool> IGoals.Resolve(Env env, bool[] cut) {
        CallbackEnv cenv = new CallbackEnv (env, cut);
        foreach (bool b in callback(cenv)) {
            Trace.Assert(! cenv.Cut, "Cut!");
            yield return b;
            cenv.Backtrack();
        }
    }
}

便宜のため,コールバックでの単一化に対するバックトラックを, ここの for ループで行う。 今や非決定性コールバックがみずから Backtrack() を行う必要はない (しても無害である。従来との互換性は維持されている)。

Python 版などの calls メソッドと異なり, 実装内部ではコールバックそのものではなく, そのラッパを節の頭部の述語に追加する。

public class Goal {
    internal readonly Pred pred;
    internal readonly object[] args;

    /// <summary>コールバックを頭部の述語オブジェクトに追加する。</summary>
    public void calls(Callback callback) {
        CallbackWrapper wrapper = new CallbackWrapper (callback);
        pred.defs.Add(new Pair<Goal, IGoals> (this, wrapper));
    }
    […略…]
}

改訂版 tiny_prolog.cs は互換性を維持しており, 従来の Makefile や例題とともに使うことができる。 Windows 上の .NET Framework 2.0 および Mac OS X "Tiger" 上の Mono 1.2.2.1 で動作を確認した。

Mono 1.2.2.1 は当初の Mono 1.2 に比べ, ドキュメント生成機能が向上している。下記を試されたい。

$ make doc

./html ディレクトリ以下に tiny_prolog の HTML ドキュメントが作成される。 未完成な点があるとはいえ,従来の同種のツールに比べ C# 2.0 によく対応している。


*1: −ん (五段動詞の連用形に接続), −りん (それ以外の動詞の連用形に接続, ただしカ変に使われることは稀): 第二人称を (暗黙の) 主語として依頼・指図を表す。 主に愛知県東部から静岡県西部で使われる。近似的に「−なさい」と交換可能。

3. IronPython からの利用

当然ながら tiny_prolog は IronPython からも利用することができる。 IronPython については Python & IronPython 入門 などを参照されたい。

実行例を下記に示す。事前に tiny_prolog.dll が make 済みであると仮定する。

$ make
make: `tiny_prolog.dll' is up to date.
$ ./test_append.py
append[null, list(1, 2, 3, 4), list(1, 2, 3, 4)]
append[list(1), list(2, 3, 4), list(1, 2, 3, 4)]
append[list(1, 2), list(3, 4), list(1, 2, 3, 4)]
append[list(1, 2, 3), list(4), list(1, 2, 3, 4)]
append[list(1, 2, 3, 4), null, list(1, 2, 3, 4)]
$ ./test_write.py
123 None
hello world 
$ ./test_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 
$ ./test_range.py
0 1 2 3 4 5 6 7 8 9
$ 

IronPython を Mac OS X "Tiger" の「ターミナル」上で対話的に使うときは, 「ターミナル」を黒地に白にし, 下記のように -X:TabCompletion オプションを付けるとよい。 行編集機能がより実用的になる。 (「ターミナル」の色などを特定用途向けに変更した場合, メニューの「ファイル」→「別名で保存...」で設定を保存すれば, 次回からは「ファイル」→「ライブラリ」ですぐに再現できる)

$ ipy -X:TabCompletion

上記のスクリプトはいずれも下記の内容ではじまっている。

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

このように clr.AddReference を使えば, 普通の Python モジュールのように C# の名前空間を利用できる。

$ MONO_TRACE_LISTENER=Console.Out ipy -X:TabCompletion -i test_append.py
append[null, list(1, 2, 3, 4), list(1, 2, 3, 4)]
append[list(1), list(2, 3, 4), list(1, 2, 3, 4)]
append[list(1, 2), list(3, 4), list(1, 2, 3, 4)]
append[list(1, 2, 3), list(4), list(1, 2, 3, 4)]
append[list(1, 2, 3, 4), null, list(1, 2, 3, 4)]
>>> dir(Goal)
['Equals', 'Finalize', 'GetHashCode', 'GetType', 'If', 'MakeDynamicType', 'Membe
rwiseClone', 'Reduce', 'ReferenceEquals', 'ToString', '__class__', '__doc__', '_
_init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '_
_str__', 'calls', 'if']
>>> getattr(Goal, 'if')
<method 'if' of 'Goal' objects>
>>> getattr(Goal, 'if')(append[123])
>>> for e in c.goals(append[X]): print e[X]
... 
123
>>> 

4. 外部イテレータと try-finally とカットの実装

Goals クラスの主要部を示す。 ただし,Trace と Debug のメソッド呼出しは省略した。 Resolve メソッドに cut 引数が無いこと, 同メソッドが int 値を yield return していること, 単一化の取り消しを finally 節で実行していることに注意されたい。

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

    […略…]
    public IEnumerator<Env> GetEnumerator() {
        Env env = new Env ();
        foreach (int q in Resolve(env)) {
            if (q != 0)
                break;
            yield return env;
        }
    }

    /// <summary>GetEnumerator() の実質的な本体</summary>
    public virtual IEnumerable<int> Resolve(Env env) {
        List<Pair<Var, Env>> trail = new List<Pair<Var, Env>> ();
        Env d_env = new Env ();
        foreach (Pair<Goal, IGoals> def in goal.pred.defs) {
            try {
                if (Core.Unify(goal, env, def.Fst, d_env, trail, d_env))
                    foreach (int q in def.Snd.Resolve(d_env)) {
                        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;
                        }
                    }
            } finally {     // 単一化を取り消す。
                foreach (Pair<Var, Env> ve in trail)
                    ve.Snd.Remove(ve.Fst);
                d_env.Clear();
                trail.Clear();
            }
        }
    }
    […略…]
}

カット述語の実装を示す。太字で強調した箇所に注目されたい。 カット述語 cut は最初に 0 を yield する (つまり普通に成功する)。 次に 1 を yield する。

/// <summary>Prolog 式を構築するメソッド,定数等の置き場所</summary>
/// <remarks>Prolog 式を構築するメソッドと定数は小文字でつづる。
/// </remarks>
public class Core {
    […略…]
    /// <summary>長さゼロの object 配列</summary>
    /// <remarks>述語 p から無引数の述語項を構築するとき,
    /// p[] では構文エラーになるから p[none] とする。
    /// </remarks>
    public static readonly object[] none = new object[0];

    private static Var var1 = var("var1");
    private static Var var2 = var("var2");
    private static Var var3 = var("var3");

   […略…]
    /// <summary>カット述語 cut/0</summary>
    public static readonly Pred cut = pred("cut");
    private class cut_Body: IGoals {
        IEnumerable<int> IGoals.Resolve(Env env) {
            yield return 0;
            yield return 1;
        }
    }

    […略…]
    static Core () {
        cut[none].DefineAs (new cut_Body());
        fail[none].DefineAs (new fail_Body());
        not[var1].DefineAs (new not_Body());
        apply[var1, var2, var3].Calls (apply_Callback);
        gapply[var1, var2, var3].Calls (gapply_Callback);
    }
}

たとえば,述語項 p[X], g1, g2, g3 が与えられたとき,

p[X] .If (g1, cut, g2);   // 標準的な Prolog 表記では p(X) :- g1, !, g2.
p[X] .If (g3);

で,g1 が成功したとき,cut を通りすぎた時点で (このとき cut は一度目だから普通に成功する), g1 の別解ともう一つの定義本体 g3 への探索木が刈り取られる。 すなわち, g2 の解がすべて失敗したとき,cut は (二度目だから) 1 を yield する。 このとき述語項の部分並び (cut, g2) は即座に終了して 2 を yield し, それにより述語項の並び (g1, cut, g2) は即座に終了して 3 を yield し, それにより p[X] に対する単一化の試みは g3 を待たずに即座に終了する (つまり失敗する)。

コメント中の cut/0 は cut が 0 個の引数をとる述語であることを示す。

注: 上記の説明と Goals クラスの Resolve メソッドには間違いがある。 処理系 六訂版 を参照されたい。(2007.3.7)

4.1 組込述語 fail, not, apply, gapply

cut 以外の組込述語の実装を示す。

無引数述語 fail は常に失敗する。 その Resolve メソッドは一度も yield return をしない。

    /// <summary>常に失敗する述語 fail/0</summary>
    public static readonly Pred fail = pred("fail");
    private class fail_Body: IGoals {
        IEnumerable<int> IGoals.Resolve(Env env) {
            yield break;
        }
    }

1引数述語 not は述語項を引数にとる。 引数が1個でも解を持てば失敗し,解を持たなければ成功する。

    /// <summary>否定する述語 not/1。引数は述語項</summary>
    public static readonly Pred not = pred("not");
    private class not_Body: IGoals {
        IEnumerable<int> IGoals.Resolve(Env env) {
            Pair<object, Env> oe = env.Dereference(var1);
            IGoal g = (IGoal) oe.Fst;
            Goals gg = goals(g);
            foreach (int q in gg.Resolve(oe.Snd)) {
                if (q != 0)
                    break;
                yield break;
            }
            yield return 0;
        }
    }

3引数述語 apply は,関数適用を簡単に実行するための, 本処理系独自の非標準的な述語である。 インタフェース IFunction を実装したオブジェクト fobj と, Prolog 変数 X が与えられたとき,述語項

apply[fobj, 123, X]

の解の探索で

fobj.call(123, env) 

が実行され,その戻り値が X と単一化される。 この例では定数 123 を渡しているが,一般に Prolog 変数を含む任意の式が許される。 処理系は式を非変数または未束縛の変数に展開して fobj.call に渡す。 式の値がリストなどの場合,子要素までは展開しないが, その値は環境引数 env から env.Dereference(子要素) などとして得られる。

    /// <summary>関数適用のための便宜述語 apply/3</summary>
    public static readonly Pred apply = pred("apply");

    /// <summary>apply 述語の第1引数</summary>
    public interface IFunction {
        object call(object arg, Env env);
    }

    private static IEnumerable<bool> apply_Callback(CallbackEnv env) {
        IFunction fun = (IFunction) env[var1];
        Pair<object, Env> oe = env.Dereference(var2);
        object result = fun.call(oe.Fst, oe.Snd);
        if (env.Unify(var3, result))
            yield return true;
    }

3引数述語 gapply は,ジェネレータ適用を簡単に実行するための, 本処理系独自の非標準的な述語である。 インタフェース IGenerator を実装したオブジェクト gobj と, Prolog 変数 X が与えられたとき,述語項

gapply[gobj, 123, X]

の解の探索で

gobj.call(123, env) 

が実行され,その各 yield 値が X と単一化される。 この例では定数 123 を渡しているが,一般に Prolog 変数を含む任意の式が許される。 その処理方法は apply 述語の場合と同様である。

    /// <summary>ジェネレータ適用のための便宜述語 gapply/3</summary>
    public static readonly Pred gapply = pred("gapply");

    /// <summary>gapply 述語の第1引数</summary>
    public interface IGenerator {
        IEnumerable call(object arg, Env env);
    }

    private static IEnumerable<bool> gapply_Callback(CallbackEnv env) {
        IGenerator gen = (IGenerator) env[var1];
        Pair<object, Env> oe = env.Dereference(var2);
        foreach (object result in gen.call(oe.Fst, oe.Snd))
            if (env.Unify(var3, result))
                yield return true;
    }

5. ベンチマーク・プログラム path (XProlog から)

Java で実装された Prolog 処理系 XProlog (http://www.iro.umontreal.ca/~vaucher/XProlog/) には path.pro というベンチマーク・プログラムが用意されている。 これは 8x8 の格子の迷路で (1,1) の座標から,与えられた座標までの経路を 深さ優先探索で求めるプログラムである。 下記は MacBook Pro (2GHz Core Duo, 1GB, OS X 10.4.8) で座標 (2,2) に対する最初の解を求めた例である。

$ curl -R -O -x proxy***:8080 http://www.iro.umontreal.ca/~vaucher/XProlog/XProl
og.zip
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100 73990  100 73990    0     0  25795      0  0:00:02  0:00:02 --:--:-- 42744
$ mkdir xprolog
$ cd xprolog/
$ unzip ../XProlog.zip
Archive:  ../XProlog.zip
  inflating: README                  
  inflating: Go.java                 
  inflating: KnowledgeBase.java      
  inflating: ParseException.java     
  inflating: Parser.java             
  inflating: ParserConstants.java    
  inflating: ParserTokenManager.java  
  inflating: Play.java               
  inflating: PostOffice.java         
  inflating: SimpleCharStream.java   
  inflating: Term.java               
  inflating: Token.java              
  inflating: TokenMgrError.java      
  inflating: XProlog.java            
  inflating: Prolog.jj               
 extracting: manifest                
  inflating: util.pro                
  inflating: path.pro                
  inflating: robot.pro               
  inflating: robot_env.pro           
  inflating: XProlog.jar             
$ java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-112)
Java HotSpot(TM) Client VM (build 1.5.0_06-64, mixed mode, sharing)
$ java -jar XProlog.jar path.pro

XProlog v.1.3, May 2002

?- solve(p(2, 2), L).

>>> Answer: [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)])]   ( 17483 ms.)
More (y/n)? 

?- quit.
$ 

性能の目安を得るため,Prolog プログラム path.pro を path.cs として移植し, 同一マシン上の Mono.framework 1.2.2.1_0 で実行した。

$ make
gmcs /d:TRACE /doc:tiny_prolog.xml /t:library tiny_prolog.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/5/2007 10:17:12 AM
solve[p[2, 2], list(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])]

Unhandled Exception: System.NullReferenceException: Object reference not set to 
an instance of an object
  at TinyProlog.Goals+<>c__CompilerGenerated2.Dispose () [0x00000] 
  at TinyProlog.Goals+<>c__CompilerGenerated2.Dispose () [0x00000] 
  […略…]
  at TinyProlog.Goals+<>c__CompilerGenerated2.Dispose () [0x00000] 
  at TinyProlog.Goals+<>c__CompilerGenerated1.Dispose () [0x00000] 
  at TestPath.Main () [0x00000] 
1/5/2007 10:17:42 AM
make: *** [path] Error 1
$

Java 1.5.0 上の XProlog の約 6 割の速度で結果を得ている。 残念ながら,イテレータの finally 節に由来するとみられる Dispose() メソッドで null 参照例外が発生している。同一ソースを Windows 上の .NET Framework 2.0 でコンパイルし,実行した場合はこの例外は発生しない。 現在の版の Mono 実装の不具合と考えられる。

同一マシン,同一 Mono 上の IronPython 1.0 では下記の結果が得られた。

$ ./path.py
solve[p[2, 2], L]
1/5/2007 10:17:53 AM
solve[p[2, 2], list(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/5/2007 10:18:24 AM
$ 

インタープリタであるが,C# 版とほとんど同じ速度である。 いったんデータ構造を構築した後は, ほとんどの処理をコンパイル済みの tiny_prolog.dll 内のコードで実行しているから, これは驚くべきことではない。 コンパイル済みの部品を組み合わせてアプリケーションに仕立てる手段としての IronPython の有効性を示す結果である。

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



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