JPH0619714B2 - プロローグ処理方法 - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明はプロローグ処理装置に係り、特に処理の高速化
を図るのに好適なプロローグ処理方法に関する。

〔発明の背景〕

従来のプロローグ処理装置においては、第２回ロジツク
プログラムミング国際シンポジウム、予稿集（1984年２
月）に掲載された“トウワード ア パイプラインド
プロローグ プロセツサ （TOWARD A PIPELINED PROLO
G PROCESSER）” イー・テイツク（E.Tick）、デイー
・ウオレン （D.Warren）著に記載されている様に、プ
ロローグプログラムにおいて、次の実行文を選択する場
合には、次の様な処理が行なわれていた。先ず、各プロ
シジヤに関する情報を参照し、次に、任意の１つの引数
の種類によつてプロシジヤ名とその引数が一致する次の
実行文を決定していた。そのため、命令として、分岐情
報と命令系列の２つが必要となり、加えて参照する引数
が１つに限られてしまい、そのため最適な引数を選択で
きず、次の実行文の決定に多大の時間を必要とするとい
う問題点があった。

次に、上記した問題点について、詳しく説明する。第１
１図は、従来のプロローグ処理装置におけるプロローグ
プログラムの処理の一例を示す図である。同図におい
て、プロローグプログラム３００は、文Ｓ１，Ｓ２から
成り、文Ｓ１は規則文、文Ｓ２は事実文を表わしてい
る。規則文Ｓ１は、：−の左側をヘツド、：−の右側を
ボデイと称し、さらに、ｐ（Ｘ，〔Ｙ〕）、ｑ（Ｘ，
Ｚ），ｒ（Ｚ，Ｙ）をそれぞれゴールと呼ぶ。事実文Ｓ
２は、ｐ（ａ，ｂ）だけで構成され、これもヘツドであ
り、ゴールと称される。プロローグプログラム３００
は、述語ｐをヘツドとする文から成り、命令に変換する
と、分岐情報３０１と、規則文Ｓ１を表わす命令系列３
０２と、事実文Ｓ２を表わす命令系列３０３に、変換さ
れる。

分岐情報３０１は、プロローグプログラム300 に対する
質問文の第１引数の種類によりジヤンプ先が決定される
命令系列３０２，３０３内の実行文のアドレスを示す。
即ち、Switch−on−term命令の（ ）内の値が、命令系
列３０２，３０３のアドレスを示し、（ ）内の左から
順に、質問文の第１引数が変数であればアドレスＣ０、
定数であればアドレスＣ０、〔 〕で囲まれたリストで
あればアドレスＣ１，Ｘ（Ｙ）という形の構造体であれ
ばアドレスＣ１にジヤンプする。

図示する様に、命令系列３０２は、アドレスＣ０ではじ
まり、try−me−else Ｃ２により別解のアドレスＣ２を
用意する。これは、アドレスＣ１の処理で失敗したと
き、アドレスＣ２にジヤンプし、別解を求めることを意
味する。アドレスＣ１においては、ｐ（Ｘ，〔Ｙ〕）の
ユニフアイ（unify、 単一化）と、ｑ（Ｘ，Ｚ）のロー
ド（Load）、その後述語ｑについての処理を実行するた
めのコール キユーエー（call qA）命令となる。ここ
で、ｑＡは述語ｑを実行する処理手続を格納したメモリ
の先頭アドレスを示す。そして、ｑ（Ｘ，Ｚ）の処理が
終わると、同様に、ｒ（Ｚ，Ｙ）のロード、及び述語ｒ
についての処理を実行するため、エグゼキュート アー
ルエー（execute rA）命令が続く。ここで、上記call命
令は、文の途中のプロシジヤの呼出しを行ない、execut
e 命令は、文の最後でのプロシジヤの呼び出しを行なわ
せる命令である。

命令系列３０３のアドレスＣ２のトラスト(trust) 命令
は、別解のないことを示し、ｐ（ａ，ｂ）のユニフアイ
を実行するものである。

