The Art of Prolog: Prologの技芸

The Art of Prolog: Prologの技芸

「The Art of Prolog: Prologの技芸」より。

Prolog言語を初めて理解したとき、人々はそれまでの考えを一変させられる。一見単純な形式を持つこの言語は、無限の潜在能力と技術的可能性を秘めている。しかしその本質を適切に伝える書物は少ない。世に出ている解説書のほとんどは入門的なものである。
本書は、多くの応用例と高度で実践的なプログラミング技法について分かりやすく説明することにより、Prologの本質を理解し、使いこなすことを望んでいる技術者の知的ニーズに応える。
本書は、もともと、Plorogの高度な「プログラミングを教える」という目的で、Leon Sterling,Hhud Shaplogによって、大学院学生向けの講義のために書かれ、MITPRESSから「Art of Prolog」として出版された。

目次は以下となる。

第1部　論理プログラム
基本構成要素
データベース・プログラミング
再帰プログラミング
論理プログラムの計算モデル
論理プログラムの理論
 
第2部　Prolog言語
純Prolog
純Prologプログラミング
算術
構造探査
メタ論理述語
カットと否定
論理外述語
実践論
 
第3部　Prologプログラミング上級技法
非決定性プログラミング
不完備データ構造
限定節文法による構文解析
2階プログラミング
探索技法
メタ・インタプリンタ
 
第4部　応用
ゲーム遊戯プログラム
信用評価エキスパート・システム
方程式を解くプログラム
コンパイラ

以下にこれらの具体的な例について述べる。

prologを用いたデータベースプログラミング

Prologは論理プログラミング言語であり、データベースプログラミングにも使用することができる。Prologでは、事実と規則を定義し、それらを使ってクエリを実行してデータベースを検索することができる。

以下に、Prologを使用した簡単なデータベースプログラミングの例を示す。

% 人々の関係を定義する
親子関係(田中太郎, 田中花子).
親子関係(田中太郎, 田中一郎).
親子関係(田中花子, 田中次郎).

% 兄弟関係を定義する
兄弟関係(X, Y) :- 親子関係(Z, X), 親子関係(Z, Y), X \= Y.

% クエリの実行
?- 親子関係(親, 子).    % 親子関係の検索
?- 兄弟関係(兄, 弟).    % 兄弟関係の検索

上記の例では、親子関係という事実を定義し、兄弟関係という規則を定義している。そして、クエリを使って親子関係や兄弟関係を検索している。

Prologでは、クエリを実行すると、システムは与えられた規則と事実に基づいて探索を行い、クエリにマッチする解を見つける。マッチする解が複数ある場合、システムはバックトラックを行い、すべての解を見つけることができる。

prologを用いた再帰プログラミング

Prologは再帰的なプログラミングに非常に適している。再帰的なルールを定義することで、複雑な問題を効果的に解決することができる。以下に、Prologを使用した再帰プログラミングの例を示す。

% 自然数の合計を計算する
合計(0, 0).                            % ベースケース: 0の合計は0
合計(N, Sum) :- N > 0,                  % 再帰ケース: Nが0より大きい場合
                N1 is N - 1,             % Nを1減らす
                合計(N1, Sum1),         % N1の合計を計算する
                Sum is Sum1 + N.         % Sum1にNを足して合計を計算する

% リストの要素数を計算する
要素数([], 0).                          % ベースケース: 空のリストの要素数は0
要素数([_|Tail], Count) :-              % 再帰ケース: リストの先頭要素を無視して、残りの要素数を計算する
                           要素数(Tail, Count1),   % 残りの要素数を計算する
                           Count is Count1 + 1.    % Count1に1を足して要素数を計算する

上記の例では、合計と要素数という再帰的なルールを定義している。合計ルールは与えられた数の合計を計算し、要素数ルールは与えられたリストの要素数を計算している。

