(57)【特許請求の範囲】
【請求項１】
環境レベルを付与したノードをアークで結合したデータフローグラフをプログラムとし、実行環境レベルを付与したトークンをアークを経由してノード上を伝播させ、環境依存発火機能と環境依存分配機能により発火制御するプログラム内のトークンの伝播上の正常性を検証するデータフローグラフ検証装置であって、
トークンが伝播してきた経路上のノードに着目して、
トークンがノードに入力できるかどうかの状態を示す入力状態を、当該トークンが伝播してきた経路上のノードに対するトークン伝播とエラー発生の状況に基づいて実行環境レベル毎に求める入力状態演算を行い、
ノードが発火するかどうかの状態を示す到達状態を、入力状態および当該ノードの環境レベルに基づいて実行環境レベル毎に求める到達状態演算を行い、
トークンが出力できるかどうかの状態を示す出力状態を、到達状態および出力アーク先ノードの環境レベルに基づいて実行環境レベル毎に求める出力状態演算を行う状態演算機能部
を有することを特徴とするデータフローグラフ検証装置。
【請求項２】
ノードが発火した際に、当該ノードへ入力するトークンに付与された関数の実行停止性に基づくと共に、前記ノードへ入力するトークンに呼び出し先関数が付与されている場合には当該呼び出し先関数の実行停止性にも基づいて、関数の相互呼び出しによる実行停止性を表す状態をノード種別に応じて求める有限再帰判別演算を行う有限再帰判別演算機能部
を更に有することを特徴とする請求項１記載のデータフローグラフ検証装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、環境依存発火機能と環境依存分配機能を有するデータフロー計算機で実行されるプログラムに対するデータフローグラフ検証装置に関する。
【０００２】
【従来の技術】
最初に、本検証装置で対象とするプログラムを実行するデータフロー計算機の動作概要について説明する。
【０００３】
このデータフロー計算機では、数値データ（環境レベルと呼ぶ）を付与したノードからなるデータフローグラフをプログラムとし、数値データ（実行環境レベルと呼ぶ）を付与したトークンを用いる。
【０００４】
ノードの集合をＮとする。ノードｎ（ｎ∈Ｎ）の環境レベルをｔａｇ（ｎ）と表す。ｎの第ｉ入力アークの先に接続されたノードの環境レベルをｔａｇin（ｎ，ｉ）、ｎの第ｊ出力アークの先に接続されたノードの環境レベルをｔａｇout （ｎ，ｊ）と表す。実行環境レベルｌを、トークンに付与する。この時、ｌ＜ｔａｇin（ｎ，ｉ）を満たす環境レベルを持つノードからｎへ張られたアークをｎの環境入力アークといい、ｎからｌ＜ｔａｇout （ｎ，ｊ）を満たす環境レベルを持つノードへ張られたアークを環境出力アークという。
【０００５】
環境依存発火機能は、全ての環境入力アーク上にトークンが全て揃うまでノードを待機させ、これらのアーク上にトークンが揃った後、ノードを発火させる機能である。環境依存分配機能は、全ての環境出力アーク上に実行環境レベルを与えたトークンを出力する機能である。
【０００６】
以上の機能により、ある実行環境レベルｌをトークンに付与してプログラムの実行を開始させると、ｌ以上の環境レベルを持つノード間にだけトークンを伝播させ、ｌ以上の環境レベルを持つノードだけを実行させることができる。
【０００７】
次に、経路識別子を用いた色付きトークンモデルについて説明する。
【０００８】
データフロー型実行装置において、色付きトークンの概念を導入することにより、異なる色を持つトークン間で、インタラクションを持たないようにできる。これにより、一つのグラフを複数の色（環境）で同時に実行させることができる。
【０００９】
まず、色付きトークンの基本モデルについて説明する。図２に実行例を示す。図中で「●（Ｋ，ａ）」は、値Ｋ色ａのトークンを表す。図２（ｂ）では、同じ色を持つトークンが全ての入力アーク上に揃っていないため、ノードの発火は行われない。図２（ｃ）では、同じ色ｉを持つトークンが全ての入力アーク上に揃ったため、ノードの発火が行われる。このように発火が行われると、データフローグラフを色別に複数の実行環境で共有できる。
【００１０】
検証を行う際に、複数ある経路を全て場合分けし、それらを一つ一つ検証するのでは、分岐命令の数が増えるほどに必要な実行回数が増加する。このため、一つのグラフを一回実行して検証を終了させるために、分岐命令では全ての出力アークに対し、異なる色を与えたトークンを出力する事とする。この際に、図３のような構造をもつプログラムの場合に問題が発生する。図中で太線で示したアーク上には、分岐ノード（楕円にＳＷの文字のあるノード）が新たな色を付与することにより、異なる色を持つトークンが伝播するため発火不可能となる。
【００１１】
上記の問題を解決するために、分岐命令（分岐ノードに与えられる命令）の、分岐経路ごとに、経路断片識別子（直井邦彰、高橋直久：プレスブルガー算術を用いたＩｎｔｅａｓｉｂｌｅ  Ｐａｔｈ検出法、知能ソフトウェア工学研究会１９９２，１１参照）Ｉｄpfを付与する。この系列＜Ｉｄpf1 ，Ｉｄpf2 ，…，Ｉｄpfj ＞を経路識別子と呼ぶ。経路識別子をトークンの色として用いることにより、複数の経路上のトークンを識別できる。制御ノードである分岐ノードでは、入力トークンの色（経路識別子）に対して、分岐方向に応じて異なる経路断片識別子を加えて経路識別子を作成し、これをトークンの色として出力アークに出力する。
【００１２】
ここで、２つの色ｃ1 ＝＜ｉｄp11 ，ｉｄp12 ，…，Ｉｄp1j ＞，ｃ2 ＝＜ｉｄp21 ，ｉｄp22 ，…，Ｉｄp2k ＞を考える。このとき、ｉ＝１，２，…，ｊ（ｊ＜ｋ）において、Ｉｄp1i ＝Ｉｄp2i のとき、ｃ1 はｃ2 の先祖（ｃ2 はｃ1 
【外１】
0003635667.tif 000002
2 を色とするトークンは同じ環境の値を運んでいると判定し、ノードを発火させる。これは、分岐ノードで分岐した２つの経路に対する検証を同時に行うとともに、各経路における検証で、その分岐ノードより前の経路断片での計算結果を共有できることを意味する。
【００１３】
次に、データフローグラフの検証方式について説明する。
【００１４】
まず、扱う構造について説明する。本検証装置により検出される、可到達性異常、伝播異常、全実行性異常、合流異常のいずれでもないプログラムは「良構造」であるという。以下の構造をもつプログラムは通常の実行時には正しく実行されるが、本検証法では合流異常として判定される。これらの構造は同じ機能をもつ良構造へ変換可能であるため問題はない。
【００１５】
図４（ａ）に示す分岐ノードを用いてサイクルを構成する繰り返し構造を考える。この構造は図４（ｂ）に変更可能である。このような指定繰り返し構造は関数の再起呼び出しに変換可能であるため、本検証系では、サイクルを構成しないプログラムだけを許し、図４（ａ）のようなサイクルを含む構造は合流異常があると判定する。
【００１６】
また、図５（ａ）に示す複数の経路が一つの実行経路を共有する構造は実行時にエラーを発生しない。しかし、この構造は図中の（ｂ）に示すような、より簡明な構造に変換可能である。このため、本検証系では、図５（ｃ）に例示するように、分岐ノードと合流ノードの対により分岐構造をネストしてできるプログラム構造だけを許し、図５（ａ）のようなネストしない構造は合流異常があると判定する。
【００１７】
次に、検出する異常について説明する。図１に異常があるプログラムの例を示す。図１において、白丸のノードは演算ノード、黒丸のノードは分配ノード、白丸にＳのノードは開始ノード、白丸にＥのノードは終了ノード、白丸にＳＷのノードは分岐ノード、逆三角形のノードは合流ノード、四角のノードは上述のノードにより形成される一つの経路を表す。また、ノードの左上の数字はノード番号を示す。以下に各異常について述べる。
【００１８】
まず、伝播異常は、開始ノードからトークンを出力しない終了ノード以外のノードに至る経路が存在するとき、伝播異常であるという。図１（ｇ）のノード４においては出力アークが存在しないためトークンを出力できない。
【００１９】
可到達性異常は、開始ノードから終了ノードまでトークンが伝播する経路が存在しないとき、可到達性異常であるという。例えば図１において、（ａ）のノード２、（ｄ）のノード６においてはトークンを出力できないため、また、（ｂ）のノード４、（ｃ）のノード３においては入力アーク上にトークンが揃わないため実行が停止し、終了ノードへトークンが到達しない。
【００２０】
全実行性異常は、開始ノードからトークンが到達する経路がないノードが存在するとき、全実行性異常であるという。例えば図１において、（ｂ）のノード２、（ｃ）のノード２は入力アークが存在しないため、発火する可能性はない。
【００２１】
合流異常は、分岐命令により分岐した経路をまとめること以外の目的で使用する合流ノードが存在する合流異常であるという。例えば図１において、（ｅ）のノード５では、合流ノードより先の経路を２つのトークンが伝播し、衝突することとなる。図１において、（ｆ）のノード２〜４の間は常にループ状態となり、先の経路上でトークンが衝突することとなる。
【００２２】
前述の経路断片識別子を値として持つトークンを検証実行に用いることにより、プログラムが良構造であるかを検出する。このために、発火規則を以下のように定める。
【００２３】
合流ノードの場合は、例えば、図６のような経路断片識別子の割り当てを表す木が与えられた場合には、値としてｃ1 とｃ2 もしくは、ｃ3 とｃ4 のよう兄弟関係にある経路断片識別子をもつトークンどうしが入力アーク上に揃った場合に発火する。
【００２４】
その他としては、等しい経路断片識別子をもつトークンが入力アーク上に揃った場合に発火する。
【００２５】
次に、検証のための実行法について説明する。ノードの実行状態を示すことにより、全実行性異常を検出する。このために、各ノードに対してフラグを付与する。このフラグを実行フラグと呼ぶ。実行フラグの値が１のときは、そのノードが実行されることを、０のときは実行されないことを表す。初期値は０である。
【００２６】
本検証装置は、データフローグラフ上の全てのノードに対して付与した実行フラグを０に初期化した後、以下に示す方式で処理を施す。
１．全ての入力アーク上にトークンが到達するまで待機させる。
２．入力アーク上にトークンが揃った後、前節で述べた発火規則に添ってノードの発火を行う。このとき、ノードの実行フラグを１にし、入力アーク上のトークンをノード内に取り込む。
３．ノード内のトークンの値をコピー（合流ノードの場合はトークンの値を親となる経路断片識別子を値とする）したトークンを出力アーク上に出力する。出力アークが存在しない場合は、トークンをノード内に取り込んだままとする。
【００２７】
それぞれのノードを上記の実行方式に従って発火させることにより、グラフ全体を非同期並列に実行する。
【００２８】
異常の検出条件について説明する。本検証装置により、検証対象とするプログラムを実行させ、実行中のノードがなくなった時点で検証のための実行を終了する。この際に、次の表１に示すことが言える。
【００２９】
【表１】
0003635667.tif 000003
図７は、従来の検証装置の構成を示す。図中で、実線矢印は制御の流れを、点線矢印はデータの流れを表す。図中の各機能について説明する。
トークン到着監視機能：全ての入力アーク上にトークンが揃ったノードを検出し、発火規則を基に発火させる。ノードが発火した場合は、ノードの実行フラグを１にして制御をトークン入力機能に移す。
トークン入力機能：入力アーク上のトークンを、入力アークの順に並べてノード内に取り込む。
ノード分類機能：発火したノードを演算命令、分配命令、分岐命令、手続き呼び出し命令、手続き開始命令、手続き復帰命令、合流命令に分類し、そのノード種別をトークン出力機能に送る。
トークン出力機能Ａ：トークン出力機能Ａの詳細構成図を図８に示す。図中で、実線矢印は制御の流れを、点線矢印はデータの流れを表す。命令デコード機構は、ｌｉｎｅＡに流れてきたデータよりノード種別を知り、対応する出力機構へ制御を移行する。トークン消去機構はノード内に取り込んだトークンを消去する。各出力機構は命令の種類に応じて以下の様に動作する。なお、入力アーク上に到達したトークンとは、ノード内に取り込んだトークンのことを指す。
【００３０】
演算命令出力機構は、入力アーク上に到達したトークンの値をコピーしてトークンを生成し、出力アーク上に置く。
【００３１】
分配命令出力機構は、入力アーク上に到達したトークンの値をコピーして新たにトークンを生成し、全ての出力アーク上へ置く。
【００３２】
分岐命令出力機構は、第２入力アーク上に到達したトークンの値より得られる経路断片識別子の孫値を２つ求める。求めた２つの経路断片識別子を値とする２つのトークンを生成し、それぞれ出力アーク上へ置く。
【００３３】
手続き呼び出し命令出力機構は、第２入力アーク上のトークンをコピーし、手続き開始ノードの第１入力アーク上に置く。また、出力アークの名前を値としたトークンを生成する。第１入力アーク上のトークンの値として格納されている関数名から関数の手続き復帰ノードを求め、そのノードの第１入力アーク上に、生成したトークンを置く。
【００３４】
手続き開始命令出力機構は、入力アーク上のトークンのコピーを出力アーク上に置く。
【００３５】
手続き復帰命令出力機構は、第２入力アーク上の値を使用してトークン（結果の値）を生成する。第１入力アーク上のトークンの値として指定されたアークにトークン（戻り先）を置く。
【００３６】
合流命令出力機構は、各入力アーク上のトークンの値より得られる経路断片識別子に対し、共通の先祖となる値を求める。求めた経路断片識別子を値とするトークンを生成し、このトークンを出力アーク上へ置く。
【００３７】
図９に実行例を示す。図中で黒丸はトークン、白丸ノードは演算ノード、白丸に十字のノードは分配ノードを表す。また、斜線ノードは実行フラグの立ったノードを表す。以下に実行例の動作説明を示す。
１．開始ノードより経路断片識別子ｃ1 なる値を持つトークンを出力する。関数呼び出しノードでは、値がｃ1 であるトークンを手続き開始ノードの入力アーク上へ置く（図９（ｃ））。
２．関数の検証が終了し、手続き復帰ノードが発火した場合には、手続き復帰ノードの第１入力アークに置かれたトークンの値より復帰先アークを求め、求めたアーク上にトークンを置く（図９（ｄ））。
３．分岐ノードでは入力アーク上のトークンの値より得られる経路断片識別子
【外２】
0003635667.tif 000004
路断片識別子を求める。次に求めた経路断片識別子をトークンの値として出力する（図９（ｅ））。
【００３８】
図９のように、全ての入力アーク上にトークンが揃った場合に、ノードに実行フラグを立てて、出力アーク上にトークンを置く。トークンが終了ノードに至った後（図９（ｆ）の時）、グラフ上に表１の検出条件を持つトークンやノードは存在しないため、異常のないプログラムと言える。
【００３９】
【発明が解決しようとする課題】
環境依存発火機能・環境依存分配機能を有するデータフロー計算機で実行されるプログラムに従来の検証装置を適用した場合、異常が検出されなくとも、ノードへの環境レベルの付け方によっては、ある実行環境レベルでは、可到達性異常、伝播異常、全実行性異常、合流異常が生じる場合がある。
【００４０】
例えば、図１０のように環境レベルを配したプログラムを考える。ここで、白丸のノードは演算ノードを表し、白丸に十字のノードは分配ノードを表す。各ノードの左側の数値はノード番号を表し、右側の数値は環境レベルを表す。実行環境レベル１，２のトークンを用いた場合には、図１０（ａ），（ｂ），（ｃ）のどのプログラムにおいても正常に動作する。しかし、実行環境レベル３のトークンが伝播する場合には、図１０（ａ）〜（ｃ）の各プログラムでそれぞれ以下に示す問題が発生する。
【００４１】
図１０（ａ）では、ノード１からノード１０まで、実行環境レベル３のトークンが伝播する経路がある。しかし、ノード６は環境レベルが３であるにもかかわらず、実行環境レベル３のトークンは到着しないため、実行は行われない。
【００４２】
図１０（ｂ）では、ノード１からノード１０まで、実行環境レベル３のトークンが伝播する経路は存在する。しかし、ノード４に到達した実行環境レベル３のトークンは、これより先のノードを実行できない。このため、このトークンはノード１０に到達しない。
【００４３】
図１０（ｃ）では、ノード７に到達した実行環境レベル３のトークンは、これより先のノードを実行できない。このため、トークンはノード１０に到達しない。
【００４４】
実行環境レベル別に実行を行った場合には、上述した誤りが発生する可能性がある。しかし、従来の検証装置による検証では、グラフの構造による可到達性異常と伝播異常と全実行性異常と合流異常を検出するだけであり、任意の環境レベルに対する可到達性異常と伝播異常と全実行性異常と合流異常の検出は行っていない。このため上述の誤りを検出できない。
【００４５】
また図１１にあるように、自関数の再帰呼び出しにより停止しない構造が考えられるが、従来の検証法ではこのような構造を検出できず、また、検証のための実行が停止しない。この異常を再帰異常と呼ぶ。
【００４６】
この問題を解決するために、与えられた実行環境レベルで実行されるべきノードが全て実行され、かつ、プログラムの開始ノードから終了ノードまでトークンが伝播することを、全ての実行環境レベルにおいて検出する必要がある。
【００４７】
本発明は、上記に鑑みてなされたもで、その目的とするところは、環境依存発火機能と環境依存分配機能を有するデータフロー計算機で実行される再帰関数を含むプログラムにおいて全ての実行環境レベルについて可到達性異常と伝播異常と全実行性異常と合流異常と、関数の再帰呼び出しによる再帰異常を検出するデータフローグラフ検証装置を提供することにある。
【００４８】
【課題を解決するための手段】
上記目的を達成するため、請求項１記載の発明は、環境レベルを付与したノードをアークで結合したデータフローグラフをプログラムとし、実行環境レベルを付与したトークンをアークを経由してノード上を伝播させ、環境依存発火機能と環境依存分配機能により発火制御するプログラム内のトークンの伝播上の正常性を検証するデータフローグラフ検証装置であって、トークンが伝播してきた経路上のノードに着目して、トークンがノードに入力できるかどうかの状態を示す入力状態を、当該トークンが伝播してきた経路上のノードに対するトークン伝播とエラー発生の状況に基づいて実行環境レベル毎に求める入力状態演算を行い、ノードが発火するかどうかの状態を示す到達状態を、入力状態および当該ノードの環境レベルに基づいて実行環境レベル毎に求める到達状態演算を行い、トークンが出力できるかどうかの状態を示す出力状態を、到達状態および出力アーク先ノードの環境レベルに基づいて実行環境レベル毎に求める出力状態演算を行う状態演算機能部を有することを特徴とする。
請求項２記載の発明は、請求項１記載の発明において、ノードが発火した際に、当該ノードへ入力するトークンに付与された関数の実行停止性に基づくと共に、前記ノードへ入力するトークンに呼び出し先関数が付与されている場合には当該呼び出し先関数の実行停止性にも基づいて、関数の相互呼び出しによる実行停止性を表す状態をノード種別に応じて求める有限再帰判別演算を行う有限再帰判別演算機能部を更に有することを特徴とする。
【００４９】
【作用】
本発明のデータフローグラフ検証装置では、トークンが伝播してきた経路上のノードに着目して、入力状態、到達状態、出力状態の各々をすべての入力アークの実行環境レベル毎の状態、入力状態とノードの環境レベル、到達状態と出力アーク先ノードの環境レベルの各々に基づいて実行環境レベル毎に状態演算し、呼び出し先関数の出力状態を引き継ぎ、関数内のノードを状態演算する。
【００５０】
【実施例】
以下、図面を用いて本発明の実施例を説明する。
【００５１】
なお、実施例を説明する前に、まず本発明のデータフローグラフ検証装置の基本概念について説明する。本検証装置は、任意の環境レベルに対する可到達性異常、伝播異常、全実行性異常、合流異常、再帰異常を検出するための手段１、および関数の再帰呼び出しによる停止しない状態を検出するための手段２を有する。
【００５２】
まず、手段１について説明し、その中の状態演算について説明する。
【００５３】
実行環境レベルは数値（ここでは自然数を用いる）で表す。数値が大きいほどレベルが高いことを意味する。ここで、ある実行環境レベルにおけるトークン伝播の状況を、その実行環境レベルの状態といい、その値を次の様に表す。
Ｔ：通常のプログラム実行時にトークンが伝播してくる可能性がある。
Ｎ：通常のプログラム実行時にトークンは伝播してこない。
Ｒ：通常のプログラム実行時に、発火出来ない。もしくは、トークンを出力出来ない状態が発生している。
Ｅ：通常のプログラム実行時に実行されない状態が発生している。
【００５４】
【外３】
0003635667.tif 000005
ｓ2 なる演算を次の様に定義する。
【００５５】
【数１】
0003635667.tif 000006
また、レベルｌの実行環境レベルの状態を第ｌ要素とした、全ての実行環境レベルの状態を表す一次元ベクトルを状態ベクトルと呼ぶ。このとき状態ベクトルＳ1 ＝（ｓ11，ｓ12，…，ｓ1n），Ｓ2 ＝（ｓ21，ｓ22，…，ｓ2n）に対して、
【外４】
0003635667.tif 000007
【数２】
0003635667.tif 000008
ノードの第ｊ入力アーク上のトークンの値をＴj ＝（ｔj1，ｔj2，…，ｔjn）とする。このとき、Ｔj は状態ベクトルであり、ｔjkは実行環境レベルｋで、そのトークンが伝播してきた経路上のノードに対する、トークン伝播とエラー発生の状況を表している。次式により求まるＩ＝（ｉ1 ，ｉ2 ，…，ｉn ）を入力状態ベクトル、入力状態ベクトルを求める演算を入力状態演算と呼ぶ。入力状態ベクトルの第ｍ要素の値がＴのとき、実行環境レベルｍのトークンが、全ての環境入力アーク上に到達することを示す。
【００５６】
【数３】
0003635667.tif 000009
【００５７】
Ｒ＝（ｒ1 ，ｒ2 ，…，ｒm ，…，ｒn ）を到達状態ベクトル、到達状態ベクトルを求める演算を、到達状態演算と呼ぶ。到達状態ベクトルの第ｍ要素の値がＴのとき、実行環境レベルｍのトークンで、ノードが発火することを示す。なお、ｔａｇはノードの環境レベルである。
【００５８】
【数４】
0003635667.tif 000010
到達状態ベクトルをＲ＝（ｒ1 ，ｒ2 ，…，ｒm ，…，ｒn ）としたとき、第ｊ出力アークに対し、各要素が次式により求まるＯj ＝（ｏj1，ｏj2，…，ｏjm，…，ｏjn）を出力状態ベクトル、出力状態ベクトルを求める演算を、出力状態演算と呼ぶ。出力状態ベクトルの第ｍ要素の値がＴのとき、実行環境レベルｍのトークンを出力できることを示す。なお、ｔａｇout （ｊ）は第ｊ出力アーク先
【外５】
0003635667.tif 000011
ある。
【００５９】
【数５】
0003635667.tif 000012
図１２に示す状態演算機能により、各実行環境レベルにおける可到達性異常、伝播異常、全実行性異常、合流異常、再帰異常を検出する。図中で実線矢印は制御の流れ、点線矢印はデータの流れを表す。データフローグラフの各ノードに対してＲフラグ、Ｅフラグと呼ぶ二つの一次元ベクトルを持たせる。これらのフラグの第ｍ要素は、実行環境レベルｍでの異常発生状況を表す。Ｒフラグの要素の値が１の時、その要素に対応する実行環境レベルで、そのノードが発火出来ないか、トークンを出力できないことを意味する。Ｅフラグの要素の値が１の時、その要素に対応する実行環境レベルでそのノードの入力アーク上にトークンが到達しないため、そのノードが実行されないことを意味する。
【００６０】
これらのフラグの要素の初期値は、０である。以下に、状態演算機能の各機構について述べる。
【００６１】
値読み取り機構は、ノード内に取り込まれたトークンより値を読み取り、その値をデータとして入力状態演算機構へ送る。
【００６２】
出力アーク判定機構は、出力アーク先にあるノードの環境レベルをデータとして、出力状態演算機構へ送る。
【００６３】
入力状態演算機構は、値読み取り機構よりトークンの値を受け取り、また、ｌｉｎｅＡよりノード種別を受け取り、入力状態演算を行う。演算結果をデータとして到達状態演算機構に送る。入力トークンの値にＲが含まれず、式（７）の結果にＲとなる要素がある場合には、その要素に対応するＲフラグの値を１とする。
【００６４】
到達状態演算機構は、入力状態演算機構より入力状態演算の結果を受け取り、到達状態演算を行う。演算結果をデータとして出力状態演算機構に送る。入力状態演算機構より受け取った値の要素がＥもしくはＮであり、演算によりＲが得られた要素がある場合には、その要素に対応するＲフラグの値を１とする。また、入力状態演算機構より受け取った値の要素がＮまたはＥであり、演算によりＥが得られた要素がある場合には、その要素に対応するＥフラグの値を１とする。
【００６５】
出力状態演算機構は、到達状態演算機構より到達状態演算の結果を受け取り、ｌｉｎｅＡよりノード種別を受け取り、また、出力アーク判定機構より出力アーク先にあるノードの環境レベルを受け取り出力状態演算を行う。演算結果をデータとして出力する。演算によりＲが得られた要素がある場合には、その要素に対応するＲフラグの値を１とする。
【００６６】
状態演算機能を有する実行経路検証系では、データフローグラフの全てのノードに対して以下に示す方式で処理を施すことにより検証のための実行を行う。
【００６７】
１．全ての入力アーク上にトークンが到達するまで待機させる。
２．入力アーク上にトークンが揃った後、従来技術と同じ発火規則に添ってノードの発火を行う。このとき、ノードの実行フラグを１にし、入力アーク上のトークンをノード内に取り込む。
３．状態演算機能は各機構を動作させる。
４．出力状態演算機構からの出力と、ノード内に取り込んだトークンの経路断片識別子と有限再帰判別ベクトルより新たにトークンを生成する。新たに生成したトークンを出力アーク上に出力する。ノード内のトークンを消去する。
【００６８】
次に、手段２について説明する。
【００６９】
有限再帰判別ベクトルは、関数の相互呼び出しによる実行停止性を表す論理値を要素として持つ一次元ベクトルであり、要素の値が１のとき呼び出しが停止することを表し、０のとき停止しないことを表す。なお、プログラムが使用している関数名とこの有限再帰判別ベクトルと実行経路検証系より得られた関数の状態ベクトルを対応付ける表を関数表と呼ぶ。
【００７０】
実行経路検証系で検証を行い、ノードが発火した際に、各ノードごとに以下に示す有限再帰判別演算を行う。
【００７１】
合流ノードに対しては、各トークンの値より得た有限再帰判別ベクトルの各要素について論理和を求める。
【００７２】
手続き呼び出しノードに対しては、各トークンの値として与えた有限再帰判別ベクトルの各要素について論理積を求める。さらに求めた有限再帰判別ベクトルと関数用の呼び出し先関数の有限再帰判別ベクトルの各要素について論理積を求める。
【００７３】
その他のノードに対しては、各要素について論理積を求める。
【００７４】
再帰関数検証系では、実行経路検証系が検証のための実行を行う際に以下のように動作する。
１．プログラムで使用している関数の中で検証を行う関数を求め、その検証対象関数名と検証対象関数の有限再帰判別ベクトルと全ての要素がＴの状態ベクトルを実行経路検証系に送る。
２．実行経路検証系の状態演算機能の実行後に、有限再帰判別演算を行う。  ３．実行経路検証系より関数に対する検証のための実行が終了した信号を受け取った際には、検証を行った関数の状態を調べ、関数表の中でその関数の項を更新する。プログラムに対する検証のための実行の終了判定を行い、終了しない場合は１に戻る。
【００７５】
上述したように、状態演算機能を有するデータ駆動実行型検証装置により、検証のための実行を行い、実行中のノードがなくなった時点で、もしくは終了判定機能により終了することを決定した時点で検証のための実行を終了する。このとき、トークンの位置と値、およびノードのフラグの値を調べることにより可到達異常、伝播異常、全実行異常、合流異常を知ることができ、また有限再帰判別ベクトルの値を調べることにより、関数の相互再帰呼び出しによる再帰異常を知ることができる。
【００７６】
次に、本発明の実施例について詳細に説明する。
【００７７】
なお、本実施例では、発火規則は次のように定める。関数復帰ノードでは、第２入力アーク上にトークンが到達した際に発火する。他のノードは従来技術と同様である。
【００７８】
図１３は、状態演算機能を有する本実施例の検証装置の構成を示すブロック図である。図１３において、実線の矢印は制御の流れを表し、点線の矢印はデータの流れを表す。
【００７９】
図１３に示す本検証装置は、再帰関数検証系１および実行経路検証系２を有する。再帰関数検証系１は、関数表作成機能部１１、検証関数更新機能部１２、関数表更新機能部１３、終了判定機能部１４、有限再帰判別演算機能部１５から構成されている。実行経路検証系２は、色付きトークン到達監視機能部２１、トークン入力機能部２２、ノード分類機能部２３、状態演算機能部２４、トークン出力機能Ｂ部２５、関数実行終了判定機能部２６から構成されている。
【００８０】
まず、再帰関数検証系１の各構成要素について説明する。
【００８１】
関数表作成機能部１１は、検証対象プログラムで使用する関数名と全ての要素の値が０の有限再帰判別ベクトルと全ての要素がＮである状態ベクトルとの対応を表す関数表を作成する。作成した関数表を記憶装置内の関数表および既関数表として登録する。また、記憶装置内の検証関数名を空にする。最後に検証関数更新機能部１２に制御を移行する。
【００８２】
検証関数更新機能部１２は、記憶装置より関数表と検証関数名を得る。次に検証関数名よりまだ検証していない関数を求め、その関数の全てのノードの実行フラグ、Ｒフラグ、Ｅフラグを初期化し、トークンを消去する。関数の開始ノード（もしくは、手続き開始ノードの入力アーク上）に対して、ノードに与えられた環境レベルのなかで最大の値と対応する要素までをＴとし、それ以上をＮとした状態ベクトルと要素の値が１の有限再帰判別ベクトル、そして経路断片識別子を値とするトークンを置き、関数名を検証関数名に登録する。全ての関数に対する検証が終了した場合は終了判定機能部１４に制御を移行する。
【００８３】
関数表更新機能部１３は、終了ノードにトークンが存在する関数について、そのトークンの値から得られる有限再帰判別ベクトルの値と状態ベクトルを、記憶装置内関数表の対応する関数の有限再帰判別ベクトルと状態ベクトルに代入する。検証関数更新機能部１２に制御を移行する。
【００８４】
終了判定機能部１４は、記憶装置内の関数表と既関数表とを比較し、等しい場合は検証のための実行を終了する。異なる場合は、記憶装置内の関数表を既関数表として記憶装置に登録し、記憶装置内の検証関数名を空にする。制御を検証関数更新機能部１２に移行する。
【００８５】
有限再帰判別演算機能部１５は、状態演算機能よりノード種別を受け取り有限再帰判別演算を行う。演算結果とノード種別をトークン出力機構に送り、制御をトークン出力機能Ｂ部２５に移す。
【００８６】
次に、実行経路検証系２の各構成要素について説明する。
【００８７】
トークン到達監視機能部２１、トークン入力機能部２２、ノード分類機能部２３は従来技術のものと同じであり、次の通りである。
【００８８】
トークン到達監視機能部２１は、全ての入力アーク上にトークンが揃ったノードを検出し、発火規則を基に発火させる。ノードが発火した場合は、ノードの実行フラグを１にして制御をトークン入力機能に移す。
【００８９】
トークン入力機能部２２は、入力アーク上のトークンを、入力アークの順に並べてノード内に取り込む。
【００９０】
ノード分類機能部２３は、発火したノードを演算命令、分配命令、分岐命令、手続き呼び出し命令、手続き開始命令、手続き復帰命令、合流命令に分類し、そのノード種別をトークン出力機能に送る。
【００９１】
状態演算機能部２４は、ノード分類機能部２３よりノード種別を受け取り状態演算を行う。演算結果とノード種別を有限再帰判別演算機能部１５に送り、制御を有限再帰判別演算機能部１５に移す。
【００９２】
トークン出力機能Ｂ部２５の詳細構成図を図１４に示す。図中で、実線矢印は制御の流れを、点線矢印はデータの流れを表す。命令デコード機構は、ｌｉｎｅＢに流れてきたデータにより、ノード種別を知る。次に、対応する出力機構に対して、ｌｉｎｅＡに流れてきた状態ベクトルと、ｌｉｎｅＣに流れてきた有限再帰判別ベクトルをデータとして対応する出力機構に送り、制御を移行する。トークン消去機構はノード内に取り込んだトークンを消去する。各出力機構は命令の種類に応じて以下の様に動作する。以降トークンとはノード内に取り込んだトークンのことを指す。
【００９３】
演算命令出力機構は、入力アーク上に到達したトークンの値の経路断片識別子と、命令デコード機構より受け取ったデータを値としてトークンを生成し、出力アーク上に置く。
【００９４】
分配命令出力機構は、トークンの値の経路断片識別子と命令デコード機構より受け取ったデータを値とするトークンを生成し、全ての出力アーク上へ置く。
【００９５】
分岐命令出力機構は、第２入力アークに到達したトークンの値の経路断片識別子に対する孫値を２つ求める。求めた２つの経路断片識別子と命令デコード機構より受け取ったデータを値とする２つのトークンを生成する。新たに生成したトークンをそれぞれの出力アーク上へ置く。
【００９６】
手続き呼び出し命令出力機構は、命令デコード機構より受け取ったデータの有限再帰判別ベクトルと、関数表より求めた呼び出し先関数の有限再帰判別ベクトルと、各要素ごとに論理積を求める。命令デコード機構より受け取ったデータの状態ベクトルと、呼び出し先関数の状態ベクトルを関数表より求めて、式（５）により新たな状態ベクトルを求める。命令デコード機構より受け取った状態ベクトルの要素にＲが含まれず、演算結果にＲの要素がある場合には、その要素に対応するＲフラグの値を１とする。最終的に得られた有限再帰判別ベクトルと状態ベクトル、第２入力アーク上に到達したトークンの値の経路断片識別子を値とするトークンを生成する。生成したトークンを出力アーク上に置く。
【００９７】
手続き開始命令出力機構は、トークンの値の経路断片識別子と命令デコード機構より受け取ったデータを値とするトークンを生成し、出力アーク上へ置く。
【００９８】
手続き復帰命令出力機構は、動作しない。
【００９９】
合流命令出力機構は、各トークンの値より得られる経路断片識別子に対し、共通の先祖となる値を求める。求めた経路断片識別子と命令デコード機構より受け取ったデータを値とするトークンを生成し、このトークンを出力アーク上へ置く。
【０１００】
関数実行終了判定機能部２６は、検証実行中の関数の終了ノードのみにトークンがある場合、関数表更新機能部１３に制御を移行する。それ以外の場合には色付きトークン到達監視機能部２１へ制御を移行する。
【０１０１】
次に、演算命令、分配命令、分岐命令、手続き呼び出し命令、合流命令の実行例を示す。以降で用いる図では、点線の白丸ノードは演算ノードもしくは各制御ノード、「●（（…），ａ，ｂ）」は状態ベクトル（…）と経路断片識別子ａと有限再帰判別ベクトルｂを値として持つトークン、右下側のベクトルは、Ｒフラグ、左下側のベクトルはＥフラグを表す。ノードの環境レベルを右上に示す。
【０１０２】
図１５に演算命令の処理例を示す。図中で白丸は演算ノードを表す。演算命令では以下のような処理を行う。
（１）トークンが、演算ノードの全ての入力アーク上に揃い、発火規則にも合致するため、演算ノードは発火する。
（２）入力状態演算、到達状態演算、出力状態演算を行う。出力状態演算で求めた到達状態ベクトルの第４要素がＲとなったので、Ｒフラグの第４要素の値を１にする。
（３）ノード内に取り込んだ各トークンの値の有限再帰判別ベクトルにより有限再帰判別演算を行い、有限再帰判別ベクトルの値を更新する。図の場合には有限再帰判別ベクトル（１１１１１）と出力状態ベクトルと経路断片識別子ｃ1 を値とするトークンを出力アーク上に置く。
【０１０３】
図１６に分配命令の実行例を示す。図中で白丸に十字のノードは分配ノードを示す。分配命令では以下のような処理を行う。
（１）トークンが分配ノードの入力アーク上に到達し、発火規則にも合致するため、分配ノードは発火する。
（２）入力状態演算、到達状態演算、出力状態演算を行う。出力状態演算で求めた出力状態ベクトルの第４要素がＲとなったので、Ｒフラグの第４要素の値を１とする。
（３）ノード内に取り込んだ各トークンの値の有限再帰判別ベクトルにより有限再帰判別演算を行い、有限再帰判別ベクトルの値を更新する。図の場合には有限再帰判別ベクトル（１１１１１）と出力状態ベクトルと経路断片識別子ｃ1 を値とするトークンを出力アーク上に置く。
【０１０４】
図１７に分岐命令の処理例を示す。図中で楕円型のノードは分岐ノードを示す。分岐命令では以下のように処理を行う。
（１）トークンが分岐ノードの入力アーク上に到達し、発火規則にも合致するため、分岐ノードは発火を行う。
（２）入力状態演算、到達状態演算、出力状態演算を行う。到達状態演算で求めた到達状態ベクトルの第５要素がＥとなったので、Ｅフラグの第５要素の値を１にする。また、出力状態演算の際に、求めた出力状態レベルの第３、第４要素がＲと求まったので、Ｒフラグの第３、第４要素の値を１にする。
（３）ノード内に取り込んだ各トークンの値の有限再帰判別ベクトルにより有限再帰判別演算を行い、有限再帰判別ベクトルの値を更新する。経路断片識別子ｃ1 の孫値となる値（ｃ11，ｃ12）を求める。図の場合には、真側の出力アーク上に真側の出力状態ベクトルと有限再帰判別ベクトル（１１１１１）と経路断片識別子ｃ11を、偽側の出力アーク上に偽側の出力状態ベクトルと有限再帰判別ベクトル（１１１１１）と経路断片識別子ｃ12を値とするトークンを置く。
【０１０５】
図１８に手続き呼び出し命令の処理例を示す。図中で長方形型のノードは手続き呼び出しノードを示す。手続き呼び出し命令では以下のように処理を行う。
（１）トークンが手続き呼び出しノードの入力アーク上に到達し、発火規則にも合致するため、手続き呼び出しノードは発火する。
（２）入力状態演算、到達状態演算、出力状態演算を行う。入力状態演算で求めた入力状態ベクトルの第４要素が新たにＲとなったので、Ｒフラグの第４要素の値を１にする。求めた状態ベクトルと関数表より得た状態ベクトルとを式（５）で演算を行い、状態ベクトルを求める。
（３）ノード内に取り込んだ各トークンの値の有限再帰判別ベクトルにより有限再帰判別演算を行い、有限再帰判別ベクトルの値を更新する。図の場合には有限再帰判別ベクトル（００１１１）と経路断片識別子ｃ1 と出力状態ベクトルを値とするトークンを出力アーク上に置く。
【０１０６】
図１９に合流命令の処理例を示す。図中で逆三角形のノードは合流ノードを示す。合流命令では以下のように処理を行う。
（１）トークンがノード３の入力アーク上に到達し、発火規則にも合致するため、ノード３は発火を行う。
（２）ノード３において、入力状態演算、到達状態演算、出力状態演算を行う。
（３）ノード内に取り込んだ各トークンの値の有限再帰判別ベクトルにより有限再帰判別演算を行い、有限再帰判別ベクトルの値を更新する。図の場合には有限再帰判別ベクトル（１１１１１）と経路断片識別子ｃ1 と出力状態ベクトルを値とするトークンを出力アーク上に置く。
【０１０７】
図２０に実行例を示す。図中で白丸ノードは演算ノード、楕円のノードは分岐ノード、白丸に十字のノードは分配ノード、長方形のノードは関数呼び出しノードを表す。網掛けのノードは実行フラグの立ったノード、ノードの右上の数字は環境レベル、左下のベクトルはＥフラグを、右下のベクトルはＲフラグを表す（図では更新されたフラグのみ記す）。ノードに与えられた環境レベルの中で、最大となるものは３であるため、全ての要素が”Ｔ”である３要素の状態ベクトルと、”ｃ”なる経路断片識別子と全ての要素の値が１の有限再帰判別ベクトルを値として持つトークンを、開始ノードにおいて処理を始める。
【０１０８】
１．図２０（１）の関数呼び出しノードが発火する際に、入力アーク上には（（ＴＴＮ），ｃ，（１１１））なる値を持つトークンが伝播してくる。発火した後には、出力状態ベクトルは（ＴＴＮ）と求まる。関数表の呼び出し先関数ｆの項の状態ベクトル（ＮＮＮ）と求めた出力状態ベクトルとで式（５）の演算を行うと（ＲＲＮ）が求まる。新たに第１，２要素がＲと求まったのでＲベクトルの第１，２要素を１にする。また、入力トークンの有限再帰判別ベクトルの論理積により（１１１）が求まる。この有限再帰判別ベクトルと関数表の有限再帰判別ベクトルとの論理積により（０００）が求まる。従って、関数呼び出し命令の出力アーク上に（（ＲＲＮ），ｃ，（０００））なる値を持つトークンを出力する（図２０（１））。
２．図２０（２）の分岐ノードが発火する際に、入力アーク上にはそれぞれ（（ＲＲＴ），ｃ，（０００）），（（ＲＲＮ），ｃ，（０００））なる値を持つトークンが伝播してくる。発火した後には出力状態ベクトルは（ＲＲＲ）と求まる。新たに第３要素がＲと求まったのでＲベクトルの第３要素を１にする。有限
【外６】
0003635667.tif 000013
なる経路断片識別子を求める。従って、出力アーク上に（（ＲＲＲ），ｃ1 ，（０００）），（（ＲＲＲ），ｃ2 ，（０００））なる値を持つトークンを出力する。
３．関数に対する検証のための実行が終了したあと、終了ノードのトークンの有限再帰判別ベクトルと状態ベクトルを関数表に代入する（図２０（３））。
４．未検証の関数に対して検証のための実行を行い、実行が終了したあと、終了ノードのトークンの有限再帰判別ベクトルと状態ベクトルを関数表に代入する（図２０（４）〜（５））。
５．全ての関数の実行が終了したあと、関数表が更新されているか確認し、更新されている場合は、再び検証のための実行を行う。
６．図２０（６）の関数呼び出しノードが発火する際に、入力アーク上には（（ＴＴＮ），ｃ，（１１１））なる値を持つトークンが伝播してくる。発火した後に、トークンの有限再帰判別ベクトルの論理積により（１１１）が求まる。この有限再帰判別ベクトルと関数表の有限再帰判別ベクトルとの論理積により（１１１）が求まる。出力状態ベクトルと関数表の状態ベクトルにより（ＴＴＮ）なる状態ベクトルが求まる。従ってトークンの値を（（ＴＴＮ），ｃ1 ，（１１１））として出力する。
７．図２０（７）では、分岐ノードの入力状態演算の際にトークンの値の状態ベクトルの第３要素が新たにＲと求まったのでＲベクトルの第３要素を１にする。
８．関数に対する検証のための実行が終了したあと、終了ノードのトークンの有限再帰判別ベクトルを関数表の有限再帰判別ベクトルに代入する（図２０（８））。
９．全ての関数の実行が終了したあと、関数表が更新されているか確認し、更新されている場合は、再び検証のための実行を行う（図２０（１０））。
１０．関数表に変化がなくなった時点で検証のための実行を終える。この時に、後述の表２で述べる検出条件により、異常の存在を確かめる。
以上説明したように、状態演算機能を有するデータ駆動実行型検証装置により、検証対象とするプログラムグラフを実行する。再帰関数検証系の終了判定機能により終了判定がなされた時点で、もしくは、実行経路検証系で検証中に実行中のノードがなくなった時点で、検証のための実行を終了する。このとき、トークンの位置と値、および、ノードのフラグの値を調べることにより表２に示すように各異常の発生を検出できる。
【０１０９】
【表２】
0003635667.tif 000014
【０１１０】
【発明の効果】
以上説明したように、本発明によれば、状態演算機能を有するデータ駆動実行型検証装置により検証のための実行を行い、実行中のノードがなくなった時点で、または終了判定機能により終了することを決定した時点で検証のための実行を終了し、この時トークンの位置と値、およびノードのフラグの値を調べることにより可到達異常、伝播異常、全実行異常、合流異常を検出することができ、また有限再帰判別ベクトルの値を調べることにより関数の相互再帰呼び出しによる再帰異常を検出することができる。
【図面の簡単な説明】
【図１】異常のあるプログラムの例および検出できる異常の例を示す図である。
【図２】色付きトークンによる実行例を示す図である。
【図３】分岐ノードで色を与える際の問題点を示す説明図である。
【図４】扱う構造（繰り返しの表現）を示す図である。
【図５】扱う構造（分岐と合流）を示す図である。
【図６】経路断片識別子の例を示す図である。
【図７】従来の色付きトークンによるデータ駆動実行型検証装置の構成を示すブロック図である。
【図８】図７の検証装置に使用されているトークン出力機能Ａの詳細な構成を示すブロック図である。
【図９】従来のデータ駆動実行による検証例を示す図である。
【図１０】不完全な実行を行うグラフの例を示す図である。
【図１１】自関数の再帰呼出状態を示す図である。
【図１２】状態演算機能を示す図である。
【図１３】本発明の一実施例に係わる状態演算機能を有する検証装置の構成を示すブロック図である。
【図１４】図１３の検証装置に使用されているトークン出力機能Ｂ部の構成を示すブロック図である。
【図１５】演算命令の処理例を示す図である。
【図１６】分配命令の処理例を示す図である。
【図１７】分岐命令の処理例を示す図である。
【図１８】手続き呼び出し命令の処理例を示す図である。
【図１９】合流命令の処理例を示す図である。
【図２０】状態演算機能を用いた検証例を示す図である。
【符号の説明】
１  再帰関数検証系
２  実行経路検証系
１１  関数表作成機能部
１２  検証関数更新機能部
１３  関数表更新機能部
１４  終了判定機能部
１５  有限再帰判別演算機能部
２１  色付きトークン到達監視機能部
２２  トークン入力機能部
２３  ノード分類機能部
２４  状態演算機能部
２５  トークン出力機能Ｂ部
２６  関数実行終了判定機能部
【図１】
0003635667.tif 000015
【図２】
0003635667.tif 000016
【図３】
0003635667.tif 000017
【図４】
0003635667.tif 000018
【図５】
0003635667.tif 000019
【図６】
0003635667.tif 000020
【図７】
0003635667.tif 000021
【図８】
0003635667.tif 000022
【図９】
0003635667.tif 000023
【図１０】
0003635667.tif 000024
【図１１】
0003635667.tif 000025
【図１２】
0003635667.tif 000026
【図１３】
0003635667.tif 000027
【図１４】
0003635667.tif 000028
【図１５】
0003635667.tif 000029
【図１６】
0003635667.tif 000030
【図１７】
0003635667.tif 000031
【図１８】
0003635667.tif 000032
【図１９】
0003635667.tif 000033
【図２０】
0003635667.tif 000034