Java functional in action

借着trustno1开坛讲学的春风, 我结合java做了一个动态类型的functional库.
目标如下:
1. reference transparent. 所有的函数本身都是immutable的. 虽然用户函数内部或许会有副作用, 但是库本身不产生任何副作用.
2. currying. 比如一个int f(int i, int j);的函数, f(1)就是一个int->int->int的函数类型.
3. 高阶函数, 支持把函数当作其它函数的参数和返回值.
4. 泛形. 即使算上generic java, java的泛形也不可能达到函数语言的组合子的类型灵活性. 所以, 我们干脆放弃静态类型, 完全利用java的动态类型(即reflection)来处理类型的灵活性.
5. 充分利用java的静态类型. java的动态类型很繁琐. 要求instanceof啦, downcast啦. 我们仍然希望至少在写函数的时候能够少用downcast.


好. 闲话说完. 我们先来看看用这个库能做什么.


[code:1]import jfun.core.Fun;
import jfun.core.Function;

public class Test{
public String cat3(String a, int b, int c){
return a+b+c;
}
public void test1(){
Function f1= Fun.fun(this, "cat3");
Function result = f1.f("hello").f(10).f(3);
System.out.println(result.getValue().toString());
}
}[/code:1]
这个f1.f(...).f(...)就是currying了.每次用f()来调用,都做了一次curry, 把一个函数变换成另外一个函数.
这里, f()可以接受任何的原始类型或者对象. 类型安全你自己保证. 但是haskell里面的类型的灵活性被保住了.

另外, 我们在写基础函数的时候还是使用传统的java method.

下面看看高阶函数的使用:
[code:1]import jfun.core.Fun;
import jfun.core.Fn;
import jfun.core.Function;

public class Test{
public interface Plus extends Fn{
int add(int i, int j);
}
public int doplus(Plus pl, int i, int j){
return pl.add(i,j);
}
public int plus(int i, int j){return i+j;}
public void test(){
final Function pl = Fun.fun(this, "plus");
final Function dpl = Fun.fun(this, "doplus");
final Function tmp = dpl.f(pl).f(10);
final Function result1 = tmp.f(3);
final Function result2 = tmp.comp(pl.f(2)).f(1);
System.out.println(result1.getValue().toString());
System.out.println(result2.getValue().toString());
}
}[/code:1]
第一和第二句是创建对应于plus, 和doplus的两个函数.
第三句是部分调用dpl,pl这个函数就被匹配给doplus的第一个Plus类型的参数, 然后10被匹配给第二个整数参数. 现在, 函数tmp只在等待最后一个参数了.

我们先直接用3来调用tmp,结果应该是13.
对result2, 我们稍微绕一下. 先把pl函数部分调用, 传入一个2, 这样pl.f(2)也在等待一个整形参数.
然后, 我们应用库预定义好的comp操作, 也就是函数组合操作.

两个函数组合如此定义:

[code:1]comp(f1, f2) = f where
f a = f1(f2(a))[/code:1]
就是说, 函数组合就是说, 来了一个参数, 先传递给f2, 然后把f2的返回值当作参数传给f1.

根据这个定义, result2的结果也是13.


对返回函数的高阶函数, 我们也有类似的处理. 这里不赘述了.

基于这个函数库, haskell的monadic combinator也是可以模拟的. 我现在还在继续写我的monad库, 已经完成了state monad部分.
回头总结一下再发.

缺点:
1. 静态类型安全没有了. 程序员要自己保证安全. 大家如果熟悉python的话可能对这个不会太惊讶.
2. java没有lamda表达式. 在这个库里面要做lamda只能借助于anonymous class, 语法冗长罗嗦.
3. 没有haskell的do notation, 在表达复杂些的函数组合逻辑时可能很麻烦.
4. 因为实现采用了reflection, 并且有很多的动态类型检测和方法查询, 效率会比较差.

总结:
这个库用来做一些简单的组合子还是很handy的. 也许还可以结合一些xml等的配置文件,脚本之类的, 提供一定的表达能力.
使用monad技术, 也许可以制作一些简单的递归下降的parser生成器. 这些在对付一些相对简单的文法时或许会比较经济.