上記したプロローグプログラム３００に対して、プロロ
ーグプログラム３０４に示す質問文？ｐ（Ａ，ｂ）を与
えると、命令系列３０５によつて、ｐ（Ａ，ｂ）のロー
ドの後、execute pAの実行により、分岐情報３０１内の
アドレスｐＡにジヤンプする。これによつて、Switch−
on−term命令が実行され、質問文ｐ（Ａ，ｂ）の第１引
数Ａが変数であるため、命令系列３０２のアドレスＣ０
にジヤンプする。アドレスＣ０において、try−me−els
e 命令を実行して別解を求めるアドレスＣ２が準備さ
れ、次にアドレスＣ１において、ｐ（Ｘ，〔Ｙ〕）との
パターンマツチング（これをユニフイケーシヨンと呼
ぶ）で失敗する。そこで、別解として準備されているア
ドレスＣ２にジヤンプし、trust 命令を実行し、次にｐ
（ａ，ｂ）のユニフイケーシヨンに成功して、変数Ａに
定数ａが代入されて終了する。

このようにSwitch−on−term命令によつて、引数の種類
を参照して次の実行文のアドレスを決定するため、もし
参照する引数が変数であるときは、プログラムの最初の
文から始めて成功するまで、全ての実行文とのユニフイ
ケーシヨンを実行しなければならない。このため、この
ような場合は高速に実行できないという問題点があり、
又、プロシジヤの分岐情報にジヤンプしてから次の実行
文を決定するまでに多大の時間を必要とするという問題
があつた。

〔発明の目的〕

本発明は、上記した従来技術の問題点に鑑みなされたも
ので、高速なプロローグ処理方法を提供することを目的
としている。

〔発明の概要〕

本発明のプロローグ処理方法は、プロローグプログラム
が、引数の種類を示すタグ部の付いたデータを処理する
命令系列に展開され、実行されるプロローグ処理方法に
適用されるものであり、次の特徴を有している。

すなわち、少なくとも各引数のタグ部を格納する第１の
ステップと、タグ部の種類別に次の実行文のアドレスと
の対応付けをとる引数タグ索引テーブルを各引数毎に格
納する第２のステップと、第１のステップにおいて格納
された複数のタグ部の中から１つのタグ部を読み出して
引数の種類を判定し、判定された引数の種類に対応する
所定の値を出力する第３のステップと、第３のステップ
において出力された引数の種類に対応する所定の値と、
上記引数に対応する前記引数タグ索引テーブルの先頭ア
ドレスとを加算する第４のステップと、第４のステップ
における加算出力に基づいて、上記引数に対応する引数
タグ索引テーブルを参照し、次に実行文のアドレスを決
定する処理を実行する第５のステップと、第５のステッ
プにおいて次の実行文のアドレスが決定できなかった場
合、前記次の実行文のアドレスが決定できるまで、第１
のステップにおいて格納された複数のタグ部の各々につ
いて前記第３から第５のステップを繰り返す第６のステ
ップとから構成されていることを特徴としている。

〔発明の実施例〕

以下、添付の図面に示す実施例により、更に詳細に本発
明について説明する。

第２図は本発明を適用したプロローグ処理装置の全体構
成を示すブロツク図である。同図において、１３０は命
令フイツチデコード部、１２０はアドレス演算部、６０
はメモリコントロールユニツト、７０はメモリ、１４０
は命令実行ユニツトであり、８０はデータ信号線、９０
はアドレス信号線をあらわす。

プログラムの命令系列は、メモリ７０に書きこまれてい
て、実行時に命令フイツチデコード部１３０により読み
出されて、解釈（デコード）され、アドレス演算部１２
０において必要なオペランドやアドレスが計算される。
この結果をもとに、メモリコントロールユニツト６０を
介して、メモリ７０から必要なデータが読み出されて、
命令実行ユニツト１４０で命令が実行される。

