JPH0690667B2 - オブジェクト変更処理方法 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は人工知能プロダクション・システム、更に詳細
に説明すれば、システム・ルールに対する作業メモリの
マッチングを延期している間に前記システムの作業メモ
リ・オブジェクトに対する変更のシーケンスを合体させ
る方法に関する。

B.従来技術 ルール・ベース方式の人工知能プロダクション・システ
ムはプロダクション・システム言語で記述されたコンピ
ュータ・プログラムを表わす。一般にプロダクション・
システムは作業メモリ−要素の集合、要素によって定義
されたルールの集合、及び制御機構、即ち要素に関して
ルールを実行する推論エンジンを含む−を包含する。制
御機構はルールと要素のマッチングを行ない、マッチン
グされた要素に結合されたルールから成るコンフリクト
集合を生成する。制御機構はルールの実行順序を選択す
ることによりコンフリクト集合を決定し、該ルールを
“発火させる”。

ルール・ベース方式の人工知能プロダクション・システ
ム及びそれらの構成をサポートする言語はよく知られて
いる。参照文献:Brownstone外，“OPS5によるエキスパ
ート・システムのプログラミング（Programming Expert
Systems in OPS5）",Addison−Wesley,1985年発行;Jac
kson,“エキスパート・システム入門（Introduction to
Expert Systems）",Addison−Wesley,1986年発行,Forg
y,“OPS5ユーザー・マニュアル（User's Manual）",CMU
−CS−81−135,1981年発行;Forgy,“RETE,ミニ・パター
ン／ミニ・オブジェクト・パターンのマッチング問題の
高速アルゴリズム（A Fast Algorithm For the Mini Pa
ttern/Mini Object Pattern Match Problem）",Artific
ial Intelligence,Vol.19,1982年発行。

Brownstoneはマッチング・ルール、選択ルール、実行ル
ールを含む３状態のサイクルに基づいたルール・ベース
方式の人工知能プロダクション・システム（“プロダク
ション・システム”）について記述している。Brownsto
neは要素とルールのマッチングがプロダクション・シス
テムの動作の非効率性の主要因であると指摘している。
前記システムの推論エンジンの速度はどれも該動作のマ
ッチング・フェーズの減少によって高められる。

OPS5のような言語でマッチングを行なう段階は、どのル
ールの実行が可能であるかを選択するシステム・ルール
とシステム要素の結合を体系化するパターン式ネットワ
ークにより実行される。OPS5で用いるマッチング・アル
ゴリズムはRETE方法と呼ばれる。RETEマッチング手続き
はよく知られており、例えば、Forgyの論文Artificial
Intelligenceに記述されている。ルール（又は“プロダ
クション”又は“プロダクション・ルール”）は２つの
部分、LHS（左側、又はif部分）及びRHS（右側、又はth
en部分）を有する。ちなみに、ルールは形式： If A,B,Cが真であると決定されれば、then行動X,Y,Zを
とる。

のif−thenステートメントとみなされる。

プロダクション・システムでは、作業メモリ（WM）はシ
ステムの汎用データ・ベースを形成する。特徴として
は、WMはクラスに分けられ、クラスは要素、又はメンバ
ーから成り、各メンバーはクラス・メンバー（CM）と呼
ばれる。ルール集合の各ルールは前述の２つの部分:LHS
及びRHSを有する。LHSは作業メモリ・クラスを参照する
論理式であり、RHSはCMで実行される動作のリストであ
る。

推論エンジンは発火させるルールを選択し次いで選択さ
れたルールのRHSの行動を実行し、該サイクルを反復す
る制御機構である。条件が満足されたルールは例示化
（instantiation）と呼ばれる。例示化はルールと該ル
ールのLHSを満足するCMのリストとから成る。推論エン
ジンは、例示化でのCMのリストを用いて、該ルールのRH
Sを実行することにより該例示化を発火させる。発火さ
せるために使用可能な全ての例示化の集合はコンフリク
ト集合と呼ばれる。推論エンジンはコンフリクト集合か
ら次に発火させる例示化を選択するためコンフリクト決
定と呼ばれる手続きを行なう。そのRHSの実行によるル
ールの発火はWMで要素を生成、変更又は削除しコンフリ
クト集合の変更に導くことができる。ルール・ベース方
式のプロダクション・システムの推論エンジンは１つの
サイクルで、コンフリクト集合中の全ての例示化を認識
するステップ、該ステップのどの例示化を発火させるべ
きかを決定するステップ、及び該選択された例示化の集
合の発火を反復実行する。該サイクルは“認識行為”サ
イクルと呼ばれる。

各ルールを発火すると、推論エンジンは、RETEアルゴリ
ズムを用いて計算することにより、再びコンフリクト集
合を決定する。RETEアルゴリズムは分類（sorting）ネ
ットワークとして表示される。ルール集合中の全てのル
ールのLHS条件はコンパイルされ、ノード−その大部分
が検査（test）に結合されている−を含む分類ネットワ
ークになる。例示化を認識する該ネットワークの使用は
“RETE"又は“マッチング処理”と呼ばれる。RETE処理
では、該ネットワークを介してトークンが転送される。
該ネットワークを横切るトークンは、コンフリクト集合
での即ちコンフリクト集合のための例示化を表わす。RE
TE処理は高価な計算であるため、それを減らすプロダク
ション・システム手法の重要性は増大する。

初期のルール・ベース方式のプロダクション・システム
は１つのルールのRHSで一定シーケンスの行動しかサポ
ートしなかった。この制約によりRHSが非常に短くなっ
た。この初歩的なRHSの形式の結果、ルールはは１つの
発火中に同じCMに対して２つ以上の変更はめったに行な
わないことになった。ルールを記述するための高級手順
言語手法の使用の増大はサブルーチン、関数、及びルー
ルRHSでのコルーチン（coroutine）のような手続きの合
併をもたらした。これらの場合には、高級手順言語が使
用されるルールRHSの実行中、手続きの実行、及びこれ
らのネスティング（nesting）は１つのRHSの実行で単一
のCMに対する変更を反復して生ずることがよくある。一
例として、RHSの実行中にサブルーチンが呼出されると
想定する。ルール・ベース方式のプロダクション・シス
テム手法を用いてプログラム言語が該サブルーチンの書
込みを許可することは明白である。サブルーチン実行
中、多くのルールが発火可能であり、サブルーチンの計
算が終了する際には、多くのCMを反復して生成、変更
し、更に親ルーチンに復帰する前に作業メモリから削除
するすることができる。そして該サブルーチンを呼出し
たRHSの実行が続行する。

通例、CMに対する変更を行なった直後にRETE処理に着手
するのが普通である。よって、プロダクション・システ
ムの計算の強度−及び費用−は、複合行動を許可し階層
ルーチン実行をサポートするRHSの能力の精巧さによっ
てのみ増幅される。

C.発明が解決しようとする問題点 本発明の目的はルール・ベース方式の人工知能プロダク
ション・システムで必要とするマッチング処理の量を減
少させることである。

更に、本発明の目的はルール・ベース方式の人工知能プ
ロダクション・システムで全てのマッチング手続きの実
行を、認識行為サイクルの終了まで延期し、しかも当該
認識行為サイクル中に作業メモリ・オブジェクトに対し
て行なわれた変更を蓄積し合体させることである。

