193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
package object comp1 {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
// Abacus to TM translation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
import lib._
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
import turing._
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
import abacus._
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
// TMs used in the translation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
val TMInc = TM((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
(L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
(L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
val TMDec = TM((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
(R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
(L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
(R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
(R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
(R, 0), (WBk, 16))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
val TMGoto = TM((Nop, 1), (Nop, 1))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
val TMMopup_aux = TM((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
(R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
def TMFindnth(n: Int) : TM = n match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
case 0 => TM(Nil)
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
case n => TMFindnth(n - 1) ++ TM((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
def TMMopup(n: Int) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
def TMMopup1(n: Int) : TM = n match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
case 0 => TM(Nil)
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
case n => TMMopup1(n - 1) ++ TM((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
}
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
TMMopup1(n) ++ TMMopup_aux.shift(2 * n)
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
// start address of the nth instruction
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
def address(p: AProg, n: Int) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
def layout(p: AProg) = p.map(_ match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
case Inc(n) => 2 * n + 9
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
case Dec(n, _) => 2 * n + 16
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
case Goto(n) => 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
})
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
layout(p).take(n).sum + 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
}
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
def compile_Inc(s: Int, n: Int) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
def compile_Dec(s: Int, n: Int, e: Int) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
def compile_Goto(s: Int) = TMGoto.shift(s - 1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
|
207
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
def compile_abc(p: AProg, s: Int, i: AInst) = i match {
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
case Inc(n) => compile_Inc(s, n)
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
case Dec(n, e) => compile_Dec(s, n, address(p, e))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
case Goto(e) => compile_Goto(address(p, e))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
// component TMs for each instruction
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
def TMs(p: AProg) =
|
207
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
p.zipWithIndex.map{case (i, n) => compile_abc(p, address(p, n), i)}
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
69 |
def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
72 |
|