但是, 因为缺乏静态类型安全和lamda, do-notation的支持, 书写大规模的monadic combinator lib可能会比较困难.

展望:
进一步实现haskell里面的部分monad库.
最终, 我们希望能够用它来制作一个简单的递归下降的monadic parser generator, 象c++的spirit那样.
当我有了java1.5之后, 还可以看看怎样利用泛形来稍微改进一下.

下面利用刚写出来的monad库,来做一下那个多利羊的例子. 假设, dolly的家族谱如下:
[code:1] final Sheep chaos = new Sheep("chaos", null, null);
final Sheep gaia = new Sheep("gaia", chaos, chaos);
final Sheep saturn = new Sheep("saturn", gaia, chaos);
final Sheep cronos = new Sheep("cronos", gaia, saturn);
final Sheep eva = new Sheep("eva", gaia, cronos);
final Sheep zeus = new Sheep("zeus", eva, cronos);
final Sheep poseidon = new Sheep("poseidon", eva, cronos);
final Sheep hades = new Sheep("hades", eva, cronos);
final Sheep athene = new Sheep("athene", null, zeus);
final Sheep giant = new Sheep("giant", gaia, null);
final Sheep hercules = new Sheep("hercules", giant, zeus);
final Sheep apollo = new Sheep("apollo", eva, zeus);
final Sheep adam = new Sheep("adam", athene, null);
final Sheep dolly = new Sheep("dolly", adam, null);[/code:1]
呵呵, 一些希腊神仙的名字记不清楚了, 所以有些杜撰. 希望达人给予指正.
然后, 我们来用函数组合制作简单的族谱查询.

首先, 背景知识, 我们有一个Monads类, 用来提供一些常用的对任何monad都有效的算法.
然后, 有Either类来模拟haskell的Either这个monad.
这两个类都是库提供的, 和多利羊无关的通用工具.
下面, 看看我们怎么来得到多利的增祖, 以及更上面的曾祖的祖父, 祖母.

先自己定义两个基本的函数:

[code:1] public Sheep mother(Sheep s){return s.getMother();}
public Sheep father(Sheep s){return s.getFather();}[/code:1]
这里, null表示父或者母不存在.

然后, 做一个辅助函数
[code:1] private static Function liftNext(Function f){
return f.cnst().flip();
} [/code:1]

f.cnst()对应haskell的const函数.

所谓const函数, 就是说不论参数是什么, 我都返回一个值.

flip()把一个函数的前两个参数顺序对调.

这样, 如梭f的类型是: Sheep -> Sheep

那么, f.cnst().flip()的类型就是: Sheep -> Object -> Sheep.

这里面第二个参数会被忽略掉.
做这个函数是为了对付monad bind的时候需要的那个额外的参数.

最后
[code:1]
final Function fmother = Fun.fun(this, "mother");
final Function ffather = Fun.fun(this, "father");
final Function fparent = maybe.mplus(fmother, ffather);
final Function nparent = liftNext(fparent);
final Function fgrandgrandparent = monads.bind(fparent, nparent, nparent);
final Function fgrandfather = monads.bind(ffather, liftNext(ffather));
final Function fgrandmother = monads.bind(fmother, liftNext(fmother));[/code:1]
fparent用了标准的maybe monad的mplus动作, 表示或者母亲, 或者父亲.
nparent调用了我们前面定义的liftNext函数, 得到一个可以持续取得父母的函数.
fgrandgrandparent对fparent和nparent连续bind的两次, 意思就是给我曾祖.
fgrandfather和fgrandmother类似, 就是得到祖父和祖母.

最终的结果应该符合如下的assert

[code:1] assertSheep(fmother.f(dolly), adam);
assertSheep(ffather.f(dolly), null);
assertSheep(fparent.f(dolly), adam);
assertSheep(fgrandgrandparent.f(dolly), zeus);
assertSheep(fgrandmother.f(zeus), gaia);
assertSheep(fgrandfather.f(zeus), saturn);[/code:1]

呵呵. monad 组合子终于初显威力了.

在实现更复杂的monad组合子之前. 还有一个课题需要攻克.

我们说functional语言的好处, 有这么几项:
1. 引用透明
2. 无副作用
3. 函数是一等公民
4. 高阶函数
5. pattern match
...

