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

Abstract

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

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 本発明は述語論理型言語処理装置に関する。

〔技術環境〕

述語論理型言語処理装置とは述語名とその引数よシなる
述語の連な）から成る節の集合として書き下す述語論理
型言語を処理する装置であるが、以下プログラミング言
語であるプ目ログ言語を例にとシ説明する。

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

好む（太部９畳物）←果物（骨物） 本例で「好む」と「果物」を述語名、「太部」「養物」
を引数と称し、蒼印はその引数が変数であることを表わ
す。即ち、上側は「太部」は「果物」という述語名で表
記された述語の引数として書かれている事物を「好む」
ことを表現している。

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

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

〔従来技術〕

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

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

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

〔発明の目的〕

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

〔発明の構成〕

本発明によると、述語名とその引数よ構成る述語の連ら
なりから成る節の集合として書き下す述語論理型言語を
処理する装置において、前記装置内での前記節の内部表
現を格納する記憶装置と、前記記憶装置から読み出され
た節の内部表現を一時的に格納する複数のバッファメモ
リと、前記複数のバッファメモリの各出力のうち１つを
選択して出力とする第１の選択回路と、前記複数のバッ
ファメモリの各出力のうち１つを選択して出力とするに
２の選択回路と、前記述語間の関係を次々にたどる道筋
を保持するためのスタック機構および内部レジスタおよ
びバッファメモリの管理機能および前記２つの選択回路
での選択指定機能およ数のバッファメモリの各出力のう
ち１つを前記第１の選択回路で選択し前記複数のバック
７メモリ制御装置に送シ前記２つの選択回路で選択され
たバッファメモリからの読出しを同時に行うことによシ
互いの述語間の一致を検出で・きるようにしたことを特
徴とする述語論理型言語処理装置が得られる。

〔実施例の説明〕

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

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

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

述語１←述語２．述語３．・・・、述語ｎ←印は論理記
号であシ、その左側に存在し得る述語は高々−箇である
。これをヘッド部と呼び、←印の右側をボディ部と呼ぶ
が、ボディ側の述語を区切る１、′印は述語間の論理積
を表わす。上記の一般形式は述語２．述語３．・・・、
述語ｎの論理積が成立するとき、述語ｌが成立すること
を表現しておシ、この形式を規則節と呼ぶ。

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

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

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

引数同士の比較において、−万が変数、他方が定数であ
れば変数に定数の値がバインドされる。また双方共に変
数であれば同一値を採るべく、−万が他方へのポインタ
に書き換えられる。

この二連シの処理も一致条件を満たすものである。

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

第１図はプロログのプログラム例を示す。図中”Ｐｉ”
、＠Ｐ２”は述語名、ｔａ）、、ｎ　、ｕＢｎ　。

６Ｃ”・“Ｄ″ｐ１Ｅ”は定数引数・＊Ｘ”　。

”Ｙ”＋”＊ｚ”は変数引数である。節１社規則説であ
〕、節２．節３は宣言節２節４は間合わせ節である。

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

プログラムの実行は間合わせ節から始まる。第１図の例
では節４の最初の述語１ｐ１（＊ｘ、＊ｙ）”の処理か
ら始まシ、ステップ（１）によって節１が見出され、す
べての引数が一致することからステップ（２）へ進む。

ここで変数観＊Ｘ”には節１の定数値＠Ａ”がバインド
され、変数６＊ｙ”には変数ｕ−４ｃ　ｚ”がバインド
されて６＊ｙ”と鴫＊ｚ”の値が等しいことが示される
。

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

前記ステップ（２）において節３が宣言節であることか
ら、節１の処理へ制御が戻る。節１のボディ部には述語
″″Ｐ２（Ｂ、Ｃ，＊ｚ）”Ｋ続く述語はないので、節
１の処理は終了し・節１の処理に制御を渡した節４の処
理へ制御が戻る。これまでの処理結果として、節４の変
数”＊ｘ”ＩＩＣは定数値りＶがバインドされ、変数Ｉ
Ｉ　＊　Ｙ　１９にも同じく定数値″′Ａ”がバインド
される。

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

