Tail Call Elimination Rust

tailcall.rs

#![allow(redundant_semicolons)]

/// The current continuation
type Cont<S,O> = (S, fn(S)->Process<S,O>);

/// The State of a Process
enum Process<S,O>
{ Continue(Cont<S,O>)
, Complete(O)
}

/// The requirement for a tail call elimination
trait TailRecursive
{ type Arg
; type State
; type Out

; fn init_state(arg : Self::Arg)->Self::State
; fn step(state : Self::State)->Process<Self::State, Self::Out>

; fn call(arg : Self::Arg) -> Self::Out
  { let mut p = Process::Continue((Self::init_state(arg), Self::step))
  ; loop 
    {match p {
      Process::Complete(out)    => return out,
      Process::Continue((s, f)) => p = f(s)
    }}
  }
}

/// A Factorial implementation
enum Fact {}
impl TailRecursive for Fact 
{ type Arg   = u8
; type State = (u128, u8)
; type Out   = u128
;
  fn init_state(arg : Self::Arg)->Self::State { (1,arg) }
  fn step((acc, n) : Self::State)->Process<Self::State, Self::Out> 
  { match n 
    { 0 | 1 => Process::Complete(acc)
    , _     => Process::Continue(((acc * n as u128, n - 1), Self::step))
    }  
  }
}

/// A Lucas numbers implementation
enum Lucas {}
impl TailRecursive for Lucas 
{ type Arg   = u8
; type State = (u128, u128, u8)
; type Out   = u128
;
  fn init_state(arg : Self::Arg)->Self::State { (2, 1 , arg) }
  fn step((current, next, countdown) : Self::State)->Process<Self::State, Self::Out> 
  { match countdown 
    { 0 => Process::Complete(current)
    , _ => Process::Continue(( ( next, current + next, countdown - 1 ) ,  Self::step )),
    }
  }
}

/// A Fibonacci numbers implementation
enum Fib {}
impl TailRecursive for Fib 
{ type Arg   = u8
; type State = (u128, u128, u8)
; type Out   = u128
;
  fn init_state(arg : Self::Arg)->Self::State { (0, 1 , arg) }
  fn step((current, next, countdown) : Self::State)->Process<Self::State, Self::Out> 
  { match countdown 
    { 0 => Process::Complete(current)
    , _ => Process::Continue(( ( next, current + next, countdown - 1 ) ,  Self::step )),
    }
  }
}



// the following used to find the abstraction

fn fact(num : u8) -> u128
{ use Process::*
; let mut p : Proc = Continue(((1,num), _fact))
; loop 
  {match p {
    Complete(out)    => return out,
    Continue((s, f)) => p = f(s)
  }}

; type State = (u128, u8)
; type Proc  = Process<State,u128>
; fn _fact((acc, n) : State)->Proc
  { match n 
    { 0 | 1 => Complete(acc)
    , _     => Continue(((acc * n as u128, n - 1), _fact))
    }
  }
}

fn fib(num : u8) -> u128 
{ use Process::*
; let mut p : Proc = Continue((State{current : 0, next : 1 ,countdown : num}, _fib))
; loop 
  {match p {
    Complete(out)    => return out,
    Continue((s, f)) => p = f(s)
  }}

; struct State {current: u128, next: u128, countdown:u8}
; type Proc  = Process<State,u128>
; fn _fib(State { current, next, countdown } : State ) -> Proc {
    match countdown 
    { 0 => Complete(current)
    , _ => Continue
      ((State 
        { current   : next
        , next      : current + next
        , countdown : countdown - 1 
        } 
      , _fib
      )),
    }
  }
}

fn lucas(num : u8) -> u128 
{ use Process::*
; let mut p : Proc = Continue((State{current : 2, next : 1 ,countdown : num}, _lucas))
; loop 
  {match p {
    Complete(out)    => return out,
    Continue((s, f)) => p = f(s)
  }}

; struct State {current: u128, next: u128, countdown:u8}
; type Proc  = Process<State,u128>
; fn _lucas(State { current, next, countdown } : State ) -> Proc {
    match countdown 
    { 0 => Complete(current)
    , _ => Continue
      ((State 
        { current   : next
        , next      : current + next
        , countdown : countdown - 1 
        } 
      , _lucas
      )),
    }
  }
}



fn main() 
{ let phi = (5.0f64.sqrt() + 1.0)/2.0
; for each in 0..34 { println!("factorial of {each} = {}", fact(each))}
; for each in 0..42 { println!("fib of {each} = {}", fib(each))}
; for each in 0..42 { println!("lucas of {each} = {}", lucas(each))}
; for each in 0..42 
  { println!(
    "diff from phi with fib vs lucas of {each} = \nfib   : {}\nlucas : {}"
  , ((fib(each+1)   as f64 / fib(each)    as f64) - phi).abs()
  , ((lucas(each+1)as f64 / lucas(each) as f64) - phi).abs()
  )}
; for each in 0..42 { println!("lucas with trait of {each} = {}", Lucas::call(each))}

}