高阶流程控制语句（二）: stackful coroutine

20 December 2011

上次介绍了 stackless coroutine(generator) , 这次介绍真正具有完整功能的coroutine

首先看一下下面这段遍历二叉树的代码:

var travel = function(tree) {
        if (leaf(tree)) {
                yield tree;
        } else {
                /*???*/ travel(left(tree));
                /*???*/ travel(right(tree));
        }
};

对于叶子节点, 直接yield就可以了, 但是对于递归的traval调用. ??? 处应该填什么?

方法1: 借助stackless coroutine实现stackful coroutine

回想一下上次实现的Fibonacci generator:

function fib() {
  var i = 0, j = 1;
  while (true) {
    yield i;
    var t = i;
    i = j;
    j += t;
  }
}

Fibonacci内部只需要保存两个状态, F(n-2)与F(n-1), 分别用i,j保存. 但是遍历二叉树, 我们需要保存的状态是 从当前叶子节点到根节点的整条路经, 遇到这种状态是动态的情况, stackless coroutine就无能为力了. 不过我们可以借助闭包, 把需要保存的状态记录在闭包里面, 这样使用stackless coroutine保存这单个闭包, 就可以了:

var join = function() {
        for (var index in arguments) {
                for (var i in arguments[index]) {
                        yield i;
                }
        }
};
var travel = function(tree) {
        if (leaf(tree)) {
                return (function() {
                        yield tree;
                })();
        } else {
                return join(travel(left(tree)), travel(right(tree)));
        }
};

由于javascript调用函数是按值传递的, 上面这段代码运行到join函数之前, 会先计算join的参数, 递归调用travel函数, 导致很多次travel调用, 我们希望在开始遍历的时候再调用travel函数, 所以这里需要一次lazy优化:

var join = function() {
        for (var index in arguments) {
                for (var i in arguments[index]()) {
                        yield i;
                }
        }
};
var travel = function(tree) {
        if (leaf(tree)) {
                return (function() {
                        yield tree;
                })();
        } else {
                return join(function() {
                        return travel(left(tree));
                }, function() {
                        return travel(right(tree));
                });
        }
};

通过这个例子, 我们用stackless coroutine实现了stackful coroutine, 其中的关键, 就是这个join函数.

使用类似概念实现的coroutine有很多, 比如Kilim
[Kilim: Isolation-Typed Actors for Java. ( pdf ) ]
. 通过把需要Join的函数调用标记出来, 可以由编译器自动生成代码, 实现类似这里Join函数的工作. Kilim就是用@pausable这个annotation来标记需要Join的函数调用.

方法2: 使用CPS变换实现stackful coroutine

除了使用这个Join函数实现stackful coroutine之外, 还可以使用CPS变换实现stackful coroutine. 在流程控制领域, CPS变换几乎是万能的, 以后会解释为什么CPS是万能的.

首先, 从原始的traval函数开始:

var travel = function(tree) {
        if (leaf(tree)) {
                yield tree;
        } else {
                travel(left(tree));
                travel(right(tree));
        }
};

然后, 对这个函数做CPS变换:

var $travel = function(k, tree) {
        if (leaf(tree)) {
                return $yield(k, tree);
        } else {
                return $travel(function() {
                        return $travel(k, right(tree));
                }, left(tree));
        }
};

最后, 把上面这个函数包装成generator:

var travel = function(tree) {
        var generator = {};
        var $yield = function(k, result) {
                generator.next = k;
                return result;
        };
        var $travel = function(k, tree) {
                if (leaf(tree)) {
                        return $yield(k, tree);
                } else {
                        return $travel(function() {
                                return $travel(k, right(tree));
                        }, left(tree));
                }
        };
        generator.next = function() {
                return $travel(function() {
                        throw "stopIterator";
                }, tree);
        };
        return generator;
};

完整的代码如下, 各位可以试试, 看看里面是如何工作的:

var leaf = function(tree) {
        return typeof tree !== "object";
};
var left = function(tree) {
        return tree.l;
};
var right = function(tree) {
        return tree.r;
};

var travel = function(tree) {
        var generator = {};
        var $yield = function(k, result) {
                generator.next = k;
                return result;
        };
        var $travel = function(k, tree) {
                if (leaf(tree)) {
                        return $yield(k, tree);
                } else {
                        return $travel(function() {
                                return $travel(k, right(tree));
                        }, left(tree));
                }
        };
        generator.next = function() {
                return $travel(function() {
                        throw "stopIterator";
                }, tree);
        };
        return generator;
};

var g = travel({
        l: {
                l: 1,
                r: 2
        },
        r: 3
});

for (;;) {
        print(g.next());
}

杂谈

javascript的语法真是又臭又长, 使用CoffeeScript重写了一下上面的代码, 发现简洁好多 (44 → 24 lines):

leaf = (tree) -> typeof tree != "object"
left = (tree) -> tree.l
right = (tree) -> tree.r

travel = (tree) ->
        $yield = (k, result) ->
                generator.next = k
                result
        $travel = (k, tree) ->
                if leaf(tree)
                        $yield(k, tree)
                else
                        $travel((() -> $travel(k, right(tree))), left(tree))
        generator =
                next: () -> $travel((() -> throw "stopIterator"), tree)

g = travel
        l:
                l: 1
                r: 2
        r: 3

while true
        console.log(g.next())

虽然CoffeeScript仅仅是完全山寨javascript, 无任何创新, 但是最近却非常火热, 说明javascript实在是丑到家了

functional programming 9