第１図は、第２図に示す命令実行ユニツト１４０と、ア
ドレス演算部１２０と、メモリコントロールユニツト６
０と、メモリ７０内のタグ索引テーブル７１の詳細を示
すブロツク図である。命令実行ユニツト１４０は、セレ
クタ１４１と、引数レジスタＡＧｉと次のゴールの処理
の先頭を示すネクストゴールレジスタＮＧＲとを含むレ
ジスタフアイル１４２と、タグ判定変換部１４５と、演
算ユニツト１４６と、マイクロプログラムコントローラ
１４７とから構成されている。アドレス演算部１２０
は、オペランドデータ１２１と、オペランドレジスタ１
２２、プログラムカウンタ１２３とから構成されてい
る。また、４０，４１は入力信号線、５０は出力信号
線、１１１，１１２，１１３，１４３，１４４，１４
８，１４９はデータ信号線である。

次に、第１図に示す回路の動作の概略について説明す
る。レジスタフアイル１４２に対する読み出しアドレス
信号は、オペランドレジスタ１２２の出力信号又はマイ
クロプログラムコントローラ１４７の出力信号のいずれ
かが、データ信号線１１２又は１４９のいずれか一方を
介し、かつセレクタ１４１の選択処理により、入力され
る。従つて、レジスタフアイル１４２の読み出しアドレ
ス信号は、オペランドレジスタ１２２の内容又はマイク
ロコントローラ１３７の出力内容のいずれか一方とな
る。この読み出しアドレス信号によつて、レジスタフア
イル１４２内の引数レジスタＡＧｉ（ｉ＝１〜５）又は
ネクストゴールレジスタＮＧＲの内容が、データ信号線
１４４へ出力される。尚、レジスタフアイル１４２のデ
ータ信号線１４３に対する読み出しアドレス信号及びレ
ジスタフアイル１４２に対する書き込みアドレス信号
は、図示していないが、マイクロプログラムコントロー
ラ１４７の制御信号線によつて指定される。タグ判定変
換部１４５は、レジスタフアイル１４２の出力信号を受
け、後述する所定のタグ判定・変換処理を行ない、入力
信号線４１へ出力する。演算ユニツト１４６の入力Ａ
は、オペランドデータレジスタ１２１の出力、マイクロ
プログラムコントローラ１４７の出力、メモリコントロ
ールユニツト６０の出力、及びレジスタフアイル１４２
のデータ信号線１４３の出力のいずれかとなる。また演
算ユニツト１４６の入力Ｂは、タグ判定変換部１４５の
出力、レジスタフアイル142 のデータ信号線１４４の出
力、及びプログラムカウンタ１２３の出力のいずれかと
なる。演算ユニツト１４６の出力は、レジスタフアイル
１４２又はマイクロプログラムコントローラ１４７へ出
力される。ここで、マイクロプログラムコントローラ１
４７は、命令実行ユニツト１４０の全体の制御を行な
う。

第３図は、タグ判定変換部１４５の処理内容を示す説明
図である。一般にプロローグプログラムの質問文の引数
には、図示する様に、変数，文字列定数，数値データ・
ａ（ｂ）の形をした構造体、〔ａ〕の形をしたリストの
５種類が、存在する。タグ判定変換部１４５は、アドレ
ス演算部１２０内のオペランドレジスタ１２２の内容を
読み出しアドレス信号として、レジスタフアイル１４２
の引数レジスタＡＧｉから読み出される質問文の引数の
種類を示すタグデータを受け、４つの種類のデータに変
換する。即ち、上記５種類の引数のうち、変数は（000
0）₁₆、文字列や数値データなどの定数は（0004）₁₆、
構造体は（0008）₁₆、リストは（000C）₁₆の４つの値に
変換される。

第４図（ａ），（ｂ）は本発明を実現するために必要と
される２つの命令、jmpt命令とcallt 命令の使用の具体
例を示す説明図である。第４図（ａ）に示す様に、ｑ
（ ）：−ｐ（ａ，ｂ），ｒ（ ）のようなプログ
ラムの場合、その命令系列は４０１のようになり、ｐ
（ａ，ｂ）の処理は、｛ｐ（ａ，ｂ）Load｝の後、jmpt
命令により実行され、処理が終了すると、｛ｒ（ ）
Load｝に処理が続くようにプログラムカウンタ１２３、
（第１図参照）を設定する。これに対して、第４図
（ｂ）に示す様に、ｑ（ ）：−ｒ（ ），ｐ
（ａ，ｂ）のようなプログラムの場合、その命令系列は
４０２のようになり、ｐ（ａ，ｂ）の処理は、｛ｐ
（ａ，ｂ）Load｝の後、callt 命令により実行され、処
理が終了すると、このプログラムについての処理が終
る。

