3 releases

✓ Uses Rust 2018 edition

0.1.4 Mar 8, 2020
0.1.2 Dec 3, 2019
0.1.1 Dec 3, 2019
0.1.0 Dec 1, 2019

#171 in Algorithms

46 downloads per month

MIT/Apache

28KB
51 lines

Tailcall

Build Status Current Crates.io Version Docs

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 = "0.2"

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.

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.

Dependencies

~385–710KB
~17K SLoC