前四个目标, 我们都已经达到了.
[list]我们的Function库是没有副作用的.
引用透明嘛, 因为java语言本身给了你==这个东西, 不可能100%透明. 但是, 只要你不对函数用==和!=, (你也根本不需要用它们), 那么剩下的就是引用透明的.
java的对象是一类公民, 所以我们的Function是一个对象, 通过方法f(...)来调用. 所以也是一类公民.
高阶函数我前面也展示了怎么做.[/list:u]

就剩下pattern match了.

所谓pattern match, 就是可以根据输入的不同形式采取不同的动作.

比如, 一个二叉树, 我们有如下的数据结构:

[code:1]data Tree = Leaf Int | BinNode Tree Tree[/code:1]
就是说, 一个树节点或者是带一个整数的叶子, 或者是有两个子树的中间节点.

假设我们要判断两颗树的大小. 逻辑上是这样:
叶子节点之间: 比较所带的整数
两个非叶子节点之间: 先比较左子树, 如果相等, 再比较又子树.
叶子节点和非叶子节点: 叶子节点小

写成haskell代码如下:

[code:1]compare (Leaf a) (Leaf b)
| a < b = -1
| a > b = 1
| otherwise = 0
compare(Leaf _) (BinNode _ _) = -1
compare(BinNode _ _) (Leaf _) = 1
compare(BinNode l1 r1) (BinNode l2 r2) = let x = compare l1 l2 in
if x == 0 then compare l2 r2 else x
compare _ _ = raise "no match"
[/code:1]

在传统的java代码中, 我们怎么处理这个问题呢?
一般有两种方法,
1. 用类型安全的visitor pattern. 可以达到针对不同节点类型采取不同策略的目的. 只不过visitor pattern相当重, 代码写起来繁琐. 尤其是对这种double dispatch甚至更多的multi-dispatch的时候, 笨重地要命.
2. 用instanceof + downcast. 写起来比visitor容易些. 但是反复的instanceof和downcast仍然繁琐, 而且很易错.

visitor我就不举了, 写起来太累. 我们来看看instanceof的方法:

[code:1]compare(Tree t1, Tree t2){
if(t1 instanceof Leaf && t2 instanceof Leaf){
final Leaf l1 = (Leaf)t1;
final Leaf l2 = (Leaf)t2;
final int x = l1.getValue() - l2.getValue();
if(x<0)return -1;
else if(x>0)return 1;
else return 0;
}
else if(t1 instanceof Leaf && t2 instanceof BinNode){
return -1;
}
else if(t1 instanceof BinNode && t2 instanceof Leaf){
return 1;
}
else if(t1 instanceof BinNode && t2 instanceof BinNode){
final BinNode l1 = (BinNode)t1;
final BinNode l2 = (BinNode)t2;
final int x = compare(l1.getLeft(), l2.getLeft());
if(x==0) return compare(l1.getRight(), l2.getRight());
else return x;
}
else{throw new IllegalStateException("sorry no match");}
}[/code:1]
很多的cast, 很多的if-else.

如果参与计算的是三个参数呢? 四个呢? 天啊. 我不玩了!

下面, 我们介绍一下用jfun怎么做更好看的,更象fp的pattern match. 我们用咱么最熟悉的方法重载来搞!
[code:1]
public static final class TreeCompare implements Fn{
public int compare(Leaf a, Leaf b){
final int r = a.getValue() - b.getValue();
if(r<0) return -1;
else if(r>0) return 1;
else return 0;
}
public int compare(BinNode a, BinNode b){
final int lr = compareTree(a.getLeft(), b.getLeft());
if(lr == 0) return compareTree(a.getRight(), b.getRight());
else return lr;
}
public int compare(Leaf a, BinNode b){
return -1;
}
public int compare(BinNode a, Leaf b){
return 1;
}
public int compare(Tree a, Tree b){
throw new IllegalStateException("no pattern");
}
}
[/code:1]
简单吧? 自然吧?
唯一有一个问题就是: 重载是静态的. 它只根据静态类型来选择不同函数版本.
而我们很有可能拿到的就是两个Tree, 根本不知道它们的静态类型到底是Leaf还是BinNode. 怎么办?
没关系, 我们用jfun库提供的动态匹配能力