D.問題点を解決するための手段 従来は、RETE処理はCMに対する変更に続いて着手されて
いる。クラス・メンバーに対する変更を対応するRETE処
理から分離させ延期させることができることが、発明者
により思いがけなく観察された。本発明により実施され
る遅延はRETE処理の全体量をしばしば減少させることが
できることがわかった。

本発明により、クラス・メンバーに対し変更が行なわれ
るときに、RETE処理に関する要求を記録する制御ブロッ
クが生成される。たとえ該RETE処理の実行以前に同じク
ラス・メンバーに対しもう１つの変更が行なわれても、
両変更を記録するただ１つの制御ブロックだけが必要で
ある。更に、該２つの変更は合体させ、１つの、多分よ
り大きな変更をもたらすことができる。RETEアルゴリズ
ムの費用は本質的に変更のサイズとは無関係であるか
ら、RETEネットワークを経由する２つのパスを１つのパ
スに減らすことにより、全RETE処理はかなり減少させる
ことができる。

ルール・ベース方式のサブルーチンの動作で更に観察さ
れる特徴は、クラス・メンバーに対して反復される変更
を相互に且つ完全にキャンセルすることができることで
ある。従って、呼出されたルーチンでのCMの変更による
呼出しルーチンでのRETE処理の延期は該呼出しルーチン
での当該CMのRETE処理の要求をうまく回避するであろ
う。一方、該呼出されたルーチンでは、RETE処理は該変
更されるCMのRETE処理の延期により少なくなる。

ルールの集合を呼出したり含んだりしない行動を処理す
るとき、複数の変更の合体は所与のCMでの動作数に比例
する効率利得を与える。ルール集合を呼出したり含んだ
りする行動の場合、効率利得の良さは随意に得られる筈
である。該改良は所与のCMに対する変更数に比例する
が、呼出されたり埋め込まれたりしたルーチンを処理し
ている間に任意に多数の変更が生ずることがある。

よって、本発明は作業メモリでのオブジェクト（CM）に
対する変更を合体させる方法であり、該方法はコンフリ
クト集合決定で用いる作業メモリ・マッチング構造体に
よりこれらの変更を処理する以前に起動される。その場
合、前記決定はルール・ベース方式の人工知能プロダク
ション・システムのパターン・マッチング、ルール選
択、ルール実行サイクル中に行なわれる。プロダクショ
ン・システムはルールを記憶するためのメモリと、作業
メモリと協動する推論エンジンと、各サイクルを実行す
るためのルールを記憶するメモリとを含む。各ルールは
パターン表示及び行動指定部を有する。ルールの行動指
定部は作業メモリ・オブジェクトに対する変更をもたら
す手続きを含む。該方法は： 第１のルールの実行から生ずるオブジェクトに対する第
１の変更に応じて、推論エンジン内に制御ブロック（C
B）を生成し、当該第１の変更を該生成された制御ブロ
ック（CB）に記録するステップ、 制御ブロックをエンキューするステップ、 作業メモリ・オブジェクトに対する第１の変更に続いて
起こり、第１のルールに続く次のルールの選択より以前
の第２の変更の場合に、エンキューされた制御ブロック
で第１及び第２の変更の正味の効果を合体させるステッ
プ、及び 第１のルールの実行を終了するとき、制御ブロックに列
挙された変更をマッチング機構を通じてパスするステッ
プ を含む。

この方法はマッチング処理を減少させる。この減少は、
ルールのネスティング、及びルールのパターン表示部に
より作業メモリ・オブジェクトを参照する共通性の程度
により拡大される。

E.実施例 本明細書では、“作成”と“生成”、“変更”と“更
新”、“除去”と“削除”、“クラス・メンバー”と
“作業メモリ要素”と“オブジェクト”はそれぞれ同義
に用いられる。更に、ルール・ベース方式の人工知能プ
ロダクション・システムの推論エンジンは“認識行為サ
イクル”−その基本動作サイクルはマッチング、選択、
実行のシーケンスを含む−と呼ばれるループ式の制御機
能を含む。例えば、前記Brownstoneの文献のpp.4−９を
参照されたい。

第２図に示す従来技術で、ルール・ベース方式のプロダ
クション・システム（プロダクション・システム）は推
論エンジン10、作業メモリ12、及びルール・メモリ即ち
ルール・ベース14を含む。これらの要素の構造、相互接
続及び機能は前述の従来技術の文献に詳しく説明されて
いる。第２図のプロダクション・システムで、ルール・
ベース14にあるルールの集合は、（プロダクション・シ
ステム動作に適合する）OPS5のような言語で記述された
アプリケーション・プログラムの形式でコンピュータ
（図示せず）に提示される。ルールは作業メモリ12でオ
ブジェクト−プロダクション・システムが動作する情報
又は事実を表わす−に適用される。作業メモリ中のオブ
ジェクトにより条件（LHS）部が満たされる全てのルー
ルの集合を決定するため、推論エンジン10はルールの集
合を作業メモリ中のオブジェクトに関連付ける。好まし
くは、このマッチングは、RETEネットワークのような、
順序付けられた構造体に基づいたマッチング手続きによ
ってなし遂げられる。各ルールのRETEネットワークはア
プリケーション・プログラムがコンパイルされるときに
確立される。以下、このマッチング・プロセスは“RETE
処理”と同義とする。ちなみに、RETEネットワーク以外
の構造体及び手続きもマッチングのために使用可能であ
ることは明白である。これに関連して、ベクトル、リス
ト、スキーマ及びフレームは全て、作業メモリ・オブジ
ェクトをルールの条件部に関連付けるため従来技術のプ
ロダクション・システムで利用されるマッチング構造体
である。

推論エンジンのマッチング手続きは、ルールの集合−そ
の条件部の全てが作業メモリ中のオブジェクトによって
満足される−から成るコンフリクト集合を生成する。推
論エンジンは実行のためコンフリクト集合から１つのル
ールを選択し、該選択されたルールを実行する。ルール
実行は該選択されたルールのRHSに列挙された１つ又は
複数の特定の行動をとることを必要とする。ルールの実
行は作業メモリ・オブジェクトの変更ないしは作成を必
要とすることが非常に多い。例えば、OPS5をベースとす
るプロダクション・システムでは、ルール実行は作業メ
モリで少なくとも１つのメモリ要素の付加、変更又は削
除を行なう。本説明では、付加、変更及び削除は全て、
作業メモリ・オブジェクトの“変更”とみなされる。従
って、もしオブジェクトがルールの実行により生成、更
新、又は削除されれば、該オブジェクトは“変更”とみ
なされる。

第２図で、推論エンジン10の認識行為サイクルは詳細に
はマッチング・サイクル20を含むことがわかる。マッチ
ング・サイクル20からルール例示化（instantiation）
のコンフリクト集合が形成される（ステップ22）。続い
て、コンフリクト決定（resolution）ステップ24で、実
行される（“発火させる”）コンフリクト集合例示化の
１つを選択する。認識行為サイクルのステップ26で、該
選択されたルールが実行され、通常は作業メモリ・オブ
ジェクトに対する変更を生ずる。該変更は実行ステップ
26で始まり、マッチング・サイクル20で終るライン27−
作業メモリに対する変更に続くマッチング処理を表わす
−で示す。

