Mercurial Mercurial > hg > tm / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
scala/comp1.scala
changeset 194 fc2a5e9fbb97
parent 193 317a2532c567
child 207 b93ec66cf4bb
equal deleted inserted replaced
193:317a2532c567 194:fc2a5e9fbb97 
     1 package object comp1 {
 
     1 package object comp1 {
 
       
     2 
       
     3 // Abacus to TM translation
 
     2 
     4 
     3 import lib._
 
     5 import lib._
 
     4 import turing._
 
     6 import turing._
 
     5 import abacus._
 
     7 import abacus._
 
     6 
     8 
     7 // TMs used in the translation
 
     9 // TMs used in the translation
 
     8 
    10 
     9 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
    11 val TMInc = TM((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),
 
    12                (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)))
 
    13                (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9))
 
    12 
    14 
    13 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
    15 val TMDec = TM((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),
 
    16                (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),
 
    17                (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),
 
    18                (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),
 
    19                (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
    18                     (R, 0), (WBk, 16)))
 
    20                (R, 0), (WBk, 16))
 
    19 
    21 
    20 val TMGoto = TM(List((Nop, 1), (Nop, 1)))
 
    22 val TMGoto = TM((Nop, 1), (Nop, 1))
 
       
    23 
       
    24 val TMMopup_aux = TM((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
 
       
    25                      (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6))
 
    21 
    26 
    22 def TMFindnth(n: Int) : TM = n match {
 
    27 def TMFindnth(n: Int) : TM = n match {
 
    23   case 0 => TM(Nil)
 
    28   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)))
 
    29   case n => TMFindnth(n - 1) ++ TM((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n))
 
    25 }
 
    30 }
 
    26 
    31 
    27 def TMMopup(n: Int) = {
 
    32 def TMMopup(n: Int) = {
 
    28   def TMMopup1(n: Int) : TM = n match {
 
    33   def TMMopup1(n: Int) : TM = n match {
 
    29     case 0 => TM(Nil)
 
    34     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)))
 
    35     case n => TMMopup1(n - 1) ++ TM((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n))
 
    31   }
 
    36   }
 
    32 
    37   TMMopup1(n) ++ TMMopup_aux.shift(2 * n)
 
    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 }
 
    38 
    39 
    39 
    40 
    40 
    41 // start address of the nth instruction
 
    41 // Abacus to TM translation
 
    42 def address(p: AProg, n: Int) = {
 
    42 def layout(p: AProg) = p.map(_ match {
 
    43   def layout(p: AProg) = p.map(_ match {
 
    43   case Inc(n) => 2 * n + 9 
    44     case Inc(n) => 2 * n + 9 
    44   case Dec(n, _) => 2 * n + 16 
    45     case Dec(n, _) => 2 * n + 16 
    45   case Goto(n) => 1
 
    46     case Goto(n) => 1
 
    46 })
 
    47   })
 
    47 
    48   layout(p).take(n).sum + 1
 
    48 def start(p: AProg, n: Int) = layout(p).take(n).sum + 1
 
    49 }
 
    49 
    50 
    50 def compile_Inc(s: Int, n: Int) = 
    51 def compile_Inc(s: Int, n: Int) = 
    51   TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
 
    52   TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
 
    52 
    53 
    53 def compile_Dec(s: Int, n: Int, e: Int) = 
    54 def compile_Dec(s: Int, n: Int, e: Int) = 
    55 
    56 
    56 def compile_Goto(s: Int) = TMGoto.shift(s - 1)
 
    57 def compile_Goto(s: Int) = TMGoto.shift(s - 1)
 
    57 
    58 
    58 def compile(p: AProg, s: Int, i: AInst) = i match {
 
    59 def compile(p: AProg, s: Int, i: AInst) = i match {
 
    59   case Inc(n) => compile_Inc(s, n)
 
    60   case Inc(n) => compile_Inc(s, n)
 
    60   case Dec(n, e) => compile_Dec(s, n, start(p, e))
 
    61   case Dec(n, e) => compile_Dec(s, n, address(p, e))
 
    61   case Goto(e) => compile_Goto(start(p, e))
 
    62   case Goto(e) => compile_Goto(address(p, e))
 
    62 }
 
    63 }
 
    63 
    64 
    64 // component TMs for each instruction
 
    65 // component TMs for each instruction
 
    65 def TMs(p: AProg) = {
 
    66 def TMs(p: AProg) = 
    66   val ss = (0 until p.length).map (start(p,_))
 
    67   p.zipWithIndex.map{case (i, n) => compile(p, address(p, n), i)}
 
    67   (ss zip p).map{case (n, i) => compile(p, n, i)}
 
       
    68 }
 
       
    69 
    68 
    70 def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)
 
    69 def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)
 
    71     
    70     
    72 }
 
    71 }
 
    73 
    72
tm