LINQで簡単DSL

これはもともとお仕事記事として書いていたのですが、いろいろ折り合いつかず流れてしまいました。
まだ書きかけですが、完成させる気もいまいち湧かなかったので、このまま公開します。
サンプルプロジェクトは

https://github.com/karino2/BParserDSL

に置いておきます。

------

概要

LINQとはC# 3.0 から導入された、SelectManyのシンタックスシュガーの事だ。

近年ではRxやSpracheなど、SQL以外の分野でのLINQの活用例も増えてきた。
このシンタックスシュガーを用いてDSLを作る方法を解説する。
SelectManyを定義する事で、とても短時間で強力なDSLを構築する事が出来る。

(以下本文）
SelectManyは非常に強力で多くの応用がある事が判明してきていて、最近の言語では大抵言語のコアの文法要素として、このシンタックスシュガーが入っている。
C#でもこの例に漏れずLINQという形でシンタックスシュガーが導入された。

SelectManyを使ったDSLの利点は

1. 実装コストが少ない（コアは数十行程度）
2. 柔軟性が高い
3. 拡張が容易
4. インテリセンスがフルで機能する
5. 型チェックがとても有効に機能して、大変バグが入りにくい

一方欠点は

1. 抽象度が高くどういう場合にどう実装したらいいのかを簡単なハウツーに落とせない
2. シンタックスが限定される
3. 生成されるコードの効率が想像しづらい

といった物になる。

以上の特徴から、DSLの名前の通り、特定のドメインに特化した、専用のフレームワークを書き捨てるのに非常に向いている。

例として、jpegのヘッダをパースする例を考えてみよう。

JPEGHeader Parse(BitStream stream) {
  var byte = stream.ReadByte();
  VerifyByte(byte, 0xFF);
  byte = stream.ReadByte();
  VerifyByte(byte, 0xD8);

  while(!stream.IsEnd) {
    var segmentType = stream.ReadBytes(2);
    var segmentLen = stream.ReadBytes(2);

    switch(segmentType) {
    case 0xFFDB:
       // parse DQT
       //...
     case 0xFFC4:
        // parse DHT
        //...
     case 0xFF93:
        // start data
     }
}

この手の処理で巨大なswitch文を書くのは、良く行われる事ではあるが、問題も多い。
一例を挙げると、各case文での処理や先頭の処理が多くなってくると関数に追い出す事になるが、このswitch文と関数の関係が密過ぎて、両者を理解していないと読めない関数になりがちである。
また、処理自体が読みにくく、バグも埋め込みやすい。

これをSelectManyを用いたDSLで書く場合は、例えば以下のように書ける。

var Start = from h1 in ByteOf(0xFF)
        from h2 in ByteOf(0xD8)
        select 0xFFD8;

var Dqt = from segType in WordOf(0xFFDB)
      from len in Word()
      from tableId in Word()
      from QFs in QF(tableId).Times(QFNum(len))
      select new {name="DQT", tableId=tableId, QFList=Qfs};

var Dht = from segType in WordOf(0xFFC4)</div>