前記Brownstone外の文献のp230に示すように、従来技術
の推論エンジン10はルール実行から生ずる各の作業メモ
リ変更に応じてマッチング・サイクルを実行する。従っ
て、単一のルールの実行中に幾つかのマッチング・サイ
クルを実行することができる。マッチング・サイクル中
に要求されるRETE処理は高価で時間がかかる。よって、
前記処理を少しでも減少させることはプロダクション・
システムの有効性、効率及び有用性を高める。

第２図で、複数のマッチング・サイクル・ステップ20を
実行する可能性は判定ブロック28で示される。これに関
連して、第２図のプロダクション・システムが初期設定
されており、実行された最初のマッチング・サイクルが
第１のルールの発火以前に最初のコンフリクト集合を生
ずると想定する。この場合、判定ブロック28が否定出口
に進み、ステップ24でルールが選択され、ステップ26で
発火される。ここで、該選択されたルールのRHSで指定
された行動の全てが終了する以前に、実行中のルールが
作業メモリ・オブジェクトに対する変更を生ずると想定
する。作業メモリ・オブジェクト変更が認識され、ライ
ン27で示すように、マッチング・サイクルが実行され、
コンフリクト集合が更新され、判定ブロック28が肯定出
口29に進み、該選択されたルールの実行を継続すること
を可能にする。この場合、判定ブロック28は明白に第２
図の推論エンジンの潜在的な特徴を表わし、プログラム
（code）中では検出できないことがある。それにもかか
わらず、選択されたルールの実行から生ずる各の作業メ
モリ変更は、たとえルール実行が終了していなくても、
マッチング・サイクルの実行をもたらす。

第１図は本発明に従って構築された推論エンジンがその
動作で第２図の従来技術の推論エンジンとどのように識
別されるかを示す概念図である。第１図で、後で説明す
る本発明を組込むルール・ベース方式のプロダクション
・システムは推論エンジン30、作業メモリ（WM）32及び
ルール・ベース（RB）34を含む。コンパイルされたRETE
ネットワークの形式のマッチング構造体は参照番号40で
示される。マッチング構造体40は例示化のコンフリクト
集合42を生成し、コンフリクト決定手続き44は発火させ
るコンフリクト集合42の１つを選択する。ステップ44で
選択されたルールはステップ46で実行される。判断ステ
ップ48−実行ステップ46に潜在的に含まれる−は、実行
ステップが終了しているかどうかを質問することによ
り、作業メモリ・オブジェクトに対する変更に応答す
る。もし終了していなければ、選択されたルールの実行
を進めながら、ステップ49で、作業メモリ・オブジェク
トに対する変更を蓄積し且つ合体する。

ルールの実行が終了すると、判断ステップ48から肯定出
口に進み、蓄積・合体された変更は、マッチング・ステ
ップ40を実行することにより作業メモリ32に導入され
る。さらに、第２図の場合のように、判定ステップ48は
再現的（representational）であり、最後に選択された
ルールの実行中に行なわれた変更の合体に応じてコンフ
リクト集合42を変えるようにRETE処理の延期に対応す
る。変更される各作業メモリ・オブジェクト毎にマッチ
ング・ステップ40が潜在的に含まれるが、第１図に示す
推論エンジンの利点は、単一の作業メモリ・オブジェク
トに対する複数の変更が、今やマッチング・ステップ40
により単一の応答しか必要としないことである。それに
対し、第２図の推論エンジンでは、例えば、もし同じオ
ブジェクトに対し２つの連続する変更が行なわれるな
ら、各の変更がマッチング・サイクルを開始するであろ
う。しかしながら、第１図の推論エンジン30で、同じデ
ータ・オブジェクトに対する連続する変更は合体され、
その結果、該変更された作業メモリ・オブジェクトのマ
ッチング・サイクルは一度しか企てられない。更に、推
論エンジン30は変更を合体し、選択されたルールの実行
で変更されるオブジェクト毎の変更処理を延期する能力
を有する。

本発明は、産業用の実施例では、ルール・ベース方式の
プロダクション・システムを定義するアプリケーション
によりプログラミングすることができる適切なコンピュ
ータ・システム・ハードウェアの存在を仮定する。プロ
ダクション・システムのルールはコンパイルされ、作業
メモリ・オブジェクトにより左側が満たされるルールの
コンフリクト集合を構築・更新するため、RETEネットワ
ーク構造体に組込まれる。

下記の説明では、作業メモリ・オブジェクトは複数のク
ラスに分離される。クラス内の該オブジェクトはクラス
・メンバー（CM）と呼ばれる。本発明により、ルール実
行の過程で、クラス・メンバーが変更される毎に、指示
された行動−オブジェクトは変更されるが、対応するマ
ッチング処理は延期される−が選択される。マッチング
処理の要求は制御ブロックの生成により記録される。も
し実行中にクラス・メンバーに対し追加の変更が行なわ
れても、追加の制御ブロックは生成されない。最初の制
御ブロックは全ての集積された変更の最終的な結果を反
映するのに十分である。ちなみに、最初の制御ブロック
は、選択されたルールの実行中、クラス・メンバーに対
する蓄積された変更を“合体”する。

ルールの実行は、例えば、最初に、CMの生成を必要とす
ると仮定する。この変更はCBを生成する際に記憶され、
CMが“作成”される。しかしながら、ルール実行が終了
していないとき、該“作成”に応じてRETE処理が行なわ
れることはない。CBは“作成”キューにエンキューされ
る。次に、該CMはその属性の１つを変更することにより
更新されると仮定する。該属性を変えることにより次の
変更が企てられる。しかしながら、今は、追加のCBは生
成されない。代りに、ルール実行が終了すると、“作
成"CBは更新されたCMを生じ、RETE処理される。ちなみ
に、“作成"CBは、“作成”及び“更新”の変化を表す
のに十分であり、その存在は単一のそれ自身に変更を合
体している。該更新されたCMをルール・ベースとマッチ
ングさせるのに、今は単一の“作成"RETEプロセスしか
必要としない。従来技術では、CMが変更されたとき、
“作成"RETEプロセスがCMの生成で実行され、続いて
“更新"RETEプロセスが実行されるであろう。従って、
本発明は、この例では、RETE処理を半分に減らす。

本発明では、プロダクション・システムを含むアプリケ
ーションがコンパイルされるとき制御オブジェクトが宣
言される。作業メモリでオブジェクトは複数のクラスに
分離されることがわかる。各のクラスはクラス・アンカ
ーによって定義される。アプリケーションを初期設定す
る際、下記の宣言（行中の記号“／＊”は注釈文の区切
りを示す）でクラス・アンカー（CA）を指定する： 各のクラス・メンバー（CM）はそのクラス・メンバーと
恒久的に結合されているヘッダ（CMH）を保持する。CMH
はそのCMとともに生成され初期設定される。CMのアドレ
スは直ちにCMHのアドレスを生じ、逆にCMHのアドレスは
CMのアドレスを生ずる。明確に言えば、CMHは下記によ
り定義される； 実行時スタック・ブロック（RTSB）と呼ばれる制御ブロ
ックは下記の宣言を満たす： CMに関する変更情報は変更ブロック（CHB）に記録され
る。CHBはクラス・メンバーに対する変更を合体する制
御ブロックである。変更ブロックは下記により与えられ
る： 次に、実行時スタック“CARES"ブロック（RCB）と呼ば
れる制御オブジェクトが下記により宣言される： 最後に、感心（care−for）クラス・ブロック（CCB）と
呼ばれるエンティティーが下記により宣言される： 上記定義されたオブジェクトの全ては、記憶装置内のア
ドレス可能な位置−“ポインタ”と呼ばれる周知のシン
タックスの要素によって指定される−を含む。