[code:1] private static Function comp = Fun.fun(new TreeCompare());
private static int compareTree(Tree a, Tree b){
final Function result = comp.f(a,b);
assertTrue(result.isValue());
return ((Integer)result.getValue()).intValue();
}[/code:1]

我们唯一要做的就是把TreeCompare对象变成一个Function, 然后调用这个Function就好了.

当然, jfun的pattern match功能还是远没有haskell的强大. 我们只能对类型match, 而无法对空表, 有一个元素的表, 有一个元素并且元素等于1的表这种东西做match.

不过, 还是别人心不足吧. java毕竟不是functional language啊.

太Cool 的。.仰慕一下，UP:P

好.
咱们上回说到哪了啊? 哦, 做了一个玩具的多利羊的例子. 这个东西虽然好玩, 但是不大容易看出实际意义. 今天我们来看一个实际一点的例子: parser.

这些天我一直在用这个库写java的monad. 你可以把Monad看成是一个高阶计算的框架. 所谓高阶计算, 就是说, 我计算的对象仍然是计算本身.

打个比方, 你写一个对某个输入字符串的验证, 你一般来说,就是对这个输入字符数据做计算.
而高阶计算, 就是说, 对一些验证算法的组合和计算.

假如基本上你有isNumber, getLength, isEnglish, NumberValuePositive 等检验算法, 我的高阶计算, 就不再直接面对输入数据, 而是直接对你这几个基本算法进行组合和计算.
我可以把一个算法的输出顺序传递给另外一个算法, 比如isNumber返回一个int, 我就可以把它传递给NumberValuePositive这个算法.
我也可以对两个算法求或, 比如: isNumber or getLength > 5, 就是或者是个数字, 或者这个字符串长度大于5.

通过把一些简单的原子计算组合起来, 我们就可以得到任意多的复杂逻辑.

你可能说, 这最终还不是要面对输入数据? 所谓”高阶”从何说起? 这个, 不通过实例, 还真不好解释. 不过, 先举个例子: 我们知道数学上乘法定义于加法, 3*2最终等价于3+3. 但是, 乘法的交换率, 结合率, 以及其后形形色色的关于乘法的兴致和定理, 我们都一般不再把它们归结于加法来理解了. 实际上, 真要什么都通过加法来理解, 嘿嘿, 真要累死人的!

闲话不提, 我们先介绍一下我们的monad库.

所谓monad, 核心有两个接口:

[code:1]interface Monad{
Function retn(Object v);
Function bind(Function f1, Function ff2);
}
interface MonadPlus extends Monad{
Function mplus(Function f1, Function f2);
Function mzero();
}[/code:1]
Monad接口代表所有monadic计算都具备的特性:
1. retn (haskell中的return), 表示向计算内部提交一个值. 它和java的return不同的是, 它不改变程序流程, 仅仅是提交一个值.
2. bind (haskell中的>>=), 表示两个计算的串接, 第一个计算f1计算完毕, 会把结果传递给计算ff2继续计算.

MonadPlus接口代表一类可以进行分支的计算. 比如, 一个parser, 面对一个输入, 往往面临两个选择: shift还是reduce. 这就可以用MonadPlus来表示.
Mzero顾名思义, 表示0. 而0有这样一个特性, 0 mplus x = x. 另外 0 bind y = 0.

除此之外, 我还实现了一些haskell里面非常有用的monad transformer:
ErrorT (用来给任意的monad添加错误处理功能)
StateT (用来给任意monad添加一个状态转移机制)
ContT(用来得到continuation的功能)
ReaderT, WriterT.

具体的代码, 回头我会给出cvs的link.
现在我们先看问题.

问题: 实现一个计算器, 用来计算整数的加减乘除. 输入是一个字符串, 输出计算结果.
为了让这个问题足够复杂, 我们允许空格, 回车, 以及java风格的行注释和块注释.
下面, 让我们看看怎么用monadic计算来解决这个问题.

Monadic计算作为一个bottom-up的方法. 一般来说都是先从最简单, 最基本的原始计算开始, 逐步组合, 最终达到我们的目的.

那么, 先来基本的parser组合子.

