2004年02月10日

一次構造・2

 先月24日の続き。

 HTMLのアンカーへのリンクのように、シーケンス中の任意の地点へと飛び込むとき、その地点の状態を構成するにはどうすればいいか。

 シーケンスを頭からレンダリングしてゆく(ただし時間変化はすべて「飛ぶ」で)、というのが答のひとつだった。もうひとつは、「すべてのオブジェクトの取りうる状態が一意に定まるまで、シーケンスを逆方向に解釈していく」である。

 シーケンスを逆方向に解釈する――手続き的プログラミングの常識では離れ業というほかないが、HTMLの「親要素へと次々にトラバースしてゆくだけで、その要素のレンダリングに必要な情報がすべて揃う」という性質を思い出そう。一次構造は階層構造ではないため手順は複雑になるが、本質的には同じことだ。

 まず、メッセージによって生じる状態変化を定義する式について思い出そう。この式のことを、以下ではアクション式と呼ぶ。アクション式は、十分短い時間で計算可能である。また、アクション式はオブジェクト(自他問わず)を参照することができるが、シーケンス中でアクション式の定義が変化することはないので(宣言的!)、シーケンス中のどの地点でも、すべての参照を数え上げることができる。参照先のオブジェクトの取りうる全状態も、シーケンスから独立に定義されている。

 ということは――一次構造においては、アクション式の参照先が取りうる全状態を数え上げることができ、そのすべてについて、アクション式の値を対応させることができる。この対応づけを再帰的に繰り返すことで、シーケンス中の任意の地点におけるオブジェクトの状態を、一意に定めることができる。

 このことを数学的に表現してみよう。

 あるシーケンスに操作されるオブジェクト(総数n個)を O1, O2 ... On と書き、また Ox の取りうる全状態の集合を s(Ox ) と書く。もし Ox が1個の真理値だけを含むなら、s(Ox ) ={T, F } である。s(O1 ) +s(O2 ) ...+s(On ) のことを、U と書く。メッセージはMx と表す。

 シーケンス中の任意の地点 P へと飛び込んだ後、シーケンスの逆方向解釈に着手する前のことを考える。このとき、P の状態はまだ制約されていないので、U であるといえる。

 ここからまず、P のひとつ前のメッセージMP-1 を解釈する。さきほど述べた対応づけというのは、U からの全射写像に等しい。この全射写像を、mP-1 (U )と表す。いまやMP-1 を解釈したことで、P の状態は制約を受け、mP-1 (U )となった。

 メッセージの解釈を、MP-2 , MP-3 ... MP-x と続けていくことにより、P の状態は、mP-xmP-x+1 ... ◦ mP-1 (U )と制約を重ねていく。制約によりP の状態が一意に定まれば、そこでメッセージの解釈を打ち切ることができる。

 が、この理屈はこのままでは、うまくいかない。先頭までさかのぼらなければP の状態が一意に定まらない、つまり逆方向に解釈する意味がないという状態が生じやすい。以下後日。

Posted by hajime at 2004年02月10日 02:33
Comments