もしルールRHSがサブルーチン、関数、又はコルーチン
の呼出しを含むなら、これらの変更の処理のため呼出し
ルーチンがイネーブルされるように、これらの制御のエ
ンティティーは、アプリケーションが呼出し中に行なわ
れたCM変更を合体することを可能にする。CMに対し変更
が行なわれるとき、CHBが生成され、RETE処理が必要で
あることを記録する。同じCMに対するもう１つの変更
が、たとえRETE処理実行前に行なわれても、両変更を記
録するのに１つのCHBしか必要としない。サブルーチン
中に、CMが生成、変更され、そして呼出しルーチンヘの
復帰が生ずる前に破壊されることがありうる。制御の流
れが呼出し者に戻る時点までに、CMの痕跡はなくなる。
本発明は、制御が呼出し者に戻るまで、呼出しルーチン
のRETE処理が延期されることを可能にする。以下の説明
を簡略化するため、１つの定義を採用する。もしルーチ
ンがルール−そのLHSがクラスを挙げる−を有するな
ら、そのルーチンのRETEアルゴリズムは、当該ルーチン
のコンフリクト決定が行なわれる前に、当該クラスのメ
ンバーに対する全ての変更を処理しなければならない。
この場合、もし該ルーチン内のあるLHSが該クラスを挙
げるなら、該ルーチンのRETEネットワークは該クラスに
感心を有すると言われる。

第３図は本発明の実施に必要な制御オブジェクト間の相
互接続を示す。第３図で、作業メモリ32は複数のクラス
−その１つのクラスはクラスＡと呼ばれる−に分割され
たオブジェクトの集合を含む。CA60はクラスＡに含まれ
た全てのCMから成る二重結合循環キューをアンカーす
る。クラスＡのキューはCM61〜64を含む。CA60は少なく
とも３つのフィールド60a、60b及び60cを含み、各のフ
ィールドはポインタ（PTR）を含む。フィールド60aはク
ラスＡの最初のCM61を指すPTRを含み、フィールド60bは
最後のCM64を指すが、フィールド60cはRTSB CARESスタ
ックの名称を付されたキューでの上部のRCBを指す。

CM61〜64の各はクラス・メンバー・ヘッダ（CMH）を含
む。CM63のCMHは参照番号69で示す。CMH69はクラスＡの
CA60を指すポインタ（CA PTR）を有する。CMH69はCM63
のCHBの“経歴”スタックを指すポインタ（HS PTR）も
有する。CM63について図示された詳細な構造はCM61〜6
4、及び作業メモリ32内のあらゆるCMに共通の構造であ
る。従って、あらゆるCMはそれ自身の専用の経歴スタッ
クを指すポインタを有し、あらゆるクラス・アンカーは
それ自身の専用のRTSB CARESスタックを指すポインタを
有する。

第３図で、プロダクション・システムは、どのルールの
RHSも従属するルーチン又は機能に対する“呼出し”を
包含するすることができる階層構造を有するものと想定
する。従属ルーチンは呼出しルーチンよりも低い階層の
レベルにあるとみなされる。第３図で、“実行時スタッ
ク”と呼ばれるスタックは、サブルーチンを呼出すとき
プッシュされ、サブルーチンから戻るときポップされる
リンクされたデータ・ブロックのリストである。このス
タック内のブロックはRTSBである。第３図の実行時スタ
ックは４つのRTSB70〜73を含む。RTSB70は階層で最初に
呼出される主ルーチンのRTSBである。RTSB70を所有する
ルーチンはRTSB71を所有するルーチンを呼出し、RTSB71
を所有するルーチンはRTSB72を所有するルーチンを呼出
している。RTSB72を所有するルーチンはルーチン74
（“プロセス”ルーチン）−RTSB73を所有する−を呼出
している。RTSB73はRTSB70〜72の構造と同一の構造を有
する。RTSB73はポインタ（次のRTR）73aにより次のRTSB
（72）を指す。フィールド73bは“関心のあるクラス”
スタックを指すポインタ（CCB PTR）を含む。最後に、
MAKE（作成）スタック、UPDATE（更新）スタック及びCH
ANGED（変更された）−短縮形CHNG−スタックをそれぞ
れ指す３つのポインタ73c、73d及び73eがある。

MAKE、UPDATE及びCHANGEDスタックは、RETE処理の要求
を記録する制御ブロックが記憶されるキューである。制
御ブロックはこれらのキューでは変更されたブロック
（CHB）と呼ばれる。MAKE、UPDATE及びCHANGEDキュー
は、そのメンバーがポインタによって接続される従来の
連結リストである。例えば、MAKEスタックはCHB110、11
1及び100を含む。UPDATEスタックはCHB120〜122を含
み、CHANGEDスタックはCHB130〜132を含む。各のRTSBは
それらのキューのそれ自身の集合を有するが、それらを
他のどのRTSBとも共用しない。

CHBは３つのタイプ：“MAKE"、“UPDATE"又は“CHANGE
D"のどれか１つになりうる。RETEアルゴリズムによって
“MAKE"がプッシュされなければならないレコードは“M
AKE"CHBで保持され；“UPDATE"のレコードは“UPDATE"C
HBで保持され；クラス・メンバーが変更され、適切なRE
TE処理が終了しているレコードは“CHANGED"CHBに保持
される。MAKE、UPDATE及びCHANGEDスタックのCHBの例は
フィールド100a〜100fを有するCHB100である。フィール
ド100aは、このタイプがどのタイプのCHBであるかを表
わすコード（TYPE）を含む。例えば、CHB100のフィール
ド100aは、それが“MAKE"タイプであることを表わすコ
ードを含む。このCHBを所有するRTSBを指すポインタは
フィールド100bにある。この場合、該CHBはRTSB73が所
有する。次に、このCHBが関係するCMは、フィールド100
cにあるクラス・メンバー・ポインタ（CM PTR）で指
す。RTSB73からのMAKEキュー内の前及び次のCHBは、そ
れぞれフィールド100d及び100eで指す。最後に、各のCH
BのCM PTRフィールドは、各のCHBを作業メモリ32内の
ただ１つのCMと結合させることが明白である。更に、CM
のCHBが属するCM毎に、経歴キューが維持される。従っ
て、各のCHBは２つのキュー：該CHBを所有するRTSBのMA
KE、UPDATE又はCHANGEDスタック、並びにそれが結合さ
れる１つのCMの経歴スタックに属する。従って、第３図
で、CHB100はRTSB73に連結されたMAKEスタックのメンバ
ーであり、更にCM63の経歴スタックのメンバーでもあ
る。CM63の経歴スタックはCHB100とCHB140及び141（図
示せず）から成る。

