設計

設計に先立ってアトムグループという概念を定義する.

アトムグループ

¶ ³

ルール左辺においてリンクでつながれているアトムの集合.

µ ´

図 4.6: アトムグループ

図4.6にアトムグループの例を示す. この定義に従うと,命令列上ではどこから どこまでが1つのアトムグループになっているかと言うと,単純にfindatomから

findatomの間ということになる. よって命令列の先頭から検索してfindatomを見

つけたら, そこから次のfindatomの直前までの命令を命令列として, それを引数

に持つgroup命令を作ればアトムグループ単位でのグループ分けは実現できる.

しかし, 実際にこの方針で実装したところ次のような問題点があった.

44

(1)同じファンクタを持つアトムを取得するグループが2つ以上ある場合.

プログラム例

¶ ³

データ: a(3), a(10).

ルール:

a(X), a(Y) :- X > 1, Y < 5 | ok.

命令列(Z1オプションによる最適化後とする):

--memmatch:

spec [1, 7]

allocatom [5, 5_1]

allocatom [3, 1_1]

group [

findatom [1, 0, a_1]

derefatom [4, 1, 0]

isint [4]

igt [4, 3] ]

group [

findatom [2, 0, a_1]

derefatom [6, 2, 0]

isint [6]

igt [6, 5]

neqatom [1, 2]

jump [L158, [0], [1, 2, 3, 4, 5, 6], []]

µ ´

本論分ではここまでに説明していなかったneqatom命令の意味は次の通り.

neqatom [atom1, atom2]

atom1とatom2が異なるアトムを参照していることを確認する。

プログラムを実行すると,

1. 1つ目のグループにa(3)がマッチ.

2. 2つ目のグループにa(10)はマッチしない.

3. 2つ目のグループのマッチングに失敗したのでルール適用失敗. となってしまう.

実際には, 1つ目のグループでa(10)を取得し直せば, 2つ目のグループでa(3) がマッチするのでルール適用成功となるはずである. このように, 同じファンク タを持つアトムを取得するグループが2つ以上あるとうまく行かない.

(2)アトムグループを跨る命令があった場合

プログラム例

¶ ³

ルール:

a(X), b(Y) :- X > Y | ok.

命令列: group [

a(X) ] group [

b(Y) ] X > Y

µ ´

2つのアトムグループを跨る命令の行き場が問題となる. 上ではグループ外に置い ているが,命令列上ではグループ単位で処理が独立しているため,この場合X > Y で失敗すると, バックトラックせずルール適用失敗となる. 仮に2つ目のグルー

プの中にX > Y を入れたとしても, b(Y)の取得をし直すだけでa(X)のアトムは

最初に1つ目のグループで取得したものから変更できない.

これら2点を踏まえると, 命令列を区切るグループの単位はアトムグループで はないことが分かる. 従って次に定義するグループ単位で分けることにする.

グループの定義

¶ ³

ファンクタが同じアトムを取得したり, ある命令でお互いに関連付けられる アトムグループを1つの集団としてまとめたもの. 命令列はグループ単位で 処理が独立するものとする.

µ ´

この定義に従い実装を行った.