lisp.rs

/// An expression that can be evaluated using eval().
#[derive(Debug, Clone, PartialEq, PartialOrd)]
pub enum Expr {
    // Atoms - These evaluate to themselves.
    Null,
    Bool(bool),
    Int(i64),
    Float(f64),

    // Eval types - These require logic for evaluation.
    Symbol(String),
    List(Vec<Expr>),
}

/// Env is used to resolve symbols while evaluating rules.
pub trait Env {
    /// resolve will be invoked to resolve value for a symbol. Env
    /// implementations are free to resolve using any approach (e.g.,
    /// lookup table, external api call, etc.).
    fn resolve(&self, symbol: &str) -> Option<Expr>;

    /// Apply an operator to the given list of unevaluated expressions.
    /// Env should evaluate the arguments as needed.
    fn apply(&self, op: &str, args: &[Expr]) -> Result<Expr, EvalErr>;
}


/// Evaluates the given Expr and returns the result or error if any.
/// env will be used for resolving any symbols.
pub fn eval(env: &impl Env, expr: &Expr) -> Result<Expr, EvalErr> {
    match expr {
        Expr::List(list) => {
            if list.is_empty() {
                return Ok(Expr::Null);
            }

            let (first, rest) = list.split_first().unwrap();

            if let Expr::Symbol(op) = first {
                env.apply(op, rest)
            } else {
                Err(EvalErr::Error(
                    "first entry in list must be operator name".to_string(),
                ))
            }
        }
        Expr::Symbol(sym) => match env.resolve(sym) {
            Some(val) => Ok(val.clone()),
            None => Err(EvalErr::UnknownSymbol {
                symbol: sym.clone(),
            }),
        },
        _ => Ok(expr.clone()),
    }
}