このときには変数”＊ｚ’ｈ％定の値がバインドされて
いない変数であり、前記ステップ（１）の処理で初めて
変数６＊×”の値６Ａ”にバインドされる。

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

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

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

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

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

第３語は、節１の述語名″′Ｐ１”に対応して、述語名
を値として持つことを示すタグフィールドと、その述語
名は具体的に”ＰＩ”であることを示す値フィールドを
持つ。第４語では述語″′Ｐ１（Ａ９才ｔ）″の第１引
数”Ａ”の属性がアトムであることをタグフィールドで
示し、その値が＠　Ａ　＃であることを値フィールドで
示す。第５語では述語ｗｐ１（Ａｔ＊ｚ）”の第２引数
である変数１＊ｚ”の属性が変数であることをタグフィ
ールドで示し、そ゛の変数が節１の中に現われる最初の
変数であることを示す番号（０）を値フィールドの値と
して持つ。

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

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

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

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

第４図は本発明の装置の一実施例を示すブロック図であ
る。図中１００は第３図の説明で述べた内部表現をその
１１の形で格納する記憶装置、１０１は記憶装置１００
に格納されているコードを読出すだめのアドレスレジス
タ、１０２．１０４．１０６．１０８は記憶装置１００
から読出されたコードを一時的に格納するバッフ丁メモ
リＡ１バッフ丁メモリＢバッファメモリＣ，バッファメ
モリＤ、１０３゜１０５．１０７，１０９　は夫々バッ
フ了メモリ１０２゜１０４．１０６，１０８　の語を示
すだめのバッフ丁ポインタＡ、バッファポインタＢ、バ
ッフ丁ポインタＣ，バッフ丁ポインタＤ、１１０は前記
の４箇のバックアメモリ１０２，１０４，１０６，１０
８の出力の中の１つの出力を選択する第１の選択回路Ａ
、１１１は前記の４箇のバッフ了メモ１Ｊ１０２゜１０
４．１０６，１０８の出力の中の１つの出力を選択する
第２の選択回路Ｂ、１１２ｔｊ：選択回路Ａ１１０　と
選択回路Ｂ１１１によって選択された語の一致を比較し
て一致を検出するための比較器である＠比較器１１２は
入力される２語のビットパターンが一致しているととを
検出するだけでなく、変数を示す語と定数を示す語との
比較において一致を検出する。１１３はスタック機構お
よび内部レジスタおよび各バッファメモリ１０２，１０
４゜１０６．１０８および記憶装置１００の管理を含み
比較器１１２からの一致検出信号に基づいて他の構成要
素の動きを制御する制御部である。制御部１１３は従来
型のプロセッサと同様の構成で実現できるので、その内
部機構については特に述べない。

第４図で、アドレスレジスタ１０１で指定するアドレス
がアドレス線２０１を介して記憶装置１００に送られる
と、出力がバス２０２を介して各バッファメモリ１０２
，１０４，１０６，１０８に送られる。バス２０２のデ
ータは前記４箇のバッファメモリ１０２，１０４，１０
６，１０８のいずれかに格納される。この格納先の選定
は制御部１１３によって行われる。バッファメモリＡｌ
Ｏ２，Ｂ１０４゜Ｃ１０６，Ｄ１０８からの出力はそれ
ぞれデータ線２０３．２０４，２０５，２０６を介して
選択回路Ａ１１０および選択回路Ｂ１１１に送られる。

選択回路Ａ１１０および選択回路Ｂ１１１では前記のデ
ータ線２０３゜２０４．２０５，２０６の信号中の１つ
を出力として選択し、それぞれデータ線２０７，２０８
に出力する。データ線２０７，２０８の信号は共に比較
器１１２および制御部１１３への入力となる。比較器１
１２で比較された結果である一致信号は信号線２０９を
介して制御部１１３に送られる。

