この記事で述べる例は、だいぶ前に雑誌に書いたことがあるのだけど、(そ れを読んだ人でも)たぶん誰も憶えてないだろうから、もう一度新たに書いて おく。この例には重要な意味があると思えるので。
平面上の折れ線を次のようなマークアップで記述するとしよう。
<polyline> <point x="0" y="0" /> <point x="1" y="0.5" /> <point x="2.3" y="-3" /> </polyline>
点が1個もなかったり、1個だけの点だと、「折れ線」と呼ぶにはふさわしく ないので、タグ名がpointである要素(以下、point要素)は2つ以上必要だと しておこう。このことを内容モデル(DTD風正規表現)で書くなら次のようになるだ ろう。
(Point, Point, Point*)
ここでPointは、point要素を一般的に表す変数である。
さて、point要素の2つの属性x, yは、データ型としてdecimal(任意の有限小 数)が指定されており、decimal以外は許さないとする。このことを象徴的に 次のように表そう。
Point ::= <point x=decimal y=decimal />
任意の折れ線(ただし、点を2つ以上含む)を、象徴的に次のように書くこと にする。
Polyline ::= <polyline>(Point, Point, Point*)</polyline>
点をちょうど3個だけ含むような折れ線は、次のように定義できるだろう。
Polyline3 ::= <polyline>(Point, Point, Point)</polyline>
細かいことはともかくとして、Polyline3がPolylineのサブセットであること (Polyline3 ⊆ Polyline )はわかるだろう。これは、正規表現(Point, Point, Point)から生成される言語が、正規表現(Point, Point, Point*)で生成 される言語のサブセットであることに対応する。
Pointは平面内の任意の点と考えてよい。次のように定義されるLatticePoint は、格子点(x座標もy座標も整数である点)を表す。
LatticePoint ::= <point x=integer y=integer />
LatticePointがPointのサブセットであること(LatticePoint ⊆ Point)も わかるだろう。これは、パターン<point x=integer y=integer />から生成さ れる言語(空内容要素の集まり)が、パターン<point x=decimal y=decimal />で生成される言語のサブセットであることに対応する。
格子点だけを含むような折れ線は次のように定義される。
LatticePolyline ::= <polyline> (LatticePoint, LatticePoint, LatticePoint*) </polyline>
直感的には、3点しか含まない格子折れ線は、「格子折れ線であり、かつ3点し か含まない折れ線」として定義されるのは明らかだ。よって、次の定義は意味 があるように思える。
LatticePolyline3 ::= LatticePolyline ∧ Polyline3
ここで、記号「∧」は論理のAND、または集合の共通部分だと解釈してよい。
Point、LatticePoint、Polyline、Polyline3、LatticePolyline、 LatticePolyline3などを一種の型だと思うと、次のような階層があると思える。
Point | LatticePoint
Polyline / \ / \ Polyline3 LatticePolyline \ / \ / LatticePolyline3
XMLで表現されたデータの型階層が、いつでもXML言語(構文的集合)の包含 関係で忠実に表現されることは期待できない。だが、この例では、型階層とまっ たく同型な包含関係がXML側にも存在する。運がよければ、このような対応関 係が得られる。
問題: