- Notifications
You must be signed in to change notification settings - Fork8
Safe, zero-cost tail recursion for stable Rust
License
Unknown, MIT licenses found
Licenses found
alecdotninja/tailcall
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Tailcall is a library that adds safe, zero-costtail recursion to stable Rust.
Eventually, it will be superseded by thebecome keyword.
Tailcall is distributed as acrate.
Add this to yourCargo.toml:
[dependencies]tailcall ="~1"
Add thetailcall attribute to functions which you would like to use tail recursion:
use tailcall::tailcall;#[tailcall]fngcd(a:u64,b:u64) ->u64{if b ==0{ a}else{gcd(b, a % b)}}
For more detailed information (including some limitations), please seethe docs.
The core idea is to rewrite the function into a loop using thetrampoline approach.Here is the (slightly reformatted) expansion for thegcd example above:
fngcd(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 thetailcall macro in your use-case withcargo expand.
Development dependencies, testing, documentation generation, packaging, and distribution are all managed viaCargo.
After checking out the repo, runcargo test to verify the test suite.The latest documentation can be generated withcargo doc.Before commiting, please make sure code is formatted canonically withcargo fmt and passes all lints withcargo clippy.New versions are released tocrates.io withcargo publish.
There are a few benchmarks available; currently the benchmarks demonstrate that forsingle-function tail-recursion, performance is the same as using a loop. Mutualrecursion runs, but suffers penalties.
$ cargo bench Finished bench [optimized] target(s) in 0.05s Running target/release/deps/tailcall-b55b2bddb07cb046running 0 teststest result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Running target/release/deps/bench-b8ab29e7ebef8d8drunning 4 teststest 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 outIf the optimization level is set to zero so thatbench_oddness_boom isn't cleverlyoptimized 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-b55b2bddb07cb046running 0 teststest result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Running target/release/deps/bench-b8ab29e7ebef8d8drunning 1 testthread 'main' has overflowed its stackfatal runtime error: stack overflowIn fact the same occurs when runningRUSTFLAGS="-C opt-level=0" cargo bench _mutrec, indicating mutual recursion can also blow the stack, but theloop and tailrec-enabledsingle-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-b55b2bddb07cb046running 0 teststest result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Running target/release/deps/bench-b8ab29e7ebef8d8drunning 1 testtest 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-b55b2bddb07cb046running 0 teststest result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Running target/release/deps/bench-b8ab29e7ebef8d8drunning 1 testtest 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 outBug reports and pull requests are welcome onGitHub.
Tailcall is distributed under the terms of both the MIT license and the Apache License (Version 2.0).
SeeLICENSE-APACHE andLICENSE-MIT, andCOPYRIGHT for details.
About
Safe, zero-cost tail recursion for stable Rust