再帰的なルールでは、ベースケース（終了条件）と再帰ケース（再帰呼び出し）が必要で、ベースケースでは再帰の終了条件を定義し、再帰ケースでは問題をより小さな部分問題に分割し、再帰的に解決する。

例えば、合計ルールでは、ベースケースとして0の合計が0であることを定義し、再帰ケースでは与えられた数を1ずつ減らしながら再帰的に合計を計算している。

同様に、要素数ルールでは、ベースケースとして空のリストの要素数が0であることを定義し、再帰ケースではリストの先頭要素を無視して残りの要素数を再帰的に計算している。

再帰プログラミングは、問題を自然な形式で表現し、効率的な解決策を見つけるための強力な手法であり、Prologの再帰機能を駆使して、様々な問題を解決することができる。

prologを用いたメタ論理述語

メタ論理述語（Metapredicate）は、Prologのパラメータとして他の述語を取る述語となる。メタ論理述語を使用することで、より一般的な述語や一般化された操作を定義することができ、これにより、コードの再利用性や柔軟性が向上する。

以下に、Prologを使用してメタ論理述語を定義する例を示す。この例では、与えられた述語をリストの要素に適用するメタ論理述語maplist/3を定義している。

% maplist/3の定義
maplist(_, [], []).                 % ベースケース: 空のリストの場合、結果も空のリストとなる
maplist(Pred, [X|Xs], [Y|Ys]) :-    % 再帰ケース: リストの先頭要素に述語を適用し、残りの要素に再帰的に適用する
                                  call(Pred, X, Y),   % PredをXに適用してYを得る
                                  maplist(Pred, Xs, Ys). % 残りの要素に再帰的に適用する

上記の例では、maplist/3というメタ論理述語を定義している。この述語は、与えられた述語（Pred）をリストの要素に適用し、結果のリストを返す。

maplist/3の動作は、ベースケースと再帰ケースに分かれている。ベースケースでは、空のリストが与えられた場合に結果も空のリストとなる。再帰ケースでは、リストの先頭要素に述語を適用して結果を得し、残りの要素に再帰的に適用する。

call/2は、与えられた述語を実行するPrologのビルトイン述語となる。ここでは、PredをXに適用してYを求めるために使用している。

このように、メタ論理述語を使用すると、一般的な操作を抽象化し、再利用性の高いコードを記述することができる。

prologを用いた論理外述語

論理外述語（Extra-logical predicate）は、Prologの論理的な操作や推論とは関係のない述語となる。これらの述語は、デバッグ、表示、制御フローの変更など、プログラムの制御や出力を操作するために使用される。

以下に、Prologを使用して論理外述語を定義する例を示す。

% デバッグ用述語：メッセージを表示する
debug_message(Message) :-
    write('Debug: '),
    write(Message),
    nl.

% 制御フローの変更：条件によって異なる述語を呼び出す
condition_predicate(X) :-
    ( X > 0 ->
        positive_case(X)
    ;
        negative_case(X)
    ).

% リストの要素を表示する
print_list([]).
print_list([X|Xs]) :-
    write(X),
    write(' '),
    print_list(Xs).

上記の例では、いくつかの論理外述語を定義している。

debug_message/1述語は、デバッグメッセージを表示するために使用され、与えられたメッセージを出力するために、Prologのビルトイン述語であるwrite/1とnl/0を使用している。

condition_predicate/1述語は、条件に基づいて異なる述語を呼び出すための制御フローの変更を行い、条件式が満たされる場合はpositive_case/1を呼び出し、満たされない場合はnegative_case/1を呼び出す。

print_list/1述語は、リストの要素を表示するために使用される。再帰的にリストの要素を取り出し、write/1を使用して要素を表示する。

これらの論理外述語は、Prologの論理的な推論とは直接関係がないため、プログラムの制御やデバッグ、出力操作など、実用的な目的に使用される。

prologを用いた非決定性プログラミング

