# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1361406881 0
# Node ID 8939cc9b14f9f60d59115e5d9a278890b49a9964
# Parent  326310016da926e26eac44bb99b89c316f19dfc0
tuned Scala implementation

diff -r 326310016da9 -r 8939cc9b14f9 turing.scala
--- a/turing.scala	Tue Feb 19 13:36:35 2013 +0000
+++ b/turing.scala	Thu Feb 21 00:34:41 2013 +0000
@@ -10,21 +10,22 @@
 def nth_of[A](xs: List[A], n: Int) = 
   if (n <= xs.length) Some(xs(n)) else None 
 
-def replicate[A](x: A, n: Int) : List[A] = n match {
-  case 0 => List(x)
-  case n => x::replicate(x, n - 1)
-}
-
 
 //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 + _)
 
 
 
-abstract class Cell
+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" }
 
@@ -36,7 +37,8 @@
 case object Nop extends Action
 
 type State = Int
-type Prog = List[(Action, State)]
+type Inst = (Action, State)
+type Prog = List[Inst]
 
 //tapes
 case class Tape(l: List[Cell], r: List[Cell]) {
@@ -58,7 +60,7 @@
 
 // standard tapes
 class STape(ns: Int*) extends 
-  Tape(Nil, ns.map(replicate[Cell](Oc, _)).reduceLeft(_ ::: List(Bk) ::: _))
+  Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
   
 
 // configurations
@@ -72,15 +74,17 @@
 // 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 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, 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
@@ -104,7 +108,6 @@
 }
 
 
-
 // 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), 
@@ -115,29 +118,22 @@
 
 def TMFindnth(n: Int) : TM = n match {
   case 0 => TM(Nil)
-  case n => {
-    val tm = TMFindnth(n - 1)
-    TM(tm.p ::: List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
-  }
+  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 => {
-      val tm = TMMopup1(n - 1) 
-      TM(tm.p ::: List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
-    }
+    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)))
 
-  val tm1 = TMMopup1(n)
-  val tm2 = TMMopup2.shift(2 * n)
-  TM(tm1.p ::: tm2.p)
+  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))))
@@ -173,6 +169,8 @@
 
   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 toTM()
  
   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
     case (None, _) => cf
@@ -223,6 +221,26 @@
 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
+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)))
+
+def TMINC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
+
+def TMDEC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
+
+
+
+
 //Recursive Functions
 abstract class Rec {
   def eval(ns: List[Int]) : Int