JPS6074040A - 述語論理型言語処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は述語論理型言語処理装置に関する。

述語論理型言語処理装置とは述語名とその引数よシなる
述語の連なりから成る節の集合として書き下す述語論理
型言Ｍを処理する装置であるが。

以下プログラミング言語であるプロログ言＠全例にと９
説明する。

プロログにおいては表現すべき事象を述語名とその引数
の結合から成る「述語」によって表現し、更に述語間の
関係を記述する。例えば、「太部は果物金好む」という
事象は下記のように記述できる。

好む（太部、＊物）←果物（＊物） 本例で「好む」と「果物」を述語名、「太部」。

「＊物」を引数と称し、＊印はぞの引数が変数であるこ
とを表わす。即ち、上側は「太部」は「果物」、という
述語名で表記された述語の引数として書かれている事物
を「好む」ことを表現している。従って。

果物（いちご）。という文が他に書かれていれば、三段
論法の推論によって、［太部はいちごを好む」という結
論が得られる。

前記のプロログは述語論理型言語としてその利用領域が
拡大している。しかし、更に利用領域を拡大するために
は、プログラムの処理効率を高める必要がある。

従来、このプロログの処理は汎用計算機で実現されてい
る。しかしながら、汎用計算機のハードウェア構成によ
る制約を受け高速にプロログプログラムを処理すること
ができなかった。

プロログプログラムの実行は述語間の一致を比較する処
理が基本になっている。例えば、前記の［・・・←果物
（＊物）。」と「果物（いちご）。」とを比較して両述
語間の一致を調べる処理が基本である。この処理を高速
に実現するためには双方の述語を同時に読み出して述語
名およびそれに続く引数の一致を順次調べる必要がある
。

しかしながら、従来の計算機では記憶装置からの読出し
は一時には一語あるいは一つのまとまった領域からのみ
可能であり、別個の領域から同時の計算機で高速バッフ
ァ機能を実現しているキャッジ−メモリでも同様で、処
理装置側からのキャッシュメモリへのお照は一語あるい
は−りの領域からのみ可能である。このハードウェア構
成が従来の計算機でプロログプログラムを高速に処理す
る際の制約となっている。

さらに従来の計算機では、述語間の一致を調べる処理を
複数個同時に並列処理できない。例えば［−・・←果物
（＊物）。」と果物（いちご）。」および「果物（少ん
ご）。」とを比較して　物を満足するものとして「いち
ご」と「ｐんご」を得ようとする場合である。従来計算
機では、　「果物（＊物）」と［果物（いちご月との一
致を調べた後に「果物（＊物）」と「果物゛（シんご〕
」との一致を調べる。これらの一致を調べる処理を同時
に並列処理することはできない。

本発明はプロログに代表される述語論理型言語のだめの
処理装置として、同時に読出し可能な複数のバッファメ
モリと述語間の比較を並行して処理できる複数の一致検
出器を備えることによシ、前記述語と述語との比較を並
列に処理できるようにしｆＣ装置を提供するものである
。

本発明によると述語名とその引数よ構成る述語の連らな
シから成る節の集合として書き下す述語論理を言語を処
理する装置に−おいて、前記節の内部表現全格納する記
憶装置と、前記記憶装置から読み出された節の内部表＊
１−一時的に格納する複数のバッファメモリと、前記複
数のバッファメモリから読み出された２つの前記述語の
間の一致を調べる複数の一致検出器と、前記述語間の関
係を次々にたどる道筋を保持するためのスタック機構お
よび複数個の内部レジスタおよびバッファメモリの管理
機能を含む制御装置とを備え、前記制御装置の制御の下
に前記複数の一致検出器で述語間の一致検出を複数個同
時に検出できるようにしたことを特徴とする述語論理型
言語処理装置が得られる。

以下本発明の一実施例を図面を用いて詳細に説明する。

本実施例では、プロログの述語を次の形式で表現する。

述語名（引数１．引数２．・・り 引数は定数または変数であシ、変数引数の先頭には＊印
を付けて区別する。プロログの一文を節と呼び、一般形
式は以下のとおりである。

述語１←述語２．述語３．・・・、述語ｎ。

←印は論理記号であシ、その左側に存在し得る述語は高
々−箇である。これをヘッド部と呼び。

←印の右側をボディ部と呼ぶが、ボディ側の述語を区切
る“、′印は述語間の論理積を表わす。上記の一般形式
杜述語２．述語３．・・・、述語ｎの論理積が成立する
とき、述語ｌが成立することを表現しておシ、この形式
を規則節と呼ぶ。

