1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
//Class hierarchy
trait Term[a]
object Var{ def unapply[a](x:Var[a]) = Some(x.name) }
class Var[a] (val name : String) extends Term[a]
object Num{ def unapply(x:Num) = Some(x.value) }
class Num (val value : int) extends Term[int]
object Lam{ def unapply[b,c](l:Lam[b,c]) = Some{l.x,l.e}}
class Lam[b, c] (val x : Var[b], val e : Term[c]) extends Term[b => c]
object App{ def unapply[b,c](a:App[b,c]) = Some{a.f,a.e}}
class App[b, c] (val f : Term[b => c], val e : Term[b]) extends Term[c]
object Suc{ def unapply(a:Suc) = true }
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)
}
object Test {
// Evaluation :
def eval[a](t : Term[a], env : Env): a = t match {
case v : Var[b] => env(v) // a = b
case n @ Num(value) => value // a = int
case i @ Suc() => { y: int => y + 1 } // a = int=>int
case f @ Lam[b,c](x,e) => { y: b => eval(e, env.extend(x, y))} // a = b=>c
case a @ App(f,e) => eval(f, env)(eval(e, env)) // a = c
}
}
|
