Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2009-07-11 (Sat)JavaでParserモナド

JavaでParserモナド

| 20:47 | JavaでParserモナド - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - JavaでParserモナド - yoshihiro503の関数的日記

Java で Parser モナドを書いてみた。

JavaGenerics(ポリモルフィズム)があるのでほとんどcastを使わず型安全に実装できたが型推論がないので型が非常に冗長になった。

このパーサーライブラリを使えば、例えばラムダ式のパーサーが次のように30行くらいで書ける。P.mbind, P.dbind, P.mor, P.mreturn はそれぞれ Haskellでいう >>=, >>, <|>, return に対応する。

    static Parser<LAMBDA> lambda () {
	return P.mor(P.map (T.ident, new Fun<String,LAMBDA>() {
		    public LAMBDA apply (final String v) {
			return new VAR(v);
		    } }),
	    P.mor (P.dbind(T.symbol('('), P.dbind(T.symbol('\\'), P.bind (T.ident, new Fun<String,Parser<LAMBDA>>() {
				public Parser<LAMBDA> apply (final String v) {
				    return P.dbind(T.symbol('.'), P.bind (lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						public Parser<LAMBDA> apply (final LAMBDA t) {
						    LAMBDA abs = new ABS(v,t);
						    return P.dbind(T.symbol(')'), P.mreturn (abs));
						} }));
				} }))),
		   P.bind(T.symbol('('), new Fun<Unit,Parser<LAMBDA>>() {
			   public Parser<LAMBDA> apply(Unit _) {
			       return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
				       public Parser<LAMBDA> apply (final LAMBDA t1) {
					   return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						   public Parser<LAMBDA> apply (final LAMBDA t2) {
						       LAMBDA app = new APP(t1, t2);
						       return P.dbind(T.symbol(')'), P.mreturn (app));
						   } });
				       } });
			   } })));
    }

使い方

 $ java Main '((\x.x) ( \ y. (y y)) )'
パース成功: ((λx.x) (λy.(y y)))

パースした結果は以下の記事にかいてあったラムダ式を利用しようかと思ったけど、ちょっとそのままじゃ使えなかったので諦めた。

Java でラムダ - IT戦記

ソースコード全体は300行くらい

http://bitbucket.org/yoshihiro503/parsecinjava/src/

2008-12-01 (Mon)

haXeでパーサーの演算

| 15:36 | haXeでパーサーの演算 - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - haXeでパーサーの演算 - yoshihiro503の関数的日記

トークンの列などを解析して、何かを読み取るパーサー型をhaXeで次のように定義した。

typedef ParserT<X> = ListT<Token> -> Either<Pair<ListT<Token>, X>, Error>;

読み取る対象はトークンのリストで、X型のものを読もうとする。

パースが成功したときは 「left(残りの列, 読んだものx)」を返し、失敗したときは「right(エラーメッセージ等)」を返す。

パーサーは関数だが、haXeは関数型言語なので、パーサー同士の演算を考えることが出来る。

パーサーの足し算

パーサー同士の足し算を次のように定義してみた。

// <|> operation : ParserT<X> -> ParserT<X> -> ParserT<X>
static function door<X> (p1 : ParserT<X>, p2 : ParserT<X>) : ParserT<X> {
    return function (source) {
	return switch p1(source) {
	case left(rest_x): left(rest_x);
	case right(err1):
            switch p2(source) {
	    case left(rest_x): left(rest_x);
	    case right(err2):
		right(err1+", "+err2);
	    }
	}
    }
}

足し算で得られるパーサーは、p1でパースして、成功したらその結果を返し、失敗したら、p2でパースしてみる。両方失敗したら失敗を返すパーサーだ。

HaskellのParsecとかにある <|> 関数(その見た目からCSNagoyaではドア関数と読んでいる)みたいなものだ。

p1とp2の型は一致していないといけない。

ここで、zeroパーサーを考える。これは何にもマッチしないパーサーだ。これは足し算における単位元になっている。

つまり door (p1, zero) === p1 かつ door (zero, p2) === p2となる。

パーサーのかけ算

パーサー同士のかけ算は次のように定義してみた。

// ParserT<X> -> ParserT<Y> -> ParserT <Pair<X,Y>>
static function prod<X, Y> (p1: ParserT<X>, p2: ParserT<Y>) : ParserT<Pair<X, Y>> {
    return function (source) {
	return switch p1(source) {
	case left(rest_x):
            var rest = Util.fst(rest_x);
            var x = Util.snd(rest_x);
 	    switch p2(rest) {
	    case left(rest_y):
		var rest = Util.fst(rest_y);
		var y = Util.snd(rest_y);
	        left(rest, (x, y));
	    case right(msg): right(msg);
            }
	case right(msg): right(msg);
	}
    }
}

かけ算によるパーサーはp1で読んでからp2で読んで、XとYのペアを返すようなパーサーで、両方パースできたときにのみパースが成功する。いくつかのパーサーで順番に読んでいくときに便利だ。


足し算とかけ算の問題点

小さいパーサーをこれらの演算で組み合わせて、大きいパーサーを構築する事ができる、さらにそれらを組み合わせて

より複雑なパーサーを作る事ができる。この足し算とかけ算は非常に便利で、いろいろなパーサーを表現する事ができる。

しかし、一見数学的にもきれいなように思えるこの演算体系はあんまりきれいじゃない。環にもならないし群も形成しない。かけ算に関しては、逆元も持たないし、推移律すら成り立たない。

また、かけ算では常にペアのパーサーしか構築できず、そのためにパーサーのmap関数とかも考えたけど、どうもかっこ悪い気がする。p1で読んだ結果に応じてp2の振る舞いを変えるとかみたいな柔軟な設計もできない。

そこで、次のような関数を考えてみた。

// combine : ParserT<X> -> (X -> ParserT<Y>) -> ParserT<Y>
static function combine<X, Y> (p1 : ParserT<X>, f : X -> ParserT<Y>) : ParserT<Y> {
    return function (source) {
	return switch p1 (source) {
	case left (rest_x):
	    var rest = Util.fst (rest_x);
	    var x = Util.snd (rest_x);
	    Util.apply (f (x), rest);
	case right (msg): right (msg);
	}
    }
}

この関数は、パーサーp1とパーサーを生成する関数fを受け取ってパーサーを返す関数である。

combine (p1, f) パーサーにトークンの列 source を渡すと、

まずp1でトークンを読んで、成功したら、読めたxにfを適用して生成したパーサーf(x)を使って残りを読み、p1で失敗したら、失敗を返す。

この関数の型をよくよく見てみると、どこかで見たことがある気がする。そうだ!モナドだ!モナドの ( >>= )関数になっている!

そこで、この関数名をmbindという名前に変えて、次はmreturnを実装してみる。

// mreturn : X -> ParserT<X>
static function mreturn<X> (x : X) : ParserT<X> {
    return function (source) return left(source, x);
}

これらmbindとmreturnを使えば、さっきのprod関数は以下のようにクールに定義できる。

// ParserT<X> -> ParserT<Y> -> ParserT <Pair<X,Y>>
static function prod<X, Y> (p1: ParserT<X>, p2: ParserT<Y>) : ParserT<Pair<X, Y>> {
    return mbind (p1, function (x) return mbind (p2, function (y) return mreturn(pair(x, y))));
}

以下の記事を読めば、より具体的に理解できるので、オススメである。

モナディック・パーサー - あどけない話

結論:パーサーモジュールは mbind と mreturn と door 関数があれば十分。