back numbers

9.02.2008

Term Reduction in Prolog

Prologで回文判定に出るような無限ループを避ける工夫は二つあって、一つはメタなルール操作を書く事、もう一つはグローバルなI/Oを行う事。実際に行うとなると、どちらも骨の折れる作業なので、これ意識せず行えるのはETが誇る到達点だと思われる。例えばメタなルール操作を行う場合、次のようにしてルール集合に対する適当な項書き換えを行う。ルール自体のセマンティクスは eval_rule/2 で実行されることとなる。

reduct([], _Ans) :- !.
reduct(T1, T3) :-
get_rule(T1, E1, Rule),
eval_rule(E2, Rule),
append(E1, E2, T2),
!, reduct(T2, T3).
get_rule(S1, S3, r(rule1(X, Y), rule1(X, Z))) :-
retrieve(S1, rule1(X, Y), S2),
retrieve(S2, rule1(X, Z), S3).
eval_rule([Y = Z, rule1(X, Y)],
r(rule1(X, Y), rule1(X, Z))).
retrieve(L1, E, L2) :-
member(E, L1),
delete(L1, E, L2).

?- reduct([rule1(X, Y), rule2(Y, Z), rule1(X, Z), rule0(Z)], Ans).
..

もう一つのグローバルなI/Oに手を出せば、これはもう完全な手続き型言語となる。循環ループかどうかを区別可能な量のフラグを用意して、特定の述語を経過するごとに assert/1 や retract/1 を実行する。問題の状態遷移に固有のパタンが事前に決定可能であるならば、そのパタンに限り、確実にループを離脱する事が可能となる。

ここで物言いが入るのは、これらが反則技じゃないのか?ということ。しかし前者は扱う集合の世界が二階になっているだけで、実行されているのはSLD導出と全く同じ内容である。後者についてはI/Oがフラグの上げ下げに限定されている事から、適当な広さのファクトテーブルが存在すれば、これもまたSLD導出で解決される。また別の非難としては、これらが全てランタイムであるというものだが、Prologユーザの視点ではコンパイルも知識ベース読み込みも、全てをランタイムに引きずり下してあるのであって、実行時にコンパイルもリンクも出来て非常に便利なのである。他の言語では実行時に出来る事など限られているのだから。

0 件のコメント:

tags

Profile

Taito, Tokyo, Japan
明けども明けども次の埒
hiro.kosh@gmail.com