3 // Abacus to TM translation |
3 // Abacus to TM translation |
4 |
4 |
5 import lib._ |
5 import lib._ |
6 import turing._ |
6 import turing._ |
7 import abacus._ |
7 import abacus._ |
|
8 import scala.annotation.tailrec |
8 |
9 |
9 // TMs used in the translation |
10 // TMs used in the translation |
10 |
11 |
11 val TMInc = TM((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), |
12 val TMInc = TM((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), |
12 (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6), |
13 (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6), |
36 } |
37 } |
37 TMMopup1(n) ++ TMMopup_aux.shift(2 * n) |
38 TMMopup1(n) ++ TMMopup_aux.shift(2 * n) |
38 } |
39 } |
39 |
40 |
40 |
41 |
41 // start address of the nth instruction |
42 // start address of the instructions |
42 def address(p: AProg, n: Int) = { |
43 @tailrec |
43 def layout(p: AProg) = p.map(_ match { |
44 def layout(p: AProg, sum: Int, out: List[Int]) : List[Int] = p match { |
44 case Inc(n) => 2 * n + 9 |
45 case Nil => out.reverse |
45 case Dec(n, _) => 2 * n + 16 |
46 case Inc(n)::p => layout(p, 2 * n + 9 + sum, 2 * n + 9 + sum::out) |
46 case Goto(n) => 1 |
47 case Dec(n, _)::p => layout(p, 2 * n + 16 + sum, 2 * n + 16 + sum::out) |
47 }) |
48 case Goto(n)::p => layout(p, 1 + sum, 1 + sum::out) |
48 layout(p).take(n).sum + 1 |
49 } |
|
50 |
|
51 def address(layout: List[Int], n: Int) = { |
|
52 //println("calculating layout of " + n) |
|
53 layout(n) + 1 |
49 } |
54 } |
50 |
55 |
51 def compile_Inc(s: Int, n: Int) = |
56 def compile_Inc(s: Int, n: Int) = |
52 TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1) |
57 TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1) |
53 |
58 |
54 def compile_Dec(s: Int, n: Int, e: Int) = |
59 def compile_Dec(s: Int, n: Int, e: Int) = |
55 TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e) |
60 TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e) |
56 |
61 |
57 def compile_Goto(s: Int) = TMGoto.shift(s - 1) |
62 def compile_Goto(s: Int) = TMGoto.shift(s - 1) |
58 |
63 |
59 def compile_abc(p: AProg, s: Int, i: AInst) = i match { |
64 @tailrec |
60 case Inc(n) => compile_Inc(s, n) |
65 def compile_abc(lay: List[Int], p: AProg, cnt: Int, out: List[TM]): List[TM] = { |
61 case Dec(n, e) => compile_Dec(s, n, address(p, e)) |
66 if (cnt % 1000 == 0) println("compile counter of instructions " + cnt); |
62 case Goto(e) => compile_Goto(address(p, e)) |
67 p match { |
|
68 case Nil => out.reverse |
|
69 case Inc(n)::p => compile_abc(lay, p, cnt + 1, compile_Inc(address(lay, cnt), n)::out) |
|
70 case Dec(n, e)::p => compile_abc(lay, p, cnt + 1, compile_Dec(address(lay, cnt), n, address(lay, e))::out) |
|
71 case Goto(e)::p => compile_abc(lay, p, cnt + 1, compile_Goto(address(lay, e))::out) |
|
72 } |
63 } |
73 } |
64 |
74 |
65 // component TMs for each instruction |
75 // component TMs for each instruction |
66 def TMs(p: AProg) = |
76 def TMs(p: AProg) = { |
67 p.zipWithIndex.map{case (i, n) => compile_abc(p, address(p, n), i)} |
77 val lay = layout(p, 0, Nil) |
|
78 println("layout calculated") |
|
79 println("number of states (38667456): " + lay.last) |
|
80 compile_abc(lay, p, 0, Nil) |
|
81 } |
68 |
82 |
69 def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _) |
83 def toTM(p: AProg) = { |
|
84 println("start TM compilation") |
|
85 TMs(p).reduceLeft(_ ++ _) |
|
86 } |
70 |
87 |
71 } |
88 } |
72 |
89 |