Crate tramp[−][src]

This crate provides some facilities for recursing in Rust.

Motivation

Most iterative problems can be solved using recursion instead of loops. In fact, when you start learning functional programming, you will see the possibility of solving a given problem using recursion. If the language does not optimize away some kinds of recursion, programming functionally may be hard, because stack overflow may happen eventually if a big case of recursion happens.

A common optimization is the so called "tail call optimization", "tail call reduction" or any similar name. First, let's understand tail call. Tail call is basically a function found in "tail" position of a function body. The tail position means the call is the last thing done in the function body. Optimizing it away means that, instead of generating a new stack frame for the called function, the compiler will reuse the current frame for the called function. In fact, the call may be turned into a loop. But it still is recursion, because the programmer did not write a loop. It's just an optimization.

Currently, Rust does not provide any language item to optimize the tail call. There is a "promised" feature named become. become, for now, is just a reserved identifer, but the intention is that it acts like a return, but does a tail call reduction. Well, there is no prevision for when this is implemented or if it ever will be implemented. So, we decided to create a library allowing the programmer to write optimized recursion with tail calls.

Example

Take a look in this factorial function:

fn fac(n: u128) -> u128 {
    if n > 1 {
        n * fac(n - 1)
    } else {
        n
    }
}

Clearly, the function above is not tail recursive. After the recursive call, we still have to multiply the result by n. However, there is a well-known version of this function which takes an extra argument: an accumulator. Take a look:

fn fac(n: u128) -> u128 {
    //!
    fn fac_with_acc(n: u128, acc: u128) -> u128 {
        if n > 1 {
            fac_with_acc(n - 1, acc * n)
        } else {
            1
        }
    }

    fac_with_acc(n, 1)
}

The function fac_with_acc is tail recursive. There is no job to be done after the call to itself. There is only one problem: Rust does not do any tail call optimization (yet). Now, the crate tramp does its job. We implemented in this crate a trampoline. A trampoline simulates a tail call optimization by calling a function which might return another function (which will be called again) or a computed result. The trampoline will keep calling in a loop the returned function, and whenever the function returns a computed value instead of a function, the trampoline returns the value. Take a look in the example below.

#[macro_use] extern crate tramp;

use tramp::{tramp, Rec};

fn factorial(n: u128) -> u128 {
    fn fac_with_acc(n: u128, acc: u128) -> Rec<u128> {
        if n > 1 {
            rec_call!(fac_with_acc(n - 1, acc * n))
        } else {
            rec_ret!(acc)
        }
    }

    tramp(fac_with_acc(n, 1))
}

assert_eq!(factorial(5), 120);

Macros

rec_call	Turns a (probably recursive) tail call into a return value of type `Rec`. The variant created is `Rec::Call`. Given an expression `x` of type `T`, then `rec_call!(x)` has type `Rec<T>`. It is equivalent to, given a fictional attribute "optimize_tail_call", `#[optimize_tail_call] return x` transforming `T` into `Rec<T>`.
rec_ret	Returns a value from a `Rec`-function. This means the recursion is done. Given an expression `x` of type `T`, then `rec_ret!(x)` has type `Rec<T>`. It is equivalent to `return x` transforming `T` into `Rec<T>`.

Rec	A single recursive-function result with static lifetime.

Crate tramp[−][src]

Motivation

Example

Macros

Structs

Enums

Functions

Type Definitions