ホーン節・ユニフィケーション・バックトラック

ホーン節とその評価（１）

ホーン節は、手続型の言語のサブルーチン（関数）のように使うことができます。
後述するように機能的にはもっと複雑なことも出来ます。

以下の例では、$xと$yが与えられて、$zに$x*$x+$yを返す関数の例を示します。

・コード（func.p）

+func($x,$y,$z),$z = $x * $x + $y,!; #--(1)
,func(30,5,$z),print($z);

・実行結果

D:\sample>adp func.p
905

コードの(1)にあります +func ・・・の行がホーン節の定義になります。一行で終了していますが、ADPでは(Prologでも）、このようにシンプルに関数を書くことができます。
最後にあります ! はカットと言いまして後述するバックトラックに影響します。後程説明します。

ホーン節とその評価（２）ユニフィケーション

ADP(Prolog)のユニークな機能の一つユニフィケーションについて説明します。

先ずは例を見てみます。

・コード（unification.p）

+kencho('茨城県','水戸市');
+kencho('栃木県','宇都宮市');
+kencho('群馬県','前橋市');
+kencho('埼玉県','さいたま市');
+kencho('千葉県','千葉市');
+kencho('東京都','新宿区');
+kencho('神奈川県','横浜市');
,kencho('東京都',$x),printn($x);

・実行結果

D:\sample>adp unification.p
新宿区

ホーン節 kencho は、関東の都県の県庁所在地のDBになっています。
ゴール節では、
,kencho('東京都',$x)
という評価が行われています。
東京都の県庁所在地は新宿区と定義されていますが、実行結果を見ますとその通り'新宿区'が出力されています。

ADPにはこのようにホーン節と評価中の項（述語）のマッチングを行い、結果マッチするホーン節が見つかったら評価を真とします。
つまり、

,kencho('東京都',$x)

の評価では、ホーン節1つ1つとマッチングを行い、1つ目の引数が'東京都'である述語を検索することになります。unification.pのソースでは該当するホーン節がありますので、評価結果は真となります。
その時に、変数$xには、'新宿区'がマッチングされます。変数は、初期状態ではマッチングにおいて（なんでも良い）ということを示し、共に以降の評価においては、マッチングされた値を使用します。

,printn($x)

では、$xにマッチングされた、'新宿区'を出力することになります。

また、unification.pのコードにおいて、

,kencho('北海道',$x),printn($x)
としても、該当するホーン節が無い為、結果は何も表示されません。

ホーン節とその評価（３）バックトラック

ADP(Prolog)にはバックトラックと呼ばれる制御構造があります。
こちらも例を見てみます。このコートでは、全ての都県の県庁所在地が出力されます。

・コード（backtrack.p）

+kencho('茨城県','水戸市');
+kencho('栃木県','宇都宮市');
+kencho('群馬県','前橋市');
+kencho('埼玉県','さいたま市');
+kencho('千葉県','千葉市');
+kencho('東京都','新宿区');
+kencho('神奈川県','横浜市');
,kencho($x,$y),printn($x,"：",$y),fail;

・実行結果

D:\sample>adp backtrack.p
茨城県：水戸市
栃木県：宇都宮市
群馬県：前橋市
埼玉県：さいたま市
千葉県：千葉市
東京都：新宿区
神奈川県：横浜市

ユニフィケーションの例との違いですが、都県の評価部分も変数になっています。

,kencho($x,$y)

上記の述語を評価しますと、全部のホーン節にマッチしますが、ADPでは先ずは先頭にあります、

+kencho('茨城県','水戸市');

にマッチして、先のprintn述語の評価を行います。その後、fail述語の評価を行いますが、fail述語は必ず評価に失敗します。
ADP(Prolog)では、述語の評価に失敗するとバックトラック（後戻り）を行います。
この例では、printn述語の再評価を行いますが、こちらも評価に失敗します。
次に、,kencho($x,$y)の再評価を行います。この再評価で、

+kencho('栃木県','宇都宮市');

にマッチし、再度printnの評価、failの評価、バックトラックと続き、結果としてkenchoの全てのホーン節とマッチします。最終的には全体がfailで終了します。
このようにADP(Prolog）ではバックトラックを使って全てのホーン節の評価を行うこともできます。

ホーン節とその評価（４）next述語（ADP独自の拡張）

バックトラックの例では、全てのホーン節kenchoの内容を出力するのにfail術語を使いましたが、fail述語では、評価に失敗するので全部のホーン節の内容を出力し終えた後は全体の評価も失敗します。
バックトラックを行いたいけど、全ての評価が終わった時は評価を続けたいということもあります。
next述語はそのような場合に使えます。以下、再び例をみていきます。


・コード（next.p）

+kencho('茨城県','水戸市');
+kencho('栃木県','宇都宮市');
+kencho('群馬県','前橋市');
+kencho('埼玉県','さいたま市');
+kencho('千葉県','千葉市');
+kencho('東京都','新宿区');
+kencho('神奈川県','横浜市');
,$c = 0 ,kencho($x,$y) ,printn($x,"：",$y) ,$c = $c + 1 ,next ,printn($c,"件");

・実行結果

D:\sample>adp next.p
茨城県：水戸市
栃木県：宇都宮市
群馬県：前橋市
埼玉県：さいたま市
千葉県：千葉市
東京都：新宿区
神奈川県：横浜市
7件

少し、プログラムが複雑になりましたが、$cでマッチした個数を数えながらnext述語でバックトラックを行い、全てのホーン節のマッチングが終了したら、next述語の次のprintn述語で、マッチした件数を出力しています。

このnext述語ですが、私が知る限り、ADPオリジナルの機能になります。next述語により非常にスッキリとループが書けます。

ホーン節とその評価（５） ! - カット述語

ルーターのパケットの許可、禁止ルールによくあるのですが、ルールを上から順に実行して、一致したらそれで評価終了ということがしたいことがあります。このような場合に、! カット述語を使います。


以下、年齢別の料金計算にカットを使ったコード例を示します。


・カットを使ったコード例(cut1.p)

+calc_age_price($age, $price, 0),       $age <  2, !;                        # -- (1)
+calc_age_price($age, $price, $result), $age < 12, $result = $price / 2, !;  # -- (2)
+calc_age_price($age, $price, $price);                                       # -- (3)

,calc_age_price(  0, 100, $result), printn("乳児料金:", $result), next; # 乳児料金を表示
,calc_age_price( 10, 100, $result), printn("子供料金:", $result), next; # 子供料金を表示
,calc_age_price( 20, 100, $result), printn("大人料金:", $result), next; # 大人料金を表示

・実行結果

D:\sample>adp cut.p
乳児料金:0
子供料金:50
大人料金:100

年齢別の料金が計算されています。よく見ると気づくかと思いますが、乳児の年齢は(２)の条件（１２未満）に合致します。従いましてnext述語でバックトラックすると(2)も実行されますが、カット述語のおかげで(2)の評価は行われません。カット述語はこのようにホーン節に対して一度マッチしたものは二度とマッチさせないという機能があります。以下、カットを外した例を掲載ます。

・カットを使わないコード例（cut2.p）

+calc_age_price($age, $price, 0),       $age <  2;                        # -- (1)
+calc_age_price($age, $price, $result), $age < 12, $result = $price / 2;  # -- (2)
+calc_age_price($age, $price, $price);                                    # -- (3)

,calc_age_price(  0, 100, $result), printn("乳児料金:", $result), next; # 乳児料金を表示
,calc_age_price( 10, 100, $result), printn("子供料金:", $result), next; # 子供料金を表示
,calc_age_price( 20, 100, $result), printn("大人料金:", $result), next; # 大人料金を表示

・実行結果

D:\sample>adp cut2.p
乳児料金:0
乳児料金:50
乳児料金:100
子供料金:50
子供料金:100
大人料金:100

乳児料金が３回出てきています。カットを使わないで、乳児料金を正しく算出させる為には、子供料金と大人料金に正しく条件を入れます。(2)の子供料金の場合は、
$age >= 2, $age < 12
とし、(3)の大人料金の場合は、
$age >= 12
とします。


＊ADPではこのように条件を手軽に記載できますが、バックトラックが発生した場合、ホーン節は出現順で評価されます。カットを使うと条件式を記載する手間が省けますが、コードは多少技巧的になります。

---

Powered by ADP.