1 package object comp1 {

     2 

     3 import lib._

     4 import turing._

     5 import abacus._

     6 

     7 // TMs used in the translation

     8 

     9 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 

    10                     (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),

    11                     (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))

    12 

    13 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),

    14                     (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),

    15                     (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),

    16                     (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),

    17                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),

    18                     (R, 0), (WBk, 16)))

    19 

    20 val TMGoto = TM(List((Nop, 1), (Nop, 1)))

    21 

    22 def TMFindnth(n: Int) : TM = n match {

    23   case 0 => TM(Nil)

    24   case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))

    25 }

    26 

    27 def TMMopup(n: Int) = {

    28   def TMMopup1(n: Int) : TM = n match {

    29     case 0 => TM(Nil)

    30     case n => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))

    31   }

    32 

    33   val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),

    34                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))

    35 

    36   TMMopup1(n) ++ TMMopup2.shift(2 * n)

    37 }

    38 

    39 

    40 

    41 // Abacus to TM translation

    42 def layout(p: AProg) = p.map(_ match {

    43   case Inc(n) => 2 * n + 9 

    44   case Dec(n, _) => 2 * n + 16 

    45   case Goto(n) => 1

    46 })

    47 

    48 def start(p: AProg, n: Int) = layout(p).take(n).sum + 1

    49 

    50 def compile_Inc(s: Int, n: Int) = 

    51   TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)

    52 

    53 def compile_Dec(s: Int, n: Int, e: Int) = 

    54   TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)

    55 

    56 def compile_Goto(s: Int) = TMGoto.shift(s - 1)

    57 

    58 def compile(p: AProg, s: Int, i: AInst) = i match {

    59   case Inc(n) => compile_Inc(s, n)

    60   case Dec(n, e) => compile_Dec(s, n, start(p, e))

    61   case Goto(e) => compile_Goto(start(p, e))

    62 }

    63 

    64 // component TMs for each instruction

    65 def TMs(p: AProg) = {

    66   val ss = (0 until p.length).map (start(p,_))

    67   (ss zip p).map{case (n, i) => compile(p, n, i)}

    68 }

    69 

    70 def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)

    71     

    72 }

    73