一般形式の特殊形として、ヘツ゛ド部のみから成る節を
宣言節、ボディ部のみから成る節を間合わせ節と呼ぶ。

プＦＣＩグのプログラム実行は、以下のステップで行わ
れる。

（１）節のボディ部に現われる述語と同一の述語金、ラ
ド部に持つ節を見出す。ここで双方の述語の引数同士を
その並び順に比較し、一致ｔ−調べる操作を行う。ここ
ですべての引数が一致するとステップ（２）ｌ：　Ｐｙ
　３゜夕すべでの引数が一致して囚なければステップ（
１〕の処理を繰シ返す。

引数同士の比較において、一方が変数、他方が定数であ
れば、変数に定数の値がバインドされる。また双方共に
変数であれば同一値を採るべく、一方が他方へのボイ／
りに書き換えられる。この二連シの処理も一致条件を満
たすものである。

（２）ステップ＋１）で比較の結果述語同士の一致が確
認された節のボディ部の処理へと制御が移り、ステップ
（１）へ戻る。もしその節が宣言節であれば、ステップ
（１）の最初に参照された節のボディ部の引き続く述語
の処理へ移る。もし引続く述語が無ければ全処理を終了
する。

第１図はプｃＬログのプログラム例を示す。図中。

“Ｐｌ“、“Ｐ２“は述語名、“Ａ“　ｔ＋Ｂ″。

“Ｃ“、“Ｄ“、“Ｅ“は定数引数、“＊Ｘ“。

“＊ｙ″、“＊２“は変数引数である。節ｌは規則節で
あシ、節２９節３は宣言節１節４は間合わせ節である。

以下、このプログラムの処理の流れを説Ｆ！Ａする。

プログラムの実行は間合わせ節から始まる。第１図の例
では節４の最初の述語“Ｐ　１　（＊ｘ、＊　ｙ　）“
の処理から始まシ、ステップ（１）によって節ｌが見出
され、すべての引数が一致することからステップ（２）
へ進む。ここで変数“＊Ｘ“には節１の定数値“Ａ“が
バインドされ、変数“＊ｙ“には変数“＊２″がバイン
ドされて“＊ｙ″と“＊２”の値が等しいことが示され
る。

ステップ（２）では節１のボディ部“Ｐ２（Ｂ、Ｃ。

＊ｚ）“の処理へ進み、ステップ（１）へ戻って述語名
“Ｐ２”をヘッド部として持つ節２との一致ｆｃ調べ不
一致であることから、次に述語名“Ｐ２“をヘッド部と
して持つ節３との一致を調べる。節１のボディ部と節３
のヘッド部とは一致して、ステップ（２）の処理へと進
む。ここで変数“＊２−には節３の定数値“Ａ”がバイ
ンドされる。前記処理の結果、変数“＊ｙ０と変数“＊
２“の饋が等しい関係にあることから変数“＊ｙ”の値
も定数値“Ａ“になる。

前記ステップ（２）において節３が宣言節であることか
ら５節１の処理へ制御が戻る。節ｌのボディ部には述語
“Ｐ２　（Ｂ、Ｃ，＊ｚ　）″に続く述語はないので１
節ｌの処理は終了し、節１の処理に制Ｍ−渡した節４の
処理へ制御が戻る。これまでの処理結果として、節４の
変数“＊Ｘ″には定数値“Ａ“がバインドされ、変数“
＊ｙ°にも同じく定数値“Ａ“がバインドされる。

次に、節４の２番目の述語“Ｐ　１　（＊　ｘ、＊　ｘ
　ｆが処理対象となシ、ステップ（１）によって節ｌが
見出され、引数を比較した結果、述語の一致が認められ
る。この引数の一致検査において、変数“＊Ｘ“の値は
前記の処理によシ得られた定数値“Ａ“である。また、
節１の変数“＊２“の値も変数“＊Ｘ“と同一の値にな
ることから、定数値“Ａ“となる。変数“＊２“は節４
の１番目の述語“Ｐｌ（＊ｘ、＊ｙ）“の処理では定数
値“Ａ“にバインドされたが５節４の２番目の述語″Ｐ
Ｉ（＊ｘ、＊ｘ）“の処理では５節ｌは新たな処理対象
である。このときには変数“＊２“は特定の値がバイン
ドされていない変数であり、前記ステップ（１）の処理
で初めて変数“＊Ｘ“が値“Ａ“にバインドされる。

以下、ステップ（２）で節１のボディ部を処理し。

