JPS61229127A - スタツク制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、プロログ（ＰＲＯＬＯＧ　）のようなバック
トランク処理や単一化（Ｕｎｉｆｉｃａｔｉｏｎ）処理
機能をも持った言語をスタックを用いて効果的に処理す
るスタック制御方式に関するものである。

〔概要〕

単一化の際の親の環境を示すポインタと、次ゴール・フ
レームへのポインタが一致しない場合でも、フラグをデ
ータに付すことにより、効率良（処理できることを特徴
とするものである。

〔従来技術と問題点〕

プロログは、ルールの集まりである。ルール（ＲＵＬＥ
　）は ヘッドニーボディ。

という形をしている。ヘッドは１つの述語であり、ボデ
ィは述語の列（述語、・・・、述語）である。ルールの
中にはボディのないものもあり、この場合はファクト（
Ｆａｃｔ　）とよぶこともある。各述語は、述語名（引
数、・・・、引数） という形をしている。引数は、定数又は変数または構造
体である。定数は小文字で始まる文字列、変数は大文字
で始まる文字列である。構造体は構造体毛（引数、・・
・、引数） という形をしている。

プロログの実行過程について説明する。いま、下記のよ
うなプログラムがあったと仮定する。

■　ｆａｔｈｅｒ（ｙｏｕｋｏ、５ｈｏｕｊｉ　）＋（
ｙｏｕｋｏの父は５ｈｏｕｊ　ｉであるという意味）■
　ｆａｔｈｅｒ（ｓｈｉｎｙａ、ｍａｒｉｏ）。

■　ｆａｔｈｅｒ（ｍｏｒｉｏ、　ｔａｉｒａ）　。

■　ｍｏｔｈｅｒ（ｓｈｉｎｙａ、ｙｏｕｋｏ）　。

■　ｇｒａｎｄｆａｔｈｅｒ（Ｘ、Ｙ）　ニーｆａｔｈ
ｅｒ（Ｘ、Ｚ）、ｆａｔｈｅｒ（Ｚ、Ｙ）。

（Ｘの祖父がＹということはＸの父の父がＹであるとい
う意味） ■　ｇｒａｎｄｆａｔｈｅｒ（Ｘ、Ｙ）　ニーｎ＋ｏｔ
ｈｅｒ（χ＋　Ｚ）　＋　ｆ　ａ　ｔｈｅｒ　（Ｚ　＋
　Ｙ）。

プログラムに対して、何らかの質問をすることによって
プログラムは起動され、その質問に一致する事実がある
か否かが調べられる。この質問のことをゴールと言う。

ゴールとして ？−ｇｒａｎｄｆａｔｈｅｒ（Ｘ、Ｙ）。

が与えられると、このゴールとパターンがマツチする（
　Ｕｎｉｆｉｃａｔｉｏｎが成功するとも言う）ヘッド
を持つルールが捜される。　Ｕｎｉｆｉｃａｔｉｏｎは
下記のようにして行われる。

ｔａ）　　ゴールの述語名とヘッドの述語名を比べる。

違っていたら失敗。

（ｂｌ　　ゴールの各引数とヘッドの各引数を比べる。

（１）　　引数が定数同士の時、違っていたら失敗。

（２）引数が変数と定数の時、変数の部分を定数で置き
換える。

（３）引数が変数同士の時、何時でも成功する。

（４）引数が変数と構造体の時、変数の部分を構造体で
置き換える。

（５）引数が構造体同士の時、構造体毛と構造体の各引
数を比較する。一つでも失敗すれば失敗。

（ａ）と（ｂ）が両方とも成功すれば成功であり、一つ
でも失敗すれば失敗である。上述の例では、最初に■の
ルールが見つかる。ルールにボディがあれば、ボディの
各述語を左から順番に新たにゴール（ヘッドとＵｎｉｆ
ｉｃａｔｉｏｎが成功したゴールからみるとサブゴール
と呼ばれる）としてＬｌｎｉｆｉｃａｔｉｏｎが成功す
るヘッドを持つルールが捜される。そしてファクトにＵ
ｎｉｆｉｃａｔｉｏｎが成功する迄、これが繰り返され
る。上述の例では、■の最初のサブゴールであるｆａｔ
ｈｅｒ（Ｘ、Ｙ）にマツチするルールが捜され、■のフ
ァクトが見つかる。そうすると、Ｘがｙｏｕｋｏ、Ｚが
５ｈｏｕｊ　ｉに置き換わり、次に■の２番目のサブゴ
ールであるｆａｔｈｅｒ（ｓｈｏｕｊｉ、Ｙ）にマツチ
するルールが捜されるが、このようなルールは存在しな
いので、最初のサブゴールをもう一度捜し直す。

