読者です 読者をやめる 読者になる 読者になる

C# 3.0の新機能を知るためにモナドパーサーコンビネータから見始めるのは無謀じゃないのか

先日のエントリ (id:ABA:20080918#p1)の結論は、XNALINQ使うのはやっぱりカスタムインポーターでのパースしかないよね!っていうことだったので、LINQで書くパーサーを見てみようと思ったのだが、

C# 3.0も知らないしモナドパーサーコンビネータも知らない人間がいきなりこれを読むのはつらいんじゃないか……まあやってみるかね。

public delegate Result<TInput, TValue> Parser<TInput, TValue>(TInput input);

Step 1はParserをデリゲートで定義している。Parserはなんらかの入力を受け取ってそれをパースできたValueと残りのまだパースしてないRestに分けるメソッド

public static Parser<TInput, TValue> OR<TInput, TValue>(
    this Parser<TInput, TValue> parser1, 
    Parser<TInput, TValue> parser2) 
{
    return input => parser1(input) ?? parser2(input);
}

Step 2はParserにORとAND演算子を追加。怪しげなthisの使い方から見てこれは拡張メソッドだよね?ORは入力を左項、右項の2つのParserに順に突っ込むラムダ式を返す。'??'という怪しげな演算は2.0から追加されたNullable型向けのもので左がnullじゃなければそれを、nullだったら右を返す。ANDは左項のParserでパースしたRestを右項のParserに突っ込むラムダ式を返す。

public static class ParserCombinatorsMonad {
    // By providing Select, Where and SelectMany methods on Parser<TInput,TValue> we make the 
    // C# Query Expression syntax available for manipulating Parsers.  
    public static Parser<TInput, TValue> Where<TInput, TValue>(
        this Parser<TInput, TValue> parser, 
        Func<TValue, bool> pred)

Step 3ではWhereとSelectとSelectManyを拡張メソッドでParserに突っ込む。ここがよく分からんのだが、この3つのメソッドを拡張しておけば、特定の型(この場合はParser)に対してLINQでの問い合わせができるという理解でいいんだよね。joinとかは別として。

で、WhereはFuncを食ってParserを返す。Funcは定義済みの汎用デリゲート。なのでWhereは入力をパースした結果のValueをFuncに食わせてtrueだったらその結果を、falseだったらnullを返すラムダ式を返す。Valueだけを見ているのは、次のパース対象をチェックするという使い方にwhereを使うから、か?

SelectはselectorにValueを食わせてから結果を返す。SelectManyは……これがよく分からん。fromがSelectとSelectManyにどのように展開されるのかがよく分かってないので理解が追いつかない。たぶん連続するfromが連接を意味するようにするためなのだろうが……

public Parser<TInput, TValue[]> Rep<TValue>(Parser<TInput, TValue> parser) {
    return Rep1(parser).OR(Succeed(new TValue[0]));
}
public Parser<TInput, TValue[]> Rep1<TValue>(Parser<TInput, TValue> parser) {
    return from x in parser 
           from xs in Rep(parser)
           select (new[] { x }).Concat(xs).ToArray();
}

んでStep 4が壊滅的に分からん。Parsersはparserを繰り返し適用するための仕組みなのだろうが、これはいったい何をやっているんだ。おそらくRepが停止条件で、Rep1がその再帰的な適用なのだろうが。CharParsersはキャラクタを1文字ずつパースする標準的なパーサらしい。

Id = from w in Whitespace
     from c in Char(char.IsLetter)
     from cs in Rep(Char(char.IsLetterOrDigit))
     select cs.Aggregate(c.ToString(),(acc,ch) => acc+ch);

Step 5までくるともはや使い方の例なので、なんとなくは分かる。fromを連続で使った場合はある連接した表記を意味しているっぽいので、例えばIdは任意数のホワイトスペース+アルファベット+任意数のアルファベットまたは数字から成り、結果はホワイトスペースを読み飛ばした残りの文字列。この文字列作るのにわざわざAggregateせんといかんのか。

あとはパース結果をselectの中でVarTermとかLambdaTermとかいう具合に構築していく。いちいちTermにキャストしないといかんのがダサイがなぜこんなことをしているんだ。こうしないとAllのところのin Termに引っかからなくなったりするのか?

public override Parser<string, char> AnyChar {
    get { { return input => input.Length > 0 ?
      new Result<string,char>(input[0], input.Substring(1)) : null; } }
}

Step 6はStep 5の呼び出し方。ここで初めてAnyCharのgetterを定義していて、最初の文字をValueに残りをRestに入れるラムダ式になっている。

というわけで結論としては良く分からんかった。まずモナドパーサーコンビネーターの基本的な理解が必要な感じ。あとたぶんこの例はSelect周りの使い方がアクロバティックすぎて、普通のLINQを理解する用途には向いてないと思われる。

もう一つ根本的な疑問として、こんなふうにLINQを駆使しなくても、素直にNParsec (http://jparsec.codehaus.org/NParsec+Tutorial)使えばいいんじゃねえのっていう気もするんだが。LINQ使ったほうが少しは関数型言語っぽく書けているのかなあ。