我们用jdk的CharSequence来描述输入. 先定义一个类来作为parse的输入和中间状态:
[code:1]
final class Source {
int getLineNo(){
return lno;
}
int getColNo(){
return cno;
}
int getInd(){return ind;}
char getCharAt(int i){return seq.charAt(i);}
Source nextChar(){
final char c = seq.charAt(ind);
if(c=='\n') return new Source(seq, lno+1,1,ind+1);
else return new Source(seq, lno, cno+1, ind+1);
}
char getChar(){
return seq.charAt(ind);
}
boolean isEof(){
return ind >= seq.length();
}
private final CharSequence seq;
private final int lno;
private final int cno;
private final int ind;
public String toString(){
return "("+lno+","+cno+"): " +
((isEof())?"EOF":""+getChar());
}
}[/code:1]
这是一个非常简单的封装类, 它代表了输入的字符串和当前扫描的行号, 列号, 以及偏移.

然后, 定义一个接口来表示对输入字符的过滤规则:
[code:1]public interface CharPredicate {
boolean isChar(char c);
}[/code:1]好, 基础设施搭好, 下面来用monad框架来建造parser.

首先, 我们需要的一定是一个MonadPlus, 因为在分析过程中, 如前所述, 必然是有分支存在的.
其次, 扫描过程中, 存在一个状态, 所以一定需要能够读取和更改当前状态, 所以, 我们须要一个MonadState (也是标准的monad框架的接口)

然后, 我们来建造地基:
[code:1] public static char getChar(final Source src){
return src.getChar();
}
public static Source nextChar(final Source src){
return src.nextChar();
}
public static int getCursor(final Source src){return src.getInd();}
private static final Function getchar =
toFun("getChar");
private static final Function nextchar =
toFun("nextChar");
private static final Function getcursor =
toFun("getCursor");[/code:1]getchar, nextchar, getcursor是几个后面要用到的基本函数, 就是用来读当前字符, 步进到下一字符, 以及得到当前的位置.
[code:1]
public Function moveNext(){
return mstate.modify(nextchar);
}
public Function getIndex(){
return mstate.gets(getcursor);
}[/code:1]这两个函数使用前面的辅助函数, 生成monad高阶函数. Mstate是从外面ioc进来的一个MonadState变量.
[code:1]
public Function peek(final CharPredicate pred){
final Function nxt = Prelude.makefun(new Lamda(){
public Object fn(final Object obj){
final char c = ((Character)obj).charValue();
if(!pred.isChar(c)) return mplus.mzero();
else return mstate.retn(obj);
}
});
return and(neof(), mplus.bind(mstate.gets(getchar), nxt));
}[/code:1]peek这个高阶函数, 根据CharPredicate来从输入读取一个字符. 如果这个字符满足需要, 就返回, 否则, 就不读任何字符. Mplus也是从外面ioc进来的, 它代表我们前面说要的那个MonadPlus.
[code:1] public Function consume(final CharPredicate pred){
return mplus.seq(peek(pred), moveNext());
}[/code:1]
consume和peek相似. 唯一的区别是, 它还把当前扫描位置向后移动一下.

[code:1] public static boolean isEof(final Source src){return src.isEof();}
private static final Function f_eof = toFun("isEof");
public Function eof(){
return mstate.bind(mstate.get(), Monads.guard(mplus).comp(f_eof));
}[/code:1]
eof()是个高阶函数, 具体的写法我先不讲解, 它的意思就是保证当前是eof.

[code:1] public Function neof(){
return mstate.bind(mstate.get(),
Monads.guard(mplus).comp(Prelude.not()).comp(f_eof));
}[/code:1]同理, neof保证当前不是eof.

[code:1] public Function consumeChar(final char c){
return consume(new CharPredicate(){
public boolean isChar(final char ch){return ch == c;}
});
}[/code:1]
consumeChar就是说, 只有当前的字符是某一个字符的时候才吃掉这个字符.

[code:1] public Function consumeNotChar(final char c){
return consume(new CharPredicate{
public boolean isChar(final char ch){return ch != c;}
});
}[/code:1]自然, consumeNotChar就是只有输入不是某个字符的时候才算数.

[code:1] public Function space(){
return mplus.mplus(
consumeChar(' '), consumeChar('\t'), consumeChar('\r'), consumeChar('\n')
);
}[/code:1]
space用来忽略空白. 使用了标准的mplus()函数来表示”or”的概念.