これをバックトラックと言う。バックトラックを行うと
、■のファクトが見つかる。そうすると、Ｘが５ｈｉｎ
ｙａＳＺがｍａｒｉｏに置き換わり、次に■の２番目の
サフ゛ゴールであるｆ　ａ　ｔｈｅｒ　（ｍｏｒ　ｉ　
ｏ　、　Ｙ）にマツチするルールが捜され、■のファク
トが見つかり、Ｙがｔａ　ｉ　ｒａに置き換わることに
より、ゴールの答はＸ＝ｓｈｉｎｙａＳＹ＝ｔａｉｒａ
ということになる。

第４図はプロログ・マシンの構成の概要を示す図である
。第４図において、１は入力部、２はデータベース、３
はＰＲＯＬＯＧ実行部、４はスタックをそれぞれ示して
いる。入力部１からルールを入力し、データベース２に
格納する。また、ＰＲＯＬＯＧ実行部３は、スタック４
とデータベース２を使って推論処理を行う。

第７図はプロログ・マシンの処理の概要を説明するため
のフローチャートである。最初にゴールをスタック４に
入れ、次にルールをデータベース２から取り出してスタ
ックに入れ、ゴールに適合するルールであるか否かを調
べる。成功すればデータベース２から次のルールを取り
出し、失敗すれば変数の状態を元に戻し、次のルールを
データベース２から取り出してスタック４に入れる。

いま、第５図に示すようなプロログ・プログラムがあり
、この状態の下で？−祖父（太部、　　ｇｐ）、という
質問が入力されると、スタック４の状態は第６図に示す
ように遷移する。第６図において、左側の数字はフレー
ムの番号を示し、右側の数字はそのフレームがどのゴー
ルに対するフレームであるかを示すものである。例えば
、右側の２−１なる数字はフレーム２の第１番目の太部
の父は誰かというサブゴールに対するものであることを
示している。第６図（ａ）に示すように、最初に太部の
祖父は誰かと言うゴールがスタック４に入れられる。次
にこのゴールと同じ述語名のヘッドを持つルールがデー
タベース２の中に存在するか否かがサーチされる。この
場合には適合するルールとして最初にＤ５のルールが見
つかるので、ルールＤ５がスタック４に入れられる。こ
の時の状態は第６図（′ｂ）に示される。そして、Ｘに
太部が代入される。次に父（太部、　ｐａｒ）、という
サブゴールに対する答えを得るために父という述語名の
ヘッドを持つルールがデータベースから取り出される。

父（太部、９夫）、というルールが取り出されたとする
と、このルールはスタック４に入れられる。

この状態は第６図（Ｃ）に示される。この父（太部。

９夫）、というルールは父（太部＋　ｐａｒ）、という
サブゴールと単一化可能であるので、ｐａｒに９夫が代
入される。次にフレーム２の中の父（９夫、　ｇｐ）、
という第２のサブゴールに対する答えを得るために、ヘ
ッドの述語名が父というルールがデータベース２から取
り出される。父（太部、９夫）、というルールが取り出
されたとすると、このルールはスタック４に格納される
。この時の状態は第６図（ｄ）に示される。父（太部、
９夫）、というルールは父（９夫、　ｇｐ）、という第
２のサブゴールと単一化不可であるので、次に父（守夫
、平）、というルールがデータベース２から取り出され
、スタック４に入れられる。父（守夫、平）、というル
ールは父（９夫、　ｇｐ）、という第２のサブゴールと
単−北回であるので、答え「平」が出力され、次の答え
（母方の祖父）を捜す処理が行われる。次の答えを捜す
処理については省略する。

従来バンクトラック処理や単一化処理を実現するために
は、スタック上に、成る実行が失敗したときに戻る地点
のアドレスや単一化処理を行うときの親の環境を示すア
ドレス、成る実行が成功したときに次に実行すべき地点
のアドレスを格納してから実行していた。しかし、この
ような方法を採用すると、スタックの長さが長くなって
しまって、スタックへデータを格納するための時間が多
くか−り、実行速度が遅くなるという欠点があった。一
方、親の環境のスタック上のアドレスと成る実行が成功
した時に次に実行すべきプログラムが格納されているス
タック上のフレーム・アドレスとは殆どの場合に同じで
あるという点を考慮に入れて、この２つを共用すること
も考えられるが、この方法を採用すると、プロログの仕
様を完全に満たさない場合が生ずるという欠点がある。

〔発明の目的〕

本発明は、上記の考察に基づ（ものであって、通常は親
の環境へのスタック上のポインタと成る実行が終了した
時に次に実行すべきプログラムが格納されているスタッ
ク上のフレーム・アドレスを示すポインタとは共用する
が、共用してはならない場合はそれを示すタグを設けて
それを指示することにより、スタックの消費量を減らし
、且つ通常処理の場合の処理速度の低下を少な（するよ
うにしたスタック制御方式を提供することを目的として
いる。

