JPH061442B2 - ユニフイケ−シヨンの並列処理装置 - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、ユニフィケーションの並列処理装置に係る。

〔発明の背景〕

従来、述語論理型言語の処理系は汎用計算機上に構築さ
れていた。このため、プログラムの実行も、当然のこと
ながら逐次的に実行されていた。そこで、１対の引数に
対してのみユニフィケーションを行なうユニファイアを
複数ならべて処理性能を上げる方式が提案された（特開
昭６０−７４０４０）。しかし実際のプログラムは引数
の数が２〜３程度と少ないため、上記方式では、処理性
能の高速化にはつながらない。ユニフィケーションの実
行で時間がかかるのは、引数がともにリスト形式のデー
タで形成されている場合である。リストは可変長のデー
タをポインタを使って結合しているため、メモリ上にデ
ータをバラバラにして持てるという利点がある。即ち、
可変長のデータをまとめて記憶する場合に発生する記憶
領域の大きさの不均一及びこれにより派生する記憶領域
のめんどうな管理を回避できる。一方、リスト形式で表
現したデータは、ポインタをたどる必要があるため、メ
モリからのデータの読み出しに時間がかかる。したがっ
て、リスト形式のデータのユニフィケーションが成功す
る場合では、その成功検出に時間がかかる。一方、定数
のユニフィケーションは、その成功・失敗の検出は短時
間で行なえる。したがって、リスト形式のデータユニフ
ィケーションが終わってから定数のユニフィケーション
を行なう方式では、定数のユニフィケーションが失敗す
る場合の失敗の検出が遅くなる。

〔発明の目的〕

本発明の目的は、ユニフィケーションの失敗を早く検出
することができるユニフィケーション並列処理装置を提
供することにある。

〔発明の概要〕

引数のユニフィケーションには、リスト同士のユニフィ
ケーションのように負荷の重いものと、変数や定数のユ
ニフィケーションのように負荷の軽いものがある。リス
ト同士のユニフィケーションは、リスト構造を次々とた
どってデータを読み出し、その読み出したデータ同士を
比較するために負荷が重くなる。一方、定数同士のユニ
フィケーションは読み出したデータ同士を比較すれば、
同一のデータか否かが直ちに判別できる。また、変数
は、どんな値でもとり得るため、ユニフィケーションは
常に成功し、引数には新たな値が書き込まれるだけであ
る。したがって、定数又は変数のユニフィケーションの
負荷は軽い。しかるに、リスト同士のユニフィケーショ
ンが失敗する確率と、定数同士のユニフィケーションが
失敗する確率は同程度とみなすことができる。

以上述べた内容から、プログラム実行時のボトルネッ
クは、リスト同士のユニフィケーションにあること、
定数同士のユニフィケーションを優先的に実行すれば、
ユニフィケーション失敗が早く見つかり、リスト同士の
ユニフィケーションのように負荷の重い処理を行なわな
くて済む、との結論を得た。

従来汎用計算機上でソフト的に実現されているような、
引数同士の詳細なユニフィケーションを行なうユニファ
イアの他にもう１つ引数同士のタグ部が定数又は変数の
場合のみユニフィケーションを実行するユニフィケーシ
ョンを優先的に実行し、後者のユニファイアで定数同士
のユニフィケーションが失敗した場合に前者のユニファ
イアに割込みを発生するユニファイアを設けた。

〔発明の実施例〕

以下、本発明の一実施例を第１図により説明する。

第１図はユニフィケーションの並列処理装置の装置構成
図である。プログラム実行部１０１は、ユニフィケーシ
ョンを行なうプログラムや引数のメモリ１０２における
格納番地をデータ線１０５、制御線１０７，１０８を通
してユニファイアＡ１０３、ユニファイアＢ１０４に送
信する。第２図にメモリに格納されているプログラムの
例を示す。２０１は質問であり、２０２は質問に対する
解の候補節である。プログラムは、質問とそれと同一名
称の関数を左辺に持つ候補節との間で引数のユニフィケ
ーションを行なうことにより実行される。質問は、３引
数を持ち、第１引数はリスト：第２引数は変数、第３引
数は定数１である。候補節は、同じく３引数を持つが、
第１引数はリスト、第２引数は定数１、第３引数は定数
２である。第３図はこれら引数のデータ形成である。引
数はタグ部とデータ部で構成される。第４図は、引数が
リストの場合のデータ形式例である。リストは、第１ワ
ード（以下carと略記）部４０１，４０３，４０５，４
０７と第２ワード（以下cdrと略記）部４０２，４０
４，４０６，４０８により構成され、cdr部は次のリス
トのcar部へのポインタとなっている。

第５図は：ユニファイアＡの制御論理である。ユニファ
イアＡは、質問のすべての引数について（リスト形式の
引数を含めて）、その出現順に順次、候補節との間でユ
ニフィケーションを行うものである。第６図は、ユニフ
ァイアＢの制御論理である。ユニフィケーション制御部
Ａ５０１は、プログラム実行制御部からユニファイ開始
の指令を５１０を通して受信すると、質問および候補節
のメモリからの読み出し番地を５０５に出力する一方、
読み出した結果を記憶するためのタイミング信号５０
７，５０８を出力する。５０２，５０３はレジスタであ
り、メモリからデータ線５０６を通して読み出された質
問および候補節の引数のデータ部を保持する。ユニフィ
ケーション制御部Ａは、質問および候補節のタグ部のチ
ェックを第１引数から順に行なう。第２図のように、引
数がリストの場合は、第４図のチェインを順次たどって
タグ部を比較する。引数が定数の場合は、タグ部の他、
データ部を比較器５０４で比較し、一致したかどうかを
信号５０９でチェックする。引数のうち一方が変数だっ
た場合は、比較したもう一方の引数の情報をメモリの変
数を読み出した場所に書き込む。