制御部１１３では信号線２０９の一致信号及びデータ線
２０７，２０８の信号を入力して、制御部１１３の中に
備えるスタック機構およびレジスタを操作する。更に制
御部１１３は、信号線２１２を介して記憶装置１００へ
の参照を制御するためにアドレスレジス゛りｌＯｌの内
容を更新する信号、記憶装置１００から読み出されたデ
ータを格納する先として４箇のバッファメモリＡｌＯ２
，Ｂ１０４゜Ｃ１０６，Ｄ１０８の１つを選択する信号
、これらのバッファメモリ参照を制御するためにノくツ
ファポインタＡｌＯ３，バクフ了ポインタＢ１０５　、
ノく１０６．１０８の中に記憶装置１００から転送が必
要なデータが既に格納されているか否かをチェックして
データ転送の要／不要を判定し、ル寺二選択回路Ａ１１
０および選択回路Ｂ１１１で選択すうＯ 以下、第３図、第４図、第５図および第６図を用いて第
１図に示しだ例題プログラムの本実施例における実行動
作を説明する。

記憶装置１００には第３図に示す形式で第１図に示すプ
ロログプログラムが格納されている０記憶装置１００の
データはプログラムの実行に伴って各バッファメモリ１
０２，１０４，１０６，１０８に格納される。第５図（
ａ）（ｂ）（ｃ）（ｄ）には、第１図のプロログプログ
ラムの処理が終了した時の各バッファメモリ１０２，１
０４，１０６，１０８の記憶状態のステップ番号、選択
回路Ａ１１０　が選択するバッファメモリおよび選択さ
れたバッファメモリの中で参照されている語のアドレス
、選択回路Ｂ１１１が選択するバッファメモリおよび選
択されたバッファメモリの中で参照されている語のアド
レス、選択回路Ａｌｌ０の出力１選択回路Ｂ１１１の出
力、制御部１１３の内部レジスタ情報およびスタック情
報、その実行ステップでの動作の順に示しである。

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

節４の内部表現は第３図に示す形式で記憶装置１００の
アドレスＣＬ４番地から順次格納されている。制御部１
１３はアドレスレジスタ１０１にＣＬ４番地を格納し、
その内容を読出すことによって実行を開始する。初期状
態では、各バッファメモリ１０２，１０４，１０６，１
０８は空であシ、節４のコードは格納されていない。こ
のため、バッファメモリＡｌＯ２に節４に対応するコー
ドを格納する・この結果、第５図に示すようにバッフ了
メモ１ＪＡ１０２の２０番地から２７番地までに節４に
対応する内部表現８語が格納される。

制御部１１３はバッフ丁ポインタＡｌＯ３に節４のコー
ドの先頭番地２０を格納して節４の「ヘッダ」、「ポイ
ンタ」を順次読出し、次に１番目の述語に対応する語を
読出す。この語は同じ述語名をヘッダ部に持つ節１への
アドレスを値として持ち、記憶装置１００から節１に対
応するコードを読出す。節１のコードは制御部１１３の
指示によって、バッフ丁メモ１ＪＢ１０４に格納される
Ｏ以下第６図に示すステップ１の処理を開始する。

ステップ１では、バッフ丁ポインタＡｌＯ３には節４０
１番目の述語り１（＊ｘ＋＊ｙ）”に対応するコードの
格納先を指示するアドレス２２が格納され、バッフ丁ポ
インタＢ１０５には節１０「ヘッダ１語の格納先番地を
示す１２０が格納されている。

