rust-eval

eval.rs

use std::collections::HashMap;
use strum_macros::Display;

/// EvalErr is returned by eval() if evaluation fails.
#[derive(Debug)]
pub enum EvalErr {
    WrongExpr { wanted: Expr, got: Expr },
    WrongArity { wanted: usize, got: usize },
    UnknownSymbol { symbol: String },
    NotInvokable { got: 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: &String) -> Option<Expr>;
}

/// An expression that can evaluated using eval().
#[derive(Debug, Display, Clone, PartialEq, PartialOrd)]
pub enum Expr {
    // Atoms - These evaluate to themselves.
    Null,
    Bool(bool),
    Int64(i64),
    Float64(f64),
    Func(fn(env: &mut dyn Env, args: &[Expr]) -> Result<Expr, EvalErr>),

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

/// Evaluates the given Expr and returns the result or error if any.
/// env will be used for resolving any symbols.
pub fn eval(env: &mut dyn Env, expr: &Expr) -> Result<Expr, EvalErr> {
    expr.eval(env)
}

impl Expr {
    fn eval(&self, env: &mut dyn Env) -> Result<Expr, EvalErr> {
        match self {
            Self::List(list) => {
                if list.len() == 0 {
                    return Ok(Self::Null);
                }

                let (first, rest) = list.split_first().unwrap();
                let op = first.eval(env)?;
                match op {
                    Expr::Func(func) => func(env, rest),
                    _ => Err(EvalErr::NotInvokable { got: op }),
                }
            }
            Self::Symbol(sym) => match env.resolve(sym) {
                Some(val) => Ok(val.clone()),
                None => Err(EvalErr::UnknownSymbol {
                    symbol: sym.clone(),
                }),
            },
            _ => Ok(self.clone()),
        }
    }
}

/// Implements the Env trait using a immutable hash-map - So, only
/// supports resolving variables but not creating/updating.
pub struct StaticEnv<'a>(&'a HashMap<String, Expr>);

impl<'a> StaticEnv<'a> {
    pub fn new(data: &'a HashMap<String, Expr>) -> Self {
        Self(data)
    }
}

impl<'a> Env for StaticEnv<'a> {
    fn resolve(&self, symbol: &String) -> Option<Expr> {
        match self.0.get(symbol) {
            Some(val) => Some(val.clone()),
            None => None,
        }
    }
}

eval_bench.rs

use slurp_rs::eval::*;
use std::{collections::HashMap, f64::consts::PI};

use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn criterion_benchmark(c: &mut Criterion) {
    let mut data = HashMap::new();

    let sym_pi = "pi".to_string();
    let sym_mul = "*".to_string();
    data.insert(sym_pi.clone(), Expr::Float64(PI));
    data.insert(
        sym_mul.clone(),
        Expr::Func(|env, args| {
            if args.len() == 0 {
                return Err(EvalErr::WrongArity { wanted: 1, got: 0 });
            }

            let mut vals: Vec<f64> = vec![];
            for arg in args {
                match eval(env, arg) {
                    Ok(res) => match res {
                        Expr::Float64(f) => vals.push(f),
                        _ => {
                            return Err(EvalErr::WrongExpr {
                                wanted: Expr::Float64(0.0),
                                got: res,
                            })
                        }
                    },
                    Err(e) => return Err(e),
                }
            }

            Ok(Expr::Float64(vals.iter().fold(1.0, |acc, &x| acc * x)))
        }),
    );

    let mut env = StaticEnv::new(&data);

    c.bench_function("eval null", |b| {
        b.iter(|| eval(&mut env, black_box(&Expr::Null)))
    });

    c.bench_function("eval symbol", |b| {
        b.iter(|| eval(&mut env, black_box(&Expr::Symbol(sym_pi.clone()))))
    });

    c.bench_function("eval function call", |b| {
        // Emulate 2*pi*r --> (* 2.0 pi 10.0)
        let expr = &Expr::List(vec![
            Expr::Symbol(sym_mul.clone()),
            Expr::Float64(2.0),
            Expr::Symbol(sym_pi.clone()),
            Expr::Float64(10.0),
        ]);

        b.iter(|| eval(&mut env, black_box(expr)))
    });
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);