What follows is an evaluator for a toy expression language. The language includes functions of a single variable (with lexical binding), along with numbers and a way to apply functions to expressions. For the sake of simplicity, bound variables are represented using De Bruijn indices.
The main questions I have are:
I want
eval
to borrow the expression being evaluated, and I also want to evaluateRc<Expr>
(e.g. when applying a closure to an argument), so I've opted to haveeval
take&Rc<Expr>
as its method receiver. Is this idiomatic? Is there a better choice for the receiver type here?I think I need to use
Rc<..>
's liberally (inExpr
,Value
, andEnv
) because many values need to be shared (for instance, a particular environment may be extended by several different calls toapply
, the body in a given closure may be evaluated with several different args on different occasions, etc.). Is this the case? And if so, have I done so in an idiomatic fashion?
use std::rc::Rc;
#[derive(Debug, PartialEq)]
pub enum Expr {
Num(isize),
Index(usize),
Abs { body: Rc<Expr> },
App { rator: Rc<Expr>, rand: Rc<Expr> },
}
#[derive(Debug, PartialEq)]
pub enum Value {
Num(isize),
Closure { body: Rc<Expr>, env: Rc<Env> },
}
impl Expr {
pub fn eval(self: &Rc<Self>, env: &Rc<Env>) -> Option<Rc<Value>> {
match &**self {
Expr::Num(n) => Some(Rc::new(Value::Num(*n))),
Expr::Index(i) => env.get(*i).map(Rc::clone),
Expr::Abs { body } => Some(Rc::new(Value::Closure {
body: Rc::clone(body),
env: Rc::clone(env),
})),
Expr::App { rator, rand } => {
let op = rator.eval(env)?;
let arg = rand.eval(env)?;
op.apply(arg)
}
}
}
}
impl Value {
pub fn apply(self: &Rc<Self>, arg: Rc<Value>) -> Option<Rc<Value>> {
match &**self {
Value::Closure { body, env } => {
let env = env.extend(arg);
body.eval(&env)
}
_ => None,
}
}
}
// An environment is either empty, or an extension of another environment.
#[derive(Debug, PartialEq)]
pub enum Env {
Empty,
Ext(Rc<Value>, Rc<Env>),
}
impl Env {
pub fn get<'a>(self: &'a Rc<Self>, i: usize) -> Option<&'a Rc<Value>> {
match &**self {
Env::Empty => None,
Env::Ext(value, rest) => {
if i == 0 {
Some(value)
} else {
rest.get(i - 1)
}
}
}
}
pub fn extend(self: &Rc<Self>, value: Rc<Value>) -> Rc<Self> {
Rc::new(Env::Ext(value, Rc::clone(self)))
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn eval() {
let env = Rc::new(Env::Empty);
// A representation of
//
// ((lambda (x) x) 42)
//
let expr = Rc::new(Expr::App {
rator: Rc::new(Expr::Abs {
body: Rc::new(Expr::Index(0)),
}),
rand: Rc::new(Expr::Num(42)),
});
let value = expr.eval(&env);
assert_eq!(value, Some(Rc::new(Value::Num(42))));
}
}
```