Tailcall

Tailcall is a library that adds safe, zero-cost tail recursion to stable Rust.

Eventually, it will be superseded by the become keyword.

Installation

Tailcall is distributed as a crate.

Add this to your Cargo.toml:

[dependencies]
tailcall = "~1"

Usage

Add the tailcall attribute to functions which you would like to use tail recursion:

use tailcall::tailcall;

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

For more detailed information (including some limitations), please see the docs.

Implementation

The core idea is to rewrite the function into a loop using the trampoline approach. Here is the (slightly reformatted) expansion for the gcd example above:

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),
    )
}

You can view the exact expansion for the tailcall macro in your use-case with cargo expand.

Development

Development dependencies, testing, documentation generation, packaging, and distribution are all managed via Cargo.

After checking out the repo, run cargo test to verify the test suite. The latest documentation can be generated with cargo doc. Before commiting, please make sure code is formatted canonically with cargo fmt and passes all lints with cargo clippy. New versions are released to crates.io with cargo publish.

Benchmarks

There are a few benchmarks available; currently the benchmarks demonstrate that for single-function tail-recursion, performance is the same as using a loop. Mutual recursion runs, but suffers penalties.

$ 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

If the optimization level is set to zero so that bench_oddness_boom isn't cleverly optimized away, it blows the stack as expected:

$ 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

In fact the same occurs when running RUSTFLAGS="-C opt-level=0" cargo bench _mutrec , indicating mutual recursion can also blow the stack, but the loop and tailrec-enabled single-function, tail-recursive functions enjoy 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

Contributing

Bug reports and pull requests are welcome on GitHub.

License

Tailcall is distributed under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE and LICENSE-MIT, and COPYRIGHT for details.

alecdotninja/tailcall