Trampolined-style Programming

今天在 pyscheme 的代码里看到许多诸如 pogo.pogo 、pogo.land 、pogo.bounce 之类的调用，感觉特别奇怪，不过它的注释写得很详细，做这样的东西是为了解决 Python 没有尾递归优化的问题。在有尾递归优化的语言里（Scheme 是最典型的一个例子，因为它甚至把尾递归作为语言的一个重要特性放在语言规范中了），如果一个函数的最后一个动作（除了 return）是调用另一个函数的话，就直接用那个函数的栈帧替换当前的栈帧，省去了 call and return 的麻烦，还避免了栈溢出，时间空间都有优势。作为一个最简单的例子，下面是“正常”的求阶乘和尾递归版本的阶乘：


def fac(n):
    result = 1
    while n != 0:
        result *= n
        n -= 1
    return result


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 就采用递归下降的方式进行构造，甚至能够解析诸如 aⁿbⁿcⁿ 这样的非上下文无关文法。扯远了，再回到尾递归。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)

land 和 bounce 只是一个简单的浅包装：


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)。

Free Mind

Trampolined-style Programming

Comments (2)