続々・C# で作る Prolog 処理系

2007.2.23 - 2007.3.16 (鈴)

1. 処理系 五訂版 …かなり普通の Prolog

cs5.tar.bz2 に含まれる tiny_prolog.dll は,Windows 2000 SP4 上の Cygwin で make csc-build によって tiny_prolog.cs, tiny_prolog_preds.cs, tiny_prolog_parser.cs の3ソースから作成した。現行の Mono 1.2.3.1 の C# 2.0 コンパイラ gmcs にも,これまでと同様のバグがあったため,.NET Framework 2.0 の csc コンパイラを使用した。

tiny_prolog.xml は,コンパイラの /doc:tiny_prolog.xml オプションによって tiny_prolog.dll と同時に作られたファイルである。Mono が利用できる環境で make doc を行えば,xml/ と html/ 以下に公開クラスのドキュメントを作成できる。

p1.exe は p1.cs から make p1 で作成した実行ファイルであり, 現行の Mono と .NET Framework 2.0 上で Prolog インタープリタとして動作する。 プライベートアセンブリとして tiny_prolog.dll を同じディレクトリに置く必要がある。

前回と同一のマシン上で Mono 1.2.3.1 を使い, YProlog 付属のベンチマーク path.pro を実行した例を下記に示す。 " >" ではじまる出力は,p1.exe が,読み込んだ節と問合せを -v (verbose) オプションにより (内部形式を人間可読な文字列に逆変換して) 表示したものである。

path-query.txt は下記の1行からなるテキスト・ファイルである。 これをコマンド行引数として path.pro に続けて与えることにより, path.pro で定義された述語 solve に対する問合せ solve(p(2, 2), L) の最初の解が探索され,表示される。

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

p1.exe にファイル名引数を与えないか,末尾の引数としてハイフンを与えると, コンソールでの対話入力が行われる。 対話入力では,解の表示後,セミコロンの打鍵で次の解が探索される。 探索終了時 "Done." が表示される。 EOF により対話入力が終了する。Mono では普通に EOF を入力できないから,便宜のため,ピリオドだけの行でも終了できるようにしてある。

下記は対話的にフィボナッチ関数を入力して実行した例である。 ただし,Mac の Mono 1.2.3.1 ではセミコロンの打鍵は実際にはエコーバックされない。

$ mono p1.exe
Tiny Prolog in C#: input clauses or ?- goals.
fib(0, 1).
fib(1, 1).
fib(N, A) :- N >= 2,
        N1 is N - 1, fib(N1, A1),
        N2 is N - 2, fib(N2, A2),
        A is A1 + A2.
?- fib(5, X).
1: 
 X = 8
;Done.
.
$ 

Java 版実装の場合と異なり, tak 関数を Prolog として標準的な文法で書くことができる。 この結果から判断する限り,Java 版実装の約 1.6 倍の実行速度である。

$ cat tak.txt
% -*- mode: prolog -*-

tak(X, Y, Z, A) :-
        X =< Y, !, Z = A.
tak(X, Y, Z, A) :- 
        X1 is X - 1,
        Y1 is Y - 1,
        Z1 is Z - 1,
        tak(X1, Y, Z, T1),
        tak(Y1, Z, X, T2),
        tak(Z1, X, Y, T3),
        tak(T1, T2, T3, A).

?- tak(4, 2, 0, A).                             % A = 1
?- tak(7, 5, 1, A).                             % A = 2
?- tak(18, 12, 6, A).                           % A = 7
$ time mono p1.exe tak.txt
1: 
 A = 1
Done.
1: 
 A = 2
Done.
1: 
 A = 7
Done.

real    0m2.153s
user    0m1.868s
sys     0m0.135s
$ 

Java 版実装での ハノイの塔の例は そのまま実行できる。 Windows XP SP2 の コマンド プロンプト での実行例を示す。 残念ながら Mac の Mono 1.2.3.1 はターミナルでの日本語入力に問題がある。