ユニファイアＢは、質問内のすべての引数の内、リスト
形式の引数については、リスト内の各引数についてユニ
フィケーションを行うことなく、そのリスト形式の引数
について、候補節例の引数との一致が検出されたものと
して処理するもので、これによりリスト形式以外の引数
のユニフィケーションをユニファイアＡより早期に行う
ようになっている。これにより、リスト形式以外の引数
についての不一致をユニファイアＡより早期に検出し、
不一致が検出されたときには、ユニファイアＡに割り込
みにより不一致を通知するようになっている。ユニフィ
ケーション制御部Ｂ６０１は、プログラム実行制御部か
らユニファイア開始の指令を６１８を通して受信する
と、質問および候補節の第１レベルの引数のメモリから
の読み出し番地６０６を出力する一方、読み出した結果
を記憶するためのタイミング信号６０８，６０９を出力
する。６０２，６０３はレジスタであり、メモリからデ
ータ線６０７を通して読み出された質問および候補節の
第１レベルの引数情報を保持する。保持された情報のタ
グ部同士は信号線６１０，６１２を通してプログラムロ
ジックアレイ（ＰＬＡ）６０４に送出される。データ部
同士は、信号線６１１，６１３を通して比較器６０６に
送出される。タグ部が共に定数を表わしている場合は、
信号６１５はtrueとなる。タグ部が、リストと定数のよ
うにユニファイ不能な場合、信号６１４はtrueとなる。
タグ部のみの比較でユニファイ不能が検出された場合お
よびタグ部が共に定数を表わしていてもデータ部が不一
致でユニファイ不能が検出された場合には信号６１７は
trueとなる。以上で述べた場合以外にはＰＬＡ（６０
４）は信号６１５を１にする。より具体的には、比較さ
れるべき一対の引数がともにリスト形式の場合、リスト
内の各引数についての比較を行なわないで一致が成立し
たものとして処理することになる。信号６１７がtrueに
なると、ユニファイアＢは以後の引数のチェックを中止
し、ユニファイアＡにユニフィケーション中止を要求す
る信号６１９を送出する。ユニファイアＡは信号６１９
を受信すると、ユニフィケーションを終了し、プログラ
ム実行制御部に、ユニフィケーション失敗の信号１０８
を送信する。以上の動作により、第２図に示すプログラ
ムのユニフィケーションは、第１引数のユニフィケーシ
ョンをユニファイアＡで完了する以前に、第３引数のユ
ニフィケーション失敗をユニファイアＢで検出すること
ができ、プログラムの実行を終了することができる。

〔発明の効果〕

本発明によれば、引数のユニフィケーションの失敗を早
く検出できるので、プログラムが無駄な、即ち失敗する
とわかつている処理を実行しないで済む。

【図面の簡単な説明】

第１図は装置構成図、第２図は、メモリに格納されるプ
ログラムの例を示す図、第３図は、プログラムの引数部
のデータ形式を示す図、第４図は、引数がリストの場合
のデータ形式を示す図、第５図は、ユニファイアＡの制
御論理を示す図、第６図はユニファイアＢの制御論理を
示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 岩▲崎▼ 正明 東京都国分寺市東恋ヶ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 坂部 俊文 神奈川県秦野市堀山下１番地 株式会社日 立製作所神奈川工場内 審査官 佐藤 秀一

Claims (1)

【特許請求の範囲】
1. 【請求項１】プログラム中の関数呼出しを行う側の複数
   の引数と呼び出される側の複数の引数とに対するパター
   ンマッチング（以後ユニフィケーションと呼ぶ）の実行
   を指示する処理装置と、 該処理装置からの上記実行指示により起動され、そのプ
   ログラム中の関数呼出しを行なう側の複数の引数と呼び
   出される側の複数の引数に対してユニフィケーションを
   順次行い、呼出し側のいずれかの引数がリスト形式の場
   合、リスト内の各引数について、呼び出される側の対応
   するリスト内の引数との比較を順次行い、その結果、不
   一致を検出したとき、および実行中のユニフィケーショ
   ンの中止を求める割込み信号が入力されたときに、実行
   中のユニフィケーションを中止し、該処理装置にユニフ
   ィケーションの失敗を通知する第１のユニファイアと、 該処理装置からの上記実行指示により、該第１のユニフ
   ァイアと同時に起動され、該プログラム中の呼出し側の
   複数の引数と呼び出される側の複数の引数を順次比較
   し、次に比較すべき引数の組が、ともにリスト形式の場
   合、そのリスト内の各引数について、比較を行うことな
   く、そのリスト形式の引数について一致が成立したもの
   として処理し、リスト形式でない引数の組についての比
   較の結果、不一致が検出された場合には、該第１のユニ
   ファイアに、そこで実行中のユニフィケーションの中止
   を求める割込み信号を出力する第２のユニファイアとを
   有することを特徴とするユニフィケーションの並列処理
   装置。