Prologは非決定性プログラミングに非常に適している。非決定性プログラミングでは、複数の可能性を同時に探索し、解空間全体を探索して解を見つけることができる。

Prologでは、バックトラック（バックトラック）と呼ばれるメカニズムを使用して非決定性を実現する。バックトラックは、選択肢が失敗した場合に前の選択肢に戻り、別の選択肢を試すことを意味する。

以下に、Prologを使用した非決定性プログラミングの例を示す。

% 与えられた数の2乗を求める
square(X, Y) :- Y is X * X.

% 与えられた数の平方根を求める
sqrt(X, Y) :- Y is sqrt(X).

% 与えられた数の絶対値を求める
abs(X, Y) :- X >= 0, Y is X.
abs(X, Y) :- X < 0, Y is -X.

% クエリの実行
?- square(3, X).   % 3の2乗を求める
?- sqrt(16, X).    % 16の平方根を求める
?- abs(-5, X).     % -5の絶対値を求める

上記の例では、square/2、sqrt/2、abs/2という非決定性を持つ述語を定義している。

square/2述語は、与えられた数の2乗を計算し、与えられた数をそのまま2乗して結果を求める。sqrt/2述語は、与えられた数の平方根を計算し、ビルトイン述語であるsqrt/1を使用して平方根を計算する。abs/2述語は、与えられた数の絶対値を計算し、与えられた数が0以上の場合はそのまま絶対値を求め、負の場合は符号を反転させる。

これらの述語を実行するとき、Prologはバックトラックを使用して可能性を探索し、与えられた条件に合う解を見つけるまで探索を続ける。複数の解が存在する場合、バックトラックによってすべての解を見つけることができる。

非決定性プログラミングは、問題の解空間を効果的に探索するための強力な手法であり、Prologの特長的な機能の一つとなる。

prologを用いた不完備データ構造

Prologを使用して不完備なデータ構造を表現する方法はいくつかある。以下に、いくつかの一般的な方法を示す。

1. 関数記号を使用したデータ表現: 関数記号を使用して不完備なデータ構造を表現する方法がある。例えば、空のデータをemptyという関数記号で表し、データが存在する場合は別の関数記号で表現する。

% 不完備なデータ構造の例: リストの先頭要素と残りの要素
data(empty).
data(element(X, Rest)) :- data(Rest).

この例では、data/1という述語を定義している。data/1の引数には、データ構造が与えられる。空のデータはemptyという関数記号で表現され、要素が存在する場合はelement(X, Rest)という関数記号で表現される。このような表現方法では、データの不完備性を示すことができる。

2. プロパティリストを使用したデータ表現: プロパティリストは、属性と値のペアのリストとして不完備なデータ構造を表現する方法となる。属性が存在する場合はリスト内のペアとして表現し、属性が存在しない場合はその属性が存在しないことを表す。

% 不完備なデータ構造の例: プロパティリスト
data([]).
data([property(X, Value)|Rest]) :- data(Rest).

上記の例では、data/1という述語を定義している。data/1の引数には、データ構造が与えられる。プロパティが存在する場合はproperty(X, Value)というペアで表現し、プロパティが存在しない場合は空のリスト[]で表現する。

これらの例では、Prologの述語を使用して不完備なデータ構造を表現している。データ構造の不完備性を表現するために、再帰的な述語定義や特定の関数記号やプロパティリストの形式を使用しており、これにより、プログラム内で不完備なデータ構造を処理することができる。

prologによる2階プログラミング

Prologは一階述語論理を基にした言語だが、2階述語論理を模倣する方法もある。2階プログラミングでは、述語を引数として受け取り、動的に生成した述語を操作することができる。

以下に、Prologを使用して2階プログラミングを行う例を示す。

% 2階述語の定義
my_predicate(Pred) :-
    Pred.

% テスト用の述語
foo(X) :- X = 1.
bar(X) :- X = 2.

% 2階述語を呼び出す
?- my_predicate(foo(1)).  % foo/1 を呼び出す
?- my_predicate(bar(2)).  % bar/1 を呼び出す