C:\Work\cs5>p1 hanoi.txt -
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:
Done.
Tiny Prolog in C#: input clauses or ?- goals.
?- hanoi(['底', '2段目', '3段目', '頂上'], '左の柱', '中央の柱', '右の柱').
move 頂上 from 左の柱 to 右の柱
move 3段目 from 左の柱 to 中央の柱
move 頂上 from 右の柱 to 中央の柱
move 2段目 from 左の柱 to 右の柱
move 頂上 from 中央の柱 to 左の柱
move 3段目 from 中央の柱 to 右の柱
move 頂上 from 左の柱 to 右の柱
move 底 from 左の柱 to 中央の柱
move 頂上 from 右の柱 to 中央の柱
move 3段目 from 右の柱 to 左の柱
move 頂上 from 中央の柱 to 左の柱
move 2段目 from 右の柱 to 中央の柱
move 頂上 from 左の柱 to 右の柱
move 3段目 from 左の柱 to 中央の柱
move 頂上 from 右の柱 to 中央の柱
1:
;Done.
^Z

C:\Work\cs5>

2. 項の変数展開のカスタマイズ―IronPython での注意点

五訂版のコアである tiny_prolog.cs の仕様と実装は四訂版とほとんど変わらない。test_append.cs のような初期の例題もコンパイルして実行できる。 ただし,前回第5節 の test_append3.py のように一般の IEnumerable オブジェクトを Prolog 項に使うときは注意が必要である。

項の単一化関数 (Core.Unify) と変数の走査関数 (Core.ScanVars) は四訂版と同様であり,一般の IEnumerable オブジェクトを使った場合でも, 求解は今までどおり行われる。 しかし,最後に具体的な結果を得ようとして,項に含まれる変数を展開するとき, 違いが現れる。 五訂版の Env クラスのインデクサは,一般の IEnumerable オブジェクトに対し,初期状態では何もしない。 なぜなら,変数を展開するとき, 元のオブジェクトと同様のオブジェクトを再構築する必要があるが,一般の IEnumerable オブジェクトについて,その方法は必ずしも明らかではないからである。 四訂版では,オブジェクトの配列 object[] で, 一般の IEnumerable オブジェクトの展開結果を代用していた。 これは,いくつかの場合について,さしあたり役に立つが, 必ずしも望ましい振舞ではない。

そのかわり,五訂版では,利用者が項の変数展開をカスタマイズできるように,一種のフックとして Core.ExpansionFilter プロパティを設けた。 Prolog の項として IronPythonタプルリストを使うときは,下記 test_append4.py のように,適切にこのプロパティを設定すればよい。 強調箇所が test_append3.py からの追加部分である。 リストやタプルの構成要素に再帰的に Env のインデクサ (env[e]) を適用していることに注意されたい。

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

def exfilter(x, env):
    if isinstance(x.Value, tuple):
        x.Value = tuple([env[e] for e in x.Value])
    elif isinstance(x.Value, list):
        x.Value = [env[e] for e in x.Value]

c.ExpansionFilter = exfilter

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_append4.py
append([], (1, (2, (3, (4, None)))), (1, (2, (3, (4, None)))))
append((1, None), (2, (3, (4, None))), (1, (2, (3, (4, None)))))
append((1, (2, None)), (3, (4, None)), (1, (2, (3, (4, None)))))
append((1, (2, (3, None))), (4, None), (1, (2, (3, (4, None)))))
append((1, (2, (3, (4, None)))), [], (1, (2, (3, (4, None)))))
$ 

3. 改修版 実行ファイル: p2.exe

便宜のため,p2.exe は tiny_prolog.dll がなくても動作可能とした。 具体的には Windows 2000 SP4 上で下記のコマンドラインによりコンパイルした。

csc /optimize p2.cs tiny_prolog.cs tiny_prolog_preds.cs tiny_prolog_parser.cs

