尾调用

尾调用是一个库，它为稳定版 Rust 添加了安全、零成本的 尾递归。

最终，它将被 become 关键字 所取代。

安装

尾调用作为 crate 发布。

将以下内容添加到您的 Cargo.toml

[dependencies]
tailcall = "~1"

用法

将 tailcall 属性添加到您想要使用尾递归的函数中

use tailcall::tailcall;

#[tailcall]
fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

有关更详细的信息（包括一些限制），请参阅 文档。

实现

核心思想是将函数重写为使用 trampoline 方法 的循环。以下是上面 gcd 示例的（略微格式化）展开

fn gcd(a: u64, b: u64) -> u64 {
    tailcall::trampoline::run(
        #[inline(always)] |(a, b)| {
            tailcall::trampoline::Finish({
                if b == 0 {
                    a
                } else {
                    return tailcall::trampoline::Recurse((b, a % b))
                }
            })
        },
        (a, b),
    )
}

您可以使用 cargo expand 查看您用例中 tailcall 宏的确切展开。

开发

开发依赖项、测试、文档生成、打包和分发都通过 Cargo 管理。

检出仓库后，运行 cargo test 以验证测试套件。最新的文档可以通过 cargo doc 生成。提交前，请确保代码以规范的方式格式化，并使用 cargo fmt 格式化，并通过 cargo clippy 通过所有 lint。新版本通过 cargo publish 发布到 crates.io。

基准测试

有几个基准测试可用；目前基准测试表明，对于单个函数的尾递归，性能与使用循环相同。相互递归可以运行，但会受到惩罚。

$ cargo bench
    Finished bench [optimized] target(s) in 0.05s
     Running target/release/deps/tailcall-b55b2bddb07cb046

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/release/deps/bench-b8ab29e7ebef8d8d

running 4 tests
test bench_oddness_boom   ... bench:           6 ns/iter (+/- 0)
test bench_oddness_loop   ... bench:           6 ns/iter (+/- 0)
test bench_oddness_mutrec ... bench:   4,509,915 ns/iter (+/- 7,095,455)
test bench_oddness_rec    ... bench:           3 ns/iter (+/- 0)

test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured; 0 filtered out

如果将优化级别设置为0，那么代码bench_oddness_boom就不会被巧妙地优化掉，预期会引发栈溢出

$ RUSTFLAGS="-C opt-level=0" cargo bench _boom
    Finished bench [optimized] target(s) in 0.05s
     Running target/release/deps/tailcall-b55b2bddb07cb046

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/release/deps/bench-b8ab29e7ebef8d8d

running 1 test

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

实际上，在运行以下命令时也会发生相同的情况：RUSTFLAGS="-C opt-level=0" cargo bench _mutrec，这表明互递归也可能引发栈溢出，但是带有尾递归优化的loop和单函数，尾递归函数可以享受尾递归优化（TCO）

$ RUSTFLAGS="-C opt-level=0" cargo bench _loop
    Finished bench [optimized] target(s) in 0.06s
     Running target/release/deps/tailcall-b55b2bddb07cb046

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/release/deps/bench-b8ab29e7ebef8d8d

running 1 test
test bench_oddness_loop   ... bench:   4,514,730 ns/iter (+/- 7,498,984)

test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 3 filtered out


$ RUSTFLAGS="-C opt-level=0" cargo bench _rec
    Finished bench [optimized] target(s) in 0.05s
     Running target/release/deps/tailcall-b55b2bddb07cb046

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/release/deps/bench-b8ab29e7ebef8d8d

running 1 test
test bench_oddness_rec    ... bench:  22,416,962 ns/iter (+/- 16,083,896)

test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 3 filtered out

贡献

欢迎在GitHub上提交错误报告和拉取请求。

许可证

尾递归（Tailcall）在MIT许可证和Apache许可证（版本2.0）的条款下分发。

请参阅LICENSE-APACHE、LICENSE-MIT和COPYRIGHT以获取详细信息。