それぞれのアドレスに対応してノ（ラフ丁メモリＡｌＯ
２からは節４の述語名″＝Ｐ１”をデータ線２０３に出
力し・）くラフアメモリＢ１０４からは節１の「ヘッダ
」をデータ＠２０４に出力する。選択回路Ａ１１０は制
御部１１３の選択指示信号２１０でバッファメモリＡｌ
Ｏ２の出力を選択するように指示される。この結果、デ
ータ線２０７には節４の述語名り１”が出力される。選
択回路Ｂ１１１は制御部１１３の選択指示信号２１１で
ノ（ラフアメモリＢ１０４の出力を選択するように指示
される。この結果、データ線２０８には節１の「ヘッダ
」力！出力される。このヘッダに含まれる情報はコード
の属性に係るものであシ、それ自体が実行制御に影響を
及ばずものではなく、）くラフ丁ポインタＢ１０５を歩
進して、内の実行ステップ状態となる。

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

ステップ３ではバッフ了ポインタＢ１０５はノ（ラフア
メモリＢ１０４の１２２番地を指示し、）ぐラフアメモ
リＢ１０４の出力として節１の述語名”Ｐｉ”をデータ
線２０４に出力する。ここで、バッフ了メモ！ＪＡ１０
２の出力は節４の最初の述語名であシ、バッファメモリ
Ｂ１０４の出力と同様に”Ｐｉ”である。選択回路Ａｌ
ｌ０ではデータ線２０３のデータを選択するので、節４
の述語名″′Ｐ１′がデータ線２０７に出力される◎選
択回路Ｂ１１１ではデータ線２０４のデータを選択する
ので、節１の述語名−ｐ　１ｍがデータ線２０８に出力
される。前記２つの選択回路１１０，１１１の出力が比
較器１１２への入力となって、入力されたデータが双方
共に述語名＠ＰＩ”であることから、一致信号を信号線
２０９を介して制御部１１３に送る■制御部１１３でＬ
この比較結果によシ１節４と節１の現在比較対象になっ
ている語に続く語を次ステツプにおける比較対象にする
ため、バッフ丁ポインタＡｌＯ３，バッファポインタＢ
１０５をそれぞれ歩進する。

ステップ４では、バッフ丁メモ！ｊＡ１０２の出力は節
４の第１の述語名″Ｐ１”に続く第１の引数である“＊
Ｘ”となシ、この“＊Ｘ”が選択回路Ａ１１０の出力と
なる。バッファメモリＢ１０４の出力は節１の述語名パ
Ｐ１”に続く第１の引数の値り”となシ、この−Ａ”が
選択回路Ｂ１１１の出力となる。

各々の出力はデータ線２０７　、２０８を介して比較器
１１２に送られる。変数頓＊ｘ”と′Ａ”とは一致条件
を満たしており、比較器１１２は信号線２０９を介して
一致信号を制御部１１３に送る。制御部１１３ではスタ
ックの先頭０番目に変数“＊Ｘ”の語を確保して、その
値を′Ａ”にする。この処理によシ、変数６＊ｘ”に”
Ａ”がノくインドされる。

バッフ了ポインタＡｌＯ３およびノぐラフ丁ポインタＢ
１０５はそれぞれ歩進する。

ステップ５では節４の変数“＊ｘ＃に続く第２の引数で
ある変数＊　＊　ｙ　ｎがノくラフアメモリＡｌＯ２の
出力となシ選択回路Ａ１１０の出力とカる。また節４の
気Ａ〃に続く第２の引数である変数１＊Ｌ“がバッファ
メモリＢ１０４の出力となシ、選択回路Ｂ１１１の出力
となる。比較器１１２では、変数１＊ｙ“と変数１＊ｔ
”は一致条件を満足しておシ、制御部１１３に信号線２
０９を介して一致信号を出力する。制御部１１３では、
スタックの１番目の語を変数”＊ｙ”の語とし、２番目
の語を変数６＊ｚ”の語として格納する。変数競＊ｙ”
と変数″′＊ｚ”が等しい値を持つべきことを示すため
に変数″Ｉ＊ｚ”の語には変数“＊ｙ”へのポインタ値
を格納して、変数６＊ｚ”を参照するときには、変数“
＊ｙ″の値を参照することにする。そしてバッファポイ
ンタＡｌＯ３、バッファポインタＢ１０５を歩進させる
。