次に、第５図と第１図とを用いて、jmpt命令について説
明する。第５図は、第４図（ａ）に示すjmpt ｐＡ，Ａ
ＧｉＡの処理を示すフローチヤートであり、ＡＧｉＡは
ジヤンプするときに参照するレジスタフアイル１４２の
引数レジスタAGi （ｉ＝１〜５）の１つを示す読み出し
アドレス信号であり、オペランドレジスタ１２２に設定
される。また、ｐＡは、メモリ７０内に各引数毎に作成
されている引数タグ索引テーブル（第１図の例では４つ
の引数タグ索引テーブルが示されている）から構成され
るタグ索引テーブル７１の先頭アドレス、すなわち第１
引数タグ索引テーブルの先頭アドレスを示している。第
１図に示す例では、前記したようにタグ索引テーブル７
１は４つの引数に各々対応した４つの引数タグ索引テー
ブルから構成され、各引数タグ索引テーブルはカスケー
ドに接続した構成を有している。そして、タグ索引テー
ブルの各引数タグ索引テーブルは、その引数の種類と一
致するような、ヘツドを有する実行文の各アドレスを分
類したものである。その詳細は、後述する第８図に示し
ている。jamp ｐＡ，ＡＧｉＡの実行時においては、命
令フイツチデコード部１３０とアドレス演算部１２０の
働きによつてあらかじめ、アドレスｐＡはオペランドデ
ータレジスタ１２１にセツトされ、アドレスＡＧｉＡは
オペランドレジスタ１２２にセツトされる。

第５図において、ステツプ５０１では、オペランドレジ
スタ１２２の出力信号によつて、レジスタフアイル１４
２内の引数レジスタＡＧｉから引数の種類を示すタグデ
ータが読み出され、タグ判定変換部１４５に入力され
る。タグ判定変換部１４５は、第３図に示す様に、引数
の種類の判定を行ない、この判定結果に従つてあらかじ
め定められた定数に変換する。演算ユニツト１４６は、
上記定数を入力Ｂとして受け、またオペランドデータレ
ジスタ１２１の内容（アドレスｐＡ）を入力Ａとして受
け、両者の加算を行なう。加算結果は、出力信号線５０
とゲート５１とを介して、メモリコントロールユニツト
６０に入力される。

ステツプ５０２においては、上記加算結果を読み出しア
ドレス信号として用い、メモリ７０内のタグ索引テーブ
ル７１から、質問文の引数の種類が一致するヘツドを有
する実行文の先頭アドレスが読み出され、メモリコント
ロールユニツト６０とゲート５２とデータ信号線８０と
を介して、プログラムカウンタ１２３にセツトされる。

次に、callt 命令について、第６図と第１図を用いて説
明する。callt 命令は、callt ｐＡ，ＡＧｉＡという形
で表わされ、ｐＡ，ＡＧｉＡにについては、jmpt命令と
同様である。callt 命令とjmpt命令が異なるのは、call
t 命令は規則文の途中のゴールについての命令なので、
ステツプ601 で示すように、最初に、そのゴールが終了
したときの戻り番地である、次のゴールの処理プログラ
ムのトツプアドレスをレジスタフアイル１４２内のネク
ストゴールレジスタＮＧＲにセツトする。即ち、最初の
プログラムカウンタ１２３の値とマイクロプログラムコ
ントローラ１４７から得た一定の値とを、演算ユニツト
１４６で加算し、レジスタフアイル１４２内のネクスト
ゴールレジスタＮＧＲにセツトする。

ステツプ６０２においては、第５図に示すステツプ５０
１の処理と全く同様の処理が行なわれ、また、ステツプ
６０３においては、第５図に示すステツプ５０２と全く
同様の処理が行なわれる。以上の説明から明らかな様
に、上記したjmpt命令とcallt 命令により、任意の引数
を指定して、その引数の内容に従つて、ジヤンプする構
成をとることができる。

