Skip to content

Instantly share code, notes, and snippets.

@aisamanra
Last active April 10, 2018 23:45
Show Gist options
  • Save aisamanra/5973863 to your computer and use it in GitHub Desktop.
Save aisamanra/5973863 to your computer and use it in GitHub Desktop.
Basic Rust implementation of an interpreter for the untyped lambda calculus
// 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)))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment