1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
//! 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: //! ```rust //! 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: //! ```rust //! 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. //! //! ```rust //! #[macro_use] extern crate tramp; //! //! use 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); //! ``` use std::fmt; /// A single recursive-function result. #[derive(Debug)] pub enum Rec<T> { /// This variant is returned when the function is done; i.e. this the /// result of the computation. Ret(T), /// This variant is returned when the function is about to call itself /// or another in a tail position (i.e. there is no job after the call), /// generally indicates recursion. Call(Thunk<Rec<T>>), } trait FnThunk { type Out; fn call_boxed(self: Box<Self>) -> Self::Out; } /// A delayed computation. This can be used in lazy evaluation environments. /// Also, it is used to delay a tail call and emulate TCO (tail call /// optimization). pub struct Thunk<T> { fun: Box<FnThunk<Out = T>>, } impl<T, F> FnThunk for F where F: FnOnce() -> T, { type Out = T; fn call_boxed(self: Box<Self>) -> T { (*self)() } } impl<T> Thunk<T> { /// Creates a new thunk from the given function. Probably you will end up /// passing closures to this function. pub fn new(fun: impl FnOnce() -> T + 'static) -> Self { Self { fun: Box::new(fun), } } /// Computes the result of this thunk, i.e. forces evaluation to happen. pub fn compute(self) -> T { self.fun.call_boxed() } } impl<T> fmt::Debug for Thunk<T> { fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result { write!(fmtr, "thunk {} ptr: {:?} {}", '{', &*self.fun as *const _, '}') } } /// Given an input closure which returns the `Rec` type, this function performs /// a trampoline over the returned value. While `Rec::Call(thunk)` is returned, /// this function will keep evauating `thunk`. Whenever `Rec::Done(x)` is /// found, `x` is returned. pub fn tramp<T>(start: impl FnOnce() -> Rec<T> + 'static) -> T { let mut res = start(); loop { match res { Rec::Ret(x) => break x, Rec::Call(thunk) => res = thunk.compute(), } } } /// 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>`. #[macro_export] macro_rules! rec_call { ($call:expr) => { return $crate::Rec::Call($crate::Thunk::new(move || $call)); }; } /// 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>`. #[macro_export] macro_rules! rec_ret { ($val:expr) => { return $crate::Rec::Ret($val); }; } /// Executes a `Rec`-function call inside a trampolin. #[macro_export] macro_rules! tramp { ($call:expr) => { $crate::tramp(move || $call) }; }