使い方そのものは p1.exe と同様である。 Prolog プログラム・ファイルを読み込んで解釈する主要箇所を下記に示す。 イテレータとして1論理行ずつ実行するが,例外発生時には Exception に対し包括的に処理して終了する。

    try {
        foreach (ParsingResult r in ps.Parse(Lines.FromFile(filename)))
            PrintResult(r, verbose, false);
    } catch (Exception ex) {
        Console.WriteLine(ex.GetType().Name + ": " + filename + ": " +
                          ex.Message);
        return 1;
    }

4. yield 文による外部イテレータの字句・構文解析への応用

外部仕様としての構文解析器のクラス構成を下記に示す。 構文解析器にあたるクラスは Parser である。 Parser の Parse メソッドは,テキスト行の集合体 IEnumerable<string> を引数とし, 1 論理行ずつ解析結果 ParsingResult を yield するイテレータを返す。 テキスト行の集合体の実体は何であってもよい。 ファイル,文字列,コンソール入力をそのような集合体とみなすための便宜関数 Lines.FromFile("ファイル名"), Lines.FromString("文字列"), Lines.FromConsole() がある。

$ grep public tiny_prolog_parser.cs
    public static class Lines {
        public static IEnumerable<string> FromFile(string fileName) {
        public static IEnumerable<string> FromString(string lines) {
        public static IEnumerable<string> FromConsole() {
    public class SyntaxException: Exception {
        public SyntaxException () {}
        public SyntaxException (string message)
        public SyntaxException (string message, Exception inner)
    public struct ParsingResult {
        public readonly Goal Head;
        public readonly Goals Body;
        public readonly IDictionary<string, Var> Vars;
    public class Parser: IEnumerable<Pred> {
        public Parser () {
        public IEnumerable<ParsingResult> Parse(IEnumerable<string> lines)
        public Pred this[string name] {
        public IEnumerator<Pred> GetEnumerator() {
$

Parser インスタンスは,Parse メソッドのローカル変数を除き, 入力テキストにかかわる遷移的なリソースを保持しない。 遷移的なリソースは,正常終了であれ,例外発生時であれ,Parse メソッドの終了時にすべて解放される。 解析時のエラー状態からの復帰は単に Parse メソッドを再び呼び出すだけである。 このようにできる理由は,状態マシンを構成する作業が,yield 文による抽象化によって,C# 内部の実装詳細になっているからである。 この状態マシンは (人間の視点での) ローカル変数の寿命とともに解放される。

(Parse メソッド駆動中ではない定常状態では) Parser インスタンスは,入力され定義された Prolog 述語の集合体であると概念的にみなすことができる。 この概念にもとづき,Parser クラスのインデクサと GetEnumerator() は述語へのアクセスを与える。 Prolog 変数の有効範囲は 1 論理行に限られているから,変数の集合体は 1 論理行の解析結果 (ParsingResult 構造体の Vars メンバ) として返される (ただし,1 論理行が節の定義のときは,述語への定義処理まで解析器内部で完結するから, 外部に変数の集合体を渡す必要はない。したがって,このとき Vars 値は null である)。

これまでの説明の実例として, 下記に五訂版 cs5.tar.bz2 に同梱の p0.cs の内容と実行例を示す。 Prolog プログラムの実行そのものは,当初の版以来変わらず Goals インスタンスのイテレーションによる。 Prolog 変数や Prolog 述語の参照さえ得ておけば,実行時に解析器は不要である。

using System;
using TinyProlog;
using c = TinyProlog.Core;

/// <summary>Prolog インタープリタの実験</summary>
public class P0
{
    /// <summary>文字列で append 述語を与えて問い合わせる。</summary>
    public static void Main(string[] args) {
        string source = ("append([], A, A)." +
                         "append([A|X], Y, [A|Z]) :- append(X, Y, Z).");
        Parser ps = new Parser ();
        foreach (ParsingResult r in ps.Parse(Lines.FromString(source)))
            Console.WriteLine(" > " + r.Head + " :- " + r.Body + ".");

        // 方法1: 文字列で問合せを与える。
        string query = "?- append(L, R, ['白', '黒', '抹茶']).";
        foreach (ParsingResult r in ps.Parse(Lines.FromString(query))) {
            Var L = r.Vars["L"];
            Var R = r.Vars["R"];
            foreach (Env env in r.Body)
                Console.WriteLine("L = " + env[L] + ", R = " + env[R]);
        }

        // 方法2: じかに問合せオブジェクトを構築する。
        Pred append = ps["append"];
        Var X = new Var ("X");
        Var Y = new Var ("Y");
        Goal q = append[X, Y, c.list("青", "白", "赤")];
        foreach (Env env in c.goals(q))
            Console.WriteLine("X = " + env[X] + ", Y = " + env[Y]);
    }
}
$ mono p0.exe
 > append([], A, A) :- true.
 > append([A | X], Y, [A | Z]) :- append(X, Y, Z).
L = , R = ['白', '黒', '抹茶']
L = ['白'], R = ['黒', '抹茶']
L = ['白', '黒'], R = ['抹茶']
L = ['白', '黒', '抹茶'], R = 
X = , Y = ['青', '白', '赤']
X = ['青'], Y = ['白', '赤']
X = ['青', '白'], Y = ['赤']
X = ['青', '白', '赤'], Y = 
$

最後の出力で "Y =" となっているのは,そのときの env[Y] の値が null だからである。この処理系で空リストは null で表現される。 "Y = []" としたい場合は,tiny_prolog.cs に含まれる Core.Str 関数を使って env[Y] のかわりに Core.Str(env[Y]) を出力すればよい。 L, R, X についても同様である。

字句解析器クラス Lexer の冒頭部を示す。 字句解析器としての主要なメソッドは,行の集合体を引数とする TokensFrom(lines) であり,行の集合体から読み取った字句を1トークンずつ yield する。

TokensFron(lines) に渡された行の集合体 lines は内部メソッド CharsFrom(lines) に渡され,そこで,行に含まれる文字が1文字ずつ yield される。 字句誤りや構文誤りのときに場所を知らせるための行番号 lineNumber はここで更新される。

TokensFrom(lines) の中で,CharsFrom(lines) は foreach 文で使われるのではない。 メソッド本体第3行の using (IEnumerator<char> ch = CharsFrom(lines).GetEnumerator()) { によってイテレータ (iterator, C# 用語で enumerator) が単独で使われる。 このイテレータ ch は,識別子を読み取る GetName(ch) などの下請けメソッドに引き渡され,そこでも必要に応じイテレーションが行われる。

/// <summary>字句解析器</summary>
internal class Lexer {
    private bool isEOF;
    private int lineNumber;

    /// <summary>行の集合体から得られる文字の並び</summary>
    /// <remarks>ピリオドだけからなる行は EOF 扱いする。</remarks>
    private IEnumerable<char> CharsFrom(IEnumerable<string> lines) {
        foreach (string line in lines) {
            lineNumber++;
            if (line == ".")
                break;
            foreach (char c in line)
                yield return c;
            yield return '\n';
        }
        isEOF = true;
    }

    /// <summary>行の集合体から得られるトークンの並び</summary>
    /// <remarks>1字句解析器あたり一度に一つしか設けられない。</remarks>
    internal IEnumerable<TokenStr> TokensFrom(IEnumerable<string> lines) {
        isEOF = false;
        lineNumber = 0;
        using (IEnumerator<char> ch = CharsFrom(lines).GetEnumerator()) {
            int anonymous_var_count = 1;
            ch.MoveNext();
            for (;;) {
                while (! isEOF && ch.Current <= '\x20')
                    ch.MoveNext();
                if (isEOF)
                    break;
                char cc = ch.Current;
                if ('a' <= cc && cc <= 'z') {
                    string name = GetName(ch);
                    if (name == "is")
                        yield return new TokenStr (Token.Is);
                    else
                        yield return new TokenStr (Token.Identifier, name);
                } else if ('A' <= cc && cc <= 'Z') {
                    string name = GetName(ch);
                    yield return new TokenStr (Token.Variable, name);

TokensFrom(lines) はメソッド本体第6行の for (;;) { でループする。 通常は 1 回のループで 1 回 yield return 文を実行してトークンを yield する。 もしも必ず 1 回のループで 1 回だけ yield return 文を実行するならば, ループをやめ,yield return 文を使わずに陽に状態マシンとして構成し直す方法は自明である (実際に状態マシンとして再構成する作業は,たとえば C# から Java への移植で発生する)。

しかし,Prolog の構文規則には1文字の先読みでは決定できない箇所がある。 たとえば,"7" と "." の列を読み取ったとき

    7.

これが整数 7 とピリオドの2トークンなのか,それとも 7. ではじまる実数なのかは,さらにもう1文字読まなくては決定できない。

                } else if ('0' <= cc && cc <= '9') {
                    bool period = false;
                    yield return GetNumber(ch, ref period);
                    if (period) // (unget の必要はない ;-)
                        yield return new TokenStr (Token.Period);

整数または実数を読み取る下請けメソッド GetNumber(ch, ref period) は,もしも整数とピリオドの2トークンだった場合,第2引数を true にし, 自分自身の戻り値として整数のトークンを返す。 このとき TokensFrom(lines) は,戻り値を yield return した後, さらにピリオド (period) を yield return するだけでよい。 一方,仮に状態マシンとして構成する場合,このような先読みのしすぎに対し, 読み取りすぎた文字をバッファに戻す (unget する) か,あるいは, 読み取りすぎたトークンを次の呼び出しまで保存する必要がある。

字句解析器クラス Lexer のオブジェクトは,構文解析器クラス Parser の Parse メソッドのローカル変数として使われる。 TokensFrom(lines) での CharsFrom(lines) のように, Parse(lines) での TokensFrom(lines) はイテレータが単独で使われ, 他のローカル変数とともに State 構造体にまとめられて,再帰下降法の各メソッドに引き渡される。

    public IEnumerable<ParsingResult> Parse(IEnumerable<string> lines)
    {
        Dictionary<string, Var> vars = new Dictionary<string, Var> ();
        Lexer lex = new Lexer ();
        using (IEnumerator<TokenStr> tk =
               lex.TokensFrom(lines).GetEnumerator()) {
            State q = new State (lex, tk, vars);
            tk.MoveNext();
            while (tk.Current.Token != Token.EOF) {

5. 処理系 六訂版 〜二訂版以来のカット実装の修正〜

二訂版以来のカット実装を修正した六訂版を下記に与える。 六訂版ではさらに,組込述語として標準的な asserta/1, assertz/1, retract/1 を実装している。 apply/3 の第1引数として IFunction インタフェースのかわりに Call デリゲートをとることもできる (使用例は tiny_prolog_preds.cs にある)。 カット実装のテスト・プログラム test-cut.pro とその模範出力 test-cut.txt を同梱している。

Goals クラスの主要部を示す。ただし Debug 関連は省略した。 枝刈りはカット述語本体 (def.body) の Resolve メソッドが 1 を yield することで始まる。このとき (if (q == 1)),カット述語本体のために用意された環境 (dv) ではなく,カット述語を呼び出している節の環境 (env) にフラグを立てる (env.cut = true)。 フラグが立っているとき,Resolve メソッドを中断する。 break 文ではなく yield break 文で中断するから, 節の頭部に対する別の候補を選ぶループ (foreach (Def def in goal.pred.defs)) も含めて中断される。 ただし,フラグは環境に設けられているから,環境に対する節を超えては中断されない。

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

    […略…]

    /// <summary>GetEnumerator() の実質的な本体</summary>
    /// <exception cref="ApplicationException">
    /// 未定義の述語が求解対象として参照された。
    /// </exception>
    public virtual IEnumerable<int> Resolve(Env env) {
        if (goal.pred.defs == null)
            throw new ApplicationException (goal.pred + " undefined");
        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) {
                            env.cut = true;
                            yield break;
                        }
                        foreach (int r in rest.Resolve(env)) {
                            if (env.cut)
                                yield break;
                            yield return 0;
                        }
                        if (env.cut)
                            yield break;
                    }
                    if (dv.cut)
                        yield break;
                }
    }

    […略…]

最内の foreach 文でループ内部だけでなくループ終了直後にも env.cut をチェックしているのは,rest.Resolve(env) が終了したときにフラグが立っていることがあるからである。

Env クラスの冒頭部を示す。cut フラグが増設されている。

/// <summary>Prolog の節に対する環境 (スタックフレーム)</summary>
/// <remarks>
/// 同じ寿命だから trail を部品とする。
/// 節が枝刈り中かどうかのフラグ cut を持つ。
/// </remarks>
public class Env: IDisposable {
    private readonly Var[] vars;
    private readonly List<Pair<object, Env>> stack;
    private readonly int[] top;
    private readonly int frame;
    private bool disposed = false;
    internal readonly Trail trail;
    internal bool cut = false;

    […略…]

カット述語そのものの実装は二訂版と同じである。 バックトラックで二度目の yield 値が求められたとき,通常の 0 ではなく, 1 を yield する。

    private class cut_Body: IGoals {
        IEnumerable<int> IGoals.Resolve(Env env) {
            yield return 0;
            yield return 1;
        }
    }

前回と同一のマシン,同一の環境で,同一の Prolog ベンチマークを実行した例を示す。

$ time mono p2.exe path.pro path-query.txt
1: 
 L = [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)]
Done.

real    0m14.812s
user    0m14.429s
sys     0m0.311s
$ 

6. Visual Basic .NET 対応

処理系 六訂版 の tiny_prolog.dll を .NET Framework 2.0 の Visual Basic Version 8.0 から使うと,Goal クラスの If メソッドに対して「class 'TinyProlog.Goal' に同じ名前のメンバが多種類存在するため、'If' があいまいです」というエラーが発生する。 対策として tiny_prolog.cs の 216-217 行

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

削除して tiny_prolog.dll を構築しなおせばよい。 元々このメソッドは Obsolete として削除する予定であった。

下図は Windows XP SP2 上の Visual Basic 2005 Express Edition SP1 での使用例である。 この環境は,入力補完時に tiny_prolog.xml によるドキュメンテーションが表示される点で便利である。


この例では Goal クラスの If メソッドを2箇所で使っている。 一箇所は .[If]() とブラケットで囲んでいるが, もう一箇所は .If(append…) と裸で使っている。 Visual Basic はどちらも受理し,プログラムは意図どおりに動作する。

Paul Vick (Microsoft Corporation): "The Visual Basic Language Specification", Version 8.0 (2005) §2.2 Identifiers によれば
Regular identifiers may not match keywords, but escaped identifiers or identifiers with a type character can. An escaped identifier is an identifier delimited by square brackets. Escaped identifiers follow the same rules as regular identifiers except that they may match keywords and may not have type characters.
とあり,If が Visual Basic のキーワードであることから, ブラケットで囲むのが本来の方法といえる。 現在の Visual Basic 実装ではブラケットで囲まなくてもよいが,これは たまたまの お目こぼし と判断するのが妥当であろう。

もう一つの例として五訂版と六訂版に付属の p0.cs の述語定義と方法2の問合せを,多少の変更を加えて Visual Basic で書き直したプログラム p0b.vb を示す。 パーサの Parse メソッドに与える IEnumerable<string> 引数として文字列の配列を与えているが, 文字列の配列は IEnumerable<string> の典型的な実装のひとつである。

Imports TinyProlog
Imports c = TinyProlog.Core

''' <summary>
''' Prolog インタープリタの実験
''' </summary>
''' <remarks>p0.cs を参照</remarks>
Module P0b
    Sub Main()
        Dim source As String() = { _
            "append([], A, A).", _
            "append([A|X], Y, [A|Z]) :- append(X, Y, Z)."}
        Dim ps As Parser = New Parser()
        For Each r As ParsingResult In ps.Parse(source)
            Console.WriteLine(" > {0} :- {1}.", r.Head, r.Body)
        Next

        Dim append As Pred = ps("append")
        Dim X As Var = New Var("X")
        Dim Y As Var = New Var("Y")
        Dim g As Goal = append(X, Y, c.list("青", "白", "赤"))
        For Each env As Env In c.goals(g)
            Console.WriteLine("X = {0}, Y = {1}", c.Str(env(X)), c.Str(env(Y)))
        Next
    End Sub
End Module

Windows XP SP2 の Cygwin からコンパイルして実行した例を示す。

$ type vbc
vbc is hashed (/cygdrive/c/WINDOWS/Microsoft.NET/Framework/v2.0.50727/vbc)
$ vbc /r:tiny_prolog.dll p0b.vb
Microsoft(R) Visual Basic Compiler Version 8.0.50727.42
for Microsoft(R) .NET Framework version 2.0.50727.42
Copyright (C) Microsoft Corporation.  All rights reserved.

$ ./p0b.exe
 > append([], A, A) :- true.
 > append([A | X], Y, [A | Z]) :- append(X, Y, Z).
X = [], Y = ['青', '白', '赤']
X = ['青'], Y = ['白', '赤']
X = ['青', '白'], Y = ['赤']
X = ['青', '白', '赤'], Y = []
$

ただし, このプログラムを mono 1.2.3.1vbnc (Visual Basic.NET Compiler) に与えても,下記のようにエラーを起こしてコンパイルできない。 Visual Basic Version 8.0 との互換性はまだ十分ではない。

$ vbnc /r:tiny_prolog.dll p0b.vb
Visual Basic.Net Compiler version 0.0.0.4805
Copyright (C) 2004-2007 Rolf Bjarne Kvinge. All rights reserved.


Unexpected error: Array index is out of range.
Compilation took 00:00:01.0429370
$ 

6.1 Visual Basic .NET による組込み述語の作成

Visual Basic による Prolog 組込み述語の作成例として 前述のプログラム p0b.vb からの追加箇所を強調して下記に示す。 追加箇所では,引数値とそれを変数展開した値をコンソールに " watch: … = …" のように表示する述語 watch/1 を定義し, append 述語の第2の節で変数 X の値を調べるために使用する。

Imports TinyProlog
Imports c = TinyProlog.Core

''' <summary>
''' Basic で組込み述語を書く実験
''' </summary>
''' <remarks>p0b.vb を参照</remarks>
Module P0c
    Sub Main()
        Dim source As String() = { _
            "append([], A, A).", _
            "append([A|X], Y, [A|Z]) :- append(X, Y, Z), watch(X)."}
        Dim ps As Parser = New Parser()

        Dim watch As Pred = New Pred("watch")
        Dim Arg As Var = New Var("Arg")
        Dim wcall As [Call] = AddressOf WatchCall
        watch(Arg).If(c.apply(wcall, Arg, Nothing))
        ps("watch") = watch

        For Each r As ParsingResult In ps.Parse(source)
            Console.WriteLine(" > {0} :- {1}.", r.Head, r.Body)
        Next

        Dim append As Pred = ps("append")
        Dim X As Var = New Var("X")
        Dim Y As Var = New Var("Y")
        Dim g As Goal = append(X, Y, c.list("青", "白", "赤"))
        For Each env As Env In c.goals(g)
            Console.WriteLine("X = {0}, Y = {1}", c.Str(env(X)), c.Str(env(Y)))
        Next
    End Sub

    Function WatchCall(ByVal arg As Object, ByVal env As Env) As Object
        Console.WriteLine(" watch: {0} = {1}", c.Str(arg), c.Str(env(arg)))
        Return Nothing
    End Function

End Module

Visual Basic での組込み述語の定義方法は,言語が異なることを除き, 述語集 tiny_prolog_preds.cs に見られるような C# での方法と同じである。 ここでは関数 WatchCall から AddressOf 演算子で TinyProlog.Call デリゲート wcall を作成し,TinyProlog.Core.apply 述語の引数にしている。 定義した述語を Parser インスタンスにインデクサ経由で組み込む (ps("watch") = watch) ことにより,構文解析時に認識される。

Windows XP SP2 の Cygwin からコンパイルして実行した例を示す。 新しく定義した watch 述語により,計算の途中経過の一部が表示されている。 この方法を応用すれば,たとえば迷路探索の経過をグラフィックスで表示することも可能である。

$ vbc /r:tiny_prolog.dll p0c.vb
Microsoft(R) Visual Basic Compiler Version 8.0.50727.42
for Microsoft(R) .NET Framework version 2.0.50727.42
Copyright (C) Microsoft Corporation.  All rights reserved.

$ ./p0c.exe
 > append([], A, A) :- true.
 > append([A | X], Y, [A | Z]) :- append(X, Y, Z), watch(X).
X = [], Y = ['青', '白', '赤']
 watch: [] = []
X = ['青'], Y = ['白', '赤']
 watch: [] = []
 watch: [A | X] = ['白']
X = ['青', '白'], Y = ['赤']
 watch: [] = []
 watch: [A | X] = ['赤']
 watch: [A | X] = ['白', '赤']
X = ['青', '白', '赤'], Y = []
$

*1: Visual Studio の Emacs 互換機能については, Visual Studio 2005 Express Editions についてのメモ 2.「Emacs 使い」編Emacs 風 キーボード マップ スキームを参照。 これを使えば,本物の Emacs と同じく,Tab キーの打鍵等で,構文的に妥当なところまで自動的に字下げできる。 C# で括弧を閉じ忘れたり,複文をブレースで囲まなかったり, といったトリビアルな誤りは,これによりただちに検出される。 実際のコーディングにおける効果は,単文をブレースで冗長に囲むなどの 旧来のささやかで煩雑なバグ予防策を無意味にするほど強力である。 しかし,今回使用した Visual Basic 2005 Express Edition SP1 のコードエディタには,なぜか非空白文字がないと Tab の打鍵が無視されるという奇妙な動作が見られる。 Visual Basic に対し,ここでの評価が厳しい真の理由は, 実は,Tab の不具合により正しい字下げ位置で書き始めることができないという 微妙だが無視できないストレスにある。

7. 処理系 七訂版

処理系 六訂版に対する小改訂である七訂版を下記に与える。

改訂の要点は2点である。

  1. Visual Basic .NET 対応として,obsolete な @if メソッドを廃止した。
  2. Resolve メソッドの戻り値の型を 初版と同じ IEnumerable<bool> に戻した。

Goals クラスの主要部を Debug 関連を省略して示す。 六訂版 と比較されたい。

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

    […略…]

    /// <summary>GetEnumerator() の実質的な本体</summary>
    /// <exception cref="ApplicationException">
    /// 未定義の述語が求解対象として参照された。
    /// </exception>
    public virtual IEnumerable<bool> Resolve(Env env) {
        if (goal.pred.defs == null)
            throw new ApplicationException (goal.pred + " undefined");
        foreach (Def df in goal.pred.defs)
            using (Env dv = new Env (df.vars, env))
                if (Core.Unify(goal, env, df.head, dv, dv.trail, dv)) {
                    foreach (bool q in df.body.Resolve(dv)) {
                        if (! q) {
                           env.cut = true;
                           yield break;
                        }
                        foreach (bool r in rest.Resolve(env)) {
                            if (env.cut)
                                yield break;
                            yield return true;
                        }
                        if (env.cut)
                            yield break;
                    }
                    if (dv.cut)
                        yield break;
                }
    }

    […略…]

カット述語の実装を示す。 バックトラックで二度目の yield 値が求められたとき,通常の true ではなく, false を yield する。

    private class cut_Body: IGoals {
        IEnumerable<bool> IGoals.Resolve(Env env) {
            yield return true;
            yield return false;
        }
    }



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