XMLに戻ろう
道具が十分揃った、とは全然言えないけど、当初の目的であったXMLへのアタックを再開しよう。そう思った理由は:
理由その1:インラインテーブル問題
昔(20世紀だな)設定したいくつかの問題のなかでも難問だと思っていた「インラインテーブル問題」、ふと思い出して考えたら、10分くらいでアッサリ/スッキリ解けてしまった。これが解けたからOKというわけではないが、2000年くらいに何ヶ月もイライラして七転八倒していたことを思えば、随分と事情は改善した気がする。
<!ENTITY % td_content "ANY"><!ELEMENT table (tr*)>
<!ELEMENT tr (td*)>
<!ELEMENT td (%td_content;)>
<!ENTITY % more_inlines ""><!ELEMENT p (#PCDATA|em %more_inlines;)* >
<!ELEMENT em (#PCDATA)>
この状況で、%td_content;に"p"を入れて、%more_inlines;に"|table"を入れたら何が起きるか? その意味論をキチンと組み立てろ -- これがインラインテーブル問題。
上のDTDと同等な文法モジュールをtable、下のDTDと同等な文法モジュールをparとする。要素集合の集合をE、内容集合の集合をC、Eを混合内容の材料と見なしたものをDとする。EとDは実際は同じだから、その同型をi, EをD(Cと同じ)に埋め込む写像をjとする。
- table:C→E
- par:D→E
- i:E→C
- j:E→D
fを次のように定義する。
- f = par;ΔE;(E × j;table);(E × ΔE);(E × (E × j))
すると、f: D → E×E×D。Dに関してfのトレースをとって、TrD1,E×E(f):1 → E×E。これが結局、インラインテーブルと段落が相互に入れ子になったものを定義する。
一見複雑そうだが、絵算を使えばそうでもない。
理由その2:圏ΩΟ
ωο(omega-omicron)集合を次のように定義する。(A, ≦, 0)がωο集合であるとは:
- (A, ≦)は順序集合。
- 0∈Aは、≦に関して最小元
- 任意のω増加列(可算上昇鎖、厳密には非減少列)は極限(上限)を持つ。
射は、単調でω連続な写像だとする。0が0に写ることは要求しない。この具象圏をΩΟ(Omega-Omicron)と呼ぶ。
この圏は終対象と直積を持ち、これに関してモノイド圏、さらにベキも存在して閉圏である。始対象(空)は存在するが(空を除外する事もある)、直和は定義できない。しかし、A+B+{⊥}やA+B+{⊥}+{T}を直和の代わりに使える。トップ添加、ボトム添加、サイド添加、下方閉ベキ集合などがΩΟ上にモナドとして作用している。
ΩΟの最大の特徴は、任意の自己射が最小不動点を持つことで、これはConway不動点オペレータとなる。したがって、カザネスク/ステファネスク/ハイランド/長谷川の定理からトレースが定義できる。よって、ΩΟは、トレース付きデカルト閉圏。
ΩΟは具体的で非常に使いやすい。これをXML意味論の背景圏(ambient category)に使える。
理由その3:XML指標
当然ながらインスティチューションを使いたいのだが、指標圏の構成が問題になる。指標は順序付き多ソート(ordered many-sorted, order-sorted)指標を使う。ある程度現実を反映させると、典型的XML指標は10個のソートを必要とする(もっと要るかも)。
- Data
- Symbol
- Attribute
- Tag
- Element
- Sequence
- Collection
- Mixture
- Content
- AttributedContent
順序は:
- Symbol⊆Tag
- Tag⊆Element
- Element⊆Sequence
- Data⊆Sequence
- Sequence⊆Content
- Element⊆Collection
- Mixture⊆Content
- Attribute⊆AttributedContent
- Content⊆AttributeedContent
演算(記号)も山のようにある。しかたないのだ!指標Σを選ぶことが、ほぼスキーマ言語を選ぶことになる。
理由その4:まだ足りない、だからこそ
実際は、まだ道具が足りない。が、足りない点を埋めるためにも、出来るところをやってしまおう、ということもある。