4 |
4 |
5 import lib._ |
5 import lib._ |
6 import abacus._ |
6 import abacus._ |
7 import recs._ |
7 import recs._ |
8 |
8 |
9 def arity(f: Rec) = f match { |
9 def AbacusAdd(m: Int, n: Int, p: Int) = |
10 case Z => 1 |
10 Abacus(Dec(m, 4), Inc(n), Inc(p), Goto(0), Dec(p, 7), Inc(m), Goto(4)) |
11 case S => 1 |
11 |
12 case Id(n, _) => n |
12 def MVReg(m: Int, n: Int) = Abacus(Dec(m, 3), Inc(n), Goto(0)) |
13 case Cn(n, _, _) => n |
13 |
14 case Pr(n, _, _) => n |
14 //move the registers ranging from i to i + n to range j to j + n |
15 case Mn(n, _) => n |
15 def MVRegs(i: Int, j: Int, n: Int) : Abacus = n match { |
|
16 case 0 => Abacus() |
|
17 case n => MVRegs(i, j, n - 1) :+ MVReg(i + n - 1, j + n - 1) |
|
18 } |
|
19 |
|
20 // clears the first n registers |
|
21 def ClearRegs(n: Int) : Abacus = n match { |
|
22 case 0 => Abacus() |
|
23 case n => ClearRegs(n - 1) :+ Abacus(Dec(n - 1, 2), Goto(0)) |
|
24 } |
|
25 |
|
26 def cn_merge_gs(x: List[(Abacus, Int, Int)], p: Int) : Abacus = x match { |
|
27 case Nil => Abacus(Nil) |
|
28 case (gprog, gpara, gn)::gs => gprog :+ MVReg(gpara, p) :+ cn_merge_gs(gs, p + 1) |
|
29 } |
|
30 |
|
31 // translation: |
|
32 // second component is the arity of the recursive function, |
|
33 // third componen is the maximum of registers used |
|
34 def compile_rec(f: Rec) : (Abacus, Int, Int) = f match { |
|
35 case Z => (Abacus(Goto(1)), 1, 2) |
|
36 case S => (AbacusAdd(0, 1, 2) :+ Abacus(Inc(1)), 1, 3) |
|
37 case Id(i, j) => (AbacusAdd(j, i, i + 1), i, i + 2) |
|
38 case Cn(n, f, gs) => { |
|
39 val cied_gs = gs.map(compile_rec) |
|
40 val (fprog, fpara, fn) = compile_rec(f) |
|
41 val pstr = (1 + n :: fn :: (cied_gs.map(_._3))).max |
|
42 val qstr = pstr + gs.length + 1 |
|
43 (cn_merge_gs(cied_gs, pstr) :+ MVRegs(0, qstr, n) :+ |
|
44 MVRegs(pstr, 0, gs.length) :+ fprog :+ |
|
45 MVReg(fpara, pstr) :+ ClearRegs(gs.length) :+ |
|
46 MVReg(pstr, n) :+ MVRegs(qstr, 0, n), n, qstr + n) |
|
47 } |
|
48 case Pr(n, f, g) => { |
|
49 val (fprog, fpara, fn) = compile_rec(f) |
|
50 val (gprog, gpara, gn) = compile_rec(g) |
|
51 val p = List(n + 3, fn, gn).max |
|
52 val e = gprog.p.length + 7 |
|
53 (MVReg(n, p) :+ fprog :+ MVReg(n, n + 1) :+ |
|
54 ((Abacus(Dec(p, e)) :+ gprog :+ Abacus(Inc(n), Dec(n + 1, 3), Goto(1))) ++ |
|
55 Abacus(Dec(n + 2, 0), Inc (n + 1), Goto (gprog.p.length + 4))), n + 1, p + 1) |
|
56 } |
|
57 case Mn(n, f) => { |
|
58 val (fprog, fpara, fn) = compile_rec(f) |
|
59 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)), |
|
61 n, List(n + 1, fn).max) |
|
62 } |
16 } |
63 } |
17 |
64 |
18 } |
65 } |
19 |
66 |