Tagless Final simple

tagless.rs

#[derive(Debug,Clone)]
enum Expr {
    Val(i32),
    Neg(Box<Expr>),
    Sum(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),

    Var(String),   
}
fn eval(expr: Expr) -> Option<i32> {
  Some(match expr {
    Expr::Val(x) => x,
    Expr::Neg(e) => -eval(*e)?,
    Expr::Sum(l, r) => eval(*l)? + eval (*r)?,
    Expr::Mul(l, r) => eval(*l)? * eval (*r)?,
    Expr::Var(var) => return None,
  })
}

fn partial_eval(expr: Expr) -> Expr {
  match expr {
    Expr::Neg(expr)          => match partial_eval(*expr) {
                                  Expr::Val(v) => { Expr::Val(-v) },
                                  otherwise    => { Expr::neg(otherwise) }
                                },
    Expr::Sum(expr, expr1)   => match [partial_eval(*expr), partial_eval(*expr1)] {
                                  [Expr::Val(l), Expr::Val(r)] => Expr::Val(l+r),
                                  [l,r] => Expr::sum(l, r)
                                },
    Expr::Mul(expr, expr1)   => match [partial_eval(*expr), partial_eval(*expr1)] {
                                  [Expr::Val(l), Expr::Val(r)] => Expr::Val(l*r),
                                  [l,r] => Expr::mul(l, r)
                                },
    Expr::Val(_) | Expr::Var(_) => expr,
  }
}

fn ast_generic_eval<D : Dsl>(e : Expr)->D {
  match e {
    Expr::Val(v)    => D::val(v),
    Expr::Neg(expr) => D::neg(ast_generic_eval(*expr)),
    Expr::Sum(l, r) => D::sum(ast_generic_eval(*l), ast_generic_eval(*r)),
    Expr::Mul(l, r) => D::mul(ast_generic_eval(*l), ast_generic_eval(*r)),
    Expr::Var(v)    => D::var(v),
  }
}



trait Dsl {
  fn val(v : i32) -> Self;
  fn neg(e : Self) -> Self;
  fn sum(l : Self, r : Self) -> Self;
  fn mul(l : Self, r : Self) -> Self;

  fn var(v : String) -> Self;
}
impl Dsl for Expr {
  fn val(v : i32           ) -> Self { Expr::Val(v) }
  fn neg(e : Self          ) -> Self { Expr::Neg(Box::new(e)) }
  fn sum(l : Self, r : Self) -> Self { Expr::Sum(Box::new(l), Box::new(r)) }
  fn mul(l : Self, r : Self) -> Self { Expr::Mul(Box::new(l), Box::new(r)) }

  fn var(v : String) -> Self { Expr::Var(v) }
}
impl Dsl for i32 {
  fn val(v : i32           ) -> Self { v     }
  fn neg(e : Self          ) -> Self { -e    }
  fn sum(l : Self, r : Self) -> Self { l + r }
  fn mul(l : Self, r : Self) -> Self { l * r }

  fn var(v : String) -> Self {
      todo!()
  }
}
impl Dsl for String {
  fn val(v : i32           ) -> Self { v.to_string()          }
  fn neg(e : Self          ) -> Self { format!("-{e}")        }
  fn sum(l : Self, r : Self) -> Self { format!("({l} + {r})") }
  fn mul(l : Self, r : Self) -> Self { format!("({l} * {r})") }

  fn var(v : String) -> Self { format!("$'{v}'") }
}
#[derive(Debug)]
enum StackInst {
  LoadVar(String),
  Lit(i32),
  Sum,
  Mul,
  Neg,
}
impl Dsl for Vec<StackInst> {
    fn val(v : i32) -> Self { Vec::from([StackInst::Lit(v)]) }

    fn neg(mut e : Self) -> Self {
        e.push(StackInst::Neg);
        e
    }
    fn sum(mut l : Self, mut r : Self) -> Self {
        l.append(&mut r);
        l.push(StackInst::Sum);
        l
    }
    fn mul(mut l : Self, mut r : Self) -> Self {
        l.append(&mut r);
        l.push(StackInst::Mul);
        l
    }
    fn var(v : String) -> Self { Vec::from([StackInst::LoadVar(v)]) }
}

fn run_bytecode_with_vars(bc : &[StackInst], vars : &HashMap<String, i32>) -> Result<Vec<i32>, (usize, Vec<i32>)> {
  let mut cur = bc;
  let mut stack = Vec::new();
  macro_rules! error {() => { {return Err((bc.len() - cur.len(), stack));}};}
  loop {
    cur = match cur {
        [] => return Ok(stack),
        [inst, rest @ ..] => {
          match inst {
            StackInst::LoadVar(name) => if let Some(&v) = vars.get(name)
                                             { stack.push(v); }
                                        else { error!() },
            StackInst::Lit(v)        => stack.push(*v),
            StackInst::Sum 
            | StackInst::Mul         => {
              let split = stack.len() - 1;
              if let ([.., l], [r]) = stack.split_at_mut(split) {
                match inst {
                    StackInst::Sum => *l += *r,
                    StackInst::Mul => *l *= *r,
                    _ => unreachable!()
                }
                stack.pop();
              } else {
                error!()
              }
            },
            StackInst::Neg => if let Some(top) = stack.last_mut() {
              *top = -*top
            } else {
              error!()
            },
          }
          // the code advances 
          rest
        }
    }
  }
}

fn dsl_expr<D : Dsl>() -> D {
  D::mul( D::val(3) , D::neg ( D::sum ( D::neg( D::val(42) ) , D::val(5)) ) )
}

fn dsl_expr_with_var<D : Dsl>() -> D {
  D::mul( D::var("x".to_string()) , D::neg ( D::sum ( D::neg( D::val(42) ) , D::val(5)) ) )
}



fn main() {
  type E = Expr;
  let as_expr   = dsl_expr_with_var::<Expr>();
  let as_bytecode   = dsl_expr_with_var::<Vec<StackInst>>();
  // let as_i32    = dsl_expr::<i32>();
  // let as_string = dsl_expr_with_var::<String>();
  
  // println!("Expr                                 : {as_expr:?}");
  // println!("Vec<StackInst>                       : {as_bytecode:?}");
  // println!("ast_generic_eval(Expr)               : {:?}", ast_generic_eval::<Vec<StackInst>>(as_expr.clone()));
  // // println!("ast_generic_eval(Expr)               : {:?}", ast_generic_eval::<String>(as_expr.clone()));
  
  println!("Expr                   : {as_expr:?}");
  let partial = partial_eval(as_expr.clone());
  println!("Expr                   : {partial:?}");
  let optimised = ast_generic_eval::<Vec<StackInst>>(partial);
  println!("Vec<StackInst> : {:?}", optimised);

  let mut vars = HashMap::new();
  vars.insert(String::from("x"), 15);

  let result = run_bytecode_with_vars(&optimised, &vars);
  println!("RUN_CODE {{\n\tcode   : {:?}\n\tvars   : {:?} \n\tresult : {:?}\n}}",optimised, vars, result)


  // println!("ast_generic_eval(partial_eval(Expr)) : {:?}", ast_generic_eval::<Vec<StackInst>>(partial_eval(as_expr.clone())));
  // // println!("ast_generic_eval(partial_eval(Expr)) : {:?}", ast_generic_eval::<String>(partial_eval(as_expr)));
  // println!("String                               : {as_string:?}");
  // println!("i32 (not the same expression)        : {as_i32:?}");
}