ステップ（１）の処理を進める。節１のボディ部と節２
は不一致となるが、節３とは一致する。次にステップ（
２）により、節４０２番目の述語の処理として一致した
ことを節４に返し、すべての処理を終了する。

本実施例の装置においては、プロログの節の内部表現と
して、第２図の例に示す形式を用いる。

第２図は第１図に示したプロログプログラムの節ｌに対
応する内部表現を示す例である。本実施例の装置では５
節毎に第２図に示すようなひとまとまシの領域で記述さ
れる内部表現を持つ。この節毎の内部表現を「コード」
と呼ぶ。第２図の各行を語と呼び、１語はタグフィール
ドと値フィールドから構成される。タグフィールドには
、その語の属性情報が保持され、値フィールドにはタグ
で示される属性に対応する値が保持されてｂる。

コードの先頭の語「ヘッダ」はコード全体に係る情報を
保持する。すなわち規則節、宣言節１間合わせ節のいず
れに対応するコードであるかを示す情報１節の中にある
ユニークな変数の数に係る情報などを保持する。

コードの第２語である「ポインタ」はそのコードと同一
の述語名をヘッド部として持つ節へのリンク情報を保持
する。

第３語は、節１の述語名“Ｐｌ“に対応して、述語名を
饋として持つことを示すタグフィールドと、その述語名
は具体的に“Ｐｌ“であることを示す値フィールドを持
つ。第４語では述語″Ｐ１（Ａ、＊ｚ）“の第１引数“
Ａ″の属性が定数であることをタグフィールドで示し、
その直が“Ａ“であることを値フィールドで示す。第５
語では述語“Ｐ　１　（Ａ、　＊　ｚ　）“の第２引数
である変数“＊２“の属性が変数であることをタグフィ
ールドで示し、その変数が節１の中に現われる最初の変
数であることを示す番号（０）　′ｆｒ、値フィ一フイ
ールドして持つ。

以下５節１のボディ部の述語名°゛Ｐ２“、引数“Ｂ′
、“Ｃ″、′＊２“にそれぞれ第２図の第６語〜第９語
が対応する。こＣで、第９語の変数“＊２“と第５＠の
変数“＊２“とが同一の変数であることはこれらの語の
値フィールドが同一変数番号（０）であることで示され
る。

第３図は以上説明した内部表現によって第１図のプログ
ラム例を表現した図である。図中値フィールド中の“ｎ
ｕｌｌ　”はメモリリンクの終端であることを示す。節
１．　２．　３．　４に対応して４つのコードが表現さ
れている。

ボディ部の述語の述語名と同一の述語名をヘッドとして
持つ述語との一致を調べるときに比較対象となる節を指
定するために、ボディ部の述語名にはヘッド部に同一述
語名を持つ節に対すする内部表現のアドレスが格納され
ている。これらの関係は図中の破線で示す。

同一の述語名をヘッド部に持つ節はコードの第２語であ
るポインタによってリンクされる。例えば、節２と節３
とは同一の述語名をヘッド部に有する節であるので、節
２から節３にリンクされる。

第４図は本発明の装置の一実施例を示すブロック図であ
る。図中１００は第３図の説明で述べた内部表現をその
ままの形で格納する記憶装置、１０１は記憶装置１００
に格納されているコードを読出すだめのアドレスレジス
タ、１０２，１０４゜１０６．１０８は記憶装置１００
から読出されたコードを一時的に格納するバッファメモ
リＡ、バッファメモリＢ、バッファメモリＣｌバッファ
メモリＤ、１０３，１０５，１０７，１０９は夫々バッ
ファメモリ１０２，１０４，１０６，１０８の語を示す
ためのバッファポインタＡ、バッファポインタＢ　、／
（ッ７アポインタＣ，バッ７アポイ７りり。

１１０は前記の４箇のバッファメモリ１０２，１０４゜
１０６．１０８の出力およびデータ線２１８を介して送
られる制御部１１３の内部データの中のｌっの出力を選
択する選択回路Ａ、１１１は前記の４箇のバッファメモ
リ１０２，１０４，１０６，１０８の出力およびデータ
線２１８の中の１つの出力を選択する選択回路Ｂ、１１
２は選択回路Ａｌｌ０と選択回路Ｂ１１１によって選択
された語を比較して一致を検出するための比較器へであ
る。比較器Ａ１１２は入力される２語のビットパターン
が一致していることを検出するだけでなく、変数を示す
語と定数を示す語との比較におして一致を検出する。

