【翻译】Rust中的尾递归优化的故事

MikeLoveRust

发布于 2020-06-19 16:19:29

1.8K0

发布于 2020-06-19 16:19:29

原文标题: The Story of Tail Call Optimizations in Rust 原文链接: https://dev.to/seanchen1991/the-story-of-tail-call-optimizations-in-rust-35hf

我认为尾调用优化(tail call optimizations)相当整洁，特别是它们解决递归函数如何调用这类基本问题的方式。诸如Haskell和Lisp家族这类函数式语言，以及逻辑语言(Prolog可能是最著名的例子)都强调采用递归的方式思考问题。这些语言通过尾调用优化可以在性能上获得许多好处。

注意: 我不会在这篇文章里解释尾调用的概念。下面是一些比较好的相关资料:

Youtube频道 Computerphile[1] 有一个视频[2]，详细讲解了尾递归函数的示例。
StackOverflow[3]上有个关于尾递归概念的详细解释。

随着最近几年编程社区强调函数范式和函数式风格的趋势，您可能会认为尾调用优化已经出现在许多编译器/解释器的实现中。然而，事实上很多这类流行语言并没有实现尾调用优化。Javascript在几年前还支持，但是后来将其移除[4]。Python不支持[5]，Rust也不支持。在深入探究为什么会这样之前，让我们简要地总结一下尾调用优化背后的思想。

尾调用优化是如何工作的(理论上)

尾递归函数，如果运行在一个不支持TCO(译者注:TCO==Tail Call Optimization, 即尾调用优化)的环境中，会出现内存随着函数输入的大小而线性增长的情况。这是因为每个递归调用都会向调用栈分配一个额外的栈帧。TCO的目标就是通过一种不需要为每个调用分配栈帧的方式运行尾递归函数来消除这种线性内存占用。一种实现方式就是让编译器来做这件事，一旦编译器发现需要执行TCO,就把尾递归函数执行转换成一个迭代循环。这意味着尾递归函数的结果只需要占用单个栈帧就能计算出来。内存使用为常量。

有了上面这些知识，让我们回来看看，为什么Rust没有做TCO。

回顾Rust的时光机

我能找到的最早关于Rust中尾调用优化的相关资料，可以追溯到Rust项目的开始阶段。我发现了来自2013年的这些邮件列表[6]，在这些邮件列表中，Graydon Hoare详细列出了关于为什么他认为尾调用优化不属于Rust的观点。

这份邮件列表是来自大约2011年的GitHub上的这个[7]issue，当时这个项目的几位初始成员正在思考如何在后来崭露头角的编译器上实现TCO。当时问题的核心似乎是由于LLVM的不兼容；说实话，他们讨论的很多东西我都无法理解。有趣的是，尽管有了最初关于TCO不会在Rust中实现(也是来自最初的作者，毫无疑问)的悲观预测，时至今日，人们仍然没有放弃尝试在rustc中实现TCO。

在rustc中添加TCO的后续提议

在2014年五月，这个[8]PR被开启，其中提到，关于早期邮件列表里提到的问题，LLVM现在已经能够支持TCO了。更具体地说，这个PR旨在通过引入一个名为become的新关键字来启用按需TCO( on-demand TCO)。在这个PR生命周期的整个过程中，有人指出rustc能够，在特定情况下，推断出什么时候TCO是合适的并且执行它[9]。因此，被提议的become关键字和unsafe类似，只是专门适用于TCO。接下来的一个RFC在2017年2月份开启，和之前的提议非常相似。有趣的是，这个RFC作者提出，实现尾调用优化(也被称为"正确尾调用(proper tail calls)")的一些最大障碍可以归结如下：

可移植性问题；LLVM当时在某些指定架构上特别是MIPS和WebAssembly，不支持正确尾调用。
LLVM中正确尾调用实际上可能会由于它们当时的实现方式而造成性能损失。
TCO让调试变得更加困难，因为它重写了栈上的值。

的确，RFC的作者承认，到目前为止，在没有TCO的情况下，Rust运行得非常好，而且会一直非常好。目前为止，显式地由用户控制的TCO还没有加入到rustc。

通过一个库启用TCO

尽管如此，许多阻碍TCO相关的RFC和提议的问题可以在一定程度上得到避免。出现了几个添加TCO到Rust里的自制解决方案。这些方案的共同思想是实现一个成为"trampoline"的东西。这指的是实际使用迭代循环来替代尾递归函数的抽象。

我们先用一个trampoline实现它，作为一个缓慢的跨平台回退实现，然后依次为每个架构/平台实现更快的方法，怎么样? 通过这种方式，该特性可以非常迅速地准备好，以便人们可以使用它进行优雅的编程。在rustc的未来版本中，这样的代码将神奇地变得更快。 @ConnyOnny[10]

Bruno Corrêa Zimmermann’s的tramp.rs[11]库可能是这些库解决方案里知名度最高的一个。让我们在下面来看一下它是如何工作的。

深入tramp.rs

tramp.rs库导出了两个宏， rec_call!和rec_ret!，这和前面提到的become关键字一样改进了相同的行为:它允许程序员通过迭代循环提示Rust运行时执行指定的尾递归函数，从而将函数的内存开销降低到一个常数级别。 rec_call!这个宏启动了这个过程，如果这个关键字被引入到rustc里的话，也是和become关键字最相似的。

macro_rules! rec_call {
   ($call:expr) => {
       return BorrowRec::Call(Thunk::new(move || $call));
   };
}

rec_call!利用了额外的两个重要的概念，BorrowRec和Thunk。

enum BorrowRec<'a, T> {
    Ret(T),
    Call(Thunk<'a, BorrowRec<'a, T>>),
}

BorrowRec枚举表示一个尾递归函数调用在任意时刻可能处于的两种状态: 要么它还没有到达基础状态(base case)，也就是我们仍然处于BorrowRec::Call状态，或者它已经达到了一个基础状态并且产生了它最终的值，这种情况下被认为是达到了BorrowRec::Ret状态。 BorrowRec枚举的Call变量包含下面这个Thunk的定义:

struct Thunk<'a, T> {
    fun: Box<FnThunk<Out = T> + 'a>,
}

Thunk结构体持有一个对尾递归函数的引用，这个尾递归函数由FnThunk这个trait来表示。最后，这些都通过tramp函数联系在一起:

fn tramp<'a, T>(mut res: BorrowRec<'a, T>) -> T {
    loop {
        match res {
            BorrowRec::Ret(x) => break x,
            BorrowRec::Call(thunk) => res = thunk.compute(),
        }
    }
}

它接收一个包含尾递归函数的BorrowRec实例作为输入，并且只要BorrowRec停留在Call状态就一直调用这个函数。另外，当递归函数到达带有最终计算出的值的Ret状态时，最终的值会通过rec_ret!宏来返回。

这是TCO吗？

所以，这样对吗？tramp.rs是我们需要来在Rust编程中启用按需TCO的英雄，对么？恐怕不是这样。虽然我很喜欢这个实现中使用trampolining作为一种增量引入TCO的方式，@timthelion[12]已经完成的性能测试[13]表明，相较于手动把尾递归函数转换成迭代循环，使用tramp.rs会导致一个轻微的性能回退。