193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
import lib._
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
import turing._
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
import abacus._
|
195
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
import recs._
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
import comp1._
|
205
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
import comp2._
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
// Turing machine examples
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
val TMCopy = TM((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
(L, 4), (L, 4), (L, 5), (R, 11), (R, 6),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
(R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
(R, 8), (L, 10), (L, 9), (L, 10), (L, 5),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
(L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
(R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
println("TMCopy: " + (TMCopy.run(Tape(3))))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
println("TMfindnth: " + (TMFindnth(3).run(Tape(1,2,3,4,5))))
|
194
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
println("TMMopup: " + (TMMopup(3).run(Tape(1,2,3,4,5))))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
// Abacus machine examples
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
def Copy(in: Int, out: Int, jump: Int) =
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
Abacus(Dec(in, jump), Inc(out), Goto(0))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
def Plus(m: Int, n: Int, tmp: Int, jump: Int) =
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
Abacus(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) =
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
Abacus(Dec(in1, jump)) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0)
|
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 |
def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = {
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
Abacus(Inc(out), Dec(in1, jump)) ++
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
Copy(tmp2, out, -1).shift(10, -1).adjust(-1, 1)
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
}
|
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 |
println("Copy 3: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
println("Plus 3 + 4: " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
println("Mult 3 * 5: " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
println("Expo 3 ^ 4: " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
// Abacus-to-TM translation examples
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
println("Compiled Copy 3: " + toTM(Copy(0, 1, Int.MaxValue).p).run(Tape(3,0,0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
println("Compiled Plus 3 + 4: " + toTM(Plus(0, 1, 2, Int.MaxValue).p).run(Tape(3,4,0,0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
println("Compiled Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(Tape(3,5,0,0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
println("Compiled Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(Tape(3,4,0,0,0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
// Recursive function examples
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
println("Add 3 4: " + Add.eval(3, 4))
|
201
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
println("Mult 3 4: " + recs.Mult.eval(3, 4))
|
200
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
println("Twice 4: " + Twice.eval(4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
println("FourTm 4: " + Fourtimes.eval(4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
println("Pred 9: " + Pred.eval(9))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
println("Pred 0: " + Pred.eval(0))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
println("Minus 6 2: " + Minus.eval(6, 2))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
println("Minus 6 8: " + Minus.eval(6, 8))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
println("Const 8: " + Const(8).eval(67))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
println("Power 2 3: " + Power.eval(2, 3))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
println("Sign 8: " + Sign.eval(8))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
println("Sign 0: " + Sign.eval(0))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
println("Less 4 4: " + Less.eval(4, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
println("Less 4 6: " + Less.eval(4, 6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
println("Less 6 4: " + Less.eval(6, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
println("Not 0: " + Not.eval(0))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
println("Not 6: " + Not.eval(6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
println("Eq 4 4: " + Eq.eval(4, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
println("Eq 4 6: " + Eq.eval(4, 6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
println("Eq 6 4: " + Eq.eval(6, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
println("Conj 0 6: " + Conj.eval(0, 6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
println("Conj 6 4: " + Conj.eval(6, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
println("Conj 0 0: " + Conj.eval(0, 0))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
println("Disj 0 6: " + Disj.eval(0, 6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
println("Disj 6 4: " + Disj.eval(6, 4))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
println("Disj 0 0: " + Disj.eval(0, 0))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
println("Sigma Add 2 3 -> 14: " + Sigma(Add).eval(2,3))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
println("Accum Add 2 3 -> 120: " + Accum(Add).eval(2,3))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
println("Accum Mult 2 3 -> 0: " + Accum(recs.Mult).eval(2,3))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
println("Fact 5: " + Fact.eval(5))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
println("Prime 0..15: " + (0 to 15).map(n => (n, Prime.eval(n))))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
println("NextPrime 3: " + NextPrime.eval(3))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
println("NthPrime 1: " + NthPrime.eval(1))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
println("Listsum [2, 3, 4 , 5, 6]: " + Listsum(5, 4).eval(2, 3, 4, 5, 6))
|
8dde2e46c69d
added all recursive functions needed for the UF
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
println("Strt: " + Strt(2).eval(2, 3))
|
198
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
|
195
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
|
205
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
println(Const(1))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
println(compile_rec(Const(1))._1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
println(compile_rec(Const(1)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
println(compile_rec(Const(1))._1.run(Map(0 -> 1, 1 -> 1, 2 -> 0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
println(Add)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
println(compile_rec(Add)._1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
println(compile_rec(Add))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
println(compile_rec(Add)._1.run(Map(0 -> 3, 1 -> 8, 2 -> 0)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
//compile_rec(Add)._1.run(Map(0 -> 3, 1 -> 4, 2 -> 0))
|