第７図は、第１１図に示すプロローグプログラム３００
と質問文３０４とを、jmpt命令とcallt 命令を使つて命
令系列７０１，７０２とに展開した図である。ここで、
質問文３０４の命令系列７０２中のcallt ｐＡ，ＡＧｋ
Ａにおいて、アドレスｐＡに対するタグ索引テーブル７
１は、アドレスＡＧｋＡが示す引数の種類に従つて、変
数・定数のときはＣ１、構造体・リストのときはＣ２に
ジヤンプする様に、生成されている。第７図から明らか
な様に、引数の種類を判定するSwitch−on−term命令
と、callt 命令が、callt 命令になり、実行の高速化を
図つている。

第８図は、メモリ７０のタグ索引テーブル７１のテーブ
ル構成を示す説明図である。第８図において、７１１は
第ｉ引数のタグ索引テーブルであり、７１２は第ｊ引数
のタグ索引テーブルである。７２１は、第ｉ引数の種類
が定数のとき、その定数の値によつてさらに実行文のア
ドレスを分類するハツシユテーブル、７３１は第ｉ引数
の種類が構造体のときのハツシユテーブル、同様に７２
２は第ｊ引数の種類が定数のときのハツシユテーブル、
７３２は第ｊ引数が構造体のときのハツシユテーブルを
示している。

今、第ｉ引数のタグ索引テーブルのトツプアドレスＬが
第１図に示すオペランドデータレジスタ１２１から与え
られ、タグ判定変換部１４５からの出力TOUTが与えられ
たとすると、次の実行文のアドレスは、jmpt命令により
求められる。そして、タグの種類が定数の場合には、引
数レジスタAGi のデータ値別の実行文のアドレスを格納
したハツシユテーブル７２１を参照する。即ち、ハツシ
ユテーブルのトツプアドレスＴＯＰとハツシユテーブル
のサイズSIZEと引数レジスタＡＧｉのデータ内容に従つ
て、一定の関数Ｆｉを用いて、ハツシングを行ない、ハ
ツシユテーブル７２１を参照する。

このように、タグの種類が定数のとき、次の実行文のア
ドレスを求める操作はハツシユテーブルを用いて行なわ
れ、命令系列中のjmpt命令によつて実行される。

さらに、タグの種類が変数のときは、第ｊ引数のタグ索
引テーブル７１２を参照して、同様に、最適な実行文の
アドレスを求める。

次に、第９図に示すプロローグプログラム930 に対し
て、質問文９３０をjmpt命令、callt 命令、jmpc命令等
を用いて実行する場合について説明する。第９図に示す
様に、質問文９１０は命令系列９２０に展開され、プロ
ローグプログラム９３０は命令系列９４０に展開され
る。このときの実行過程を第１０図に示すフローチヤー
トに従つて、次に説明する。即ち、ステツプ１００１に
おいては、次の様な処理が実行される。第９図に示す命
令９２１により（callt ｐ１Ａ，ＧＡ１Ａ）、タグ索引
テーブルのトツプアドレｐ１Ａと引数レジスタのアドレ
スＡＧ１Ａを得て、先ずタグ判定変換部が引数の種類を
判定する。質問文９１０の第１引数は変数Ｘであるた
め、タグ判定変換部は変数を示す変換データを出力す
る。ステツプ1002においては、名９４１（jmpt ｐ２
Ａ，ＧＡ２Ａ）により、タグ索引テーブルのトツプアド
レスｐＡ２と、他の引数の種類を示すタグデータを格納
した引数レジスタのアドレスＡＧ２Ａを得、タグ判定変
換部が引数の種類の判定を行なう。引数レジスタのアド
レスＡＧ２Ａの内容は、質問文の第２引数ｂの種類を示
すものとなり、定数となる。ステツプ１００３において
は、命令９４２（jmpc，TOP,SIZE，AG2A）により、アド
レスＡＧ２Ａの引数レジスタの内容（定数を示すタグデ
ータ）と、ハツシユテーブルのトツプアドレスＴＯＰ
と、ハツシユテーブルのサイズSIZEに従つて、ハツシン
グを行ない、次の実行文のアドレスを求める。ここで
は、アドレスＡＧ２Ａの引数レジスタの内容に対する演
算結果、即ち次の実行文のアドレスを第９図中の９４３
に示し、質問文の第２引数が定数ｂであるため、アドレ
スＣ３が得られる。そして、ステツプ１００４におい
て、アドレスＣ３の命令分９４４により、｛ｐ（ａ，
ｂ）のユニフイフアイ｝が実行され、終了する。

