a basic evaluator in rust

main.rs

use std::collections::HashMap;
use std::rc::Rc;

macro_rules! ident_list {
    () => {
        vec![]
    };
    ($a:ident) => {
        vec![stringify!(a)]
    };
    ($a:ident $b:ident) => {
        vec![stringify!(a), stringify!(b)]
    };
}

macro_rules! expr {
    ((lambda ($($p:ident)*) $b:tt)) => {
        Expression::Lambda {
            params: ident_list!($($p)*),
            body: Rc::new(expr! {$b}),
        }
    };

    (($($r:tt)+)) => {
        Expression::Apply(vec![$(expr!{$r}),+])
    };

    ($x:ident) => {
        Expression::Ident(stringify!($x))
    };

    ($x:expr) => {
        Expression::Integer($x)
    };
}

fn main() {
    let expr = expr! {((lambda (a b) b) 12 34)};
    let ctx = EvaluationContext::new();
    println!("{:?}", ctx.eval(&expr));
}

#[derive(Debug, Clone)]
enum Value {
    Bool(bool),
    Int(i64),
    Lambda {
        params: Vec<&'static str>,
        body: Expression,
    },
}

struct EvaluationContext {
    env: HashMap<&'static str, Value>,
}

impl EvaluationContext {
    pub fn new() -> Self {
        EvaluationContext {
            env: HashMap::new(),
        }
    }

    pub fn with_local_env(&self, params: &[&'static str], values: Vec<Value>) -> Self {
        let mut env = HashMap::new();
        for (p, a) in params.into_iter().zip(values.into_iter()) {
            env.insert(*p, a);
        }
        EvaluationContext { env }
    }

    pub fn lookup(&self, name: &'static str) -> Value {
        self.env[name].clone()
    }
}

impl EvaluationContext {
    fn eval(&self, expr: &Expression) -> Value {
        use Expression::*;
        match expr {
            Boolean(b) => Value::Bool(*b),
            Integer(x) => Value::Int(*x),
            Ident(x) => self.lookup(x),
            Lambda { params, body } => Value::Lambda {
                params: params.clone(),
                body: substitute(body, &self.env),
            },
            Apply(items) => match self.eval(&items[0]) {
                Value::Lambda { params, body } => {
                    let args = items.iter().skip(1).map(|a| self.eval(a)).collect();
                    let local_context = self.with_local_env(&params, args);
                    local_context.eval(&body)
                }
                _ => unimplemented!(),
            },
        }
    }
}

fn substitute(expr: &Expression, mapping: &HashMap<&'static str, Value>) -> Expression {
    use Expression::*;
    match expr {
        Boolean(b) => Boolean(*b),
        Integer(x) => Integer(*x),
        Ident(s) => Ident(*s),
        Lambda { params, body } => {
            let mut mapping = mapping.clone();
            for p in params {
                mapping.remove(p);
            }
            Lambda {
                params: params.clone(),
                body: Rc::new(substitute(body, &mapping)),
            }
        }
        Apply(items) => Apply(items.iter().map(|a| substitute(a, mapping)).collect()),
    }
}

#[derive(Debug, Clone)]
enum Expression {
    Boolean(bool),
    Integer(i64),
    Ident(&'static str),
    Lambda {
        params: Vec<&'static str>,
        body: Rc<Expression>,
    },
    Apply(Vec<Expression>),
}