--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/README Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,21 @@
+
+The packages can be compiled with
+
+ scalac *.scala
+
+If you get an error, it is advisable to clean
+out the existing class-files
+
+ rm */*.class
+
+
+After compilation, the examples can be run in
+the REPL as well as in scala. For example
+
+ scala -cp $PWD ex.scala
+
+
+The directory can be cleaned with
+
+ rm -rf *~ lib turing abacus comp1
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/abacus.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,57 @@
+package object abacus {
+
+import lib._
+
+// Abacus machines
+sealed abstract class AInst
+case class Inc(n: Int) extends AInst
+case class Dec(n: Int, l: Int) extends AInst
+case class Goto(l: Int) extends AInst
+
+type AProg = List[AInst]
+type Regs = Map[Int, Int]
+
+case class AConfig(s: Int, regs: Regs)
+
+case class Abacus(p: AProg) {
+
+ def ++ (that: Abacus) = Abacus(this.p ::: that.p)
+
+ def shift(offset: Int, jump: Int) = Abacus(p.map(_ match {
+ case Inc(n) => Inc(n)
+ case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset)
+ case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset)
+ }))
+
+ def adjust(old_jump: Int, jump: Int) = Abacus(p.map(_ match {
+ case Inc(n) => Inc(n)
+ case Dec(n, l) => if (l == old_jump) Dec(n, jump) else Dec(n, l)
+ case Goto(l) => if (l == old_jump) Goto(jump) else Goto(l)
+ }))
+
+ def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
+ case (None, _) => cf
+ case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
+ case (Some(Dec(n, l)), s) => {
+ if (dget(cf.regs, n) == 0) AConfig(l, cf.regs)
+ else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
+ }
+ case (Some(Goto(l)), _) => AConfig(l, cf.regs)
+ }
+
+ def steps(cf: AConfig, n: Int) : AConfig = n match {
+ case 0 => cf
+ case n => steps(step(cf), n - 1)
+ }
+
+ def steps(regs: Regs, n: Int) : AConfig = steps(AConfig(0, regs), n)
+
+ def run(cf: AConfig) : AConfig = {
+ if (cf.s >= p.length || cf.s < 0) cf else run(step(cf))
+ }
+
+ def run(regs: Regs): Regs = run(AConfig(0, regs)).regs
+}
+
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/comp1.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,73 @@
+package object comp1 {
+
+import lib._
+import turing._
+import abacus._
+
+// TMs used in the translation
+
+val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4),
+ (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
+ (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
+
+val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
+ (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
+ (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
+ (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
+ (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
+ (R, 0), (WBk, 16)))
+
+val TMGoto = TM(List((Nop, 1), (Nop, 1)))
+
+def TMFindnth(n: Int) : TM = n match {
+ case 0 => TM(Nil)
+ case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
+}
+
+def TMMopup(n: Int) = {
+ def TMMopup1(n: Int) : TM = n match {
+ case 0 => TM(Nil)
+ case n => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
+ }
+
+ val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
+ (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
+
+ TMMopup1(n) ++ TMMopup2.shift(2 * n)
+}
+
+
+
+// Abacus to TM translation
+def layout(p: AProg) = p.map(_ match {
+ case Inc(n) => 2 * n + 9
+ case Dec(n, _) => 2 * n + 16
+ case Goto(n) => 1
+})
+
+def start(p: AProg, n: Int) = layout(p).take(n).sum + 1
+
+def compile_Inc(s: Int, n: Int) =
+ TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
+
+def compile_Dec(s: Int, n: Int, e: Int) =
+ TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
+
+def compile_Goto(s: Int) = TMGoto.shift(s - 1)
+
+def compile(p: AProg, s: Int, i: AInst) = i match {
+ case Inc(n) => compile_Inc(s, n)
+ case Dec(n, e) => compile_Dec(s, n, start(p, e))
+ case Goto(e) => compile_Goto(start(p, e))
+}
+
+// component TMs for each instruction
+def TMs(p: AProg) = {
+ val ss = (0 until p.length).map (start(p,_))
+ (ss zip p).map{case (n, i) => compile(p, n, i)}
+}
+
+def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)
+
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/ex.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,47 @@
+import lib._
+import turing._
+import abacus._
+import comp1._
+
+// Turing machine examples
+val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3),
+ (L, 4), (L, 4), (L, 5), (R, 11), (R, 6),
+ (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9),
+ (R, 8), (L, 10), (L, 9), (L, 10), (L, 5),
+ (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12),
+ (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
+
+println("TMCopy: " + (TMCopy.run(Tape(3))))
+println("TMfindnth: " + (TMFindnth(3).run(Tape(1,2,3,4,5))))
+println("TMMopup: " + (TMMopup(3).run(Tape(1,2,3,4,5))))
+
+
+// Abacus machine examples
+def Copy(in: Int, out: Int, jump: Int) =
+ Abacus(List(Dec(in, jump), Inc(out), Goto(0)))
+
+def Plus(m: Int, n: Int, tmp: Int, jump: Int) =
+ Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4)))
+
+def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) =
+ Abacus(List(Dec(in1, jump))) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0)
+
+def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = {
+ Abacus(List(Inc(out), Dec(in1, jump))) ++
+ Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++
+ Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
+}
+
+println("Copy: 3 " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
+println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
+println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
+println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
+
+
+// Abacus-to-TM translation examples
+println("Compiled Copy 3: " + toTM(Copy(0, 1, Int.MaxValue).p).run(Tape(3,0,0)))
+println("Compiled Plus 3 + 4: " + toTM(Plus(0, 1, 2, Int.MaxValue).p).run(Tape(3,4,0,0)))
+println("Compiled Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(Tape(3,5,0,0)))
+println("Compiled Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(Tape(3,4,0,0,0)))
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/lib.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,20 @@
+package object lib {
+
+//some list functions
+def tl[A](xs: List[A]) : List[A] = xs match {
+ case Nil => Nil
+ case x::xs => xs
+}
+
+def hd[A](xs: List[A]) : A = xs.head
+
+def nth_of[A](xs: List[A], n: Int) =
+ if (n <= xs.length) Some(xs(n)) else None
+
+//some map functions
+def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
+
+//some string functions
+def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/recs.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,46 @@
+package object recs {
+
+
+//Recursive Functions
+abstract class Rec {
+ def eval(ns: List[Int]) : Int
+}
+case object Z extends Rec {
+ override def eval(ns: List[Int]) = ns match {
+ case n::Nil => 0
+ case _ => throw new IllegalArgumentException("Z: args")
+ }
+}
+case object S extends Rec {
+ override def eval(ns: List[Int]) = ns match {
+ case n::Nil => n + 1
+ case _ => throw new IllegalArgumentException("S: args")
+ }
+}
+case class Id(n: Int, m: Int) extends Rec {
+ override def eval(ns: List[Int]) =
+ if (ns.length == n && m < n) ns(m)
+ else throw new IllegalArgumentException("Id: args")
+}
+case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {
+ override def eval(ns: List[Int]) =
+ if (ns.length == n) f.eval(gs.map(_.eval(ns)))
+ else throw new IllegalArgumentException("Cn: args")
+}
+case class Pr(n: Int, f: Rec, g: Rec) extends Rec {
+ override def eval(ns: List[Int]) =
+ if (ns.length == n - 1) {
+ if (ns.last == 0) f.eval(ns.init)
+ else {
+ val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))
+ g.eval(ns.init ::: List(ns.last - 1, r))
+ }
+ }
+ else throw new IllegalArgumentException("Cn: args")
+}
+case class Mn(n: Int, f: Rec) extends Rec {
+ override def eval(ns: List[Int]) = 0
+
+}
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/scala/turing.scala Thu Feb 21 16:07:40 2013 +0000
@@ -0,0 +1,100 @@
+package object turing {
+
+import scala.annotation.tailrec
+import lib._
+
+sealed abstract class Cell {
+ def * (n: Int) : List[Cell] = n match {
+ case 0 => Nil
+ case n => this :: this * (n - 1)
+ }
+}
+case object Bk extends Cell { override def toString = "0" }
+case object Oc extends Cell { override def toString = "1" }
+
+sealed abstract class Action
+case object WBk extends Action
+case object WOc extends Action
+case object R extends Action
+case object L extends Action
+case object Nop extends Action
+
+type State = Int
+type Inst = (Action, State)
+type Prog = List[Inst]
+
+//tapes
+case class Tape(l: List[Cell], r: List[Cell]) {
+
+ def update(a: Action) = a match {
+ case WBk => Tape(l, Bk::tl(r))
+ case WOc => Tape(l, Oc::tl(r))
+ case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)
+ case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))
+ case Nop => Tape(l, r)
+ }
+
+ def read = r match {
+ case Nil => Bk
+ case x::_ => x
+ }
+
+ override def toString = join(l.reverse) + ">" + join(r)
+}
+
+//standard tapes
+object Tape {
+ def apply(ns: Int*) : Tape =
+ Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
+}
+
+
+// configurations
+case class Config(s: State, tp: Tape) {
+ def is_final = s == 0
+
+ override def toString = tp.toString
+}
+
+
+// Turing machines
+case class TM(p: Prog) {
+
+ def ++ (that: TM) = TM(this.p ::: that.p)
+
+ def shift(n: Int) =
+ TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
+ def adjust(n: Int) : TM =
+ TM(p.map{case (a, s) => (a, if (s == 0) n else s)})
+ def adjust : TM = adjust(p.length / 2 + 1)
+
+ def fetch(s: State, a: Cell) = (s, a) match {
+ case (0, _) => (Nop, 0)
+ case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
+ case None => (Nop, 0)
+ case Some(i) => i
+ }
+ case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
+ case None => (Nop, 0)
+ case Some(i) => i
+ }
+ }
+
+ def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {
+ case (a, s_next) => Config(s_next, cf.tp.update(a))
+ }
+
+ def steps(cf: Config, n: Int) : Config = n match {
+ case 0 => cf
+ case n => steps(step(cf), n - 1)
+ }
+
+ @tailrec
+ final def run(cf: Config) : Config = {
+ if (cf.is_final) cf else run(step(cf))
+ }
+
+ def run(tp: Tape) : Tape = run(Config(1, tp)).tp
+}
+
+}
--- a/turing.scala Thu Feb 21 14:49:26 2013 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,313 +0,0 @@
-import scala.annotation.tailrec
-
-//some list functions
-def tl[A](xs: List[A]) : List[A] = xs match {
- case Nil => Nil
- case x::xs => xs
-}
-
-def hd[A](xs: List[A]) : A = xs.head
-
-def nth_of[A](xs: List[A], n: Int) =
- if (n <= xs.length) Some(xs(n)) else None
-
-
-//some map functions
-def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
-
-
-//some string functions
-def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
-
-
-
-sealed abstract class Cell {
- def * (n: Int) : List[Cell] = n match {
- case 0 => Nil
- case n => this :: this * (n - 1)
- }
-}
-case object Bk extends Cell { override def toString = "0" }
-case object Oc extends Cell { override def toString = "1" }
-
-sealed abstract class Action
-case object WBk extends Action
-case object WOc extends Action
-case object R extends Action
-case object L extends Action
-case object Nop extends Action
-
-type State = Int
-type Inst = (Action, State)
-type Prog = List[Inst]
-
-//tapes
-case class Tape(l: List[Cell], r: List[Cell]) {
- def update(a: Action) = a match {
- case WBk => Tape(l, Bk::tl(r))
- case WOc => Tape(l, Oc::tl(r))
- case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)
- case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))
- case Nop => Tape(l, r)
- }
-
- def read = r match {
- case Nil => Bk
- case x::_ => x
- }
-
- override def toString = join(l.reverse) + ">" + join(r)
-}
-
-// standard tapes
-class STape(ns: Int*) extends
- Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
-
-
-// configurations
-case class Config(s: State, tp: Tape) {
- def is_final = s == 0
-
- override def toString = tp.toString
-}
-
-
-// Turing machines
-case class TM(p: Prog) {
-
- def ++ (that: TM) = TM(this.p ::: that.p)
-
- def shift(n: Int) =
- TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
- def adjust(n: Int) : TM =
- TM(p.map{case (a, s) => (a, if (s == 0) n else s)})
- def adjust : TM = adjust(p.length / 2 + 1)
-
- def fetch(s: State, a: Cell) = (s, a) match {
- case (0, _) => (Nop, 0)
- case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
- case None => (Nop, 0)
- case Some(i) => i
- }
- case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
- case None => (Nop, 0)
- case Some(i) => i
- }
- }
-
- def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {
- case (a, s_next) => Config(s_next, cf.tp.update(a))
- }
-
- def steps(cf: Config, n: Int) : Config = n match {
- case 0 => cf
- case n => steps(step(cf), n - 1)
- }
-
- @tailrec
- final def run(cf: Config) : Config = {
- if (cf.is_final) cf else run(step(cf))
- }
-
- def run(tp: Tape) : Tape = run(Config(1, tp)).tp
-}
-
-
-// Turing machine examples
-val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3),
- (L, 4), (L, 4), (L, 5), (R, 11), (R, 6),
- (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9),
- (R, 8), (L, 10), (L, 9), (L, 10), (L, 5),
- (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12),
- (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
-
-def TMFindnth(n: Int) : TM = n match {
- case 0 => TM(Nil)
- case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
-}
-
-def TMMopup(n: Int) = {
- def TMMopup1(n: Int) : TM = n match {
- case 0 => TM(Nil)
- case n => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
- }
-
- val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
- (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
-
- TMMopup1(n) ++ TMMopup2.shift(2 * n)
-}
-
-println("TMCopy: " + (TMCopy.run(new STape(3))))
-println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
-println("TMMopup: " + (TMMopup(3).run(new STape(1,2,3,4,5))))
-
-
-// Abacus machines
-sealed abstract class AInst
-case class Inc(n: Int) extends AInst
-case class Dec(n: Int, l: Int) extends AInst
-case class Goto(l: Int) extends AInst
-
-
-type AProg = List[AInst]
-type Regs = Map[Int, Int]
-
-case class AConfig(s: Int, regs: Regs)
-
-case class Abacus(p: AProg) {
-
- def ++ (that: Abacus) = Abacus(this.p ::: that.p)
-
- def shift(offset: Int, jump: Int) = Abacus(p.map(_ match {
- case Inc(n) => Inc(n)
- case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset)
- case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset)
- }))
-
- def adjust(old_jump: Int, jump: Int) = Abacus(p.map(_ match {
- case Inc(n) => Inc(n)
- case Dec(n, l) => if (l == old_jump) Dec(n, jump) else Dec(n, l)
- case Goto(l) => if (l == old_jump) Goto(jump) else Goto(l)
- }))
-
- def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
- case (None, _) => cf
- case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
- case (Some(Dec(n, l)), s) => {
- if (dget(cf.regs, n) == 0) AConfig(l, cf.regs)
- else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
- }
- case (Some(Goto(l)), _) => AConfig(l, cf.regs)
- }
-
- def steps(cf: AConfig, n: Int) : AConfig = n match {
- case 0 => cf
- case n => steps(step(cf), n - 1)
- }
-
- def steps(regs: Regs, n: Int) : AConfig = steps(AConfig(0, regs), n)
-
- def run(cf: AConfig) : AConfig = {
- if (cf.s >= p.length || cf.s < 0) cf else run(step(cf))
- }
-
- def run(regs: Regs): Regs = run(AConfig(0, regs)).regs
-}
-
-// Abacus examples
-def Copy(in: Int, out: Int, jump: Int) =
- Abacus(List(Dec(in, jump), Inc(out), Goto(0)))
-
-def Plus(m: Int, n: Int, tmp: Int, jump: Int) =
- Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4)))
-
-def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) =
- Abacus(List(Dec(in1, jump))) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0)
-
-def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = {
- Abacus(List(Inc(out), Dec(in1, jump))) ++
- Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++
- Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
-}
-
-println("Copy: 3 " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
-println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
-println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
-println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
-
-
-
-// Abacus to TM translation
-def layout(p: AProg) = p.map(_ match {
- case Inc(n) => 2 * n + 9
- case Dec(n, _) => 2 * n + 16
- case Goto(n) => 1
-})
-
-def start(p: AProg, n: Int) = layout(p).take(n).sum + 1
-
-def compile_Inc(s: Int, n: Int) = {
- val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4),
- (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
- (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
- TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
-}
-
-def compile_Dec(s: Int, n: Int, e: Int) = {
- val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
- (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
- (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
- (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
- (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
- (R, 0), (WBk, 16)))
- TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
-}
-
-def compile_Goto(s: Int) = {
- val TMGoto = TM(List((Nop, 1), (Nop, 1)))
- TMGoto.shift(s - 1)
-}
-
-def compile(p: AProg, s: Int, i: AInst) = i match {
- case Inc(n) => compile_Inc(s, n)
- case Dec(n, e) => compile_Dec(s, n, start(p, e))
- case Goto(e) => compile_Goto(start(p, e))
-}
-
-def tms(p: AProg) = {
- val ss = (0 until p.length).map (start(p,_))
- (ss zip p).map{case (n, i) => compile(p, n, i)}
-}
-
-def toTM(p: AProg) = tms(p).reduceLeft(_ ++ _)
-
-//examples
-println("Copy 3: " + toTM(Copy(0, 1, Int.MaxValue).p).run(new STape(3,0,0)))
-println("Plus 3 + 4: " + toTM(Plus(0, 1, 2, Int.MaxValue).p).run(new STape(3,4,0,0)))
-println("Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(new STape(3,5,0,0)))
-println("Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(new STape(3,4,0,0,0)))
-
-
-//Recursive Functions
-abstract class Rec {
- def eval(ns: List[Int]) : Int
-}
-case object Z extends Rec {
- override def eval(ns: List[Int]) = ns match {
- case n::Nil => 0
- case _ => throw new IllegalArgumentException("Z: args")
- }
-}
-case object S extends Rec {
- override def eval(ns: List[Int]) = ns match {
- case n::Nil => n + 1
- case _ => throw new IllegalArgumentException("S: args")
- }
-}
-case class Id(n: Int, m: Int) extends Rec {
- override def eval(ns: List[Int]) =
- if (ns.length == n && m < n) ns(m)
- else throw new IllegalArgumentException("Id: args")
-}
-case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {
- override def eval(ns: List[Int]) =
- if (ns.length == n) f.eval(gs.map(_.eval(ns)))
- else throw new IllegalArgumentException("Cn: args")
-}
-case class Pr(n: Int, f: Rec, g: Rec) extends Rec {
- override def eval(ns: List[Int]) =
- if (ns.length == n - 1) {
- if (ns.last == 0) f.eval(ns.init)
- else {
- val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))
- g.eval(ns.init ::: List(ns.last - 1, r))
- }
- }
- else throw new IllegalArgumentException("Cn: args")
-}
-case class Mn(n: Int, f: Rec) extends Rec {
- override def eval(ns: List[Int]) = 0
-
-}
-