〔目的を達成するための手段〕

そしてそのため本発明のスタック制御方式は、単一化の
際の環境を示すポインタとその単一化が成功した時に次
に実行すべきプログラムを示すポインタとを共用してい
るプロログのような単一化を行う言語を処理する処理系
において、上記２つのポインタが共用出来ない場合が生
じた時でも、このことを示すフラグをデータに付随させ
、このフラグに基づいて処理を行うことにより、両方を
共用している場合の処理速度を損なわず、かつ上記２つ
のポインタが共用できない場合の処理にも対処できるよ
うにしたことを特徴とするものである。

〔発明の実施例〕

以下、本発明を実施例を参照しつつ説明する。

第１図はスタックのフレーム構成を示す図、第２図は本
発明によるスタックの内容を示す図、第３図はＣＡＬＬ
を含むプログラムが実行されるときのスタックの変化を
示す図である。図において、Ｓ（（ｉ＝０．１．・・・
）はスタック・アドレス、ＰＰＰは親フレーム・ポイン
タ部、ＡＲＧは引数部、Ｓｕはサクセッサ部をそれぞれ
示している。本発明をプロログにおける組込み述語″Ｃ
ＡＬＬ”の実行例で説明する。第１図で８１は“ＣＡＬ
Ｌ”のフレームの先頭アドレス、Ｓ、はＣＡＬＬの引数
の変数ｍＸの値Ｑ７のフレームの先頭アドレスであり、
Ｓ、はＣＡＬＬの親のフレームの先頭アドレスである。

述＠ＣＡＬＬは、その引数の値（こ＼ではＱ、）を再び
ゴールとして実行するというものであるが、このゴール
Ｑ、、を解くときの環境が問題となる。こ＼で通常のよ
うにインタプリタで実行してい（と、この時の環境は“
ＣＡＬＬ”のフレームということになるが、この場合に
はそうではなくてＣＡＬＬの環境、即ちＣＡＬＬの親の
フレームということになる。従って、このような情報を
何等かの形でＱ、、のフレームに残しておかなければな
らない。特にこのことはプロログ・マシンにおいてバン
クトラックしてこのＣＡＬＬのフレームに戻った時に致
命的となる。なお、サクセッサ部ＳＵには、実行すべき
サブゴールが記入されている。即ち、Ａｔ　、Ａ、、Ａ
、ｌはそれぞれサブゴールを示しており、Ａｔの次にＡ
、が実行され、Ａ、の次にＡ７が実行される。最後のサ
ブゴールＡ、１の答えが見つかったことは単一化が成功
したことを意味している。Ａ７が実行された後、親フレ
ームによって指示される次の処理が実行される。

第３図は組込み述語ＣＡＬＬを含むプログラムが実行さ
れるときのスタックの変化を示す図である。

まず、前述の例を用いて単一化の際の環境を示すポイン
タとその単一化が成功した時に次に実行すべきプログラ
ムを示すポインタを共用できない場合を示す。前述の例
でゴール？−祖父（太部、　ｇｐ）は、以下のように書
きかえても、その効果は全く同じである。

’ｉｌ−１，、、（祖父、太部、　ｇｐ）　、　ＣＡＬ
Ｌ（Ｘ）。

ここでオペレータ＝０．は、右辺にリストを引数として
取りこのリストから祖父（太部、　ｇｐ）のような構造
体を作り出すものである。この場合には、変数Ｘに祖父
（太部、　ｇｐ）が代入される。次にＣＡＬＬが実行さ
れるがこのときに、前述のポインタが共用比できない場
合が生じる。以下にこのゴールが実行される様子を説明
する。

第３図（ａ）はゴールが実行されようとしているところ
を示している。ここで親フレーム・ポインタ部ＰＰＰは
、このゴールを呼び出した親のフレームを指している。

Ｓｏは、このゴールを実行するためのスタック・フレー
ムのアドレスである。

第３図（ｂ）は、初期ゴールのうち、最初のゴールを実
行しようとしている時のスタック・フレーム構成である
。ここでＳ、のスタック・フレームの親フレーム・ポイ
ンタ部ＰＦＰは、このゴールを呼んだフレームＳ０を指
している。またサクセッサ部Ｓｕには、この最初のゴー
ルが成功したときに次に実行すべきゴールＣＡＬＬ　（
Ｘ）が入っている。

第３図（ｅ）はＸ＝、、　（祖父、太部、ｇｐ）の実行
が成功して次のゴールＣＡＬＬ　（Ｘ）の実行に入った
ところの図である。ここで親フレーム・ポインタ部ＰＰ
ＰはＳｏを指しており、サクセフサ部Ｓｕはもう実行す
べきゴールがないので１なし”を指している。

