21 def ClearRegs(n: Int) : Abacus = n match { |
21 def ClearRegs(n: Int) : Abacus = n match { |
22 case 0 => Abacus() |
22 case 0 => Abacus() |
23 case n => ClearRegs(n - 1) :+ Abacus(Dec(n - 1, 2), Goto(0)) |
23 case n => ClearRegs(n - 1) :+ Abacus(Dec(n - 1, 2), Goto(0)) |
24 } |
24 } |
25 |
25 |
26 def cn_merge_gs(x: List[(Abacus, Int, Int)], p: Int) : Abacus = x match { |
26 def cn_merge_gs(x: List[(Abacus, Int)], n: Int, p: Int) : Abacus = x match { |
27 case Nil => Abacus(Nil) |
27 case Nil => Abacus(Nil) |
28 case (gprog, gpara, gn)::gs => gprog :+ MVReg(gpara, p) :+ cn_merge_gs(gs, p + 1) |
28 case (gprog, gn)::gs => gprog :+ MVReg(n, p) :+ cn_merge_gs(gs, n, p + 1) |
29 } |
29 } |
30 |
30 |
31 // translation: |
31 // translation: |
32 // second component is the arity of the recursive function, |
32 // second component is the arity of the recursive function, |
33 // third componen is the maximum of registers used |
33 // third componen is the maximum of registers used |
34 def compile_rec(f: Rec) : (Abacus, Int, Int) = f match { |
34 def compile_rec(f: Rec) : (Abacus, Int) = f match { |
35 case Z => (Abacus(Goto(1)), 1, 2) |
35 case Z => (Abacus(Goto(1)), 2) |
36 case S => (AbacusAdd(0, 1, 2) :+ Abacus(Inc(1)), 1, 3) |
36 case S => (AbacusAdd(0, 1, 2) :+ Abacus(Inc(1)), 3) |
37 case Id(i, j) => (AbacusAdd(j, i, i + 1), i, i + 2) |
37 case Id(i, j) => (AbacusAdd(j, i, i + 1), i + 2) |
38 case Cn(n, f, gs) => { |
38 case Cn(n, f, gs) => { |
39 val cied_gs = gs.map(compile_rec) |
39 val cied_gs = gs.map(compile_rec) |
40 val (fprog, fpara, fn) = compile_rec(f) |
40 val (fprog, fn) = compile_rec(f) |
41 val pstr = (1 + n :: fn :: (cied_gs.map(_._3))).max |
41 val qstr = (fn :: (cied_gs.map(_._2))).max |
42 val qstr = pstr + gs.length + 1 |
42 (cn_merge_gs(cied_gs, n, qstr) :+ |
43 (cn_merge_gs(cied_gs, pstr) :+ MVRegs(0, qstr, n) :+ |
43 MVRegs(0, qstr + gs.length, n) :+ |
44 MVRegs(pstr, 0, gs.length) :+ fprog :+ |
44 MVRegs(qstr, 0, gs.length) :+ |
45 MVReg(fpara, pstr) :+ ClearRegs(gs.length) :+ |
45 fprog :+ |
46 MVReg(pstr, n) :+ MVRegs(qstr, 0, n), n, qstr + n) |
46 MVReg(f.arity, qstr + gs.length + 1) :+ |
|
47 ClearRegs(gs.length) :+ |
|
48 MVRegs(qstr + gs.length , 0, n + 1), qstr + gs.length + n + 1) |
47 } |
49 } |
48 case Pr(n, f, g) => { |
50 case Pr(n, f, g) => { |
49 val (fprog, fpara, fn) = compile_rec(f) |
51 val (fprog, fn) = compile_rec(f) |
50 val (gprog, gpara, gn) = compile_rec(g) |
52 val (gprog, gn) = compile_rec(g) |
51 val p = List(n + 3, fn, gn).max |
53 val qstr = List(fn, gn).max |
52 val e = gprog.p.length + 7 |
54 val e = gprog.p.length + 7 |
53 (MVReg(n, p) :+ fprog :+ MVReg(n, n + 1) :+ |
55 (MVReg(0, qstr) :+ |
54 ((Abacus(Dec(p, e)) :+ gprog :+ Abacus(Inc(n), Dec(n + 1, 3), Goto(1))) ++ |
56 MVRegs(1, 0, n) :+ |
55 Abacus(Dec(n + 2, 0), Inc (n + 1), Goto (gprog.p.length + 4))), n + 1, p + 1) |
57 fprog :+ |
|
58 MVReg(n, n + 1) :+ |
|
59 MVRegs(0, 2, n) :+ |
|
60 ((Abacus(Dec(qstr, e)) :+ gprog :+ Abacus(Inc(0), Dec(n + 1, 3), Goto(1))) ++ |
|
61 Abacus(Dec(n + 2, 0), Inc (1), Goto (gprog.p.length + 4))), qstr + 1) |
56 } |
62 } |
57 case Mn(n, f) => { |
63 case Mn(n, f) => { |
58 val (fprog, fpara, fn) = compile_rec(f) |
64 val (fprog, fn) = compile_rec(f) |
59 val len = fprog.p.length |
65 val len = fprog.p.length |
60 (fprog ++ Abacus(Dec(n + 1, len + 5), Dec(n + 1, len + 3), Goto(len + 1), Inc(n), Goto(0)), |
66 (MVRegs(0, 1, n) :+ |
61 n, List(n + 1, fn).max) |
67 (fprog ++ Abacus(Dec(n + 1, len + 5), Dec(n + 1, len + 3), Goto(len + 1), Inc(0), Goto(0))), |
|
68 fn) |
62 } |
69 } |
63 } |
70 } |
64 |
71 |
65 } |
72 } |
66 |
73 |