１１３はスタック機構および内部レジスタおよび各バッ
ファメモリ１０２，１０４，１０６，１０８および記憶
装置１００の管理を含み、比較器Ａ１１２からの一致検
出信号に基づいて他の構成要素の動作を制御する制御部
である。制御部１１３は従来型のプロセッサと同様の構
成で実現できるので、その内部機構については特に述べ
ない。

１１４は前記の４箇のバッファメモ！Ｊ１０２゜１０４
．１０６，１０８の出力およびデータ線２１８の出力の
中の１つを選択する選択回路Ｃ，１１５は前記の４箇の
バッファメモ！Ｊ１０２，１０４゜１０６，１０８の出
力およびデータ線２１Ｂの出力の中のＩＱｋ選択する選
択回路り、１１６は選択回路Ｃ１１４と選択回路Ｄ１１
５によって選択された語を比較して一致を検出するため
の比較器Ｃである。

１１７は選択回路Ａ１１０と選択回路Ｂ１１１と比較器
Ａ１１２とで構成する一致検出器Ａ。

１１８は選択回路Ｃ１１４と選択回Ｗ＆Ｄ１１５と比較
器０１１６とで構成する一致検出器Ｃである。

第４図で、アドレスレジスタ１０１で指定するアドレス
がアドレス線２０１を介して記憶装置１ｏＯに送られる
と、出力がバス２０２を介して各バッファメモリ１０２
，１０４，１０６，１０８に送られる。バス２０２のデ
ータは前記４箇の／＜ラフアメモリ１０２，１０４，１
０６，１０８のいずれかに格納される。０の格納先の選
定は制御部１１３によって行われる。バッファメモリＡ
ｌＯ２，Ｂ１０４、Ｃ１０６，Ｂ１０８からの出力はそ
れぞれデータ線２０３，２０４，２０５，２０６を介し
て選択回路Ａｌｌ０．選択回路Ｂ１１１　、選択回路Ｃ
１１４および選択回路Ｄ１１５に送られる。選択回路Ａ
Ｉｔｏおよび選択回路Ｂｌｌ　１では前記のデータ線２
０３，２０４，２０５，２０６および制御部１１３から
のデータを出力するデータ線２１８の中の出力の１つを
出力として選択し、それぞれデータ線２０７，２０８に
出力する。選択回路Ａ１１０および選択回路Ｂ１１１に
対する選択指示は信号線２１０，２１１を介して制御部
１１３によって行われる。データ線２０７，２０８は共
に比較器Ａ１１２および制御部１１３への入力線となる
。

比較器Ａ１１２で比較された結果は信号線２０９を介し
て制御部１１３に送られる。

選択回路Ｃ１１４および選択回路Ｄ１１５では前記のデ
ータ線２０３，２０４，２０５，２０６および制御部１
１３からのデータを出力するデータ線２１８の出力の中
の１つを出力として選択し、それぞれデータ線２１２，
２１３に出力する。選択回路Ｃ１１４および選択回路Ｄ
１１５に対する選択指示は信号線２１５，２１６ｆｆｉ
介し人制御部１１３によって行われる。データ線２１２
，２１３は共に比較器Ｃ１１６および制御部１１３への
入力線である。比較器Ｃ１１６で比較された結果である
一致信号は信号線２１４を介して制御部１１３に送られ
る。

制御部１１３では信号線２０９，２１４の一致信号およ
びデータ線２０７，２０８，２１２，２１３を入力して
、制御部１１３の中に備えるスタック機構およびレジス
タ全操作する。更に制御部１１３は、信号線２１７′ｆ
ｔ介して記憶装置ｌＯＯへの参照を制御するためにアド
レスレジスタ１０１の内容を更新する信号、記憶装置ｌ
ＯＯから読み出されたデータを格納する先として４箇の
バッファメモリＡｌＯ２，Ｂ１０４．Ｃ１０６，Ｂ１０
８の１つを選択する信号、これらのバッファメモリ参照
を制御するためにバッ７アボインメＡｌＯ３，バッファ
ポインタＢ１０５．　バッファポインタＣ１０７゜バッ
ファポインタＤ１０９を更新する信号を送出し、且つ、
バッファメモリ１０２，１０４，１０６゜１０８の中に
記憶装置１００から転送が必要なデータが既に格納され
ているか否かをチェックしてデータ転送の要／不要を判
定し、選択回路Ａｌｌ０゜選択回路Ｂ１１１．選択回路
Ｃ１１４および選択回路Ｄ１１５への選択指示を行う。

以下、第３図、第４図、第５図および第６図を用いて第
４図に示した例題プログラムの本実施例における実行動
作を説明する。

