Basic Rust implementation of an interpreter for the untyped lambda calculus

untyped.rs

// A basic intepreter for the untyped lambda calculus

enum Term
  { Num(int)
  , Var(~str)
  , Lam(~str, ~Term)
  , App(~Term, ~Term)
  , Let(~str, ~Term, ~Term)
  }

enum Val
  { VNum(int)
  , VLam(~str, ~Term, ~Env)
  }

enum Env
  { Empty
  , Binding(~str, ~Val, ~Env)
  }

fn lookup(s : &str, e : &Env) -> ~Val
  { match *e
      { Empty => fail!(fmt!("Couldn't find %s in environment", s))
      , Binding(ref n, ref v, ref p) =>
          { if core::str::eq_slice(*n, s)
              { copy *v }
            else
              { lookup(s, *p) }
          }
      }
  }

fn eval(t : &Term, e : &Env) -> ~Val
  { match *t
      { Num(num) => ~VNum(num)
      , Var(ref str) => lookup(*str, e)
      , Lam(ref s, ref b) => ~VLam(copy *s, copy *b, ~copy *e)
      , App(ref f, ref x) =>
          { match *(eval(*f, e))
              { VLam(ref arg, ref body, ref env) =>
                  { let newEnv = Binding
                      ( copy *arg
                      , eval(*x, e)
                      , copy *env
                      )
                  ; eval(*body, &newEnv)
                  }
                _ => fail!()
              }
          }
      , Let(ref s, ref t, ref b) =>
          { let newEnv = Binding
              ( copy *s
              , eval(*t, e)
              , ~copy *e
              )
          ; eval(*b, &newEnv)
          }
      }
  }

fn main()
  { let s1 = ~App(~App(~Lam(~"x",~Lam(~"y", ~Var(~"x"))),~Num(5)),~Num(8))
  ; let s2 = ~Let( ~"f"
                 , ~App(~Lam(~"x",~Lam(~"y", ~Var(~"x"))),~Num(2))
                 , ~App(~Var(~"f"),~Num(4))
                 )
  ; let e = Empty
  ; println(fmt!("s1: %?", eval(s1, &e)))
  ; println(fmt!("s2: %?", eval(s2, &e)))
  }