作業メモリ・オブジェクトに関する変更の合体は第３図
のMAKE、UPDATE及びCHANGEDキュー並びにCHBを参照する
ことにより理解を深めることができる。説明中の実施例
で、もしCMが除去されるなら、（未決定でCHBに記録さ
れているより早い変更を無視して）該“除去される"RET
E処理が直ちに実行される。その後、該除去されたCMの
全てのCHBが破壊される。従って、“除去される"CHBも
なく、RTSBから“除去される”キューもない。CMの作成
とその後の更新に関する前述の例を思い出して、もし該
CMの作成が、実行時スタックで上部のRSSBの“作成"CHB
の生成及びエンキューによって示されるなら、該CMの次
の変更は“更新"CHBの生成を必要としない。更に、“作
成"CHBに対する追加の変更は行なわれない。同様に、も
しルールが実行されるとき現に存在するCMが現に実行中
のルーチンによって更新されるなら、該上部のRTSBの
“更新"CHBが生成され、該CMの更新キューRTSB及び経歴
スタックに入れられる。もし当該クラス・メンバーが前
実行中に再び変更されるなら、該生成された“更新"CHB
は該CMに対する変更を記録するが、該CHBの変更は必要
とせず、新しい“更新"CHBの生成も必要としない。これ
らの２つの事実と前述の“除去”の処理は、CMに対する
変更を合体することを特徴とする。

上部のRTSBからエンキューされた“変更された"CHBは、
現に実行中のルーチン中に該指定されたCMが前に生成又
は変更されたこと、及びこれらのより早い変更のRETE処
理が終了されたことを記録する。前のRETE処理が終了し
たとき、前のCHBがその作成又は更新キューから除去さ
れ、TYPEフィールドは“CHANGED"に変更され、CHBは該
“CHANGED"キューに挿入されている。もし該CMが再び変
更されると、該CHBは上部のRTSBからのCHANGEDキューか
ら除去され、該CHBは同じRTSBのUPDATEキューに挿入さ
れる。同時に、そのTYPEフィールドは“更新”に変更さ
れる。これはいま追加RETE処理の実行が必要であること
を反映する。

CMの経歴スタックはCMのために構築されたあらゆるCHB
を含む。従って、CMの経歴スタックはRTSBが異なると別
のCHBを含むことができる。経歴スタックが複数のCHBを
含むときは、それらは別のRTSBからエンキューされ、実
行時スタックにあるRTSBのサブセットを有する一対一の
対応をCHBの経歴スタックに付与する。この一対一の対
応は実行時と経歴スタックの間の順序を保存する。経歴
スタックにあるCHBに対応するRTSBは、そのルーチンがC
Mの含まれているクラスに“関心を有する"RTSBのサブセ
ットである。しかしながら、CMのCHB経歴スタックは、
該CMのクラスに関心を有する全てのルーチンの完全なリ
ストを持たないことがある。例えば、ルーチンＸのRETE
ネットワークがクラスＡに関心を有し、ＸがルーチンＹ
を呼出し、且つクラスＡのメンバーがＹに生成されるも
のと想定する。実行がＹに留まる間、ルーチンＸのRETE
ネットワークには新しいクラス・メンバーの経歴がな
く、ルーチンＸのRTSBからエンキューされた新しいクラ
ス・メンバーのCHBがない。ルーチンＹがルーチンＸに
戻ると、ルーチンＸのRETEネットワークが実際に新しい
クラス・メンバーに関心を有するかどうかが（例えば探
索することにより）決定されるであろう。しかしなが
ら、本発明では、クラス・ポインタからエンキューされ
たRTSB CARESスタックはどとRTSBが当該クラスに“関心
を有する”かを記録する。従って、ルーチンＹがルーチ
ンＸに戻ると、クラスＡのRTSB CARESスタックを“歩行
する（walking）”ことにより、ルーチンＸのRETEネッ
トワークがクラスＡの参照を含むという事実を迅速に決
定することができる。

クラス・アンカー60のフィールド60cのRCS PTRはクラ
スＡのRTSB CARESスタック内の上部ブロックを指す。RC
BはRTSB CARESスタック内にある。実行時スタックがプ
ッシュされる（即ち、サブルーチンが呼出される）毎
に、もし当該サブルーチンのRETEネットワークがクラス
に関心を持つなら、RTSB CARESスタックも当該スタック
の上部へのRCBの付加によりプッシュされる、新しいRTS
Bを指す。ちなみに、クラスＡのRTSB CARESスタックは
連結リストのRCB150〜152から成る。各のRCBは、RCB150
のフィールド150a及び150bに対応する少なくとも２つの
ポインタ・フィールドを含む。フィールド150aには、ク
ラスＡに関心をもつルーチンのRTSBを指すポインタがあ
る。フィールド150bには、RTSB CARESスタック内の次の
RCBを指すポインタがある。

前述のように、ルーチンの呼出しは実行時スタックへの
RTSBのプッシュ動作、及び呼出されたルーチンが関心を
もつ各のクラスのRTSB CARESスタックへのRCBのプッシ
ュ動作を生ずる。ルーチンが関心をもつ全てのクラスの
高速アクセスがCARED_FOR CLASSES（関心クラス）スタ
ックで提供される。第３図で、このスタックはCCB160〜
162を含む。このスタック内の各のCCBは、ブロック160
のフィールド160a及び160bに対応する少なくとも２つの
フィールドを含む。第１のフィールドは呼出されたルー
チンが関心をもつクラスの１つのクラス・アンカーを指
すポインタ（CA PTR）を含む。第２のフィールドは該
スタック内の次のCCBを指す。

第３図の説明で、用語“リスト”、“キュー”及び“ス
タック”は、連結されたブロックのシーケンスを表わす
ため互換的に用いられている。これらのシーケンスには
プロダクション・システム・アプリケーションでのルー
チンの階層に対応する順序を有するものがある。これら
のシーケンスの全てはアプリケーションの初期設定時に
従来の方法を用いて生成され、該アプリケーションの実
行中に従来のルーチンを用いて処理されることは明白で
ある。本発明はリスト、キュー又はスタックの発明では
なく、むしろ、その実行のため、これらの周知の構造に
依存する。

本発明の実施はRHS実行でルーチン呼出しを用いるプロ
ダクション・システムに限定されるものではない。その
最も簡単なアプリケーションでは、本発明は、呼出しを
用いないことがあるが複合RHSを認識し実行するプロダ
クション・システム・アプリケーションに有用である。
この最も簡単な場合には、第３図の構造は簡単なRTSB及
び作業メモリの全てのクラスを指すCARED−FOR CLASSES
スタック並びに単一のRTSBを指す単一のRCBを有するRTS
B CARESスタックを示す。なお、この基本的な利用で、M
AKE、UPDATEおよびCHANGEDキューは、ルール実行毎に、
変更を合体し実行の終了まで変更を延期するのに役立つ
であろう。

しかしながら、サブルーチンへのRHS呼出しをサポート
するプロダクション・システムで本発明が適用されると
きは、一組の仮定が行なわれる。最初に、もしルーチン
の階層で任意のルーチンがルール−そのLHSがクラスを
挙げる−を有するなら、当該ルーチンのRETEアルゴリズ
ムは、ルーチンの実行が可能になる前のコンフリクト決
定以前に、当該クラスのCMに対する全ての変更を処理し
なければならない。この点で、このルーチンのRETEネッ
トワークは、もしルーチンのルール・ベース内のLHSが
クラスを挙げることがあるなら、該クラスに“関心”が
あると言われる。これと共に、下記の仮定がルーチンに
適用される： （１）各のルーチンはそれ自身の、異なるRETEネットワ
ークを有する。

（２）ルーチンが呼出されるとき生成され、該ルーチン
がその呼出し者に戻るとき削除される異なるコンフリク
ト集合がある。

