use crate::sexp::{SExp, SExp::*, SLeaf::*, util::*}; impl SExp { /// Evaluates the s-expression one step. /// /// **Integer operations** /// /// Addition, subtraction, multiplication and division /// are supported. /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons(Add, scons(1, scons(1, Nil))).step(), /// Ok(Atom(Int(2))) /// ); /// /// assert_eq!( /// scons(Sub, scons(1, scons(2, Nil))).step(), /// Ok(Atom(Int(-1))) /// ); /// /// assert_eq!( /// scons(Mul, scons(2, scons(3, Nil))).step(), /// Ok(Atom(Int(6))) /// ); /// /// assert_eq!( /// scons(Div, scons(6, scons(2, Nil))).step(), /// Ok(Atom(Int(3))) /// ); /// ``` /// /// Division truncates the decimals. /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons(Div, scons(5, scons(2, Nil))).step(), /// Ok(Atom(Int(2))) /// ); /// ``` /// /// Also, addition and multiplication can take more than two arguments: /// (as of 2025-08-05 not allowed by the type system, might change) /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons(Add, scons(1, scons(2, scons(3, Nil)))).step(), /// Ok(Atom(Int(6))) /// ); /// /// assert_eq!( /// scons(Mul, scons(1, scons(2, scons(3, Nil)))).step(), /// Ok(Atom(Int(6))) /// ); /// ``` /// /// Here's an example of a bit more complicated expression /// from wikipedias article on s-expressions. /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// fn main() { /// let exp = scons( /// Mul, /// scons( /// 2, /// scons( /// scons(Add, scons(3, scons(4, Nil))), /// Nil /// ) /// ) /// ); /// /// let exp = exp.step().unwrap(); /// assert_eq!(exp, scons(Mul, scons(2, scons(7, Nil)))); /// /// let exp = exp.step().unwrap(); /// assert_eq!(exp, Atom(Int(14))); /// } /// /// ``` /// /// **Integer comparisons** /// /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons(Lt, scons(1, scons(2, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(Lt, scons(2, scons(2, Nil))).step(), /// Ok(Atom(False)) /// ); /// /// assert_eq!( /// scons(Gt, scons(2, scons(1, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(Lt, scons(1, scons(1, Nil))).step(), /// Ok(Atom(False)) /// ); /// /// assert_eq!( /// scons(Le, scons(1, scons(2, Nil))).step(), /// Ok(Atom(True)), "le 1" /// ); /// assert_eq!( /// scons(Le, scons(2, scons(2, Nil))).step(), /// Ok(Atom(True)), "le 2" /// ); /// assert_eq!( /// scons(Le, scons(2, scons(1, Nil))).step(), /// Ok(Atom(False)), "le 3" /// ); /// /// assert_eq!( /// scons(Ge, scons(2, scons(1, Nil))).step(), /// Ok(Atom(True)), "ge 1" /// ); /// assert_eq!( /// scons(Ge, scons(1, scons(1, Nil))).step(), /// Ok(Atom(True)), "ge 2" /// ); /// assert_eq!( /// scons(Ge, scons(1, scons(2, Nil))).step(), /// Ok(Atom(False)), "ge 3" /// ); /// /// assert_eq!( /// scons(Eq, scons(1, scons(2, Nil))).step(), /// Ok(Atom(False)) /// ); /// assert_eq!( /// scons(Eq, scons(2, scons(2, Nil))).step(), /// Ok(Atom(True)) /// ); /// /// assert_eq!( /// scons(Neq, scons(1, scons(2, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(Neq, scons(2, scons(2, Nil))).step(), /// Ok(Atom(False)) /// ); /// ``` /// /// **Boolean expressions** /// /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// assert_eq!( /// scons(And, scons(True, scons(True, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(And, scons(False, scons(True, Nil))).step(), /// Ok(Atom(False)) /// ); /// /// assert_eq!( /// scons(Or, scons(False, scons(True, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(Or, scons(False, scons(False, Nil))).step(), /// Ok(Atom(False)) /// ); /// /// assert_eq!( /// scons(Xor, scons(False, scons(True, Nil))).step(), /// Ok(Atom(True)) /// ); /// assert_eq!( /// scons(Xor, scons(False, scons(False, Nil))).step(), /// Ok(Atom(False)) /// ); /// assert_eq!( /// scons(Xor, scons(True, scons(True, Nil))).step(), /// Ok(Atom(False)) /// ); /// /// assert_eq!( /// scons(Not, scons(True, Nil)).step(), /// Ok(Atom(False)) /// ); /// assert_eq!( /// scons(Not, scons(False, Nil)).step(), /// Ok(Atom(True)) /// ); /// ``` /// /// **Quotes** /// /// If an s-expression should not be evaluated /// as a function, but it is instead to be treated /// as a list, `quote` can be used. /// With it as the operator, the rest of the list /// is evaluated to values, but they are not passed /// to the operator after that. /// /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// assert_eq!( /// scons(Quote, scons(1, scons(2, Nil))).step(), /// Ok(scons(Quote, scons(1, scons(2, Nil)))) /// ); /// assert_eq!( /// scons(Quote, scons( /// scons(Sub, scons(2, scons(1, Nil))), /// scons(2, Nil))).step(), /// Ok(scons(Quote, scons(1, scons(2, Nil)))) /// ); /// ``` /// /// **Vectors** /// /// The same as quotes functionally, but they require /// the elements to be of the same type. /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// assert_eq!( /// scons(Vector, scons(1, scons(2, Nil))).step(), /// Ok(scons(Vector, scons(1, scons(2, Nil)))) /// ); /// assert_eq!( /// scons(Vector, scons( /// scons(Sub, scons(2, scons(1, Nil))), /// scons(2, Nil))).step(), /// Ok(scons(Vector, scons(1, scons(2, Nil)))) /// ); /// ``` /// /// **Let-bindings** /// /// Basic operation: /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons( /// scons(Let, scons(var("x"), scons(5, Nil))), scons( /// scons(Add, scons(var("x"), scons(1, Nil))), Nil /// ) /// ).step(), /// Ok(scons(Add, scons(5, scons(1, Nil)))) /// ); /// assert_eq!( /// scons( /// scons(Let, scons(var("y"), scons(4, Nil))), /// scons( /// scons(Let, scons(var("x"), scons(5, Nil))), /// scons(scons(Add, scons(var("x"), scons(var("y"), Nil))), Nil) /// ) /// ).step(), /// Ok(scons( /// scons(Let, scons(var("x"), scons(5, Nil))), scons( /// scons(Add, scons(var("x"), scons(4, Nil))), Nil /// ) /// )) /// ); /// ``` /// /// **Functions** /// ```rust /// use myslip::{sexp::{SExp::*, SLeaf::*, util::*}, r#type::{Type::*, util::*}}; /// /// let varlist = scons(var("a"), scons(var("b"), Nil)); /// let typelist = scons(Ty(List(vec![Integer, Integer])), Nil); /// let ret = Atom(Ty(Boolean)); /// let body = scons(Gt, varlist.clone()); /// let fun = scons(Fun, scons(varlist, scons(typelist, scons(ret, scons(body, Nil))))); /// let args = scons(2, scons(1, Nil)); /// assert_eq!( /// scons(fun, args).multistep(), /// Ok(Atom(True)) /// ); /// ``` /// /// **Pattern matching** /// ```rust /// use myslip::{sexp::{SExp::*, SLeaf::*, util::*}, r#type::{Type::*, util::*}}; /// use myslip::parse::parsetree::parse_to_ast; /// /// let exp = "case (+ 1 2) (3 true) (_ false)"; /// let exp = parse_to_ast(exp); /// let exp = exp.and_then(|e| e.step()); /// let expshould = parse_to_ast("case 3 (3 true) (_ false)"); /// assert_eq!(exp, expshould); /// let exp = exp.and_then(|e| e.step()); /// assert_eq!(exp, Ok(Atom(True))); /// ``` /// /// Shadowing: /// ```rust /// use myslip::sexp::{SExp::*, SLeaf::*, util::*}; /// /// assert_eq!( /// scons( /// scons(Let, scons(var("x"), scons(4, Nil))), /// scons( /// scons(Let, scons(var("x"), scons(5, Nil))), /// scons(scons(Add, scons(var("x"), scons(4, Nil))), Nil) /// ) /// ).step(), /// Ok(scons( /// scons(Let, scons(var("x"), scons(5, Nil))), scons( /// scons(Add, scons(var("x"), scons(4, Nil))), Nil /// ) /// )) /// ); /// ``` /// pub fn step(self) -> Result { match self { // t is value // ---------- // t -> t t if t.is_value() => Ok(t), // List processing // op not a value // ----------------------- // (op x) -> (op.step() x) SCons(op, l) if !(*op).is_value() => Ok(scons(op.step()?, l)), // let binds SCons(op, l) if op.clone().check_let().is_some() => match (*op).check_let() { Some((varname, val)) => Ok(match *l { SCons(a, b) if *b == Atom(Nil) => *a, t => t, }.subst(&varname, &val)), None => panic!("unreachable as per match guard arm"), }, // case expressions SCons(op, l) if scons(op.clone(), l.clone()).check_case().is_some() => { let (scrutinee, patarms) = scons(op, l).check_case().unwrap(); if !scrutinee.is_value() { return Ok(SExp::back_to_case(scrutinee.step()?, patarms)); } let (scrutinee, rest_pat_struct) = match scrutinee { SCons(q, v) if *q == Atom(Quote) => (*v, Some(Quote)), SCons(q, v) if *q == Atom(Vector) => (*v, Some(Vector)), t => (t, None), }; for patarm in patarms { let (pat, arm) = match patarm { SCons(pat, arm) => Ok((*pat, *arm)), _ => Err("unreachable after type checking".to_string()) }?; let mut arm = match arm { SCons(x, n) if *n == Atom(Nil) => *x, t => t, }; if let Some(ctx) = scrutinee.matches_pat(&pat) { for (name, value) in ctx { arm = match name { Var(name) => arm.subst(&name, &value), RestPat(name) => match rest_pat_struct.clone() { Some(kw) => arm.subst(&name, &scons(kw, value)), None => arm.subst(&name, &value) }, _ => panic!("unreachable") }; } return Ok(arm); } } Err("This should be unreachable after type checking".to_string()) }, // op value and a1 .. an values, and b0, b1 .. bn not values // --------------------------------------------------------- // (op a1 ... an b) -> (op a1 ... an b0.step() b1 .. bn) SCons(op, l) if !(*l).consists_of_values() => { fn inner(s: SExp) -> Result { match s { SCons(a, b) if (*a).is_value() => Ok(scons(a, inner(*b)?)), SCons(a, b) => Ok(scons(a.step()?, b)), x => x.step() } } Ok(scons(op, inner(*l)?)) }, // Custom anonymous functions SCons(op, l) if (*op).is_fun() => { // Get function parts let ls = op.parts(); let argnames = ls.get(1).unwrap() .clone().parts(); let mut argnamevec = vec![]; for name in argnames.clone() { argnamevec.push(match name { Atom(Var(s)) => Ok(s), _ => Err("invalid entry in argument list (should be unreachable after type checker)".to_string()), }?); } let mut body = ls.get(4).unwrap().clone(); // Get argument parts let suppliedargs = l.parts(); for (name, value) in argnamevec.into_iter().zip(suppliedargs) { body = body.subst(&name, &value); } Ok(body) }, // Fixed point recursion SCons(op, l) if *op == Atom(Fix) => { let ls = match (*l).clone() { SCons(a, n) if *n == Atom(Nil) => a.clone(), _ => todo!() }.parts(); let argls = ls[1].clone(); let argname = match argls { Atom(Var(name)) => name, _ => todo!() }; let body = ls[4].clone(); Ok(body.subst(&argname, &scons(op, l))) }, // Arithmetic // t1, ..., tn integers // ------------------------------ // (+ t1 ... tn) -> t1 + ... + tn SCons(op, l) if *op == Atom(Add) => l.into_vec()? .iter() .fold( Ok(0), |acc, el| { match el { Int(x) => acc.map(|v| x+v), _ => Err( "'+' should only be given integers".to_string() ) } } ).map(|x| Atom(Int(x))), // t1, ..., tn integers // ------------------------------ // (* t1 ... tn) -> t1 * ... * tn SCons(op, l) if *op == Atom(Mul) => l.into_vec()? .iter() .fold( Ok(1), |acc, el| { match el { Int(x) => acc.map(|v| x*v), _ => Err( format!("'*' should only be given integers, found {:?}", el) ) } } ).map(|x| Atom(Int(x))), // t1,t2 integers // -------------------- // (- t1 t2) -> t1 - t2 SCons(op, l) if *op == Atom(Sub) => { let ls = l.into_vec()?; if ls.len() == 2 { match (ls[0].clone(), ls[1].clone()) { (Int(a), Int(b)) => Ok(Atom(Int(a - b))), _ => Err("'-' should be only given integers".to_string()) } } else { Err(format!("'-' should be given 2 arguments, found {}", ls.len())) } }, // t1,t2 integers // -------------------- // (/ t1 t2) -> t1 / t2 SCons(op, l) if *op == Atom(Div) => { let ls = l.into_vec()?; if ls.len() == 2 { match (ls[0].clone(), ls[1].clone()) { (_, Int(0)) => Err("division by zero".to_string()), (Int(a), Int(b)) => Ok(Atom(Int(a / b))), _ => Err("'/' should be only given integers".to_string()) } } else { Err(format!("'/' should be given 2 arguments, found {}", ls.len())) } }, // t1,t2 booleans // ----------------------- // (and t1 t2) -> t1 && t2 SCons(op, l) if *op == Atom(And) => { let ls = l.into_vec()?; if ls.len() == 2 { match (ls[0].clone(), ls[1].clone()) { (True, True) => Ok(Atom(True)), (True | False, True | False) => Ok(Atom(False)), _ => Err("'and' should be only given booleans".to_string()) } } else { Err(format!("'and' should be given 2 arguments, found {}", ls.len())) } }, // t1,t2 booleans // ----------------------- // (or t1 t2) -> t1 || t2 SCons(op, l) if *op == Atom(Or) => { let ls = l.into_vec()?; if ls.len() == 2 { match (ls[0].clone(), ls[1].clone()) { (False, False) => Ok(Atom(False)), (True | False, True | False) => Ok(Atom(True)), _ => Err("'or' should be only given booleans".to_string()) } } else { Err(format!("'or' should be given 2 arguments, found {}", ls.len())) } }, // t1,t2 booleans // -------------- // (xor t1 t2) -> t1 ^ t2 SCons(op, l) if *op == Atom(Xor) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (True, False) => Ok(Atom(True)), (False, True) => Ok(Atom(True)), (True | False, True | False) => Ok(Atom(False)), _ => Err("invalid args".to_string()), } }, // Not SCons(op, l) if *op == Atom(Not) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; match t1 { True => Ok(Atom(False)), False => Ok(Atom(True)), _ => Err("invalid args".to_string()), } }, // Lt SCons(op, l) if *op == Atom(Lt) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a < b).into()), _ => Err("invalid args".to_string()), } }, // Gt SCons(op, l) if *op == Atom(Gt) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a > b).into()), _ => Err("invalid args".to_string()), } }, // Le SCons(op, l) if *op == Atom(Le) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a <= b).into()), _ => Err("invalid args".to_string()), } }, // Ge SCons(op, l) if *op == Atom(Ge) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a >= b).into()), _ => Err("invalid args".to_string()), } }, // Eq SCons(op, l) if *op == Atom(Eq) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a == b).into()), _ => Err("invalid args".to_string()), } }, // Neq SCons(op, l) if *op == Atom(Neq) => { let ls = l.into_vec()?; let t1 = ls.get(0).ok_or("wrong list length".to_string())?; let t2 = ls.get(1).ok_or("wrong list length".to_string())?; match (t1, t2) { (Int(a), Int(b)) => Ok((a != b).into()), _ => Err("invalid args".to_string()), } }, // Nil in list SCons(op, _) if *op == Atom(Nil) => { Ok(scons(Vector, Nil)) }, // Print SCons(op, l) if *op == Atom(Print) => { println!("{}", *l); Ok(Atom(Nil)) }, t => Err(format!("unimplemented: {:?}.step()", t)), } } pub fn multistep(self) -> Result { match self.clone().step()? { x if x == self => Ok(self), x => x.multistep() } } }