前記の述語名及び述語内のすべての引数の一致を検出し
た処理によシ、節４の第１述語と節１のヘッダ部の述語
とは一致することが判明する。これによって制御は節１
のボディ部と、そのボディ部の述語名と同一の述語名を
ヘッド部に持つ節との一致検出に進む。

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

制御を述語名″′Ｐ２”の一致検出に移す前に、節４の
２番目の述語名１Ｐ１”を指示するアドレスを制御部１
１３のＮＥＸＴレジスタに格納する。これは以降での述
語″′Ｐｚ（Ｂ、Ｃ，＊ｚ）”の比較処理で述語の一致
を検出したとき制御を節４の第２述語”ＰＩ（＊ｘ、＊
ｘ）”の一致検出処理に進めるためのものである。また
、同時に、節１のボディ部の述語名″＝Ｐ２”を示すア
ドレスを制御部１１３のＭＴｆ’ｔＹレジスタに格納す
る。これは、節１のボディ部の述語″’Ｐ２（Ｂ、Ｃ，
＊ｚ）”と一致検査対象の述語・Ｐ２（Ｂ、Ｄ、Ｅ）”
をヘッド部に持つ節との一致検査結果が不一致のときに
、述語°′Ｐｚ（Ｈ，Ｃ，Ａ）”をヘッド部に持つ節３
との比較を改めて述語″’Ｐ２（Ｂ、Ｃ，＊乙）＃から
開始するためのものである。

この不一致の処理はステップ７以後に示す。

ここで、ＮＥＸＴレジスタ、ＲＥＴＲＹレジスタに格納
されるアドレスはそれぞれ記憶装置１００に格納されて
いる前記述語名°“Ｐｌ”、前記述語名″Ｐ２”に対応
するアドレス２５，１２５　である。各バッファメモリ
１０２，１０４．１０６，１０８のアドレスと記憶装置
１００のアドレスとの対応づけは制御部１１３のバッフ
ァメモリ管理機能を利用して実現する。

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

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

ステップ８では節２のポインタを参照する。このポイン
タの値は制御部１１３の内部レジスタであるＬＩＮＫレ
ジスタに保存する。これは、以下の述語名”Ｐ２”に係
る一致検査が不一致にｋつだ時にヘッド部に述語り２（
Ｂ、Ｃ，Ａ）’を持つ節３との一致検査を開始するため
に、この節３へのアドレス情報を制御部１１３の中に退
避するためのものであシ、このステップ８にＬＩＮＫレ
ジスタを含んだ操作を示す。

ステップ９では述語名６Ｐ２”の一致を検出する＠続い
て、パラフチポインタＣ１０フ、バツフアポインタＢ１
０５を歩進する。

ステップ１０では述語名”Ｐ２”の第１引数が両方共に
″Ｂ”であることがら一致が検出される。

続くステップ１１では節２の引数が”Ｄ”、節１の引数
が′Ｃ”であることから不一致となる。この結果は信号
ａ２０９を介して比較器１１２がら制御部１１３に送ら
れる。

制御部１１３ではヘッド部の述語名がａＰ２”である他
の節すなわち節３との比較を開始するため、ステップ１
２では節１の述ｒｔｕｐ２＋Ｂｔｃ＋＊ｚ）”に関する
一致を改めて調べるために、以前に対比しておいたＲＥ
ＴＲＹレジスタの節１の述語名”　Ｐ　２”へのアドレ
スに対応するバッファメモリＢ１０４内のアドレスの値
１２５をバッファポインタＢ１０５に格納する０また、
以前に退避しておいたＬＩＮＫレジスタの内容は節３へ
のアドレスであシ、節３は節１の述語＠ｐ２（Ｂ、Ｃ，
＊ｚ）”との比較対象となる０節３はどのバッファメモ
リにも格納されていないので節３のコードが記憶装置１
００がらバス２０２を介してバッファメモ！ＪＤ１０８
に格納される。