記憶装置１００には第３図に示す形式で第１図に示すプ
ロログプログラムが格納されている。記憶装置１００の
データはプログラムの実行に伴って各バッファメモリ１
０２，１０４，１０６，１０８に格納される。第５図ｆ
ａ）（ｂ）（Ｃ）（ｄ）には、第１図のプロログプログ
ラムの処理が終了した時の各バッファメモリ１０２，１
０４，１０６，１０８の記憶状態を示す。

第６図は第１図に示したプログラムの実行ステップを説
明するための図を示す。第６図（ａｌは一致検出器Ａ１
１７の処理を中心に実行時のステップ番号９遺択回路Ａ
ｌｌ０が選択するバッファメモリおよび選択されたバッ
ファメモリの中で参照σれている語のアドレス、選択回
路Ｂ１１１が選択するバッファメモリおよび選択された
バッファメモリの中で１照されている語のアドレス、選
択回路Ａ１１０の出力、選択回路Ｂ１１１の出力、制御
部１１３の内部レジスタ情報およびスタック情報、その
実行ステップでの動作、の順に記述しである。

更に第６図（ｂ）では、第６図（ａ）で示した情報の他
。

一致検出器Ｃ１１８が一致検出器Ａ１１７と並列に動作
していることを示すため、選択回路Ｃ１１４および選択
回路Ｄ１１５に関する情報を追加している。

第１図において、節４はプロログにおける問合わせの命
令を表わしている。すなわち５節４の如くボディ部のみ
から成る間合わせ節によって実行が始まる。

節４の内部表現は第３図に示す形式で記憶装置１００の
アドレスＣＬ４番地から順次格納されている。制御部１
１３はアドレスレジスタ１０１　ＫＣＬ４番地を格納し
、その内容を読出すことにょって実行を開始する。初期
状態では、各バッファメモリ１０２，１０４，１０６，
１０８は空であり。

節４のコードは格納されてぃなり０このため、バッファ
メモリＡｌＯ２に節４に対応するコードを格納する。こ
の結果、第５図に示すようにバッファメモ！ＪＡ１０２
の２０番地から２７番地までに節４に対応する内部表現
８語が格納される。

制御部１１３はバッファポインタＡｌＯ３に節４のコー
ドの先頭番地２ｏを格納して節４の「ヘッダ」、「ポイ
ンタ」を順次読出し、次に１番目の述語に対応する語を
読出す。この語は同じ述語名をヘッダ部に持つ節ｌへの
アドレスを値として持ち、記憶装置１００から節ＩＫ対
応するコードを読出す。節１のコードは制御部１１３の
指示によって１バツクアメモリＢ　１０４’に格納され
る。

以下、第６図（ａ）に示すステップｌの処理を開始する
。

ステップ１では、バッファポインタＡｌＯ３には節４の
１番目の述語“ＰＩ（＊ｘ、＊ｙ）”に対応するコード
の格納先を指示するアドレス２２が格納され、バッファ
ポインタＢ１０５には節１の「ヘッダ」語の格納先番地
を示す１２０が格納されている。それぞれのアドレスに
対応してバッファメモリＡｌＯ２からは節４の述語名“
Ｐｌ“をデータ線２０３に出力し、バッファメモＩＪＢ
１０４からは節】の１ヘツダ」をデータ線２０４に出力
する。選択回路Ａｌｌ０は制御部１１３の選択指示信号
２１０でバッファメモ！ＪＡ１０２の出力を選択するよ
うに指示される。この結果、データ線２０７には節４の
述語名“Ｐｌ“が出力される。選択回路Ｂ１１１は制御
部１１３の選択指示信号２１１でバッファメモリＢ１０
４の出力を選択するように指示される。この結果、デー
タ線２０８には節１の「ヘッダ」が出力される。Ｃのヘ
ッダに含まれる情報はコードの属性に係るものであり、
それ自体が実行制御に影響を及ばずものではなくバッフ
ァポインタＢ１０５を歩進して。

次の実行ステップ状態となる。

第６図のステップ２ではバッファポインタＢ１０５は節
１の「ヘッダ」に続く「ポインタ」を指示し、その結果
バッファメモ！ＪＢ１０４はデータ線２０４に「ポイン
タ」の値を出力する。この「ポインタ」はヘッダ部に同
一の述語名を持つ節へのリンク情報であるが、リンクの
最終であるときにはその値はｎｕｌｌｌ−となっている
。節４のような間合わせ節では常に「ポインタ」は“ｎ
ｕｌｌ　”″である。バッファポインタＢ１０５は引き
続き歩進する。

