Initial proposal for Tail-Drop Elimination

tail_drop_elimination.rs

///! Proposal for guaranteed Tail-Drop elimination for functions that do not return values.
///!
///! We revisit the `become` keyword limiting it to functions that do not return values
///! Given this constraint, it becomes much easier to implement.
///! A programmer can always supply the place to return to with a continuation anyways quite trivialy.

/// This is why it must be done at a language level.
/// The programmer cannot do this themselves or they would have a stack overflow.
/// If the programmer did try to do it themselves, it would require a very complex, type unsafe way to do it.
/// All parts can be guaranteed to be sound statically

struct Defer<Return, Cont: FnOnce(Return)>(Option<(Return, Cont)>);

impl<Return, Cont: FnOnce(Return)> Default for Defer<Return, Cont> {
  fn default() -> Self {
    Defer(None)
  }
}

impl<Return, Cont: FnOnce(Return)> Defer<Return, Cont> {
  fn return_cont(ret: Return, cont: Cont) -> Self {
    Self(Some((ret, cont)))
  }
}
impl<Return, Cont: FnOnce(Return)> core::ops::Drop for Defer<Return, Cont> {
  fn drop(&mut self) {
    // If the compiler has followed it's guarantees, the activation record at the top of the function stack
    // can now be replaced with the frame of the continuation.
    // If we chain the `become`'s destructors we use no extra stack space

    if let Some((ret, cont)) = self.0.take() {
      cont(ret)
    }
  }
}

#[derive(Debug)]
struct OverflowError;

/// What we want to write
/// ```compile_fail
/// fn fact(n:u128)->Result<u128,OverflowError> {
///   let mut out = 0;
///   fact_inner((n,1,&mut out));
///   return if out == 0
///     { Err(OverflowError) } else {Some(out)};
///
///   // where :
///   fn fact_inner((n,acc0,out) : (u128,u128,&mut u128)){
///     if n == 0 { *out=acc0; return; };
///
///     let acc1 = acc0.wrapping_mul(n);
///     if acc1 < acc0 { *out=0; return; };
///
///     become fact_inner((n-1,acc1, out))
///   }
/// }
/// ```
/// /// What we would interpret as the semantics as a programmer.
fn fact(n: u128) -> Result<u128, OverflowError> {
  let mut out = 0;
  fact_inner((n, 1, &mut out));
  return if out == 0 { Err(OverflowError) } else { Ok(out) };

  // where :
  fn fact_inner(args: (u128, u128, &mut u128)) {
    #![allow(unused)]
    let mut recurse = Default::default();
    '_ensure_drop_order: {
      let (n, acc0, out) = args;
      
      if n == 0 {
        *out=acc0;
        return;
      };
    
      let acc1 = acc0.wrapping_mul(n);
      if acc1 < acc0 {
        *out=0;
        return; // we must return immediately
      };
    
      recurse = Defer::return_cont((n - 1, acc1, out), fact_inner);
      return; // this is here for redundancy, we must return immediately
    }
  }
}

// a second example with a little more explanation

/// What we want to write
/// ```compile_fail
/// fn safe_div_cps(x: i32, y: i32, cont_success: impl FnOnce(i32), cont_fail: impl FnOnce(String)) {
///   if y == 0 {
///     become cont_fail(format!("cannot divide by zero"))
///   } else {
///     become cont_success(x+y)
///   }
/// }
/// ```
///
/// What we would interpret as the semantics as a programmer.
fn safe_div_cps(x: i32, y: i32, cont_success: impl FnOnce(i32), cont_fail: impl FnOnce(String)) {
  // if we can guarantee that all branches have destructors at the beginning of scope,
  // The compiler must guarantee that any assignment to the following variables is followed by an immediate return
  #![allow(unused)]
  let (mut success, mut fail) = Default::default();
  // the arguments have to be moved after the `Defer`
  '_ensure_drop_order: {
    let x = x;
    let y = y;
    let cont_success = cont_success;
    let cont_fail = cont_fail;
    
    Defer::return_cont((), |_| println!("attempting safe_div() ..."));
    if y == 0 {
      fail = Defer::return_cont(format!("cannot divide by zero"), cont_fail);
      return; //we must return immediately
    }
    
    success = Defer::return_cont(x + y, cont_success);
    return; // this is here for redundancy, we must return immediately
  }
}

fn main() {
  {
    println!("fact(5) = {:?}", fact(5));
    safe_div_cps(5, 0, |s| println!("Success! : {s}"), |f| println!("Failure! : {f}"))
  }
}