lambda.scala

lambda.scala

// c.f. "Matching Objects With Patterns",p.19
object lambda {
  //Class hierarchy
  trait Term[a]
  class Var[a] (val name : String) extends Term[a]
  class Num (val value : Int) extends Term[Int]
  class Lam[b, c] (val x : Var[b], val e : Term[c]) extends Term[b => c]
  class App[b, c] (val f : Term[b => c], val e : Term[b]) extends Term[c]
  class Suc () extends Term[Int => Int]
  // Environments:
  abstract class Env {
    def apply[a](v : Var[a]): a
    def extend[a](v : Var[a], x : a) = new Env {
      def apply[b](w: Var[b]): b = w match {
        case _: v.type => x // v eq w, hence a = b
        case _ =>  Env.this.apply(w)
  }}}
  object empty extends Env {
    def apply[a](x : Var[a]): a = throw new Error("not found : "+x.name) 
  }
  // Evaluation:
  def eval[a](t : Term[a], env : Env): a = t match {
    case v : Var[b] => env(v) // a = b
    case n : Num => n.value // a = Int
    case i : Suc => { y : Int => y + 1 } // a = Int=>Int
    case f : Lam[b, c] => { y : b => eval(f.e, env.extend(f.x, y)) } // a = b=>c
    case a : App[b, c] => eval(a.f, env)(eval(a.e, env)) // a = c
  }
}