[code:1] public Function consumeStr(final String str){
Function f = mplus.retn(Unit.instance());
for(int i=0; i<str.length(); i++){
f = mplus.seq(f, consumeChar(str.charAt(i)));
}
return f;
}[/code:1]


consumeStr表示只有当前的输入符合某个字符串才算匹配.
下面, 在进行更复杂些的组合子之前, 我先来介绍几个非常有用的通用组合子:
[code:1] public Function optional(final Function f){
return or(f, mplus.retn(Unit.instance()));
}[/code:1]
optional, 就是我们ebnf里面用的?了. 表示或者有, 或者没有. 我这里这个?是greedy的.

[code:1] public Function and(final Function f1, final Function f2){
return mplus.seq(f1, f2);
}[/code:1]
and就是顺序parse, parse完了第一个, 再来第二个.
[code:1] public Function or(final Function f1, final Function f2){
return mplus.mplus(f1,f2);
}[/code:1]
or就是分支, 或者第一个, 或者第二个.

[code:1]
private Function lazy_many(final Function f){
return Prelude.makefun(new Lamda(){
public Object fn(final Object v){
return many(f).f(v);
}
});
}
public Function many(final Function f){
return optional(and(f, lazy_many(f)));
}
public Function many1(final Function f){
return and(f, many(f));
}[/code:1]many就是*, 0个或多个.
Many1就是+, 1个或多个.

这几个组合子可以应用在任何其它的高阶组合子身上, 它们的用途就象ebnf里面的?+*等一样广泛.

好, 接着来写我们的parser:
[code:1] public Function consumeLineComment(){
return mplus.seq(consumeStr("//"),
or(eof(),many(consumeNotChar('\n')))
);
}[/code:1]这个用来过滤掉行注释.
[code:1]
public Function notFollowedBy(final char c){
return peek(new NotChar(c));
}
public Function isCommentedChar(final char c){
if(c=='*')return mplus.seq(moveNext(), notFollowedBy('/'));
else return moveNext();
}
private final Function f_isCommentedChar = Fun.fun(this, "isCommentedChar");
public final Function commentedChar(){
return mplus.bind(peek(
new CharPredicate(){
public boolean isChar(final char ch){return true;}
}),
f_isCommentedChar
);
}

public Function consumeBlockComment(){
return and(new Function[]{
consumeStr("/*"),many(commentedChar()),consumeStr("*/")
});
}[/code:1]这几个小函数是用来处理块注释的.

[code:1] public Function lexeme(final Function f){
final Function lcomment = consumeLineComment();
final Function bcomment = consumeBlockComment();
final Function spc = space();
return and(many(or(lcomment, bcomment, spc)), f);
}[/code:1]
lexeme也是一个通用组合子, 把它作用于任何其它的组合子之上, 作用都是去掉前导的空格和注释.

[code:1] public Function digit(){
return consume(new CharPredicate(){
public boolean isChar(final char ch){
return ch >= '0' && ch <= '9';
}
});
}[/code:1]
digit()用来判断单个的数字字符.

[code:1] public Function number(){
return many1(digit());
}[/code:1]
number()就是一个以上的digit了.

