Simple expression evaluator in Rust

Question

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))));
    }
}
```

Answer 1

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))));
    }