diff options
Diffstat (limited to 'test/files/presentation/callcc-interpreter')
-rw-r--r-- | test/files/presentation/callcc-interpreter/Runner.scala | 3 | ||||
-rw-r--r-- | test/files/presentation/callcc-interpreter/src/CallccInterpreter.scala | 86 |
2 files changed, 89 insertions, 0 deletions
diff --git a/test/files/presentation/callcc-interpreter/Runner.scala b/test/files/presentation/callcc-interpreter/Runner.scala new file mode 100644 index 0000000000..1ef3cf9025 --- /dev/null +++ b/test/files/presentation/callcc-interpreter/Runner.scala @@ -0,0 +1,3 @@ +import scala.tools.nsc.interactive.tests._ + +object Test extends InteractiveTest
\ No newline at end of file diff --git a/test/files/presentation/callcc-interpreter/src/CallccInterpreter.scala b/test/files/presentation/callcc-interpreter/src/CallccInterpreter.scala new file mode 100644 index 0000000000..ce3b996b96 --- /dev/null +++ b/test/files/presentation/callcc-interpreter/src/CallccInterpreter.scala @@ -0,0 +1,86 @@ +object callccInterpreter { + + type Answer = Value + + /** + * A continuation monad. + */ + case class M[A](in: (A => Answer) => Answer) { + def bind[B](k: A => M[B]) = M[B](c => in (a => k(a) in c)) + def map[B](f: A => B): M[B] = bind(x => unitM(f(x))) + def flatMap[B](f: A => M[B]): M[B] = bind(f) + } + + def unitM[A](a: A) /*?*/ = M[A](c => c(a)) + + def id[A] /*?*/ = (x: A) => x + def showM(m: M[Value]) /*?*/ = (m in id).toString() + + def callCC[A](h: (A => M[A]) => M[A]) = + M[A](c => h(a => M[A](d => c(a))) in c) + + type Name = String + + trait Term + case class Var(x: Name) extends Term + case class Con(n: int) extends Term + case class Add(l: Term, r: Term) extends Term + case class Lam(x: Name, body: Term) extends Term + case class App(fun: Term, arg: Term) extends Term + case class Ccc(x: Name, t: Term) extends Term + + trait Value + case object Wrong extends Value { + override def toString() = "wrong" + } + case class Num(n: Int) extends Value { + override def toString() = n.toString() + } + case class Fun(f: Value => M[Value]) extends Value { + override def toString() = "<function>" + } + + type Environment = List[Pair[Name, Value]] + + def lookup(x: Name, e: Environment): M[Value] = e match { + case List() => unitM(Wrong) + case Pair(y, b) :: e1 => if (x == y) unitM(b) else lookup(x, e1) + } + + def add(a: Value, b: Value) /*?*/ = Pair(a, b) match { + case Pair(Num(m), Num(n)) => this./*!*/unitM(Num(m + n)) + case _ => unitM(Wrong) + } + + def apply(a: Value, b: Value): M[Value] = a match { + case Fun(k) => k(b) + case _ => unitM(Wrong) + } + + def interp(t: Term, e: Environment): M[Value] = t match { + case Var(x) => lookup(x, e) + case Con(n) => unitM(Num(n)) + case Add(l, r) => for (val a <- interp(l, e); + val b <- interp(r, e); + val c <- add(a, b)) + yield c + case Lam(x, t) => unitM(Fun(a => interp(t, Pair(x, a) :: e))) + case App(f, t) => for (val a <- interp(f, e); + val b <- interp(t, e); + val c <- apply(a, b)) + yield c + case Ccc(x, t) => callCC(k => interp(t, Pair(x, Fun(k)) :: e)) + } + + def test(t: Term): String = showM(interp(t, List())) + + val term0 = App(Lam("x", Add(Var("x"), Var("x"))), Add(Con(10), Con(11))) + val term1 = App(Con(1), Con(2)) + val term2 = Add(Con(1), Ccc("k", Add(Con(2), App(Var("k"), Con(4))))) + + def main(args: Array[String]) { + println(test(term0)) + println(test(term1)) + println(test(term2)) + } +}
\ No newline at end of file |