（３）データ駆動式のルールのサブルーチンの再帰的呼
出しは、該呼出されたルーチンの追加のRETEネットワー
ク−該ルーチンのネスティングのレベル毎に１つのネッ
トワーク−の生成によってだけサポートされる。

（４）実行時スタックはルーチンが呼出されるときプッ
シュされ、該ルーチンが戻されるときポップされる。

（５）ルーチンが呼出されるとき、該ルーチンの入口
で、該呼出されたルーチンのRETEネットワークは、該ル
ーチンのRETEネットワークが関心のある全てのクラスの
全てのメンバーを処理しなければならない。該処理は関
心のあるクラスの全てのCMについて“MAKES"として処理
される。ルーチンを脱出するとき、該ルーチンのRETEネ
ットワークは、RETEネットワークが関心のあるあらゆる
クラスのあらゆるメンバーを“除去”することによりフ
ラッシュされる。

第３図の制御ブロック及び制御ブロック結合を利用し
て、本発明による変更を合体する方法について更に詳細
に説明する。

クラス・メンバーが生成されるとき、“作成"CHBも生成
される。CHBは実行時スタック内の上部RTSBからMAKEキ
ューにエンキューされる。CHBは生成されたクラス・メ
ンバーのCMHにアンカーされた経歴スタックにもプッシ
ュされる。もしCMに対する追加の変更がルーチンのコン
フリクト決定に先行するなら、これらの変更は作成動作
に合体され、それ以上は、該作成されたCMがRETE処理に
かけられるまで、CHBに対して何も行なわれない。

コンフリクト決定が要求されると、上部RTSBのMAKEキュ
ーが歩行される。ちなみに、MAKEキューは下部から上部
への順に横切られ、該キューにCHBを有する各CMの“作
成”はRETEネットワークによりプッシュされる。MAKEキ
ューでCHBに連結されたCMがマッチング・サイクルにか
けられる毎に、該CHBはMAKEキューからCHANGEDキューに
移される。

もしCMが除去されれば、クラス・メンバーのクラスに関
心があり且つ実行時スタックにRTSBを有する全ての活動
状態のルーチンのため、除去のRETE処理が直ちに行なわ
れる。クラス・メンバーの全てのCHBはそれらの夫々の
キューから除去され、破壊される。もし生成又は変更が
除去要求の前に、しかも該進行中のコンフリクト決定ス
テップ後に生じたなら、該生成及び（又は）更新のため
の全てのRETE処理が回避される。

もし既存のCMに連続して複数の変更が作成されるなら、
当該CMの既存のCHBが最初の変更としてCHANGEDキューか
らUPDATEキューに移され、該CHBのTYPEフィールドに対
し適切な変更が行なわれる。該CMの最初の更新後に作成
されたこれらの変更についてはCHBの変更は必要としな
い。コンフリクト決定が、最後に、発火される次のルー
ルに移行することを必要とするとき、該UPDATEキューが
最初に歩行され、各のCMについて行なわれる“更新"RET
E処理はそれぞれのマッチング・サイクルで変更され、C
HBは全てCHANGEDキューに戻される。

CHANGEDキューは、主に、呼出し者のRETEネットワーク
での処理のため、合体された変更を呼出し者に戻すの
を、ルーチンの終了が妨げないことを保証するように維
持される。ルーチンＸがルーチンＹを呼出し、ルーチン
Ｙが終了までのランを有するものと仮定する。いま、制
御の流れがルーチンＹからルーチンＸに戻る。更に詳細
に説明すれば、ルーチンＹの呼出しを含んだルーチンＸ
で、あるルール（例えばRR）のRHSはいま実行を終了し
なければならない。他の行動は、該復帰の後、しかもル
ールRRの実行が終了し且つRETE処理がコンフリクト決定
を開始するため開始される前に起こすことができる。該
呼出しは、例えば、多数回反復されるループでルーチン
Ｙに対する呼出しかもしれない。もしルーチンＸが関心
をもつクラス・メンバーに対して行なわれた変更がルー
チンＸのRETEアルゴリズムによって直ちに処理されない
なら、本発明の実行による利点が得られる。代りに、本
発明はルーチンＹで行なわれた変更をルーチンＸで以前
に行なわれた変更と合体させる。

呼出しルーチンへの復帰時の合体は、呼出されたルーチ
ンのRTSBからのMAKE、UPDATE及びCHANGEDキューの各を
歩行することにより行なわれる。ルーチンＹのMAKE、UP
DATE又はCHANGEDキューにCHBがあると仮定して、もし当
該CHBが関係したCMの経歴スタックでの唯一のCHBであれ
ば、該CMはルーチンＹ（又はルーチンＹにより呼出され
たルーチン）内に生成されているに相違ない。この場
合、該CMのクラス・アンカーのRTSB関心スタックを見る
ことにより、ルーチンＸがこの新しいCMに関心があるか
どうかについて迅速な決定を行なうことができる。もし
ルーチンＸが新たに作成されたCMを含むクラスに関心が
あるならば、該CHBはルーチンＸのMAKEキューにはい
る。同様に、もしルーチンＹとルーチンＸの間に階層的
に置かれたルーチンが該クラスに関心があるならば、CH
Bは当該ルーチンのMAKEキューに移る。さもなければ、
該CHBは破壊される。

もし該CHBが該CMの経歴スタックでの唯一のCHBではない
ならば、次に古いCHBはルーチンＸに結合されるか、又
はルーチンＸとルーチンＹの間に階層的に置かれるルー
チンに結合される。即ち、該ルーチンは呼出しチェーン
でＸの前且つＹの後に置かれる。その可能性は該CHB内
のRTSB PTRをルーチンＸのRTSBのアドレスと比較するこ
とにより容易に決定される。もしルーチンＸがCMを含む
クラスに関心があれば、ルーチンＸが呼出されたときル
ーチンＸが関心をもつ全てのメンバー及び全てのクラス
が生成される（ルーチンＸのRETEネットワークにより新
しいCMとしてプッシュされる）仮定のために、ルーチン
ＸのRTSBからエンキューされたCHBがあるに相違ない。
もしルーチンＸのエンキューされたCHBがあるならば、C
HBをルーチンＸのUPDATEキューに−もしそれが以前にル
ーチンＸのCHANGEDキューにあったなら−戻すことだけ
が必要である。同様に、もし実行時スタックでＸより下
のRTSBのエンキューされたCHBがあれば、そのCHANGEDキ
ュー内のCHBはルーチンUPDATEキューに移す必要があ
る。全ての場合に、ルーチンＹのCHBを削除するため経
歴スタックがポップされる。

ルーチンＹがルーチンＸに戻ると、実行時スタックがポ
ップされ、同時に、ルーチンＹが関心をもつ各のクラス
・アンカーの位置を迅速に探すため“CARED FOR CLASSE
S"キューが歩行される。これらのルーチンの各につい
て、前記クラス・アンカーの各について、RTSB CARESス
タックがポップされ、ポップされたRTSBを指すRCBを除
去する。

ルーチンＸがルーチンＹを呼出すとき、逆のステップが
とられ、実行時スタックがプッシュされる。CARED FOR
CLASSESキューは歩行され、クラスCCB毎に、該指定され
たクラス・アンカーについて２つの行動がとられる。第
１に、RTSB CARESスタックがプッシュされ、該RTSBを指
す新しいRCBが実行時スタックにプッシュされる。第２
に、CARED FOR CLASSESのキューがルーチンＹで用いるC
Mを生成するように歩行され、各の経歴スタックがプッ
シュされ、当該スタック内の新しいCHBもRTSBのMAKEキ
ューでエンキューされる。