ステップ１２からステップ１７までにおいて節１の述語
″’Ｐ２（Ｂ、Ｃ，＊Ｚ）”と節３の述語ｕ　ｐ　２（
Ｂ、Ｃ，Ａ）”との一致が検出される。ステップ１７で
は変数１＊ｚ〃に”Ａ”がバインドされる。

との結果、スタック中の変数”＊ｚ’の領域からポイン
トされている変数１＊ｙ”の領域に”Ａ”が格納される
。

以上の処理により、節４の第１述語”Ｐｉ（＊ＸＪ＊ｙ
）”に関する処理が終了して、次に節４の第２述語であ
るｔｌＰｌ　（＊ｘ　＋　＊ｘ）”の処理に進む。第２
述語の述語名は第１述語の述語名と同様″−ｐ１”であ
るので節ｌとの一致を調べる。節１は既にバッフ丁メモ
１ＪＢ１０４に格納されているので記憶装置１００から
の読出しは行う必要はない。ステップ１８からステップ
２３までにおいて、節１の述語”ＰＩ　（Ａ、＊ｚ）”
との一致が検出される。

以後の処理では節１の述語″Ｐ２（Ｂ、Ｃ，＊ｚ）”と
節２の一致を調べ、不一致であることから節３との一致
を調べ、結果が一致することで、節４の第２述語の処理
が終了する。節４には続く述語が力いので、節４の処理
全体が終了する。

比較器１１２は制御部１１３への制御信号を出力する。

この比較器１１２０機能は制御部１１３の一部とも考え
られる。第４図に示す実施例の説明では、比較器１１２
は選択回路Ａ１１０および選択回路Ｂ１１１からの出力
を同時に参照して比較できることを説明するために制御
部１１３とは別に示しである。

〔発明の効果〕

以上の説明で明らかなように、本発明によシ、プロログ
に代表される述語論理型言語の処理を高速に実行するこ
とができる。

【図面の簡単な説明】

第１図はプロログのプログラム例を示す図、第２図はこ
の例における内部形式を示す図、第３図は第１図のプロ
グラム例を内部形式に変換したときの記憶装置イメージ
を示す図、第４図は本発明の装置の一実施例を示すブロ
ック図、第５図（ａ）（ｂ）（Ｃ）（ｄ）は第１図のプ
ログラム例を処理するために記憶装置からバッファメモ
リに格納された内部表現のイメージを示す図、第６図は
第１図のプログラム例を第４図に示した実施例によって
実行するときの実行ステップを示す図である。 １００・・・・・・記憶装置、１ｏ１・・・・・アドレ
スレジスタ、１０２・・・・・・バッファメモリＡ１１
０３・・・・・・バク７丁ポインタＡ、１０４　・・・
・バッファメモリＢ、１０５・・・・・・バッファポイ
ンタＢ、１０６・・川・バッフ了メモＩＪｃ、１０７・
・・・・・バッファポインタＣ，１０８・・・・・・バ
ッファメモリＤ、１０９　・・・・・バッファポインタ
Ｄ１１１０・・・・・・選択回路Ａ、１１１・・・・・
・選択回路Ｂ、１１２・・・・・比較器、１１３・・・
・・・制御部。 代理人　弁理士　内　原　音 １！Ｉｔ　ＰＩ（Ａ　才Ｚ＞ＰＩ（Ｂ、ｅ、水：ｌ入伸
７Ｐ２（β、Ｄ、Ｅ八 姉３　ＰＺ（Ｂ、ｅ、Ａへ １４　−　ＰＩ（＜；ｌ）　ｔ　Ｖジ、　ＰＩと＜ｚ　
、ｔ、ｚ）。 姶　／　２ 第７　図

Claims (1)

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