Java で作る Prolog 処理系

2006.10.3 - 2006.11.3 (鈴)

1. 内部データ構造と手続き

ソース・ファイルへのリンクを下記に示す。 対象は Java バージョン 1.5.0 以降である。 Mac 上の 1.5.0_06, Linux および Windows 上の 1.5.0_09 および 1.6.0-rc-b100 の計 5 本の Java 実装で動作を確認した。

Core.java が定義する Core クラスは 2項組,変数,述語,述語項,環境などのデータ構造を表す クラスと,単一化操作などを実現する静的メソッド (実質的に単なる手続き) から構成される。Core クラス自体のインスタンスは使われない。 事実上の名前空間である。Core の内容の一覧を示す。

$ grep 'class\|static' Core.java
public class Core
    public static class Pair<First, Second> {
    public static String str(Object x) {
    public static class Var {
    public static class Pred {
    private static interface IBody {}
    public static interface ICallback extends IBody {
    public static class Goal {
    public static class Cut extends Goal {
    public static final Cut CUT = new Cut ();
    public static class Goals extends Pair<Goal, Goals>
    public static final class Env {
    public static final class CallbackEnv {
    private static boolean unify(Object x, Env xEnv, Object y, Env yEnv,
    private static class Resolver implements Iterator<Env> {
    private static class ResolveBody {
$ 

Pair<First, Second> クラスは Ruby 版の Cons クラスに相当する2項組クラスである。 Pair<First, Second> クラスのインスタンスと null で可変長リストを構成する。 str メソッドは引数の文字列値を返す。 とりわけ,引数が null のときは空リストを意味する "[]" を返す。

IBody インタフェースは節の本体を表す。 Goals クラスは,Pair<Goal, Goals> で実装された Goal の並びである (注: Java でジェネリック・クラスの型引数に自分自身を再帰的に与えるには, このようにクラス派生すればよい)。 Resolver クラスは Python 版の resolve ジェネレータ, Ruby 版の resolve イテレータに相当する。 残りの対応関係は名前から明らかであろう。 基本的に Python 版 および Ruby 版 の直訳である。

Prolog プログラムを実行する操作, すなわち,与えられたゴールの解を検索する操作は, Java の標準的なイテレータ・インタフェースに統合されている。 X, Y が Prolog 変数を表す Var インスタンス, goals が Prolog のゴールの並びを表す Goals インスタンスであるとき, goals を解決して解の値を表示する処理は,次のように書かれる。

for (Env env: goals) {
    Object x = env.get(X);
    Object y = env.get(Y);
    System.out.println("x = " + x + ", y = " + y);
}

下記は実験用のクラス P0 である。append 述語を定義した後, 上述の for 文を使ってゴールに対する解を検索し,結果を表示する。 ここで,一回だけ検索操作をした後で解の集合の各要素を for 文で一つ一つ表示するのではないことに注意されたい。 for 文をループするごとに新しく解を検索し, 得られたばかりの新しい結果を制御変数 (ここでは env) に渡すのである。

package exp;

import tiny_prolog.Core;

/** Core の実験 */
public class P0 extends Core
{
    static Goal _(Pred pred, Object... terms) {
        return new Goal (pred, terms);
    }
    
    static Goals __(Goal goal) {
        return new Goals (goal, null);
    }
    
    static Pair<Object, Object> cons(Object car, Object cdr) {
        return new Pair<Object, Object> (car, cdr);
    }

    /** append 述語を定義し,実行結果を表示する。 */
    public static void main(String[] args) {
        Var A = new Var ("A");
        Var X = new Var ("X");
        Var Y = new Var ("Y");
        Var Z = new Var ("Z");
        Pred append = new Pred ("append");

        // append([], A, A).
        _(append, null, A, A).si(null);

        // append([A|X], Y, [A|Z]) :- append(X, Y, Z).
        _(append, cons(A, X), Y, cons(A, Z)).si(__(_(append, X, Y, Z)));

        // ?- append(X, Y, [1, 2, 3]).
        Goals goals = __(_(append, X, Y, cons(1, cons(2, cons(3, null)))));

        for (Env env: goals) {
            Object x = env.get(X);
            Object y = env.get(Y);
            System.out.println("x = " + x + ", y = " + y);
        }
    }
}

実行例を示す。 連結して [1, 2, 3] になるリスト X, Y の組み合わせが表示される。

$ java exp.P0
x = null, y = [1, 2, 3]
x = [1], y = [2, 3]
x = [1, 2], y = [3]
x = [1, 2, 3], y = null
$ 

Goals は Iterable<Env> の実装クラスである。 上に述べた for 文では, Iterable<Env> の実装クラスのインスタンスとして goals が受け取られ,その iterator() が実行される。 そして,iterator() の戻り値である Iterator<Env> オブジェクトが hasNext() で true を返す限り,for 文ループが繰り返され, 同オブジェクトの next() の戻り値が制御変数 env に与えられる。 Goals クラスの定義を下記に示す。

    public static class Goals extends Pair<Goal, Goals>
        implements IBody, Iterable<Env>
    {
        public Goals (Goal goal, Goals rest) {
            super(goal, rest);
            assert goal != null;
        }
        
        /** 解決結果の環境を与えるイテレータを構築する。 */
        public Iterator<Env> iterator() {
            return new Resolver (this);
        }

        /** 文字列表現。Pair の具体型だが前後のカッコを省く。*/
        @Override
        public String toString() {
            return toStringWithoutParens();
        }
    }

これから分かるように,ここで iterator() が返す Iterator<Env> の実際のクラスは Resolver である。 その定義を下記に示す。

    private static class Resolver implements Iterator<Env> {
        private Env env;
        private ResolveBody iter;

        private Resolver (Goals body) {
            env = new Env ();
            boolean[] cut = new boolean[] { false };
            iter = new ResolveBody (body, env, cut);
        }

        public boolean hasNext() { 
            return iter.hasNext();
        }

        public Env next() {
            return env;
        }
        
        public void remove() {
            throw new UnsupportedOperationException ();
        }
    }

これを Python の resolve ジェネレータと比較されたい。 また,Goals クラスを Iterable として公開しているから, Iterator である Resolver クラスは非公開にできることに注意されたい。 対外的には iterator() が返す Iterator<Env> の実装クラスという情報だけで十分である。

上記から分かるように,Resolver クラスが対外的に Iterator<Env> として必要なメソッドを用意する一方, 実質的な処理は内部で ResolveBody クラスが担当している。 ResolveBody クラスの定義をここに示す。 ResolveBody クラスは,Python のジェネレータ _resolve_bodyRuby で作る Prolog 処理系 7. に示す手順で有限状態機械にハンドコンパイルして作成したものである。

注: "resolve body" (「(節の) 本体を解決する」) は動詞句であり, Java 言語仕様 §6.8 が定める命名規約にクラス名として適合しない。 しかし,ResolveBody クラスは非公開クラスの内部実装にだけ使われる 二重に非公開のクラスであり, 将来の仕様変更によっても外部に現れる可能性は考えられない。 ここでは他言語実装との共通性を優先した。

2. JavaCC による構文解析器

*1 CUP は,の表紙で有名なコンパイラの教科書
A. W. Appel: Modern Compiler Implementation in Java: Basic Techniques, Cambridge University Press, 1997, ISBN 0-521-58654-2
で使われていた Java のコンパイラ・コンパイラである。以前は http://www.cs.princeton.edu/~appel/modern/java/CUP/ で配布されていた。 C# にも移植されている。

2.1 JavaCC の導入

JavaCC (Java Compiler Compiler) は, http://javacc.dev.java.net/ で BSD ライセンスのもとでソースとバイナリが配布されている。 利用するには, javacc-4.0 のバイナリをダウンロードし,適当な場所に展開すればよい。 Unix 類では,たとえば次のようにすればよい。

$ tar xzf ~/Downloads/javacc-4.0.tar.gz
$ ls javacc-4.0
LICENSE         bin/            doc/            examples/
$ 

展開した javacc-4.0/bin に PATH を通してもよいが, なんら環境変数を設定しなくても,java に PATH が通っていれば, javacc は絶対パスや相対パスで指定するだけで起動できる*2。 無引数で起動すると英語で簡単なヘルプが出力される。

$ type java
java /usr/bin/java
$ ./javacc-4.0/bin/javacc
Java Compiler Compiler Version 4.0 (Parser Generator)

Usage:
    javacc option-settings inputfile

"option-settings" is a sequence of settings separated by spaces.
(...中略...)
The string valued options are:

    OUTPUT_DIRECTORY       (default Current Directory)
    JDK_VERSION       (default 1.4)

EXAMPLE:
    javacc -STATIC=false -LOOKAHEAD:2 -debug_parser mygrammar.jj

$ 

*2 javacc-4.0/bin 下には,Unix 用のシェルスクリプトと Windows 用のバッチファイルがある。 Unix 用のシェルスクリプトは Cygwin にも対応しており, Windows ネイティブの Java を利用して JavaCC を実行できる。 ただし,この Unix 用シェルスクリプトは, パス名に空白が含まれていると正しく起動できない。

2.2 文法ファイル Prolog.jj

文法ファイル (grammar file) へのリンクを下記に示す。

javacc に文法ファイルを与えると, 構文解析器クラスと各種補助クラスの Java ソース・ファイルが生成される。

$ ./javacc-4.0/bin/javacc -OUTPUT_DIRCTORY=parser Prolog.jj
Java Compiler Compiler Version 4.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file Prolog.jj . . .
Warning: Output directory "parser" does not exist. Creating the directory.
Note: UNICODE_INPUT option is specified. Please make sure you create the parser/
lexer using a Reader with the correct character encoding.
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated with 0 errors and 1 warnings.
$ ls parser
ParseException.java             SimpleCharStream.java
Prolog.java                     Token.java
PrologConstants.java            TokenMgrError.java
PrologTokenManager.java
$ 

文法ファイルは (コメントを別にして) オプション指定で始まる。 STATIC を false にすることで, 生成される構文解析器クラスのメソッドやフィールドが 非 static になる (つまり,普通のクラスとして生成されるようになる)。 UNICODE_INPUT を true にすることで, 構文解析器の入出力にエンコーディングを指定して, 非 ASCII 文字 (例えば日本語のかなと漢字) を利用できるようになる。 もしも必要なければ,オプション指定全体を省略してよい。 また,オプション指定をコマンド行から与えてもよい。

options {
    JDK_VERSION="1.5.0";
    STATIC=false;
    UNICODE_INPUT=true;
}

PARSER_BEGIN(Prolog)

PARSER_BEGIN には,生成する Java ソース・ファイルのベース名を与える。 ここから PARSER_END までの内容が,ベース名 + ".java" として出力される。 この例では "Prolog.java" が出力される。 したがって,普通はここから PARSER_END までのあいだで同名の公開クラス (この例では Prolog) を定義する。 補助的なソース・ファイルのいくつかも,このベース名をもとに出力される。

package tiny_prolog;

import java.util.Map;

/** Prolog 処理系。
 * Core に構文解析処理を追加したクラス。
 * 変数表と述語表をもつ。
 * <p>
 * 典型的には read() メソッドで1論理行の入力を読む。
 * この入力で節を与えると,述語表に述語が定義される。
 * この入力で問い合わせを与えると,戻り値に Goals インスタンスが返される。
 * この Goals インスタンスをイテレートすれば処理系を駆動できる。
 */
public class Prolog extends Core
{
    /** 変数表。要初期化。*/
    public Map<String, Var> vars;

    /** 述語表。要初期化。*/
    public Map<String, Pred> preds;

    /** 内部関数。変数名に対応する Var インスタンスを返す。
     * なければ変数表に登録する。
     */
    private Var getVar(String name) {
        (...略...)
    }

    /** 内部関数。述語名に対応する Pred インスタンスを返す。
     * なければ述語表に登録する。
     */
    private Pred getPred(String name) {
        (...略...)
    }

    /** read メソッドの結果 */
    public static class Read { // 過去分詞... What has been _read_
        /** 問い合わせ以外ならば null */
        public final Goals goals;
        /** ファイルの終端ならば true */
        public final boolean isEOF;

        public Read (Goals goals, boolean isEOF) {
            this.goals = goals;
            this.isEOF = isEOF;
        }
    }
}
PARSER_END(Prolog)

Prolog クラスには,上記の内容に加えて, 非終端記号に対応するメソッドが,これ以降の定義内容にしたがって追加される。 コメント中で言及されている read() はそのようなメソッドのひとつである。 また,フィールドやコンストラクタ等も追加される。

2.3 字句解析の定義の実際

PARSER_END に続けて,入力テキストの具体的な構成要素となる終端記号, すなわちトークンを定義する。空白文字やコメントの処理もここで与える。 つまり,字句解析の処理全般をここで定義する。

空白文字は読み飛ばすこととする。

SKIP: { " " | "\t" | "\f" | "\r" | "\n" }

/* ではじまるコメントは */ まで入れ子不可で複数行にまたがるとする。 MORE による定義は,次の字句へと読み込みを継続させる。 字句解析は状態機械的に実行され,ふだんは DEFAULT 状態にある。 入力テキストの "/*" により COMMENT_TEXT 状態に遷移する。 この状態で "*/" に遭遇すると,それまで継続されていた読み込み内容を COMMENT というスペシャル・トークンにまとめて,通常の DEFAULT モードに遷移する。 COMMENT_TEXT 状態におけるそれ以外の任意の文字の出現は ~[] とマッチする。

/* 複数行コメントは C と同じ */
MORE: { "/*": COMMENT_TEXT }
<COMMENT_TEXT> SPECIAL_TOKEN: { <COMMENT: "*/">: DEFAULT }
<COMMENT_TEXT> MORE: { < ~[] > }

SPECIAL_TOKEN で定義されるスペシャル・トークンのオブジェクトは, その後に出現する通常のトークンに対する Java オブジェクトのフィールドに格納されるから, 必要ならば処理系から参照することができる。 しかし,それ以外,構文解析に影響を与えることなく無視される。 つまり,スペシャル・トークンは典型的にはコメントを実装するために使われる。 "%" から行末までは1行コメントを表すスペシャル・トークン SINGLE_LINE_COMMENT とする。 (~["\n"])* は改行文字 "\n" 以外の任意の文字の 0 回以上の繰り返しとマッチする。

/* 1行コメントは % から行末まで */
SPECIAL_TOKEN: { <SINGLE_LINE_COMMENT: "%" (~["\n"])* "\n" > }

通常のトークンを定義する。ここでは,さしあたり動くものを作ることを目標に, ごく簡略化した定義を用いる。 大文字ではじまる英数字 (下線も含む) を変数 VARIABLE とし, 小文字で始まる英数字 (ここでは識別子 IDENTIFIER) と区別する。 文字列 STRING はシングルクォートで囲まれ,改行を含めないものとする。 十進数 DECIMAL は "0",または, 省略可能な負号 "-" の後 "1" から "9" までの 1 数字に "0" から "9" までの数字が 0 回以上繰り返されるとする。

TOKEN: {
    <VARIABLE: ["A"-"Z"] (["a"-"z", "A"-"Z", "0"-"9", "_"])* >
  | <IDENTIFIER: ["a"-"z"] (["a"-"z", "A"-"Z", "0"-"9", "_"])* >
  | <STRING: "'" (~["'", "\n"])* "'">
  | <DECIMAL: "0" | (("-")? ["1"-"9"] (["0"-"9"])*) >
  | <LBRACKET: "[">
  | <RBRACKET: "]">
  | <CONS: "|">
  | <LPAREN: "(">
  | <RPAREN: ")">
  | <IF: ":-">
  | <PERIOD: ".">
  | <COMMA: ",">
  | <KUT: "!">
  | <QUERY: "?-">
}

2.4 構文解析の定義の実際

構文規則とそれに対するアクションを記述した非終端記号の定義が, 文法ファイルの主要な内容である。 Prolog.jj の非終端記号の拡張 BNF (Backus-Naur Form) を示す (この表は JavaCC の補助コマンド javacc-4.0/bin/jjdocProlog.jj を与えて作成した 同ファイルの内容の要約である)

term ::= <VARIABLE>
| <STRING>
| <DECIMAL>
| goal_or_id
| list
list ::= <LBRACKET> ( list2 )? <RBRACKET>
list2 ::= term ( ( <COMMA> list2 ) | ( <CONS> term ) | )
goal_or_id ::= <IDENTIFIER> ( args | )
args ::= <LPAREN> ( term ( <COMMA> term )* )? <RPAREN>
goal ::= <IDENTIFIER> ( args | )
goals ::= ( goal | <KUT> ) ( ( <COMMA> goals ) | )
clause ::= goal ( <IF> goals )? <PERIOD>
read ::= clause
| <QUERY> goals <PERIOD>
| <EOF>

各非終端記号に対して同名の Java メソッドが作られる。 たとえば,下記の「項」の定義から, Object を戻り値の型とする term() メソッドが生成されて, Prolog クラスに追加される。

/* 項 */
Object term():
{
    Token t;
    Object x;
}
{
    t = <VARIABLE> { return getVar(t.image); }
  | t = <STRING> { return t.image.substring(1, t.image.length() - 1); }
  | t = <DECIMAL> { return new Integer (t.image); }
  | x = goal_or_id() { return x; }
  | x = list() { return x; }
}

最初の波カッコの中ではメソッドのローカル変数を宣言する。 次の波カッコの中では構文とそのアクションを定義する。 構文の定義には,非終端記号と, 終端記号,つまりトークンを利用できる。

t = <VARIABLE> { return getVar(t.image); } は,入力テキストに出現したのがトークン VARIABLE だったとき, そのオブジェクトを t に代入して, return getVar(t.image); を実行する,という意味である。 image フィールドはトークンに対応するテキスト文字列 (この場合,大文字ではじまる英数字) を保持する。

トークン STRING に対しては,t.image の最初と最後の文字を削って 文字列両端のシングルクォートを省いてから return する。

トークン DECIMAL に対しては, new Integer (t.image) で得られた整数値を return する。

非終端記号 goal_or_id と list に対しては, 対応するメソッドの戻り値をそのまま return する。

非終端記号 list は Prolog のリスト構文を定義する。 メソッド list() はアクションの結果として Pair<Object, Object> オブジェクトを返す。

/* 項としての リスト */
Pair<Object, Object> list():
{ Pair<Object, Object> r = null; }
{
    <LBRACKET> (r = list2())? <RBRACKET>
    { return r; }
}

/* 項としての リスト のカッコの内部 */
Pair<Object, Object> list2():
{
    Object x, y;
    Pair<Object, Object> r;
}
{
    x = term()
    (
     (<COMMA> y = list2() { r = new Pair<Object, Object> (x, y); })
     | (<CONS> y = term() { r = new Pair<Object, Object> (x, y); })
     | { r = new Pair<Object, Object> (x, null); }
    ) 
   { return r; }
}

[a, b, c] のように COMMA で区切られた Prolog のリストから

    new Pair<Object, Object> 
        (a, new Pair<Object, Object> 
            (b, new Pair<Object, Object>
                (c, null)))

のようなオブジェクトを構築するため, カッコの内部に対応する非終端記号 list2 を定義する。 list2() は第1引数 x と第2引数 y または null から Pair<Object, Object> オブジェクトを構築する。

上の例でいえば a, b, c に対し, まず "a" が x = term() で処理され, 次に "," がトークン COMMA とマッチする。 そして b, c が再帰的に y = list2() で処理される。 こうして得られた x, y に対し,アクション { r = new Pair<Object, Object> (x, y); } が実行され,最後に { return r; } により r が返される。

[a | b] のように要素 a と残りのリスト b からなるリストについては,"|" がトークン CONS とマッチし, 結果として new Pair<Object, Object> (a, b) が返される。

述語項または識別子に対する非終端記号 goal_or_id の定義を示す。 左右の丸カッコ LPAREN, RPAREN で囲まれた引数 (args) があるかどうかで 両者を区別する。 述語項ならば Goal オブジェクトを構築して返す。 簡単のため,識別子ならば単純に文字列と同一視し,戻り値として t.image を返す。

/* 項としての 述語項 または 識別子 (ただし今は文字列と同一視する)。
   丸カッコがあるかどうかで両者を区別する。
*/
Object goal_or_id():
{
    Token t;
    Object[] a;
}
{
    t = <IDENTIFIER>
    (   a = args() { return new Goal (getPred(t.image), a); }
      | { return t.image; /* String */ }
    )
}

/* 述語項の引数 */
Object[] args():
{
    java.util.ArrayList<Object> a = new java.util.ArrayList<Object> ();
    Object x;
}
{
    <LPAREN>  (
       x = term() { a.add(x); }
       (<COMMA> x = term() { a.add(x); })* 
    )? <RPAREN>
    { return a.toArray(); }
}

他の述語項の引数になっていない述語項 (goal) では丸カッコは省略可能とする。 この非終端記号は節や問い合わせに使われる。

/* 他の述語項の引数になっていない述語項。丸カッコは省略可能 */
Goal goal():
{
    Token t;
    Object[] a;
}
{
    t = <IDENTIFIER>
    (
       a = args()
     | { a = new Object[0]; }
    )
    { return new Goal (getPred(t.image), a); }
}

述語項の並び (goals) は,前述の list2 とよく似た再帰的定義である。メソッド list2() が構築して返すのが Pair<Object, Object> であること, goals() が構築して返すのが Pair<Goal, Goals> の派生クラス Goals であることに注意されたい。 どちらも並びを右から結合する必要があることから,この類似性は説明できる。

/* 述語項の並び。カット演算子も含む */
Goals goals():
{
    Goal g;
    Goals r;
}
{
      (
        g = goal() 
      | <KUT> { g = CUT; }
      )
      (
        (<COMMA> r = goals() { r = new Goals (g, r); })
      | { r = new Goals (g, null); }
      )
     { return r; }
}

節 (clause) のメソッドの戻り値型は void である。 アクションとして,Goal クラスの si メソッドによる述語定義をするから, 戻り値は必要ない。

/* 節 */
void clause():
{
    Goal head;
    Goals body = null;
}
{
    head = goal()
    ( <IF> body = goals() )?
    <PERIOD>
    { head.si(body); }
}

1 論理行の入力に対応する非終端記号を read として定義する。 1 論理行ずつ処理するインタープリタでは,これを開始記号として利用できる。 Prolog.jj の 冒頭付近にある Prolog クラスのドキュメンテーション・コメントを参照されたい。

/* 節,または ?- で始まる問い合わせ,またはファイル終端 */
Read read():
{
    Goals body;
}
{
    clause() {
        return new Read (null, false);
    }
    | <QUERY> body = goals() <PERIOD> {
        return new Read (body, false);
    }
    | <EOF> {
        return new Read (null, true);
    }
}

2.5 簡単な対話型インタープリタ

Prolog クラスを利用した簡単な対話型インタープリタの実装例 P1.java を示す。

package exp;

import java.util.HashMap;
import tiny_prolog.Prolog;

/** 簡単な対話型インタープリタの実装例 */
public class P1
{
    public static void main(String[] args) throws Exception
    {
        System.out.println("Tiny Prolog in Java:  Input clauses or ?- goals.");
        Prolog ip = new Prolog (System.in);
        ip.vars = new HashMap ();
        ip.preds = new HashMap ();
        for (;;) {
            Prolog.Read r = ip.read();
            if (r.isEOF) break;
            if (r.goals != null) {
                int i = 0;
                for (Prolog.Env env: r.goals) {
                    i++;
                    System.out.println(i + " " + env.get(r.goals));
                }
                System.out.println((i == 0) ? "No" : "Yes");
            }
        }
        System.out.println("bye");
    }
}

利用例を示す。節の入力と問い合わせを受け付ける。 問い合わせるときは利用者が自分で ?- を入力する。 インタープリタはすべての解をゴールごと番号をつけて表示し, (検索の終了を示すため) 最後に Yes と表示する。 解がない場合は No と表示する。

$ java exp.P1
Tiny Prolog in Java:  Input clauses or ?- goals.
append([], A, A).
append([A|X], Y, [A|Z]) :- append(X, Y, Z).
?- append(X, Y, [1, 2, 3]).
1 append([], [1, 2, 3], [1, 2, 3])
2 append([1], [2, 3], [1, 2, 3])
3 append([1, 2], [3], [1, 2, 3])
4 append([1, 2, 3], [], [1, 2, 3])
Yes
man(adam).
parent(adam, cain).
parent(adam, abel).
father(P, C) :- man(P), parent(P, C).
?- father(X, Y).
1 father(adam, cain)
2 father(adam, abel)
Yes
?- father(X, cain).
1 father(adam, cain)
Yes
?- father(X, adam).
No

漢字などの非 ASCII 文字はシングルクォートで囲んだ文字列として入力できる。 プログラムでは特に文字エンコーディングを指定していないから, Java 実装のデフォルト・エンコーディングが使われる。 Mac 上で UTF-8 端末を利用している場合など, Java 実装のデフォルト・エンコーディングと利用環境が一致しない場合は, 陽に file.encoding を指定する必要がある (指定しない場合,入力によっては奇妙な文字化けを起こす)

$ java -Dfile.encoding=UTF-8 exp.P1

このプログラムはほぼ最小限の実装例である。改造のヒントを示す。

  1. 解としてゴール全体ではなく変数値だけ表示したい場合は, for 文の制御変数 env に含まれるキーを参照するようにすればよい。 キーを得るためには,フィールド情報を公開するように Core.java の Env クラスを改造する必要がある。 注: この方法の妥当性は実装に依存する。 変数どうしの単一化の実装によっては,必ずしもゴールの変数がすべて env に含まれるとは限らない。より妥当な方法については 3.1 を参照せよ。
  2. 複数の解を求めるかどうか制御したい場合は, for 文のループ内でキー入力を行い,break すればよい。 中断されたループのイテレータは,正常終了したループのイテレータと同じく, やがてガーベジ・コレクトされる。
  3. 入力の構文誤りで終了しないようにするには,適切に try 文で囲む必要がある。
  4. プログラムで入出力の文字エンコーディングを指定するには, たとえば java.io.Reader, java.io.Writer の実装クラスを使えばよい。 文字列オブジェクトを入力テキストとして与えたい場合は, java.io.StringReader を使えばよい。

2.6 ここまでのまとめ

Linux 上でのコンパイルから実行までの操作例を示す。 JDK 1.5.0 以降をインストールし, JavaCC をダウンロードしておく。 Windows の Cygwin 等,他の Unix 類でも同様の手順である。 ソース・ファイルに Shift_JIS を使っているため, デフォルト・エンコーディングの異なる Linux で javac にオプションとして -encoding Shift_JIS を与えている点に注意されたい。

$ unzip ../p1-all.zip 
Archive:  ../p1-all.zip
  inflating: Core.java               
  inflating: Prolog.jj               
  inflating: P0.java                 
  inflating: P1.java                 
  inflating: append.pl               
$ tar xzf ../javacc-4.0.tar.gz 
$ ls
Core.java  P0.java  P1.java  Prolog.jj  append.pl  javacc-4.0/
$ mkdir parser
$ ./javacc-4.0/bin/javacc -OUTPUT_DIRECTORY=parser Prolog.jj 
Java Compiler Compiler Version 4.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file Prolog.jj . . .
Note: UNICODE_INPUT option is specified. Please make sure you create the parser/
lexer using a Reader with the correct character encoding.
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated successfully.
$ ls . parser
.:
Core.java  P0.java  P1.java  Prolog.jj  append.pl  javacc-4.0/  parser/

parser:
ParseException.java   PrologTokenManager.java  TokenMgrError.java
Prolog.java           SimpleCharStream.java
PrologConstants.java  Token.java
$ javac -encoding Shift_JIS -d . Core.java
$ javac -encoding Shift_JIS -Xlint:unchecked -d . parser/*.java
parser/Prolog.java:422: 警告: [unchecked] raw 型 java.util.Vector のメンバとして
の addElement(E) への無検査呼び出しです。
        jj_expentries.addElement(jj_expentry);
                                ^
警告 1 個
$ ls
Core.java  P1.java    append.pl    parser/
P0.java    Prolog.jj  javacc-4.0/  tiny_prolog/
$ ls tiny_prolog/
Core$1.class            Core$Pair.class         Prolog.class
Core$CallbackEnv.class  Core$Pred.class         PrologConstants.class
Core$Cut.class          Core$ResolveBody.class  PrologTokenManager.class
Core$Env.class          Core$Resolver.class     SimpleCharStream.class
Core$Goal.class         Core$Var.class          Token.class
Core$Goals.class        Core.class              TokenMgrError.class
Core$IBody.class        ParseException.class
Core$ICallback.class    Prolog$Read.class
$ javac -encoding Shift_JIS -d . P0.java
$ javac -encoding Shift_JIS -d . P1.java
$ ls
Core.java  P1.java    append.pl  javacc-4.0/  tiny_prolog/
P0.java    Prolog.jj  exp/       parser/
$ ls exp
P0.class  P1.class
$ java exp.P0
x = null, y = [1, 2, 3]
x = [1], y = [2, 3]
x = [1, 2], y = [3]
x = [1, 2, 3], y = null
$ java exp.P1 < append.pl
Tiny Prolog in Java:  Input clauses or ?- goals.
1 append([], [1, 2, 3, 4], [1, 2, 3, 4])
2 append([1], [2, 3, 4], [1, 2, 3, 4])
3 append([1, 2], [3, 4], [1, 2, 3, 4])
4 append([1, 2, 3], [4], [1, 2, 3, 4])
5 append([1, 2, 3, 4], [], [1, 2, 3, 4])
Yes
bye
$

3. インタープリタの拡張

ここでは対話型インタープリタを拡張する。 実装例のソース・ファイルへのリンクを下記に示す。 コンパイル方法は P1.java と同様である。

P2.java のドキュメンテーション・コメントからインタープリタの使用法を引用する。

コマンド行引数の書式は次のとおり:

[-e encoding] file... [-]

-e オプションで文字エンコーディングを指定できる。以降,引数があるときは, その名前のファイルの内容を Prolog プログラムとして非対話的に順に実行し, "-" が現れたら,あるいは引数がなければ,対話セッションに入る。

コマンド行の例を示す。これは utf-8 で test.pl を実行した後, utf-8 で対話セッションに入る。

java exp.P2 -e utf-8 test.pl -

非対話的実行での "?-" で始まる問い合わせに対し,解がなければ No を出力する。 解があれば 1 から始まる番号を接頭して問い合わせの具体値を出力し, Yes を出力する。

対話セッションでの節の入力には Ok で答える。 対話セッションでの "?-" で始まる問い合わせに対し, 問い合わせに含まれる変数の値を出現順に表示する。 ここでセミコロンが入力されると次の解を検索する。 解が (もう) ないとき No で答える。それ以外は Yes で答える。 EOF に対し,対話セッションは Bye で答えて終了する。

前節 2.6 から引き続き,コンパイルし,実行した例を示す。 コンパイル後の最初の実行では append.pl を非対話的に実行して終了している。 その次の実行ではコマンド行引数として append.pl に続けて "-" を与えることで, append.pl の非対話的な実行の後,そのまま対話セッションに入っている。 対話セッションでは append(L, R, [a, b, c]) の解を問い合わせている。

$ javac -encoding Shift_JIS -d . P2.java
$ java exp.P2 append.pl
1 append([], [1, 2, 3, 4], [1, 2, 3, 4])
2 append([1], [2, 3, 4], [1, 2, 3, 4])
3 append([1, 2], [3, 4], [1, 2, 3, 4])
4 append([1, 2, 3], [4], [1, 2, 3, 4])
5 append([1, 2, 3, 4], [], [1, 2, 3, 4])
Yes
$ java exp.P2 append.pl -
1 append([], [1, 2, 3, 4], [1, 2, 3, 4])
2 append([1], [2, 3, 4], [1, 2, 3, 4])
3 append([1, 2], [3, 4], [1, 2, 3, 4])
4 append([1, 2, 3], [4], [1, 2, 3, 4])
5 append([1, 2, 3, 4], [], [1, 2, 3, 4])
Yes
Tiny Prolog in Java:  Input clauses or ?- goals in EUC-JP-LINUX.
?- append(L, R, [a, b, c]).
L = []
R = [a, b, c] ;

L = [a]
R = [b, c] ;

L = [a, b]
R = [c] ;

L = [a, b, c]
R = [] ;

No

対話セッションを終了するには Control-D の打鍵などで EOF を入力する。

コマンド行引数 String[] args に対する exp.P2 内部のファイルの読込みと非対話的実行の処理の骨組みを示す。

String encoding = System.getProperty("file.encoding");
if (...) {
    encoding = args[1];  // utf-8 や shift_jis など
    ...
}
...
PrintWriter writer = new PrintWriter
                         (new OutputStreamWriter (System.out, encoding), true);
...
Sring arg = null;
for (...) {
    arg = args[i];       // ファイル名
    ...
    Reader reader = new InputStreamReader(new FileInputStream (arg), encoding);
    try {
        Prolog ip = new Prolog (reader);
        ...
        for (;;) {
            Prolog.Read read = ip.read();
            if (read.isEOF) break;
            ...
        }
    } finally {
        reader.close();
    }
}

対話セッション処理の骨組みを示す。 キー入力での字句や構文の誤りから ip.read() が TokenMgrError や ParseException のオブジェクトを送出したときは, catch 節で捕捉し,ip.ReInit メソッドで再初期化する。

if (arg == null) {
    Reader reader = new InputStreamReader (System.in, encoding);
    writer.println("Tiny Prolog in Java:  " +
                   "Input clauses or ?- goals in " + encoding + ".");
    ...
    Prolog ip = new Prolog (reader);
    ...
    for (;;) {
        ...
        try {
            Prolog.Read read = ip.read();
            if (read.isEOF) break;
            if (read.goals == null) {
                writer.println("Ok");
            } else {
                 ...
            }
        } catch (ParseException ex) {
            ...
            ip.ReInit(reader);
        } catch (TokenMgrError ex) {
            ...
            ip.ReInit(reader);
        }
    }
    writer.println("Bye");
}

3.1 解の表示

対話セッションでは,一般的な Prolog 処理系と同じように,解を表示するとき, 問い合わせに含まれる変数の具体値を出現順に出力する。

インタープリタの変数表 ip.vars の中に,問い合わせに含まれる変数がすべて含まれ, かつそれ以外の変数が含まれないようにするため, 変数表を ip.vars.clear() で空にしてから, ip.read() で問い合わせを読み込む。 この変数表を解の表示に使う。 Prolog の変数の有効範囲は一つの節,または一つの問い合わせに限られているから, ip.read() の実行ごとに変数表を空にすることができる。

問い合わせでの出現順序どおりに変数を表示するため, 変数表 ip.vars の実装クラスとして, エントリの追加順序を保存する java.util.LinkedHashMap を用いる。 いずれにせよ変数表は,構文解析後の狭義の Prolog プログラムの実行過程である for (env: read.goals) {...} のイテレーションには直接関与しないから, その実装クラスが何であるかは実行時の性能にほとんど影響しない。

    Prolog ip = new Prolog (reader);
    ip.vars = new LinkedHashMap<String, Prolog.Var> ();
    ip.preds = preds;
    ...
    for (;;) {
        ip.vars.clear();
        try {
            Prolog.Read read = ip.read();
            if (read.isEOF) break;
            if (read.goals == null) {
                writer.println("Ok");
            } else {
                boolean failed = true;
                for (Prolog.Env env: read.goals) {
                    int size = ip.vars.size(); // ゴール内の変数の個数
                    if (size > 0) {
                        int j = 0; // 最終行で改行しないためのカウンタ
                        for (Map.Entry<String, Prolog.Var> entry:
                                ip.vars.entrySet()) {
                            String name = entry.getKey();
                            Prolog.Var var = entry.getValue();
                            Object x = env.get(var);
                            writer.print(name + " = " + Prolog.str(x));
                            j++;
                            if (j < size) writer.println();
                            else writer.print(" ");
                            writer.flush();
                        }
                        // ";" が入力されたら検索を続行する。
                        ...
                        if (...) { ...; continue; }
                    }
                    failed = false;
                    break;
                }
                writer.println((failed) ? "No" : "Yes");
            }
        } catch (...) { ... }
    }

3.2 組込み述語

P2.java のドキュメンテーション・コメントから組込み述語の説明を引用する。

下記の組込み述語をもつ。ただし A, B は具体的な整数とする。

P2 クラスの main メソッドでは次のようにして組込み述語を述語表に追加する。

Map<String, Prolog.Pred> preds = new HashMap<String, Prolog.Pred> ();
...
predefine(preds, writer);

実際に述語表に組込み述語を追加する処理を示す。 ここでは Prolog 変数の同一性を Java 変数 A, B, X の同一性で実現しているから,変数表は不要である。

    /** 述語項を作成するための便宜関数 */
    static Prolog.Goal goal(Prolog.Pred pred, Object... terms) {
        return new Prolog.Goal (pred, terms);
    }

    /** 述語表 preds に組込み述語を追加する。
     * 引数 writer は印字を行う述語で使われる。
     */
    static void predefine(Map<String, Prolog.Pred> preds,
                          final PrintWriter writer)
    {
        final Prolog.Var A = new Prolog.Var ("A");
        final Prolog.Var B = new Prolog.Var ("B");
        final Prolog.Var X = new Prolog.Var ("X");

        Prolog.Pred write = new Prolog.Pred ("write");
        goal(write, A).calls(new Prolog.ICallback () {
                public boolean call(Prolog.CallbackEnv env) {
                    Object a = env.get(A);
                    String s = (a == null) ? "[]" : a.toString();
                    writer.print(s);
                    return true;
                }
            });
        preds.put("write", write);

        Prolog.Pred nl = new Prolog.Pred ("nl");
        goal(nl).calls(new Prolog.ICallback () {
                public boolean call(Prolog.CallbackEnv env) {
                    writer.println();
                    return true;
                }
            });
        preds.put("nl", nl);

        Prolog.Pred le = new Prolog.Pred ("le");
        goal(le, A, B).calls(new Prolog.ICallback () {
                public boolean call(Prolog.CallbackEnv env) {
                    int a = (Integer) env.get(A);
                    int b = (Integer) env.get(B);
                    return a <= b;
                }
            });
        preds.put("le", le);

        Prolog.Pred subt = new Prolog.Pred ("subt");
        goal(subt, A, B, X).calls(new Prolog.ICallback () {
                public boolean call(Prolog.CallbackEnv env) {
                    int a = (Integer) env.get(A);
                    int b = (Integer) env.get(B);
                    return env.unify(X, a - b);
                }
            });
        preds.put("subt", subt);
    }

*3 特定の一言語からの視点に限られている点を除けば, http://www.shiro.dreamhost.com/scheme/trans/icad-j.html は「人間コンパイラ」や (デザイン) 「パターン」の問題に関する 極めて的確な指摘を含んでいると思われる。

3.3 実行例

tak 関数 tak.txt (MacBook Pro, Core Duo 2GHz, 1GB, OS X 10.4.8, Java 1.5.0_06)

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

eq(X, X).

tak(X, Y, Z, A) :-
        le(X, Y), !, eq(Z, A).
tak(X, Y, Z, A) :- 
        subt(X, 1, X1),
        subt(Y, 1, Y1),
        subt(Z, 1, Z1),
        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 java -Xmx110m exp.P2 tak.txt
1 tak(4, 2, 0, 1)
Yes
1 tak(7, 5, 1, 2)
Yes
1 tak(18, 12, 6, 7)
Yes

real    0m3.489s
user    0m3.191s
sys     0m0.214s
$  

ハノイ (河内) の塔 hanoi.txt

$ nkf hanoi.txt
/* 河内の塔 -*- mode: prolog -*-
*/
write_move(X, A, B) :-
        write('move '), write(X),
        write(' from '), write(A),
        write(' to '), write(B), nl.

hanoi([], A, B, C).
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 に移す。

?- hanoi([base, '2nd', 'top'], 'Left', 'Center', 'Right').
$ java exp.P2 -e utf-8 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 hanoi([base, '2nd', top], 'Left', 'Center', 'Right')
Yes
Tiny Prolog in Java:  Input clauses or ?- goals in utf-8.
?- 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 中央の柱
Yes
Control-DBye
$

Control-D は実際には画面表示されない。

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



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