Location : Home > Languages > Perl > Package Title : Math::Logic::Predicate

　注意：正直なところ、この原文の英文が分かりにくいものばかりで、日本語訳はお世辞にも分かりやすいとは言えない。いずれ見直す。

名称

　Math::Logic::Predicate - 第一階述語論理の処理

バージョン

　Math::Logic::Predicate version 0.03, July 28, 2002.
　2002年7月26日にこのモジュールを最初に使った。

概要

use Math::Logic::Predicate;

$db = new Math::Logic::Predicate;

# データベースに述語を入力
$db->add(<retract( 'plays(lister, guitar)' );

# パターンに基づいて
$db->retract( 'smart(_)' );

# クエリを出す
$query = $db->parse( 'human(H) & name(H, X) ?' );
$iter = $db->match($query, $iter);

# 結果を取得
$name = $db->get($iter, 'X');

# 規則に格納
$db->add( 'human_name(H, N) := human(H) & name(H, N).' );

# クエリを使う
$iter = $db->match( 'human_name(lister, N) ?' );

# ファイルに格納
use Storable;
store($db->rules, 'red_dwarf'); 

説明

概括

　Math::Logic::Predicate は第一階述語論理の部分集合のためのソルバを実装している。version 1.0 までには第一階述語論理計算全体を扱いたいと思う。以下のものを提供する。

• 規則と述語を特定する Prolog のような言語
• 言語及び規則を作成するオプション
• 高速ソルバ
• コード化された規則を指定する能力（下記参照）
• 高速解法のためのデータ組織化

　述語論理とは以下の点が異なる。

• クエリ内に存在量化子（existential quantifier）を使うことができる。
• 格納時の変数に全称記号（universal quantifier）を使うことができる。存在量化子を使うためにはそのオブジェクトが何を扱っているかを知っている必要がある。
• 関数のサポートはない。すなわちオブジェクトの属性が述語より勝っている。

　幸運にも最初の２つは必要なもので、最後のものは制限がないということである。しかしいくつかのケースでは簡単にできるであろう。これらの全てはいずれ実装する。

Math::Logic::Predicate を使う

　Math::Logic::Predicate は全面的にオブジェクト指向で標準的な方法で実装されている。ユーザが望む規則の追加以外は設定する必要がない。
　後述するように、Math::Logic::Predicate は低水準と高水準の２つのインタフェースメソッドをサポートしている。高水準インタフェースは小規模な Parse::RecDescent 文法に従う印テフェースを持ち、様々な支援を行う。低水準インタフェースは自動生成時、すなわちパースツリーをトラバースするとき（使いやすいように開発したが、奇妙にもＣに似ていて、不気味だ）に向く。

高水準インタフェース

　このインタフェースはユーザが規則と格納を特定する小規模な Prolog のような言語を用いるパーサを実装している。言語は以下のようなものである。
　何かを格納するにはピリオドで終わる。クエリを渡すにはクエスチョンマークで終わる。

color(orange, orange).      # 格納
color(orange, orange)?      # クエリ

（コメントは認識されず、構文エラーとなるので注意すること。）
　上の例では語 "color" は述語であり、 "orange" はその引数である。複数の引数をもつ述語では最初の引数が通常目標として参照され、残りは目標の属性である。（このあたり、Perl のオブジェクト指向スタイルに似てない？）
　変数は大文字で始まる文字列で（デフォルトでは。下を見よ。）、どこにでも現れる。格納時に用いれば何かに適合するワイルドカードとして用いられる。文字を使わなくとも、匿名変数として _ が利用できる。これらを述語自身として用いるのであれば、変数が予め限定されている場合にのみ機能する。（値を持っているなど。）

color(orange, X)?           # X はオレンジ色への参照
color(Everything, black).   # ゴシックの理想

　記号のみを使うと、/\w+/ となる。データ型の全体を使う。

weight(duck, 13.75).
weight(witch, 13.75).

speech('Old man from scene 24', 'Who would cross the Bridge of Death...').

q{Favorite color}(galahad, "Blue--no, yel--ahhhhhhhhh").

　最初の文字が大文字であれば変数として数えないことに注意すること。
　もちろん、述語を用いるにはこれらをチェーンする必要がある。従属している述語のリストを作成するには以下のようにする。

weight(duck, W) & weight(X, W) ? # duck と同じ重さのもの全てを探し出せ

　述語を適合するために & または "and," を用いる。引数を束縛することを保証するには | または "or," を用いる。最後に左が成立し右が成立しない場合に - "minus," を用いる。これらはすべて期待通りに動作する。
　たとえばスマートではないが、全ての人間またはホログラム X を探索することは次のようにするとよい。

human(X) | hologram(X) - smart(X) ?

　あらゆる演算子は左結合であり同じ優先順位である。
　規則、すなわちクエリを拡張する述語を定義するためには := 演算子を使う。

dumb_human_like(X) := human(X) | hologram(X) - smart(X).

　他の長い文字列の替わりに dumb_human_like を使うことができる。他の利点もある。規則は再帰的であることだ。
　最後に適合する変わりに Perl コードを実行するために規則を定義することができる。以下のセクションを見よ。

インタフェース関数

　データベースに add を用いて規則を追加することができる。

$db->add( 'color(orange, orange).' );

　retract を用いてデータベースから削除する。

$db->retract( 'color(_, orange).' );  # 全てのオレンジのものを削除

　parse を用いて規則またはクエリを生成。

$query = $db->parse( 'human(X) - smart(X)?' );

　適合パターンのために必要で、もっとも難関の部分である。まず反復子が必要で結果を格納し、答えの残りを取得することができる。

$iter = $db->match($query, $iter);      # 最初の適合を取得

　反復子が定義されれば適合させるために用いられる。最初は必要ないが持続性のために必要である。$iter を変数として用いるために取得する。

$dumb = $db->get($iter, 'X');

　次の適合のために引数として反復子とともに match を呼び出す。

$iter = $db->match($query, $iter);      # 次の適合を取得

　反復子がなくなれば match は undef を返す。割り当ては最後のものが持続性のために必要であることに留意すること。match は $iter を修正する。
　クエリとともに反復子を放棄することができる。

どのように稼動するか

　このセクションがなぜこんな真ん中にあるのかと疑問に思うような人であれば、それは既に組み込みコードが書ける人なのだろう。
　さて、以下のようなクエリを考えよう。

month(X) & person(X) ?

　これは月の名前にちなんだ人名を探索する（month と person が適切に定義されている必要があるが）。これを走らせるとこうなる。

month('January'). month('February').            # ... など
person('Larry'). person('Damian').              # ... もちろん
person('April'). person('May'). person('June'). # ... などなど

　month を最初に探索し、 "January" を X に格納する。month が成功すれば処理は person に移り、person('January') があれば変数を埋める。うまく行かなければ month に戻り次の月についての処理を行う。これはまずアルファベット順に処理を行い、その後数字・記号という順に行う。（ビットを大きく修正するので例には示していない。）
　"April." まで行う。person('April') を試し、match から "'April." に制限された X を返す（アポストロフィに意味を考えよう）。もし match にもう一度やれと命じれば person が失敗したときまで戻る。"April," という名前の人がいればいいが、いないなら month に戻る。最後に month がなくなれば最初に戻り、全体のクエリがうまく行かなかったことを示す。
　 | "or," 各被演算子は列の中にあるものとし、全てをとったようになる。

human(P) | hologram(P) | android(P) ?

　これはまず human について、次に hologram について最後に android について返す。 それぞれは必要なときに実行される。バックトラック時には再実行し前に進む。
　- "minus," ２番めの被演算子は最初がうまく行ったときのみ利用する。
　これは何もマイナスのもののがないときにうまく行くようにである。
　マイナスの２つめの規則はバックトラックしないことである。

コードの埋め込み

　ビルトインされているデータ管理はきわめて有用で、時には機能的である。すなわち計算する能力または変数の値を出力する能力である。ビルトインされたものだけで万人に満足してもらえることは想定しておらず、ユーザが自分で書くべきである。

print(X) := { $track ? print "$X\n" : undef }.

　まず名称を与えることである。チェーンの途中ではできない。

# 悪い例
printcolors := color(X) & { $track ? print "$X\n" : undef } & fail.

　例では $track は適合しているかバックトラックしているかを教えている。適合しているときには true を、それ以外は false を返す。通常はバックトラック時に何も述語を用いなければ失敗する。$X は変数 X に限定を与える。
　X の範囲が限定されていなければ undef である。限定するには値を充てる（簡単にするには多くの魔法が必要であることに注意）。
　変数を解放するには undef とする。
　もう１つ特別な変数 $local がある。これはローカルデータを格納しているハッシュへの参照である。$track が true であれば新しい $local を取得できる。このように $local は反復子を格納するのによい場所である(通常の振る舞いをする述語が反復子を格納する）。
　以下に全ての数を引数に取る述語 whole の例がある。引数が無限定であれば 1 から始まる全ての数を取る。

whole(X) := {
   if (defined $X) {
      $track ? $X =~ /^[1-9]\d*$/ : undef
   }
   else {
      $X = ++$local->{num}
   }
}

　（ピリオドを忘れないこと。）　全ての数を出力するには [1, inf) とすることもできる。

whole(X) & print(X) & fail ?

　fail はクエリがうまく行かなかったときに終了するために必要である。

低水準インタフェース

　このインタフェースは美しくないのだが、文字列を構築してパーサを通して実行するよりは速い（しかしそれだけだ）。クエリと規則の自動生成には向いている。
　基本的には、全てプロシージャで呼び出される。newproc を使って呼び出され、以下のような形態である。

$proc = $db->newproc($name, [ @args ], $context, $next, $prev);

　 　$context と $next はオプションである。
　$name は新しいプロシージャの名称を含む文字列である。小文字・数字・文字列であることを示すアポストロフィから始まる。これは $proc->{rule} でアクセスされる。
　@args （または既に参照があれば $args）はこのプロシージャがとる引数のリストである。（現在のところ）すべて文字列でなければならない。もし大文字や下線で始まっていれば変数と見なされる。前述したようにアポストロフィで始まっていればそれは文字列で、定値である。$proc->{args} でアクセスされる。
　$context はこの文字列の 文脈 context を示す文字列である。チェーンにおいては演算子の型が最初に来る（または最初であれば and）。$proc->{context} でアクセスされる。妥当な文脈は以下の通り。

true

　このプロシージャが常に真であることを示す。ただし一方向（欲しいときのみ）。

false

　今のところ、規則が全く定義されていないことと同じである。将来の方向性セクションを見よ。

and

　プロシージャが適合したときにのみ開始することを示す。

or

　このプロシージャ必要な適合を行うことなしに実行できることを示す。１つが適合すればそれでよい。

sub

　このプロシージャは事前のものが失敗したときにのみ進むことができることを示す。

bind

　バインド (:=) 演算の左側への適用を示す。

　最後に $next 及び $prev はチェーンにおける次と前の項への参照である。これらはそれぞれ $proc->{next} 及び $proc->{fail} でアクセス可能である（失敗すると次に進むので）。既に設定されていない場合は $next, $next の $prev を設定することができる。
　このインタフェースではプロシージャを追加することができる。実際、全ての parse では Parse::RecDescent を通じてこれらの関数でプロシージャを構成できる。

　例として以下のように構築・追加さればよい。

crew(X) := human(X) | hologram(X) - smart(X).

　低水準インタフェースは以下の通り。

my $proc = $db->newproc('smart', [ 'X' ], 'sub');

$proc = $db->newproc('hologram', [ 'X' ], 'or',   $proc);
$proc = $db->newproc('human',    [ 'X' ], 'and',  $proc);
$proc = $db->newproc('crew',     [ 'X' ], 'bind', $proc);
$db->add($proc);

将来の方向性

　将来的には以下の内容を追加する予定である。

• 構造！　これが最大のものである。これにより引数をとる引数を利用できるようになり、これに対応する適合することもできる。
• 「証明できない」ということと「偽」を区別すること。これはある意味に false の文脈を与えることができる。
• パーサにコメントを入れること。これは重要ではない。
• 演算子を挿入するなど、パーサへのアクセスの簡素化。現在ではパーサには $db->{parser} という形式でアクセスできるが、１つずつしか処理できない。
• 述語探索。これはすごいが必然的に遅くなる。述語の名称を無限定の変数として与えると各述語は引数と適合作業を行うからである。

バグ

　これまでのところバグは見つかっていない。しかし汚いコードなのでバグがあるかも知れない。

著者

　Luke Palmer （fibonaci@babylonia.flatirons.org）

著作権

　Copyright (C) 2002, Luke Palmer. All Rights Reserved.

　本モジュールはフリーソフトウェアである。the Perl Artistic License （http://www.perl.com/perl/misc/Artistic.html）の条件に従い修正／再配布することができる。

Updated : 2008/05/14