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/