月: 2010年8月

変数間の循環参照関係を調べる方法を考えてみました。

プログラミング言語とまでいかなくても、簡単なスクリプトや設定ファイルの中で、変数の初期化に、定数式だけでなく他の変数の値が参照できるという文法の場合を想定しています。

ぶっちゃけ、ここで話題にしているTECSのCDLでも、セルの変数の初期値に、セルの属性の初期値を参照できるという文法になっているため、CDLを解釈するプログラムの実装時には気をつける必要があるというのが、今回の考察の動機です。

注）現在公開されているTECSのCDLの文法では、ここで問題にしている循環参照は起こりません。この記事はあくまでも、解釈するプログラムの実装についての考察です。

ここでN個の変数をv1,・・,vnとします。
初期化の対象となる変数をvxとするとし、初期化を記号”=”で表すと、

vx = (v1,・・,vnを含む定数式)

となります。
これは一般的な関係を表すものであり、まったく他の変数を参照しない場合も含みます。
上記の右辺において、参照しない変数に対しては係数0を掛けているものとします。

ここで問題にしているのは、変数が１回でも参照されているか否かです。
具体的に上記の右辺でv1が何回加減乗除されようと、式にあらわ得るv1の個数ではなく、その個数ではなく、あくまでも式に変数v1が現るか、現れないかだけです。

N個変数それぞれについて、初期化を表すと、以下のようになります。

v1 = (v1,・・,vnを含む定数式)
・
・
vn = (v1,・・,vnを含む定数式)

ここで、変数vxの初期値を求めるために、変数vxの右辺に現れる他の変数をその変数の右辺で置き換えます。
右辺が全て定数式になれば、変数vxの初期値が確定します。

しかしここで変数の参照が循環していると、いつまでたっても置き換えが終わりません。
極端な話、

v1 = v1

のように指定された場合です。

さらに、以下のようなたすき掛けの参照関係で循環していることを見つけるのは簡単ではありません。

v1 = v2
v2 = v3
v3 = v1

このような循環した参照関係が存在していなければ、置き換えを実行して初期値を求めことが出来ます。
逆に循環した参照関係が存在していれば、エラーとして置き換えを実行せずに済みます。

以下は私が考えた方法です。

v1 = (v1,・・,vnを含む定数式)
・
・
vn = (v1,・・,vnを含む定数式)

から、左辺の変数を集めてベクトルと見なします。

v = (v1,・・,vn)

各初期化式の右辺で変数が参照されていれば1、参照されていなければ0とする行列Bを用いると、

v = B * v

となります。
ここで、左辺のベクトルをv’として区別します。

v’ = B * v

これは、初期化式を素直に表したものですが、置き換えすることは、v’からvを求めることになりますので、行列Bの転置行列をAとして、

v = A * v’

とします。

v1 = (1,0,・・,0,0)
v2 = (0,1,・・,0,0)
・
・
vn = (0,0,・・,0,1)

つまり、ベクトルvは各変数を表すベクトルが基底ベクトルになります。

A * v’は、変数xがどの変数を（自分自身も含めて）参照しているかを示すベクトルになります。
つまり、上記で言う（１回の）置き換えを表しています。
A^2(行列Aの２乗）は、２回目の置き換えを表しています。

A * v’
A^2 * v’
・
・
A^n * v’

ベクトル(A^x * v1)が、変数v1への参照を含んでいるかは、(A^x * v1)とv1の内積の値により分かります。
内積が0であれば、参照を含んでいません。
逆に内積が0でなければ、参照を含んでいます。

以上をまとめると、以下のようになります。

・行列Aは成分が0か1のどちらかである非負行列です。
・行列Aは、変数の参照関係に基づく1回の置き換えを表します。
・各変数を表すベクトルは、基底ベクトルである。
・x回目の置き換え結果を表すベクトル(A * vn’)とvn’の内積が0であれば、x回目の置き換えは、変数vnへの参照を含みません。

行列Aの対角成分が0であれば、上記の内積は必ず0になります。
行列Aの性質より、行列の対角要素の和であるトレース(trace)が0であれば、どの基底ベクトルに対しても0になります。

従って、行列Aの1乗からn乗までを求め、それぞれのトレース(trace)が0であれば、変数間に循環参照は存在しないといえます。

逆にいえば、トレース(trace)が0でない場合が見つかれば、その時点で循環参照が存在するといえます。

また、行列の性質から、A^xが零行列になれば、A^(x+1)からA^nも零行列になるため、零行列が得られた時点で打ち切っても構いません。

参考文献

「線形代数的グラフ理論」　竹中淑子　培風館

「プログラミングのための線形代数」　平岡和幸・堀玄共著　オーム社