上記の例では、my_predicate/1という2階述語を定義している。この述語は、引数として受け取った述語を実行する。具体的には、Predという引数を受け取り、それを実行している。

テスト用の述語として、foo/1とbar/1を定義しており、これらの述語は、引数に応じて特定の条件を満たすように定義されている。

my_predicate/1を呼び出す際に、具体的な述語を引数として与えることで、その述語を実行することができる。例では、my_predicate(foo(1))とmy_predicate(bar(2))を呼び出している。

このように、2階プログラミングでは述語を引数として受け取り、動的に生成した述語を操作することができる。これにより、より柔軟なプログラムの定義や制御を行うことができるが、Prolog自体は一階述語論理をベースにしているため、2階述語論理の完全な機能を提供するわけではない。

prologによるメタ・インタプリンタ

Prologはメタプログラミングの特徴を持っており、メタ・インタプリタ（Meta-Interpreter）を構築することができる。メタ・インタプリタは、プログラムの実行を制御し、プログラム自体を操作するメタプログラムとなる。

以下に、Prologを使用して簡単なメタ・インタプリタを実装する例を示す。

% メタ・インタプリタの定義
interpret(true) :- !.
interpret((A, B)) :- !,
    interpret(A),
    interpret(B).
interpret(Head) :-
    clause(Head, Body),
    interpret(Body).

% テスト用の述語
foo(a).
foo(b).
foo(c).

% メタ・インタプリタの使用
?- interpret((foo(X), X = a)).

上記の例では、interpret/1というメタ・インタプリタを定義している。このメタ・インタプリタは、与えられたプログラムを解釈し実行する。

interpret/1の定義では、3つのケースを取り扱っている。まず、trueが与えられた場合は成功として終了し、次に、(A, B)の形式のプログラムを受け取った場合は、AとBを順番に実行する。最後に、述語clause/2を使用してプログラムのヘッドとボディの対応を取得し、ボディを再帰的に実行する。

テスト用の述語として、foo/1を定義しており、この述語は単純な事実として定義されている。

最後のクエリでは、interpret/1を使用してプログラム(foo(X), X = a)を実行している。このプログラムはfoo(X)を実行し、その結果Xにaをバインドすることを意味する。

このように、Prologのメタプログラミング機能を利用して、メタ・インタプリタを構築することができる。メタ・インタプリタは、プログラムの解釈や実行を制御するための柔軟な手法として利用されている。

prologを用いた信用評価エキスパート・システム

信用評価エキスパートシステムは、信用度や信頼性を評価するためのルールベースのシステムとなる。Prologを使用して信用評価エキスパートシステムを実装するためには、ルールベースの知識ベースと推論エンジンを組み合わせる必要がある。

以下に、Prologを使用して簡単な信用評価エキスパートシステムを実装する例を示す。

% ルールベースの定義
trustworthy(X) :-
    has_good_reputation(X),
    has_completed_successful_projects(X).

has_good_reputation(john).
has_good_reputation(susan).

has_completed_successful_projects(john).

% 信用評価エキスパートシステムのクエリ
?- trustworthy(john).

上記の例では、trustworthy/1という信用評価を行う述語を定義している。この述語は、has_good_reputation/1とhas_completed_successful_projects/1の両方を満たす人物を信頼できると判断している。

has_good_reputation/1とhas_completed_successful_projects/1は事実として定義されており、特定の人物がそれぞれの条件を満たしているかどうかを示している。

最後のクエリでは、trustworthy/1を使用してjohnの信用度を評価している。このクエリは、has_good_reputation(john)とhas_completed_successful_projects(john)の両方を満たすため、johnを信頼できると結果が返される。

このように、Prologを使用して信用評価エキスパートシステムを構築することができる。より複雑なルールや評価基準を追加することで、より高度な信用評価を行うシステムを構築することが可能となる。