diff -r 317a2532c567 -r fc2a5e9fbb97 scala/comp1.scala --- a/scala/comp1.scala Thu Feb 21 16:07:40 2013 +0000 +++ b/scala/comp1.scala Fri Feb 22 14:31:34 2013 +0000 @@ -1,51 +1,52 @@ package object comp1 { +// Abacus to TM translation + import lib._ import turing._ import abacus._ // TMs used in the 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 TMInc = TM((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))) +val TMDec = TM((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)) -val TMGoto = TM(List((Nop, 1), (Nop, 1))) +val TMGoto = TM((Nop, 1), (Nop, 1)) + +val TMMopup_aux = TM((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3), + (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)) def TMFindnth(n: Int) : TM = n match { case 0 => TM(Nil) - case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n))) + case n => TMFindnth(n - 1) ++ TM((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 => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n))) + case n => TMMopup1(n - 1) ++ TM((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))) - - TMMopup1(n) ++ TMMopup2.shift(2 * n) + TMMopup1(n) ++ TMMopup_aux.shift(2 * n) } - -// Abacus to TM translation -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(p: AProg, n: Int) = layout(p).take(n).sum + 1 +// start address of the nth instruction +def address(p: AProg, n: Int) = { + def layout(p: AProg) = p.map(_ match { + case Inc(n) => 2 * n + 9 + case Dec(n, _) => 2 * n + 16 + case Goto(n) => 1 + }) + layout(p).take(n).sum + 1 +} def compile_Inc(s: Int, n: Int) = TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1) @@ -57,15 +58,13 @@ def compile(p: AProg, s: Int, i: AInst) = i match { case Inc(n) => compile_Inc(s, n) - case Dec(n, e) => compile_Dec(s, n, start(p, e)) - case Goto(e) => compile_Goto(start(p, e)) + case Dec(n, e) => compile_Dec(s, n, address(p, e)) + case Goto(e) => compile_Goto(address(p, e)) } // component TMs for each instruction -def TMs(p: AProg) = { - val ss = (0 until p.length).map (start(p,_)) - (ss zip p).map{case (n, i) => compile(p, n, i)} -} +def TMs(p: AProg) = + p.zipWithIndex.map{case (i, n) => compile(p, address(p, n), i)} def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)