〔発明の効果〕

本発明によれば、質問文を処理する場合、第１の引数に
基づいて次の実行文のアドレス決定ができなかった場
合、第２の引数に基づく次の実行文のアドレス決定、第
３の引数に基づく次の実行文のアドレス決定というよう
に、順次処理を進める事が可能になり、しかも各引数毎
に設けられた引数タグ索引テーブルを用いる事により、
次の実行文のアドレス決定処理を高速に行なうことが可
能になる。従つて、プロローグ処理装置の高速化を図る
ことができる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロツク図、第２図は
本発明を適用したプロローグ処理装置の全体構成を示す
ブロツク図、第３図は第１図に示すタグ判定変換部の判
定・変換処理を示す説明図、第４図（ａ）は本発明で用
いるjmpt命令の命令系列を示す説明図、第４図（ｂ）は
本発明で用いるcallt 命令の命令系列を示す説明図、第
５図はjmpt命令の処理内容を示すフローチヤート、第６
図はcallt 命令の処理内容を示すフローチヤート、第７
図はjmpt命令とcallt 命令を用いたプログラムの命令系
列の一例を示す説明図、第８図は第１図に示すメモリの
詳細を示すブロツク図、第９図は第１図に示す実施例を
用いて質問文を処理する命令系列の具体例を示す図、第
１０図は第９図に示す命令系列の処理を示すフローチヤ
ート、第１１図は従来のプロローグプログラムの処理の
一例を示す説明図である。 ６０……メモリコントロールユニツト、７０……メモ
リ、７１……タグ索引テーブル、１２０……アドレス演
算部、１２１……オペランドデータレジスタ、１２２…
…オペランドレジスタ、１２３……プログラムカウンタ
ー、１３０……命令フイツチデコード部、１４０……命
令実行ユニツト、１４１……セレクタ、１４２……レジ
スタフアイル、１４５……タグ判定変換部、１４６……
演算ユニツト、１４７……マイクロプログラムコントロ
ーラ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 坂東 忠秋 茨城県日立市久慈町4026番地 株式会社日 立製作所日立研究所内 (72)発明者 中西 宏明 茨城県日立市大みか町５丁目２番１号 株 式会社日立製作所大みか工場内 (56)参考文献 特開 昭60−107137（ＪＰ，Ａ) 特開 昭60−136832（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】プロローグプログラムが、引数の種類を示
   すタグ部の付いたデータを処理する命令系列に展開さ
   れ、実行されるプロローグ処理方法において、 少なくとも各引数のタグ部を格納する第１のステップ
   と、 タグ部の種類別に次の実行文のアドレスとの対応付けを
   とる引数タグ索引テーブルを各引数毎に格納する第２の
   ステップと、 第１のステップにおいて格納された複数のタグ部の中か
   ら１つのタグ部を読み出して引数の種類を判定し、判定
   された引数の種類に対応する所定の値を出力する第３の
   ステップと、 第３のステップにおいて出力された引数の種類に対応す
   る所定の値と、上記引数に対応する前記引数タグ索引テ
   ーブルの先頭アドレスとを加算する第４のステップと、 第４のステップにおける加算出力に基づいて、上記引数
   に対応する引数タグ索引テーブルを参照し、次に実行文
   のアドレスを決定する処理を実行する第５のステップ
   と、 第５のステップにおいて次の実行文のアドレスが決定で
   きなかった場合、前記次の実行文のアドレスが決定でき
   るまで、第１のステップにおいて格納された複数のタグ
   部の各々について前記第３から第５のステップを繰り返
   す第６のステップと から構成されていることを特徴とするプロローグ処理方
   法。