Trampolined-style Programming

May 15, 2008 – 3:56 pm

今天在 pyscheme 的代码里看到许多诸如 pogo.pogopogo.landpogo.bounce 之类的调用,感觉特别奇怪,不过它的注释写得很详细,做这样的东西是为了解决 Python 没有尾递归优化的问题。

在有尾递归优化的语言里(Scheme 是最典型的一个例子,因为它甚至把尾递归作为语言的一个重要特性放在语言规范中了),如果一个函数的最后一个动作(除了 return)是调用另一个函数的话,就直接用那个函数的栈帧替换当前的栈帧,省去了 call and return 的麻烦,还避免了栈溢出,时间空间都有优势。

作为一个最简单的例子,下面是“正常”的求阶乘和尾递归版本的阶乘:

1
2
3
4
5
6
def fac(n):
    result = 1
    while n != 0:
        result *= n
        n -= 1
    return result
1
2
3
4
def iter_fac(n, acc=1):
    if n == 0:
        return acc
    return iter_fac(n-1, acc*n)

后者是 Scheme 鼓励的写法,也是一个典型的尾递归,当然鼓励这样写并不是因为可以少写几行代码。其实两者是完全不同的编程风格:前者通过赋值将状态保存在 result 变量中,属于传统的命令式编程,而后者则没有任何赋值操作,而是将状态依次传递下去。至于函数编程的威力,我想从近日 Erlang 和诸如 Google 的 MapReduce 之类的东西开始引起人们的广泛关注就可以了解到了。

而且尾递归优化不止在函数式编程中有用,即使在命令式编程中,许多算法还是使用递归的方式表达出来更加清晰。比如编译器的 parser ,用递归下降方式写出来的代码和用 LALR 方式写出来的代码(实际上绝大部分时候都是直接生成吧,我想很少有人能够手写 LALR parser 吧)一对比就知道了,一个简单一个复杂,一个清晰一个混乱。当然递归下降分析器的解析能力不如 LALR 强,但这不是递归的问题,Parsing expression grammar 就采用递归下降的方式进行构造,甚至能够解析诸如 anbncn 这样的非上下文无关文法。

扯远了,再回到尾递归。Trampolined-style programming 可以看作是一种在没有尾递归的语言中的 workaround ,它的执行方式是建立一个中央的调度循环(成为 pogo ),不断地调用需要完成的任务,即 bounce ,直到任务 land 为止:

def pogo(bouncer):
    "A trampoline that bounces a single bouncer."
    while True:
        if bouncer[0] == 'land':
            return bouncer[1]
        elif bouncer[0] == 'bounce':
            bouncer = bouncer[1](*bouncer[2])

而在我们实际的任务代码中(例如求阶乘),需要递归调用某个函数来完成任务的时候,并不是直接调用,而是把这个函数包装成一个任务(bounce)返回到中央调度那里,由那里发起调用,这样就可以避免栈越叠越高了。如果任务完成了,直接将结果包装为一个 land 任务返回即可。

def tramp_fac(n, k=1):
    if n == 0:
        return land(k)
    return bounce(tramp_fac, n-1, k*n)

landbounce 只是一个简单的浅包装:

def bounce(function, *args):
    """Returns a new trampolined value that continues bouncing on the
    trampoline."""
    return ('bounce', function, args)
 
def land(value):
    """Returns a new trampolined value that lands off the trampoline."""
    return ('land', value)

这就是 Trampolined-style Programming 了。如果感兴趣的话,可以看看这篇论文:Trampolined Style (1999)

  1. 2 Responses to “Trampolined-style Programming”

  2. …, 这么好的文章为啥没有人回喃,觉得就算没有所以然,随便唠嗑唠嗑也好啊。现在真是很少能见到道理有趣,解释清楚的文章了。前后看了Blog都很有意思啊.

    By is on Jul 13, 2008

  3. 确实满新颖的思路,我正好在思考递归函数的性能问题,你的文章给了很多启发

    By vincent on Jun 21, 2009

Post a Comment