ものがたり(旧)

atsushieno.hatenablog.com に続く

derivativeアルゴリズムについて(4)

startTagOpenDeriv (OneOrMore p)

(OneOrMore p)は、(Group p (Choice Empty (OneOrMore p)))であると考えれば、他のパターンの定義に吸収することができる。すなわち、(OneOrMore p)にstartTagOpenDerivを適用した結果は、pにstartTagOpenDerivを適用した結果と、「もう空集合でも良い」pの繰り返しとのgroupになる。



startTagOpenDeriv (OneOrMore p) qn =

  applyAfter (flip group (choice (OneOrMore p) Empty))

             (startTagOpenDeriv p qn)

（「pにstartTagOpenDerivを適用した結果」を先頭に付けることには意味がある。compact syntaxで (element x { empty } )+ のような場合では意味が無いが、(element x { empty }, element y { empty })+ のような定義があった場合、xが出現した後に期待されるのは、xではなくてyだからだ。）

ちなみに、OneOrMoreは、ハマる人にはハマるパターンだと思う。(OneOrMore p)は、一度pが出現したら素直に(ZeroOrMore p)となってくれればいいのに、(Choice Empty (OneOrMore p)) という回りくどいパターンになってしまう。これは、ZeroOrMoreというパターンを導入しないためだ。というのは、ZeroOrMoreというパターンを追加してしまうと、オートマトンが無用に複雑になってしまうからだ（オートマトンが複雑になる、というのは、derivativeアルゴリズムを説明するときに、全ての関数について、そのZeroOrMoreをパターンとして追加した場合にHaskellコードが増えてしまうし、他の関数にも影響するかもしれない、ということを考えれば、分かるかもしれない）。

startTagOpenDeriv (Interleave p1 p2)

interleaveは、RELAX NG固有のパターンで、2つのブランチの内容が、順不同で出現できる、というものだ。しかし、これは単純に p1 & p2 を (p1 p2) | (p2 p1) と置き換えられるというものではない。試しに、以下のようなインスタンスをvalidateしてみよう:












#interleave

element root {

  element foo {empty} & ( element bar {empty} )+ }


#choice of group

element root {

  (element foo {empty}, (element bar {empty})+) |

  ((element bar {empty})+, element foo {empty}) }

groupのchoiceにしていると、2つ目のbar要素がエラーとなってしまうことに気付いただろうか? interleaveは、単なるgroupのchoiceの集合を簡略に記述できるようにしたものではないのである。これは「RELAX NG入門」のinterleaveについてのセクションでも「interleaveはSGML DTDの&とは違う」として説明されている。

（ちなみに、XML Schemaのallの内容として出現できるパーティクルがなぜ「0か1しか許されない」のかも、これで理解できたかもしれない。XML SchemaではDTDの&レベルの内容モデルしか許されていないのだ。）

というわけで、startTagOpenDeriv (Interleave p1 p2)の正式な定義は、以下のように「p1で開きタグを処理した結果について、その要素が閉じるまでvalidateした結果と、p2をinterleaveしたもの」または（「」内のp1とp2を入れ替えたもの）ということになる:



startTagOpenDeriv (Interleave p1 p2) qn =

  choice (applyAfter (flip interleave p2) (startTagOpenDeriv p1 qn))

         (applyAfter (interleave p1) (startTagOpenDeriv p2 qn))

「p1で開きタグを処理した結果について、その要素が閉じるまでvalidateした結果」は、startTagOpenDerivが返す（であろう）Afterパターンについて、endTagDeriv (After p1 p2) が（notAllowedでなければ）p1を処理し終えた後のp2である、と考えれば良い。

ちなみに、同じ事が textDeriv (Interleave p1 p2) についても言える。

コラム: RELAX NGの非決定的内容モデル

RELAX NGの面白いところは、非決定的内容モデルも拒絶しないところだ。ただし、RELAX NGも独自の制約をかかえていて、それらがsimple syntax上で定義されているため、ユーザーが普通に記述するfull syntaxからは遠く及ばないところでチェックされて、何だか良く分からないけどエラー扱いされてしまって混乱することもあろう。RELAX NGの文法は簡単だが、複雑なスキーマ定義はやはり多少は難しいのだ。

たとえば、dataやvalueと、textやelementを、同一のgroupに含むことはできない。前者は、どこまでをdataの文字列とし、どこまでをtextの文字列とするかという面倒なvalidationになり、後者はmixed contentをvalidateすることになる）。

attributeのname classがワイルドカード（nsNameやanyName）である場合、そのattributeはoneOrMoreの中に存在しなければならない。oneOrMoreといってもsimple syntax上でのことなので、full syntaxにおいてはzeroOrMoreで良い（普通はanyNameやnsNameな属性を必須とすることは無いであろう）。これは、ワイルドカードで指定するような属性を1つだけ許容するというのでは意味がないためである。（anyNameやnsNameなattributeなら複数の属性を許す、という設計にすると、検証系の実装が無用に複雑になるので、リテラルな文法上は許容しながらもセマンティックな文法で制約するという方が合理的だ。）

After再訪

さて、最後に説明が不足していたAfterまわりを少し補足しておこうと思う。まず復習しておくと、Afterとは、あるパターンに対してstartTagOpenDeriv関数を適用した結果を表すものだ。パターン Element foo { Element bar { Empty }, baz { Empty } } に対して startTagOpenDeriv p (QName "" "foo") を適用した結果は、After (Element (QName "" "bar") Empty) (Element (QName "" "baz") Empty) となる。

実のところ、Afterパターンという直感的でないものを導入せずに、終了タグに該当する(EndElementみたいな）パターンを導入しても、validationは実現できるが、Afterを導入することで、サブパターンを遅延評価することができる、というメリットがある（ようだ）。

Afterパターンが実際に生成されるのは、startTagOpenDerivでapplyAfterが呼び出されたときになる。applyAfterはその最初の引数に「引数を残り1つだけ受け取ると実行できる関数」を受け取る。その関数の多くは2つ引数をとるもので、最初の引数はapplyAfterの評価時に既に渡されている。たとえば (interleave p1) という式があれば、これは「1つの引数をもち、それとp1を引数にinterleave関数を評価する」という関数オブジェクトということになる。

渡される関数の実態は、interleave, group, afterのいずれかのみだが、groupとafterについては、渡される引数の順番が重要なので、このderivativeアルゴリズムでは、Haskellのflipという関数が利用されている。flipは引数の順番をひっくり返すものだ。たとえば



startTagOpenDeriv (After p1 p2) qn =

  applyAfter (flip after p2) (startTagOpenDeriv p1 qn)
Afterを受け取るstartTagOpenDerivは、applyAfterに、最初の引数として「p2を2番目の引数とするようなafter関数」を、次の引数として「そのafter関数の引数となるパターン」として「p1にstartTagOpenDerivを適用した結果」を、それぞれ渡している。after関数は、引数の順番に意味があるので、flipを使わなければならない。

同様に、groupをapplyAfterに渡す場合も、flipが必要になる。もう一度OneOrMoreに対するstartTagOpenDerivを眺めてみよう。



startTagOpenDeriv (OneOrMore p) qn =

  applyAfter (flip group (choice (OneOrMore p) Empty))

             (startTagOpenDeriv p qn)

さて、今回でこの一連のシリーズで書こうと思っていたことは全て書き終えたわけだが、この辺で切ると後味が悪いので、もしかしたら最後に最適化についての話を書いて終わりにするかもしれない。多分書いた方が良いんだろうな。