前述の動作手続きは第４図に示す。第４図で、プロセス
・ステップ210、220、230、240及び250をその順序に含
む認識行為サイクルを実現する親ルーチン200にルーチ
ンＸが組込まれている。RETE処理がマッチング・ステッ
プ210で実現され、コンフリクト集合220を生成する。発
火させるルールが解決ステップ230で選択され、該ルー
ルは、ステップ230で選択された例示化を実行すること
により、ステップ240で実行される。例示化を実行する
過程の間に、アプリケーション・コードが、ルール実行
の一部として作成、更新、又は除去される作業メモリ・
オブジェクトに対する変更を開始する。更に、該実行の
過程はサブルーチンＹの呼出し（CALL_Y）を含むことが
できる。ルーチンＹの呼出しがない、即ちＹから制御が
戻ると仮定すると、マッチング及びコンフリクト集合ス
テップ210及び220は、DO_RETE処理と呼ばれるルーチン2
50の呼出しに先行される。

ルーチンDO_RETE処理は表Ｉに示す。表Ｉで、該ルーチ
ンはルーチンRTSBのUPDATEキュー内のCHB毎に、パラメ
ータとして上部RTSBのRETEネットワーク、CHBによって
指定されるCM、及びUPDATE処理を実行するコマンドと一
緒に、ステップ210及び220のRETE処理を呼出す。次に、
CHBはCHANGEDキューに移され、そのタイプはCHANGEDに
セットされる。そして、MAKEキュー内のCHB毎に、上部R
TSBのRETEネットワーク、CHBによって指定されるCM、及
びMAKEルーチンをパラメータとして用いるステップ210
及び220のRETE処理ルーチンが呼出される。次に、CHBは
CHANGEDキューに移され、そのタイプはCHANGEDにセット
される。

第４図で実行ステップ240からのCALL_Yに続いて、サブ
ルーチンＹのプロダクション・システム・ルーチンが開
始される。サブルーチンＹへの入口で、ステップ320が
呼込まれる。ステップ320は呼出されたルーチン、サブ
ルーチン・プロローグから成り、DO_RETE処理ルーチン
が後続する。サブルーチン・プロローグ・ステップ320
の詳細は表IIに示す。サブルーチン・プロローグはプロ
ダクション・システムにおける各の呼出されたデータ駆
動式のルーチンのプロローグの一部として実行される。
その基本的な機能は、該ルーチンが関心をもつクラスの
全てのメンバーのRETE処理を呼込み、変更を合体するた
めに必要とする全てのスタックをプッシュすることであ
る。このルーチンは、終了後、呼出されたルーチンに戻
って認識行為サイクルを呼出す。

表IIに示すように、該ルーチンのRTSBが構築され、実行
時スタックにプッシュする。該ルーチンのCARED FOR CL
ASSESキューによって指定されたCA毎に新しいRCBが生成
され、RTSB CARESスタックにプッシュされる。それか
ら、ルーチンＹのCARED FOR CLASSESキューにあるCCBに
よって指定されたCAから、クラス・メンバーのキューで
CM毎に、新しいCHBが生成され、結合されたCMの経歴ス
タックにプッシュされ、該ルーチンのRTSBからMAKEキュ
ーにエンキューされる。サブルーチン・プロローグ・ル
ーチンはそのあと表ＩのDO_RETE処理ルーチンを呼出
し、ルーチンＹのMAKEキューにある“作成”の全てを処
理する。このように、ＹのRETEネットワークはＹが関心
をもつWM301からの全てのCMとともに初期設定される。
これはサブルーチンＹによりプロダクション・システム
処理を開始するために必要である。

次に、サブルーチンＹは認識行為ルーチン340−その詳
細は表IIIに示す−を呼出すことにより、そのプロダク
ション・システム動作を開始する。認識行為ルーチン
は、呼出し者、ルーチンＸにルーチンを渡すべき時期を
表わすフラグをアプリケーションがセットするものと仮
定する。このようなフラグはOPS5プログラミングで用い
るような制御要素は形式をとることができる。表IIIの
ルーチンは初めに実行するルーチンを選択し、その後、
発火させる例示化があるものと仮定して、該例示化を発
火させる。サブルーチンＹでの該ルーチンの実行はアプ
リケーション・コード−実行中に作成し、更新し、除去
する行動をとる−により遂行される。フラグ、又は制御
要素処理は、制御をサブルーチンＹの呼出し者に戻す時
期をアプリケーションに知らせるためにも、ルール実行
中に該アプリケーションによって遂行される。

ルール実行中、認識行為ルーチンがCMの実行、更新又は
除去を必要とすることがある。もし要求されれば、表I
V、Ｖ及びVIの夫々のルーチンに関連してこれらの行動
がとられる。

従って、認識行為ルーチン340で新しいCMが作成される
なら、作成手続きが実行され、表IVの作成実行手続きが
呼出される。表IVの手続きはCHBにある“作成された"CM
のRETE処理の必要を記録する。該CMが作成されるとき、
それはクラス−それが所属することになっている−の表
示を含むものと仮定する。この表示を用いて、該クラス
のCAが位置決めされ、該CAは該クラスCAからのクラス・
メンバー・キューに挿入されるとともに、作成“CHB"が
生成され、該CMについて初期設定され、該CMの経歴スタ
ックにプッシュされ、上部RTSBからのMAKEキューに挿入
される。

既存のクラス・メンバーが更新によって変更されると
き、該変更が作成され、表Ｖの実行・更新手続きが呼出
される。先の記述では、もしルーチンが現に実行中であ
り且つ１つのクラスに関心があるなら、該クラスでのCM
毎に、該ルーチンのMAKE、UPDATE又はCHANGEDキューにC
HBが存在するに相違ないことを想起されたい。従って、
CHBは、表Ｖの機能が呼込まれる時に、これらの３つの
キューの１つに存在するに相違ないことが知られてい
る。更に、該位置決めされたCHBがCHANGEDキューにはな
いなら、RETE処理の必要は既に記録されており、それよ
って、この変更は既に記録された変更と合体されている
ので、それ以上何も実行することはない。

この実施例では、“除去”処理はCB戦略により実現され
ない。全体の処理を減らすために、後の“作成”が所与
の“除去”と合体されるであろうという期待により、
“除去”はエンキューされないであろうが、本実施例は
むしろCMの全てのトレースを、アプリケーションが“除
去”動作を要求すると直ちに削除する。

“除去”が実行されるとき、表VIの除去実行手続きが呼
出され、“UPDATE"又は、“CHANGED"キューにあるCHBが
見つけられ、CMが除去され、CHBが現在のRTSBのMAKE、U
PDATE又はCHANGEDキューからデキューされ且つCHBがCM
の経歴スタックからポップされ破壊される。最後に、該
CMが破壊されルーチンは終了する。

表IIの認識行為ルーチンに戻って、選択された例示化が
発火を終了しているとき、ステップ350で“DO_RETE"処
理ルーチン（表Ｉ）が呼出される。ステップ350のRETE
処理が終了するとき、もし復帰フラグがセットされてい
なければ（ステップ360）、再びステップ340で認識行為
ルーチンが実行される。もしフラグがセットされていれ
ば、ステップ370のサブルーチン・エピローグが呼出さ
れる。