第３図（ｄ）は、実際にＣＡＬＬの中に分岐してからの
実行途中のスタックの様子である。ＣＡＬＬ述語は、そ
の引数をそのままゴールとして実行するものである。Ｃ
ＡＬＬ述語の処理ルーチンの中ではＣＡＬＬ述語のフレ
ームの下に引数のフレームを作り、この引数をゴールと
して実行する。このとき親フレーム・ポインタ部ＰＰＰ
の指す位置であるが、この場合の環境は、本来はＳｌや
Ｓ２と同様に８０であるべであるが、このようにしてし
まうとその他の処理ルーチン、たとえば、トレーサ（ユ
ーザ・プログラムのデバッグのために用意されているモ
ジュール）などがうまく動かないなどという不都合が生
じる。したがって親フレーム・ポインタ部ＰＰＰのポイ
ンタの指す位置はこのままにしておいて、環境は、必要
に応じて切りかえるという方式が必要になってくる。以
下、この方式についてより一般の場合について説明する
。ここで親フレーム・ポインタＰＰＰなどの設定は、マ
イクロプログラム化された処理系によって行われる。

そこで、親フレーム・ポインタ部ＰＰＰに以上のことを
示す目的でタグ・フィールドの１ビツトにフラグを設け
、これにより示すことにする。このフラグのオン／オフ
は、マイクロプログラム化された処理系よって行われる
ものとする。特に、この場合はＣＡＬＬ述語の処理ルー
チンの中で行われるものとする。第２図は本発明の親フ
レーム・ポインタ部ＰＰＰの１実施例構成を示すもので
あって、親フレーム・ポインタ部ＰＰＰはタグ・フィー
ルドを有している。第２図（′ｂ）はＱ７のフレームの
親フレーム・ポインタ部ＰＰＰの構成を示し、タグ・フ
ィールドの右側のビットは「１」とされ、アドレス・フ
ィールドにはアドレスＳｌが記入されている。このこと
はＱ、１フレームの親環境はＣＡＬＬのフレームではな
くてＣＡＬＬフレームの親フレーム・ポインタ部ＰＰＰ
の内容に依存することを示している。

第２図（ａ）はＣＡＬＬのフレームの親フレーム・ポイ
ンタ部ＰＰＰの構成を示し、タグ・フィールドの右側の
ビットは「０」とされ、アドレス・フィールドにはアド
レスＳ、が記入されている。このことはＣＡＬＬのフレ
ームの親環境は親フレームであることを示している。第
２（ａ）及び（ｂ）の結果、Ｑ、フレームの親環境は親
フレームということになる。つまり、第２図に示すよう
にタグ・フィールドの右側ビットが１かＯかによってそ
れをデータと見るか、アドレスと見るかを区別するもの
である。本発明の方式を採用することにより、制御と環
境の２つのデータを別々に持つことなく共用して持つこ
とにより、効果的にプロログ・プログラムを実行するこ
とが出来る。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、スタ
ックの消費量を減少することが出来、またプロログの実
行に必須の特殊な機能も比較的に簡単なハードウェアで
実現できることから、プロログの実行を高速に行うこと
が出来るという効果が生ずる。

【図面の簡単な説明】

第１図はスタックのフレームの構成を説明する図、第２
図は本発明による親フレーム・ポインタ部の内容を説明
する図、第３図は組込み述語ＣＡＬＬを含むプログラム
が実行されるときのスタックの変化を示す図、第４図は
プロログ・マシンの構成の概要を示す図、第５図はプロ
ログ・プログラムの１例を示す図、第６図はスタックの
状態遷移の概要を示す図、第７図はプロログ・マシンの
処理の概要を説明するためのフローチャートである。 １・・・入力部、２・・・データベース、３・・・ＰＲ
ＯＬＯＧ実行部、４・・・スタック、Ｓｓ　（ｉ＝０．
１．・・・）・・・スタック・アドレス、ＰＰＰ・・・
親フレーム・ポインタ部、ＡＲＧ・・・引数部、ＳＵ・
・・サクセッサ部。 特許出願人　　　富士通株式会社 代理人弁理士　　京　谷　四　部 スターノア・７ドレス 第３図（ｃ） 第４図 什 第５図

Claims (1)

【特許請求の範囲】
1. 単一化の際の環境を示すポインタとその単一化が成功し
   た時に次に実行すべきプログラムを示すポインタとを共
   用しているプロログのような単一化を行う言語を処理す
   る処理系において、上記２つのポインタが共用出来ない
   場合が生じた時でも、このことを示すフラグをデータに
   付随させ、このフラグに基づいて処理を行うことにより
   、両方を共用している場合の処理速度を損なわず、かつ
   上記２つのポインタが共用できない場合の処理にも対処
   できるようにしたことを特徴とするスタック制御方式。