Tailcall

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

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

安装

Tailcall 以 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 时也会发生相同的情况，这表明相互递归也可能崩溃栈，但启用了尾递归的单函数尾递归函数享有尾递归优化（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。