ステップ３ではバッファポインタＢ１０５はバッファメ
モリＢ１０４の１２２番地全指示し、バッファメモリＢ
１０４の出力として節１の述語名″Ｐｌ″をデータ線２
０４に出力する。ここで、バッファメモリＡｌＯ２の出
力は節４め最初の述語名であシ、バッファメモリＢ１０
４の出力と同様にＰＩ”である。

選択回路Ａｌｌ０ではデータ線２０３のデータを選択す
るので５節４の述語名“Ｐｌ”がデータＩＩｉ！２０７
に出力される。選択回路Ｂ１１１ではデータ線２０４の
データを選択するので、節１の述語名“ｐｌ−がデータ
線２０８に出力される。前記２つの選択回路１１０，１
１１の出力が比較器Ａ１１２への入力となって、入力さ
れたデータが双方共に述語名“Ｐｌ”であることから、
比較器Ａ１１２では一致を検出する。この結果、一致検
出器Ａ１１７の出力として一致信号を信号線２０９を介
して制御部１１３に出力する。

１１１１１１部１１３では、節４と節１の現在比較対象
になっている語に続く語を次ステツプにおける比較対象
にするため、バッファポインタＡｌＯ３゜バッファポイ
ンタＢ１０５　’ｉそれぞれ歩進する。

ステップ４では、バッファメモリＡｌＯ２の出力は節４
の第１の述語名“Ｐ１″に続く第１の引数である“＊Ｘ
″となシ、この“＊Ｘ“が選択回路ＡＩｔｏの出力とな
る。バックアメモリＢ１０４０出力は節１の述語名“Ｐ
１″に続く第１の引数の値“Ａ“となシ、この“Ａ“が
選択回路Ｂ１１１の出力となる。各々の出力はデータ線
２０７，２０８を介して比較器Ａ　Ｉ　１．２に送られ
る。変数“＊Ｘ”と″へ°とは一致条件を満たしておル
、比較器Ａ１１２は信号線２０９を介して一致信号を制
御部１１３に送る。制御部１１３ではスタックの先頭０
番地に変数“＊Ｘ”の語を確保して、その値を“八“に
する。この処理によシ、変数“＊Ｘ“に“Ａ“がバイン
ドされる。バッフアポインクＡｌＯ３およびバッファポ
インタＢ１０５はそれぞれ歩進される。

ステップ５では節４の変数“＊ｘ′″に続く第２の引数
である変数“＊ｙ“がバッファメモリＡｌＯ２の出力と
なり選択回路Ａ１１０の出力となる。また、節４の“Ａ
“に続く第２の引数である変数“＊２“がバッファメモ
リＢ１０４の出力とな勺１選択回路Ｂ１１１の出力とな
る。比較器Ａ１１２では、変数“＊ｙ“と変数“＊２″
は一致条件を満足していることを検出し、制御部１１３
に信号線２０９を介して一致信号を出力する。制御部１
１３では、スタックの１番目の語を変数“＊ｙ“の語と
し、２番目の語を変数“＊２”の語として格納する。変
数“＊ｙ“と変数“＊２”が等しい値を持つべきことを
示すために変数“＊２″の語には変数“＊ｙ“へのポイ
ンタ値を格納して、変数“＊２″を参照するときには、
変数“＊ｙ“の値を参照することにする。そしてバッフ
ァポインタＡＩＯ”ｓ　バッファポインタＢ　１０５検
出した処理によシ、節４の第１述語と節１のヘッダ部の
述語とは一致することが判明する。これによって制御は
節１のボディ部と、そのボディ部の述語名と同一の述語
名をヘッド部に持つ節との一致検出に進む。

ステップ６では節１のボディ部の述語名はバッファメモ
リＢ１０４の出力“Ｐ２”″であシ、制御部１１３は“
Ｐ２“をヘッド部に持つ節２へのアドレスを得る。

制御を述語名“Ｐ２″の一致検出に移す前に、節４の２
番目の述語名“Ｐ１″を指示するアドレスを制御部１１
３のＮＥＸＴ　レジスタに格納する。

これは以降での述語“Ｐ２　（Ｂ、　Ｃ，＊ｚ　）“の
比較処理で、述語の一致を検出したとき制御を節４の第
２述語“ＰＩ　（＊ｘ、　＊ｘ　）　”の一致検出処理
に進めるだめのものである。にでＮ　ＥＸＴレジスタに
格納されるアドレスは記憶装置１００に格納されている
前記述語名″Ｐｌ″に対すするアドレスである。各バッ
ファメモリ１０２，１０４゜１０６．１０８のアドレス
と記憶装置１００のアドレスとの対応づけは制御部１１
３のバッファ管理機能を利用して実現する。

