Skip to content

Instantly share code, notes, and snippets.

@godfat
Created Aug 15, 2009
Embed
What would you like to do?
implicit def envToTreeMap(env: Env) = env.map
abstract class Val
case class Num(n: Int) extends Val
case class Cls(f: Val => Val) extends Val
case object Err extends Val
abstract class Expr
case class Lit( n: Int) extends Expr
case class Var( n: String) extends Expr
case class Lam( n: String, e: Expr) extends Expr
case class App(e0: Expr, e1: Expr) extends Expr
case class Add(e0: Expr, e1: Expr) extends Expr
import scala.collection.immutable.TreeMap
class Env(val map: TreeMap[String, Val]){
def this() = this(new TreeMap[String, Val])
def insert(k: String, v: Val): Env = new Env(map.insert(k, v))
def eval(expr: Expr): Val = expr match{
case Lit(n) => Num(n)
case Var(n) => map.get(n) match{
case Some(v) => v
case None => Err
}
case Lam( n, e) => Cls((arg: Val) => {
insert(n, arg).eval(e)
})
case App(e0, e1) => eval(e0) match{
case Cls(f) => f(eval(e1))
case _ => Err
}
case Add(e0, e1) => (eval(e0), eval(e1)) match{
case (Num(e0), Num(e1)) => Num(e0 + e1)
case _ => Err
}
}
}
val expr: Expr = App(Lam("x", Add(Var("x"), Var("y"))), Lit(2))
val env: Env = (new Env).insert("y", Num(5))
println(env.eval(expr))
// Num(7)
// De Bruijn index
implicit def env2ToList(env: Env2) = env.list
abstract class Expr2
case class Lit2( n: Int) extends Expr2
case class Var2( n: Int) extends Expr2
case class Lam2( e: Expr2) extends Expr2
case class App2(e0: Expr2, e1: Expr2) extends Expr2
case class Add2(e0: Expr2, e1: Expr2) extends Expr2
class Env2(val list: List[Val]){
def this() = this(List())
def ::(v: Val) = new Env2(v :: list)
def eval(expr: Expr2): Val = expr match{
case Lit2(n) => Num(n)
case Var2(n) => list(n - 1)
case Lam2(e) => Cls((arg: Val) => {
(arg :: this).eval(e)
})
case App2(e0, e1) => eval(e0) match{
case Cls(f) => f(eval(e1))
case _ => Err
}
case Add2(e0, e1) => (eval(e0), eval(e1)) match{
case (Num(e0), Num(e1)) => Num(e0 + e1)
case _ => Err
}
}
}
val expr2: Expr2 = App2(Lam2(Add2(Var2(1), Var2(2))), Lit2(2))
val env2: Env2 = Num(5) :: new Env2
println(env2.eval(expr2))
// Num(7)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment