# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1361456834 0
# Node ID 98370b96c1c5ca9e534a9af0598f5c24d71217e0
# Parent  f1ecb4a68a5400046b6d21bc37137751c2d43736
compilation from Abacus to Turing in Scala

diff -r f1ecb4a68a54 -r 98370b96c1c5 turing.scala
--- a/turing.scala	Thu Feb 21 05:34:39 2013 +0000
+++ b/turing.scala	Thu Feb 21 14:27:14 2013 +0000
@@ -1,3 +1,4 @@
+import scala.annotation.tailrec
 
 //some list functions
 def tl[A](xs: List[A]) : List[A] = xs match {
@@ -103,7 +104,8 @@
     case n => steps(step(cf), n - 1)
   } 
 
-  def run(cf: Config) : Config = {
+  @tailrec
+  final def run(cf: Config) : Config = {
     if (cf.is_final) cf else run(step(cf))
   }
  
@@ -136,7 +138,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))))
@@ -148,20 +149,6 @@
 case class Dec(n: Int, l: Int) extends AInst
 case class Goto(l: Int) extends AInst
 
-// shifting and adjusting labels
-def ashift(ai: AInst, offset: Int, jump: Int) = ai 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 aadjust(ai: AInst, old_jump: Int, jump: Int) = ai 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)
-}
-
-
 
 type AProg = List[AInst]
 type Regs = Map[Int, Int]
@@ -170,10 +157,19 @@
 
 case class Abacus(p: AProg) {
 
-   def ++ (that: Abacus) = Abacus(this.p ::: that.p)
+  def ++ (that: Abacus) = Abacus(this.p ::: that.p)
 
-  def shift(offset: Int, jump: Int) = Abacus(p.map(ashift(_, offset, jump)))
-  def adjust(old_jump: Int, jump: Int) = Abacus(p.map(aadjust(_, old_jump, jump)))
+  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
@@ -185,6 +181,7 @@
     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)
@@ -215,14 +212,24 @@
   Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
 }
 
-
-println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
+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
+type Layout = List[Int]
+
+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(ly: Layout, n: Int) = ly.take(n).sum + 1
+
 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)))
@@ -234,11 +241,30 @@
                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
                     (R, 0), (WBk, 16)))
 
-def TMINC(s: Int, n: Int, e: Int) = (TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n)).shift(s - 1).adjust(e)
+def TMINC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
+
+def TMDEC(s: Int, n: Int, e: Int) = TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
+
+def TMGOTO(n: Int) = TM(List((Nop, n), (Nop, n)))
+
+def compile(ly: Layout, s: Int, i: AInst) = i match {
+  case Inc(n) => TMINC(s, n)
+  case Dec(n, e) => TMDEC(s, n, start(ly, e))
+  case Goto(e) => TMGOTO(start(ly, e))
+}
 
-def TMDEC(s: Int, n: Int, e: Int) = (TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n)).shift(s - 1).adjust(e)
+def tms(p: AProg) = {
+  val ss = (0 until p.length).map (start(layout(p),_))
+  (ss zip p).map{case (n, i) => compile(layout(p), n, i)}
+}
 
-//def toTM()
+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