ステップ７では節２のコードの先頭にあるヘッダーを参
照する。節２はバッファメモリに格納されていないので
記憶装置１００からバッファメモリ０１０６に読込む。

バッファメモ！ＪＣ１０６に格納した後、バッファポイ
ンタＣ１０７の値は節２のヘッダーを指示する“１５０
”番地となる。

続くステップ８以降を第６図（ｂ）に示す。

ステップ８では節２のポインタを参照する。このポイン
タの値は“ｎｕｌｌ″ではなく２節２のヘッダと同一の
述語名を持つ節３のヘッドを指示している。このポイン
タで指示された節３はバッファメモリには格納されてい
ないので、バッファメモリＤ１０８に格納する。このと
きのバッ７７メモリの状態を第５図に示す。

ステップ８までの処理においては一致検出器Ａ１１７の
みを用いて述語の一致を検出した。以後の処理では、一
致検出器Ａ１１７と一致検出器Ｃ１１８と金層いて一致
検査を行う。ステップ８において、バッファポインタＤ
１０９には節３のヘッダを指示するアドレス“２００°
を格納する。

ステップ９では選択回路Ｃ１１４の出力として選択した
節３のヘッダを読出し、バッファポインタＤ１０９を歩
進する。ステップ１０では選択回路Ｃ１１４の出力とし
て選択した節３のポインタを読出し、バッフアポインク
Ｄ１０９　’ｅ歩進する。

ステップ１１以降では、一致検出器Ａ１１７と一致検出
器０１１８とを並列に動作させ、節１の述語“Ｐ２　（
Ｂ、Ｃ，＊ｚ　）　”と節２の述語“Ｐ２（Ｂ、Ｄ、Ｅ
）”との一致検査および節１０述語“Ｐ２（Ｂ、Ｃ，＊
ｚ）”と節３の述語“Ｐ２（Ｂ、Ｃ，Ａ）“との一致検
査を同時に行う。ステップ１１では４箇の選択回路１１
０，１１１゜１１４．１１５の出力はすべて述語名“Ｐ
２“であシ、一致検出器Ａ１１７と一致検出器Ｃ１１８
は一致信号を制御回路１１３に送る。続いて両一致検出
器Ａ、Ｃ，１１７，１１８で第１引数の一致検査処理の
ために、バックアポインｐＢ、ｃ、Ｉ）。

１０５．１０７，１０９　を歩進する。

ステップ１２では４箇の選択回路１１０．Ｉｌｌ。

１１４．１１５が述語名“Ｐ２“を持つ述語の第１引数
としてすべて“Ｂ″を出力する。この結果一致検出器Ａ
１１７と一致検出器０１１８は一致信号を制御部１１３
に送る。バッファポインタＢ。

Ｃ，Ｄ、１０５，１０７，１０９　を歩進する。

ステップ１３では、一致検出器Ａ１１７では不一致を検
出する。つまシ、選択回路Ａｌｌ０は節２の述語名’Ｐ
２″の第２引数“Ｄ″を出力し、選択回路Ｂ１１１では
節１の述語名“Ｐ２“の第２引数“Ｃ″を出力する。こ
の結果比較器Ａ　１１２は不一致信号を制御部１１３に
出力し、制？ｉ１１部１１３では、節１の述語“Ｐ２　
（Ｂ、Ｃ，＊ｚ　）″と節２の述語“Ｐ２’（Ｂ、Ｄ、
Ｅ）“とけ一致しないことを検出する。他方、一致検出
器Ｃ１１８でけ一致を検出する。つ［Ｌ選択回路Ｃ１１
４は節３の述語名“Ｐ２“の第２引数″Ｃ“を出力し、
選択回路Ｄ１１５は節１の述語名“Ｐ２″の第２引数“
Ｃ′を出力するので、比較器Ｃ１１６で一致を検出する
。バッファボイ／りＢ１０５およびバッファポインタＤ
１０９を歩進し、第３引数の一致検査に備える。

ステップ１４では、節１と節３の述語“Ｐ２（・・−）
″の一致を検査する。選択回路Ｃ１１４は節３の述語名
“Ｐ２”の第３引数“八〇を出力し、選択回路Ｄ１１５
は節４の述語名″Ｐ２°の第３引数“＊２″を出力する
。これは、定数と変数の組合わせとして、比較器Ｃ１１
６では一致を検出し、信号線２１４を介して制御部１１
３に一致信号を出力する。この結果、制御部１１３内の
スタックでは、変数“＊Ｚ″にＡ“を結合する処理を施
す。この処理では、スタック中の変数“＊ｚ′″の領域
からポイントされている変数“＊ｙ″の領域に“Ａ゛が
格納される。

