5
\$\begingroup\$

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:

  1. I want eval to borrow the expression being evaluated, and I also want to evaluate Rc<Expr> (e.g. when applying a closure to an argument), so I've opted to have eval take &Rc<Expr> as its method receiver. Is this idiomatic? Is there a better choice for the receiver type here?

  2. I think I need to use Rc<..>'s liberally (in Expr, Value, and Env) because many values need to be shared (for instance, a particular environment may be extended by several different calls to apply, 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))));
    }
}
```
\$\endgroup\$
3
\$\begingroup\$

There is one part that immediately that immediately catches attention: all impl fn don't use Self, &Self or &mut Self as first attribute, but a wrapped variant:

impl Expr {
    pub fn eval(self: &Rc<Self>, env: &Rc<Env>) -> Option<Rc<Value>> {
        match &**self {
            ...
        }
    }
}

impl Value {
    pub fn apply(self: &Rc<Self>, arg: Rc<Value>) -> Option<Rc<Value>> {
        match &**self {
            ...
        }
    }
}

impl Env {
    pub fn get<'a>(self: &'a Rc<Self>, i: usize) -> Option<&'a Rc<Value>> {
        match &**self {
            ...
        }
    }

You noted that yourself in your first question, and indeed, there is another approach. Since Rc<Type> implements Borrow<Type>, we can use &Type instead of Rc<Type>, unless we clone self:

impl Expr {
    pub fn eval(&self, env: &Rc<Env>) -> Option<Rc<Value>> {
        match self {
            // rest unchanged
        }
    }
}

impl Value {
    pub fn apply(&self, arg: Rc<Value>) -> Option<Rc<Value>> {
        match self {
            // rest unchanged
        }
    }
}

impl Env {
    pub fn get(&self, i: usize) -> Option<&Rc<Value>> {
        match self {
            // rest unchanged
        }
    }
    // rest unchanged, as extend clones itself
}

Note that this also makes the match a lot simpler: we only match on self, not on &**self anymore.

This is a common idiom in Rust (and other languages that provide a similar interface): use the most generic variant that has all functions we need. Any Rc<Type> can yield &Type, but so can Arc<Type> and Box<Type>. By making the type more general, we are now able to use eval with Expr in almost all contexts (as long as we can borrow one):

    #[test]
    fn eval_with_rc() {
        let env = Rc::new(Env::Empty);

        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))));
    }
    
    #[test]
    fn eval_without_rc() {
        let env = Rc::new(Env::Empty);

        //        vvvvv no Rc here
        let expr = 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))));
    }
\$\endgroup\$
1
  • \$\begingroup\$ Thank you! Aside from answering my questions posted above, your response resolves several nagging questions that I didn't even know I had (especially with respect to the Borrow<T> trait). \$\endgroup\$ Sep 19 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.