# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1361005627 0
# Node ID 1c2e639d4e549f40b6f5cb2e84685b31bc5bd4e1
# Parent  d2c85556d290fbe4a38d5730b01f2e196b024096
added abacus programs

diff -r d2c85556d290 -r 1c2e639d4e54 turing.scala
--- a/turing.scala	Fri Feb 15 18:24:00 2013 +0000
+++ b/turing.scala	Sat Feb 16 09:07:07 2013 +0000
@@ -23,6 +23,10 @@
 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)
+
+
 
 //tapes
 case class Tape(l: List[Cell], r: List[Cell]) {
@@ -61,7 +65,7 @@
 
 
 // Turing Machines
-case class TM(p: Prog, tp: Tape) {
+case class TM(p: Prog) {
   
   def fetch(s: State, a: Cell) = (s, a) match {
     case (0, _) => (Nop, 0)
@@ -84,13 +88,11 @@
     case n => steps(step(cf), n - 1)
   } 
 
-  def steps(n: Int) : Config = steps(Config(1, tp), n)
-
   def run(cf: Config) : Config = {
     if (cf.is_final) cf else run(step(cf))
   }
  
-  def run : Tape = run(Config(1, tp)).tp
+  def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 }
 
 
@@ -102,7 +104,57 @@
           (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)), new STape(n))
+          (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
+
+println("TM: " + (new TMCopy(0)).run(new STape(3)))
+
+
+// Abacus
+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)  
 
-println((new TMCopy(0)).run)
+case class Abacus(p: AProg) {
+  
+  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
+}
+
+// examples
+class Copy(in: Int, out: Int) extends 
+  Abacus(List(Dec(in, -1), Inc(out), Goto(0))) 
+
+class Plus(in1: Int, in2: Int, out: Int) extends 
+  Abacus(List(Dec(in1, 4), Inc(in2), Inc(out),
+              Goto(0), Dec(out, -1), Inc(in1), Goto(4))) 
+
+
+println("Ab: " + (new Plus(0, 1, 2)).run(Map(0 -> 3, 1 -> 4)))