以上の処理によ１節４の第１述語“Ｐｌ（＊ｘ、＊ｙ）
“に関する処理が終了して、次に節４の第２述語である
“ＰＩ（＊Ｘ、＊Ｘ）”の処理に進む。第２述語は第１
述語同様述語名が“Ｐ１″であるので節ｌとの一致を調
べる。節ｌは既にバッファメモ”ＪＢ１０４に格納され
ているので記憶装置１００からの読出しは行う必要はな
い。以降の処理では、節１の述語″ＰＩ（Ａ、＊ｚ）”
’との一致が検出される。更に、節ｌの述語”　Ｐ　２
　（Ｂ、Ｃ，＊ｚ　）“と節２および節３との一致を前
記並列処理で調べる。節２との比較は不一致で節３との
比較は一致することで５節４の第２述語の処理が終了す
る。節４には続く述語がないので、節４の処理全体が終
了する。

本発明における前記の一実施例では５節を表現する内部
表現形式として、先頭にヘッダ情報９次にポインタ情報
が配置される例で処理を説明した。

ここで、並列動作を効率よく行うために、ポインタ情報
をできるだけ早い機会に得て、並列処理の可否を早く検
出するためには、ポインタ情報を先頭にする方が効果的
な場合がある。本発明はボインタ情報を節の内部表現の
先頭に配置する表現形式の場合にも適用される。

以上の説明で明らかなように、本発明によシ。

プロログに代表される述語論理型言語の処理を高速に実
行することができる。

【図面の簡単な説明】

第１図はプロログのプログラム例を示す図、第２図はこ
の例における内部形式を示す図、第３図は第１図のプロ
グラム例を内部形式に変換したときの記憶装置イメージ
を示す図、第４図は本発明の装置の一実施例を示すブロ
ック図、第５図（ａ）（ｂ）（Ｃ）（ｄ）は第１図のプ
ログラム例を処理するために記憶装置からバッファメモ
リに格納された内部表現のイメージを示す図、第６図（
ａ）（ｂ）は第１図のプログラム例を第４図に示した実
施例によって実行するときの実行ステップを示す図であ
る。 １００・・・・・・記憶装置、１０１・・・・・・アド
レスレジスＪ、１０２・・・・・・バッファメモリＡｂ
１０３・・・・・・バッファポインタ人、１０４・・・
・−・バッファメモリＢ、１０５・・・・・・バッファ
ポインＪＢ、１０６・・・・・・バッファメモ！ＪＣ，
１０７・・・・・・バッファポインタＣ，１０８・・・
・−・バッファメモ！ＪＤ、１０９・・・・・・バッフ
ァポインタＤ、１１０・・・・・・選択回路Ａ、１１１
・・・・・・選択回路Ｂｔｌ１２・・・・・・比較器Ａ
ｂｌ１３・・・・・・制御部、１１４・・・・・・選択
回路Ｃ，１１５・・・・・・選択回路り、１１６・・・
・・・比較器Ｃ０神　Ｉ　Ｐ／　を乙　；＊ｚ）←Ｐ２
　（Ｂ、ｃ、；ｒｚ）−沖　２　β２　（Ｂ、ｖ、ｂ　
）。 吟、づ　ｒｚ　（Ｂ、　ｃ、ｙ＋ハ 管“ｐ４　＝ｔｎ；＊χ、末ｌ）、ｆ”Ｎネχ１オχ九
茅１　広 ￥−ｚ’ｓ （０−）　（ａ） 卒Ｓ珂

Claims (1)

【特許請求の範囲】
1. 述語名とその引数よシ成る述語の連らなりから成る節の
   集合として書き下す述語論理型言語を処理する装置にお
   いて、前記節の内部表現を格納する記憶装置と、前記記
   憶装置から読み出された節の内部表現を一時的に格納す
   る複数のバッファメモリと、前記複数のバッファメモリ
   から読み出された２つの前記述語の間の一致を調べる複
   数の一致検出器と、前記述語間の関係を次々にたどる道
   筋を保持するためのスタック機構および複数個の内部レ
   ジスタおよびバッファメモリの管理機能を含む制御装置
   とを備え、前記制御装置の制御の下に前記複数の一致検
   出器で述語間の一致検出を複数筒同時に検出できるよう
   にしたことを特徴とする述語論理型言語処理装置。