41 |
41 |
42 // compiler - built-in functions |
42 // compiler - built-in functions |
43 // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html |
43 // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html |
44 // |
44 // |
45 |
45 |
46 val library = """ |
|
47 .class public XXX.XXX |
|
48 .super java/lang/Object |
|
49 |
|
50 .method public <init>()V |
|
51 aload_0 |
|
52 invokenonvirtual java/lang/Object/<init>()V |
|
53 return |
|
54 .end method |
|
55 |
|
56 .method public static write(I)V |
|
57 .limit locals 1 |
|
58 .limit stack 2 |
|
59 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
60 iload 0 |
|
61 invokevirtual java/io/PrintStream/println(I)V |
|
62 return |
|
63 .end method |
|
64 |
|
65 """ |
|
66 |
46 |
67 // for generating new labels |
47 // for generating new labels |
68 var counter = -1 |
48 var counter = -1 |
69 |
49 |
70 def Fresh(x: String) = { |
50 def Fresh(x: String) = { |
71 counter += 1 |
51 counter += 1 |
72 x ++ "_" ++ counter.toString() |
52 x ++ "_" ++ counter.toString() |
73 } |
53 } |
|
54 |
|
55 |
|
56 |
|
57 // Abstract syntax trees for the Fun language |
|
58 abstract class KExp |
|
59 |
|
60 case class KVar(s: String) extends KExp |
|
61 case class KNum(i: Int) extends KExp |
|
62 case class KAop(o: String, x1: String, x2: String) extends KExp |
|
63 case class KIfeq(x1: String, x2: String, e1: KExp, e2: KExp) extends KExp |
|
64 case class KCall(o: String, vrs: List[String]) extends KExp |
|
65 case class KLet(x: String, e1: KExp, e2: KExp) extends KExp { |
|
66 override def toString = s"let $x = $e1 in \n$e2" |
|
67 } |
|
68 |
|
69 def K(e: Exp) : KExp = e match { |
|
70 case Var(s) => KVar(s) |
|
71 case Num(i) => KNum(i) |
|
72 case Aop(o, a1, a2) => { |
|
73 val x1 = Fresh("tmp") |
|
74 val x2 = Fresh("tmp") |
|
75 KLet(x1, K(a1), KLet(x2, K(a2), KAop(o, x1, x2))) |
|
76 } |
|
77 case Call(name: String, args: List[Exp]) => { |
|
78 val args_new = args.map{a => (Fresh("x"), K(a))} |
|
79 def aux(as: List[(String, KExp)]) : KExp = as match { |
|
80 case Nil => KCall(name, args_new.map(_._1)) |
|
81 case (x, a)::rest => KLet(x, a, aux(rest)) |
|
82 } |
|
83 aux(args_new) |
|
84 } |
|
85 |
|
86 } |
|
87 |
|
88 def Denest(e: KExp) : KExp = e match { |
|
89 case KLet(xt, e1, e2) => { |
|
90 def insert(e: KExp) : KExp = e match { |
|
91 case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4)) |
|
92 case e => KLet(xt, e, Denest(e2)) |
|
93 } |
|
94 insert(Denest(e1)) |
|
95 } |
|
96 case _ => e |
|
97 } |
|
98 |
|
99 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Num(2), Num(3)))), Num(4)) |
|
100 println(K(e)) |
|
101 println(Denest(K(e))) |
|
102 |
|
103 |
74 |
104 |
75 // convenient string interpolations |
105 // convenient string interpolations |
76 // for instructions, labels and methods |
106 // for instructions, labels and methods |
77 import scala.language.implicitConversions |
107 import scala.language.implicitConversions |
78 import scala.language.reflectiveCalls |
108 import scala.language.reflectiveCalls |
84 } |
114 } |
85 |
115 |
86 |
116 |
87 type Env = Map[String, Int] |
117 type Env = Map[String, Int] |
88 |
118 |
|
119 |
|
120 |
89 // compile expressions |
121 // compile expressions |
90 def compile_exp(a: Exp, env : Env) : String = a match { |
122 def compile_exp(a: Exp, env : Env, k: Int) : (String, Int) = a match { |
91 case Num(i) => i"ldc $i" |
123 case Num(i) => (i"%$k = add i32 0, i32 $i", k) |
92 case Var(s) => i"iload ${env(s)}" |
124 case Var(s) => (i"%$k = add i32 0, i32 %${env(s)}", k) |
93 case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd" |
125 case Aop("+", a1, a2) => { |
94 case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub" |
126 val (cs1, k1) = compile_exp(a1, env, k) |
95 case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul" |
127 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
96 case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv" |
128 (cs1 ++ cs2 ++ i"%${k2+1} = add i32 %$k1, i32 %$k2", k2 + 1) |
97 case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem" |
129 } |
|
130 case Aop("-", a1, a2) => { |
|
131 val (cs1, k1) = compile_exp(a1, env, k) |
|
132 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
|
133 (cs1 ++ cs2 ++ i"%${k2+1} = sub i32 %$k1, i32 %$k2", k2 + 1) |
|
134 } |
|
135 case Aop("*", a1, a2) => { |
|
136 val (cs1, k1) = compile_exp(a1, env, k) |
|
137 val (cs2, k2) = compile_exp(a2, env, k1 + 1) |
|
138 (cs1 ++ cs2 ++ i"%${k2+1} = mul i32 %$k1, i32 %$k2", k2 + 1) |
|
139 } |
|
140 /* |
98 case If(b, a1, a2) => { |
141 case If(b, a1, a2) => { |
99 val if_else = Fresh("If_else") |
142 val if_else = Fresh("If_else") |
100 val if_end = Fresh("If_end") |
143 val if_end = Fresh("If_end") |
101 compile_bexp(b, env, if_else) ++ |
144 compile_bexp(b, env, if_else) ++ |
102 compile_exp(a1, env) ++ |
145 compile_exp(a1, env) ++ |
116 case Write(a1) => { |
159 case Write(a1) => { |
117 compile_exp(a1, env) ++ |
160 compile_exp(a1, env) ++ |
118 i"dup" ++ |
161 i"dup" ++ |
119 i"invokestatic XXX/XXX/write(I)V" |
162 i"invokestatic XXX/XXX/write(I)V" |
120 } |
163 } |
121 } |
164 */ |
|
165 } |
|
166 |
|
167 val e = Aop("*", Aop("+", Num(2), Num(4)), Num(5)) |
|
168 compile_exp(e, Map(), 1)._1.mkString |
|
169 |
122 |
170 |
123 // compile boolean expressions |
171 // compile boolean expressions |
124 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
172 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { |
125 case Bop("==", a1, a2) => |
173 case Bop("==", a1, a2) => |
126 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" |
174 compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp" |