サブルーチン・エピローグは表VIIに示され、サブルー
チンＹを含む、各のルーチンの終了の部分として実行さ
れる。該エピローグは現在のRTSBのCCBにリストされた
各クラスのRTSB CARESスタックから上部RCBをポップす
る。そして、上部RTSBによって指定されるMAKE、UPDATE
及びCHANGEDキューにあるCHB毎に、該CHBはその結合さ
れたCMの経歴スタックからポップされ、そのRTSBキュー
からデキューされる。もし該のCMの経歴スタックは空で
あり、該CMのクラスのRTSB CARESスタックは空ではない
ならば、該CHBはMAKEに変更され、該クラスのRTSB CARE
Sスタックの上部RTSBによって指定されたRTSBのMAKEキ
ューに置かれる。さもなければ、経歴スタックの上部CH
BはCHANGED CHBに変換され、クラスRTSB CARESスタック
のRCBによって指定されたRTSBのUPDATEキューに移され
る。その後、このルーチンの該CHBは破壊され、実行時
スタックがポップされ、ステップ380で、該ルーチンのR
ETEネットワークは、Ｙが関心をもつクラスWM301でクラ
ス・メンバーの全ての除去を実行することにより“フラ
ッシュ”され、制御は（ステップ390で）ルーチンＸに
戻る。

表 Ｉ DO_RETE_processing: Do ‘更新’キューで各のCHBについて； RETE処理ルーチンを、上部RTSBのRETEネットワーク及び
パラメータとしてCHBのCM並びに‘更新’と共に呼出す CHBを‘変更された’キューに移しCHBのタイプを‘変更
された’にセットする End; Do ‘作成’キューで各のCHBについて； RETE処理ルーチンを、上部RTSBのRETEネットワーク及び
パラメータとしてCHBのCM並びに‘作成’と共に呼出す CHBを‘変更された’キューに移しCHBのタイプを‘変更
された’にセットする End; End DO_RETE_processing; 表 II subroutine_prologue:ルーチンの識別子がパラメータを
渡される；実行時スタックをプッシュする、即ち、新し
いRTSBを付加し初期設定する； Do ルーチンのCARED_FORクラス・キューの各のCCBにつ
いて； CCBにより指定されたCAからRTSB_CARESキューに新しいR
CBをプッシュし、RCBが新しいRTSBを指す； Do CCBにより指定されたCAからクラス・メンバーのキ
ューで各のCMについて； 各のCMのCHBを生成する； CHBをCMの経歴スタックにプッシュする； 上部RTSBから‘作成’キューにCHBをエンキューする； End; End DO_RETE_processingを呼出す;/＊全ての‘作成’を処理
する End subroutine_prologue; 表 IV Execute_a_make:CMにパラメータが渡される； クラス名又は他の識別子を用いてクラスのアンカー（C
A）を見つける； CAからクラス・メンバー・キューにCMを挿入する； CMのCHBを生成し初期設定する； CHBをCMから経歴スタックにプッシュする； 実行時スタックの上部RTSBからCHBを‘作成’キューに
挿入する； End execute_a_make; 表 Ｖ execute_an_update:CMにパラメータを渡す； If CMの経歴スタックの上部CHBが‘変更された’キュ
ーにある Then CHBを‘更新’キューに移し、CHBのタイプを‘更
新’に変更する； End execute_an_update; 表 VI execute_a_remove;CMにパラメータを渡す； Do CMにアンカーされた経歴スタックの各のCHBについ
て； If CHBが‘更新’又は‘更新された’キューにある Then CHBのRTSBのRETEネットワーク及びパラメータと
してCM及び‘除去’と共にRETE処理ルーチンを呼出す； 作成、更新又は変更されたキューからCHBをデキューす
る； 経歴スタックからCHBをポップする； CHBを破壊する； End; CMを破壊する； End execute_a_remove; 表 VII subroutine_epilogue: Do RTSBからのCARED_FORキューでCCB毎に； CCBにより指定されたCAのRTSB CARESスタックをポップ
する； End; Do 上部RTSBからの作成、更新及び変更されたキューで
各のCHBについて； CHBのCMの経歴スタックからCHBをポップする； 作成／更新／変更されたキューからCHBをデキューす
る； If 経歴スタックは空であるが、RTSB CARESスタックは
空ではない Then ／＊ 作成を早期のルーチンにより呼出しチェー
ンにプッシュする＊/RTSB CARESスタックで上部RCBによ
って指定されたRTSBの‘作成’キューにCHBを生成す
る； Else If 経歴スタックにある上部CHBが‘変更’され
る Then 同じRTSBの‘更新’キューにCHBを移し、CHBのタ
イプを‘更新’にセットする； CHBを破壊する； End; 実行時スタックをポップする； End subroutine_epilogue; F.発明の効果 本発明を用いれば、プロダクション・システムの処理効
率を向上させることができる。

【図面の簡単な説明】

第１図は本発明による認識行為サイクルの手続きのシー
ケンスを示す流れ図である。 第２図は従来技術の、ルール・ベース方式のプロダクシ
ョン・システムの認識行為サイクルでの最も重要なステ
ップのシーケンスを示す手続きの流れ図である。 第３図は本発明の実行に必要な制御構造体の集合及び制
御構造体の相互接続を示す図である。 第４図はルール・ベース方式のプロダクション・システ
ムで、ルール実行中にルーチン呼出しを行なう本発明の
手続きのシーケンスを示す流れ図である。 10……推論エンジン、12……作業メモリ、14……ルール
・メモリ／ルール・ベース、20……マッチング・サイク
ル、30……推論エンジン、30、32……作業メモリ（W
M）、34……ルール・ベース（RB）、40……マッチング
構造体、42……コンフリクト集合、44……コンフリクト
決定手続き。

Claims (1)

【特許請求の範囲】
1. 【請求項１】作業メモリ中のオブジェクトに対する変更
   を処理する方法であって、該方法はルール・ベース方式
   の人工知能プロダクション・システムの認識行為サイク
   ル中に起きるコンフリクト集合決定で用いるマッチング
   構造体により前記変更を処理する前に実行され、 前記システムはルール集合及び推論エンジンを含み、該
   推論エンジンは前記ルール集合及び作業メモリと協動し
   て連続した認識行為サイクルを実行し、各ルールはパタ
   ーン表示及び行動指定部分を有し、前記ルールの行動指
   定部分は前記オブジェクトに変更をもたらす手続きを含
   み、 前記方法は、 第１のルールの実行から生ずるオブジェクトに対する第
   １の変更に対する第１の変更に応答して、制御ブロック
   （CB）を生成し且つ前記第１の変更を該生成されたCBに
   記録するステップと、 前記CBをキューにエンキューするステップと、 前記第１のルールに続く次のルールの選択より前に、前
   記第１のルールによって前記オブジェクトに対する前記
   第１の変更に続いて第２の変更があった場合に、前記マ
   ッチング構造体に前記第１又は前記第２の変更をパスせ
   ずに、前記第２の変更も前記CBに蓄積し、前記CBは前記
   キューに維持し、 前記第１のルールの前記実行が終了すると、前記マッチ
   ング構造体に前記CBに記録された変更を合体してパスす
   るステップと を含む前記方法。