[code:1]Public Function consumeOp(){
Return or(consumeChar(‘+’), consumeChar(‘-’), consumeChar(‘*’), consumeChar(‘/’);
}[/code:1]
consumeOp就是读一个操作符.

好了, 地基打好了. 下面来写我们的表达式:

[code:1] public Function paren(){
return and(
consumeChar('('), lazy_expr, lexeme(consumeChar(')'))
);
}[/code:1]
paren就是括号括起来的表达式.
[code:1] public Function unary(){
return or(number(), paren());
}
public Function expr(){
return or(and(unary(), consumeOp(), lazy_expr), unary);
}
private final Function lazy_expr = Prelude.makefun(new Lamda(){
public Object fn(final Object v){
return expr().f(v);
}
});[/code:1]写成bnf就是:
[code:1]expr ::= unary op expr | unary
unary ::= number | ‘(‘ expr ‘)’[/code:1]

基本上是照着bnf翻译就是了.
Lazy_expr是为了解决递归的问题, 如果没有lazy, 就无穷递归了.
这是因为java是strict semantics, 换成lazy的haskell就没这个问题了.



好了, 到此, 一个初具规模的parser已经出炉了. 它是一个recursive desent parser.
可以看到, 这样的parser非常容易写, 也容易读. 因为它几乎直接对应bnf.
熟悉c++的朋友也许可能发觉, 它非常象spirit. 不错, spirit也是一个递归下降的parser生成框架. 关于用c++式的静态gp vs. java的动态monadic parser, 我回头会找个时间再比较探讨一下.

不过, 细心的你可能已经发现了. 这个parser并没有做到我们前面需要的功能:
它没有计算, 仅仅是检验了一下输入是否是一个合法的表达式.

是的, 凡事不能一口吃个胖子不是? 要计算就要涉及到所有递归下降方法都要面对的消除左递归问题, 还要解决运算符的优先级, 光是bnf就要麻烦好多. 今天我先演示一个monadic programming的大意, 完整的贴出我的计算器代码并非我的本意. 如果一个简单的例子能够让大家对monadic programming有所理解, 甚至庶几能引起大家的一些思考, 我就心满意足了.
今天先到这里, 下回我再来具体完善这个计算器.

一个真正完整的parser往往是分为scanner和parser两步分.
scanner用来把字符序列转换成tokens. 然后parser再在token的基础上解析语法.

我们这里的例子把两者混在一起了. 这一方面是为了方便, 另一方面, 也为了表现一下组合子逻辑的强大. 你可以把scanner分开, 也可以不分开, 编码上不分开也并没有太大的麻烦.

不过, 这些小parser的效率可实在不怎么样, 就一个简单的测试, parse并计算那么几十个小字符串, 居然花了2秒钟.
要命啊.

这里是cvs的连接, 大家有兴趣的可以下载下来玩玩. (还是个unstable版本). 运行ant test就行了.

cvs -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/jfunctional co jfun



或者, 象我一样在防火墙后面的话:
cvs -d:pserver:anonymous@cvs-pserver.sf.net:443/cvsroot/jfunctional co jfun

这个project还没有release, 也还没来得及写javadoc呢.



haskell的monadic parser确实是有效率低的问题.
这主要是因为monad是一个非常generic的面对一般性计算的framework, 它不是专门为parser设计的, 但是它甚至支持非确定性解析, 对付非常二义性的文法.

但是这样的灵活性也造成了效率上的下降, 任何两个计算的串接都不一定是一对一的. 计算1可能产生100中可能的结果, 计算二要对这一百个结果都处理. 于是你不能用简单的循环, 只能借助于递归.


对此, haskell有一个叫parsec的parser框架. 它对问题做了一定的简化, 同时也做了很大的优化. 使用这个框架, 你写出的递归下降文法, 效率上得到大大的提高.

我的下一步将是对parsec进行移植, 争取在java里也写出一个类似parsec, spirit一样的parser generator库.


另外一个方面, monadic programming有一个讨厌的问题: 调试困难. 面对很多高阶函数组合, 你很难知道下一步程序要走到哪里. 当然, 这比haskell中好多了, 毕竟我们还是有调试器, 有println可用.
于是, 我要思考的另一个问题, 就是怎样refactor这个库, 以方便用户的调试.

完蛋了，俺看不懂!
悄悄问ajoo一句：看不懂的是不是都可以被认为是很笨的！
如果这样的话，我会很难过的！

只是一个示意. 为了让大家感觉一下monadic programming看起来什么样子, 能干什么.
很多相关的代码都没有. 看不懂很正常. 你看懂了, (而且是没有任何haskell经验, 没有任何monad数学理论的经验的情况下), 我就只能惊叹你为天才了.

其实我这里贴的还是怎么从下水道起, 建造一个parser generator framework.

但是, 最终的目的则是, 你不必自己做这些工作.

使用这个parsec库, 你需要做的, 只是把ebnf直接翻译成java.

比如:
对[code:1](number | word)*[/code:1]
只需要
[code:1]Function myparser(){
return many(lexeme(or(number(), word())));
}[/code:1]
就是一个分析数字和单词的tokenizer了.

太帅了，虽然不是很懂，不过看了很兴奋的说