625
|
1 |
// A Small Compiler for a Simple Functional Language
|
644
|
2 |
// (includes an external lexer and parser)
|
645
|
3 |
//
|
|
4 |
// call with
|
|
5 |
//
|
|
6 |
// scala fun.scala fact
|
|
7 |
//
|
|
8 |
// scala fun.scala defs
|
|
9 |
//
|
|
10 |
// this will generate a .j file and run the jasmin
|
|
11 |
// assembler (installed at jvm/jasmin-2.4/jasmin.jar)
|
|
12 |
// it runs the resulting JVM file twice for timing
|
|
13 |
// purposes.
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
|
645
|
15 |
|
|
16 |
|
625
|
17 |
|
644
|
18 |
object Compiler {
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
645
|
20 |
import java.io._
|
|
21 |
import scala.util._
|
|
22 |
import scala.sys.process._
|
|
23 |
|
644
|
24 |
// Abstract syntax trees for the Fun language
|
|
25 |
abstract class Exp extends Serializable
|
|
26 |
abstract class BExp extends Serializable
|
|
27 |
abstract class Decl extends Serializable
|
626
|
28 |
|
|
29 |
case class Def(name: String, args: List[String], body: Exp) extends Decl
|
|
30 |
case class Main(e: Exp) extends Decl
|
|
31 |
|
|
32 |
case class Call(name: String, args: List[Exp]) extends Exp
|
|
33 |
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
|
|
34 |
case class Write(e: Exp) extends Exp
|
|
35 |
case class Var(s: String) extends Exp
|
|
36 |
case class Num(i: Int) extends Exp
|
|
37 |
case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
|
|
38 |
case class Sequence(e1: Exp, e2: Exp) extends Exp
|
|
39 |
case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
|
|
40 |
|
|
41 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
// compiler - built-in functions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
// copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
//
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
val library = """
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
.class public XXX.XXX
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
.super java/lang/Object
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
.method public <init>()V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
aload_0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
invokenonvirtual java/lang/Object/<init>()V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
.end method
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
.method public static write(I)V
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
.limit locals 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
.limit stack 2
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
getstatic java/lang/System/out Ljava/io/PrintStream;
|
380
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
iload 0
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
invokevirtual java/io/PrintStream/println(I)V
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
return
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
.end method
|
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 |
"""
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
|
626
|
67 |
// calculating the maximal needed stack size
|
|
68 |
def max_stack_exp(e: Exp): Int = e match {
|
|
69 |
case Call(_, args) => args.map(max_stack_exp).sum
|
|
70 |
case If(a, e1, e2) => max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e2)).max)
|
|
71 |
case Write(e) => max_stack_exp(e) + 1
|
|
72 |
case Var(_) => 1
|
|
73 |
case Num(_) => 1
|
|
74 |
case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
|
|
75 |
case Sequence(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max
|
|
76 |
}
|
644
|
77 |
|
626
|
78 |
def max_stack_bexp(e: BExp): Int = e match {
|
|
79 |
case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
|
|
80 |
}
|
|
81 |
|
|
82 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
// for generating new labels
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
84 |
var counter = -1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
def Fresh(x: String) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
counter += 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
x ++ "_" ++ counter.toString()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
|
625
|
91 |
// convenient string interpolations
|
|
92 |
// for instructions, labels and methods
|
|
93 |
import scala.language.implicitConversions
|
|
94 |
import scala.language.reflectiveCalls
|
|
95 |
|
|
96 |
implicit def sring_inters(sc: StringContext) = new {
|
|
97 |
def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n"
|
|
98 |
def l(args: Any*): String = sc.s(args:_*) ++ ":\n"
|
|
99 |
def m(args: Any*): String = sc.s(args:_*) ++ "\n"
|
|
100 |
}
|
|
101 |
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
102 |
|
625
|
103 |
type Env = Map[String, Int]
|
|
104 |
|
|
105 |
// compile expressions
|
|
106 |
def compile_exp(a: Exp, env : Env) : String = a match {
|
|
107 |
case Num(i) => i"ldc $i"
|
|
108 |
case Var(s) => i"iload ${env(s)}"
|
|
109 |
case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd"
|
|
110 |
case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub"
|
|
111 |
case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul"
|
|
112 |
case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv"
|
|
113 |
case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem"
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
114 |
case If(b, a1, a2) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
115 |
val if_else = Fresh("If_else")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
116 |
val if_end = Fresh("If_end")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
117 |
compile_bexp(b, env, if_else) ++
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
118 |
compile_exp(a1, env) ++
|
625
|
119 |
i"goto $if_end" ++
|
|
120 |
l"$if_else" ++
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
compile_exp(a2, env) ++
|
625
|
122 |
l"$if_end"
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
123 |
}
|
625
|
124 |
case Call(name, args) => {
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
val is = "I" * args.length
|
625
|
126 |
args.map(a => compile_exp(a, env)).mkString ++
|
|
127 |
i"invokestatic XXX/XXX/$name($is)I"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
}
|
625
|
129 |
case Sequence(a1, a2) => {
|
|
130 |
compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env)
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
case Write(a1) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
compile_exp(a1, env) ++
|
625
|
134 |
i"dup" ++
|
|
135 |
i"invokestatic XXX/XXX/write(I)V"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
}
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
|
625
|
139 |
// compile boolean expressions
|
|
140 |
def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
case Bop("==", a1, a2) =>
|
625
|
142 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp"
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
143 |
case Bop("!=", a1, a2) =>
|
625
|
144 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp"
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
145 |
case Bop("<", a1, a2) =>
|
625
|
146 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
case Bop("<=", a1, a2) =>
|
625
|
148 |
compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp"
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
149 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
150 |
|
625
|
151 |
// compile function for declarations and main
|
|
152 |
def compile_decl(d: Decl) : String = d match {
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
case Def(name, args, a) => {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
val env = args.zipWithIndex.toMap
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
val is = "I" * args.length
|
625
|
156 |
m".method public static $name($is)I" ++
|
|
157 |
m".limit locals ${args.length.toString}" ++
|
|
158 |
m".limit stack ${1 + max_stack_exp(a)}" ++
|
|
159 |
l"${name}_Start" ++
|
223
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
compile_exp(a, env) ++
|
625
|
161 |
i"ireturn" ++
|
|
162 |
m".end method\n"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
case Main(a) => {
|
625
|
165 |
m".method public static main([Ljava/lang/String;)V" ++
|
|
166 |
m".limit locals 200" ++
|
|
167 |
m".limit stack 200" ++
|
223
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
compile_exp(a, Map()) ++
|
625
|
169 |
i"invokestatic XXX/XXX/write(I)V" ++
|
|
170 |
i"return" ++
|
|
171 |
m".end method\n"
|
221
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
}
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
173 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
174 |
|
626
|
175 |
// main compiler functions
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
176 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
177 |
def time_needed[T](i: Int, code: => T) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
178 |
val start = System.nanoTime()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
179 |
for (j <- 1 to i) code
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
180 |
val end = System.nanoTime()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
181 |
(end - start)/(i * 1.0e9)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
182 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
183 |
|
645
|
184 |
def deserialise[T](fname: String) : Try[T] = {
|
|
185 |
import scala.util.Using
|
|
186 |
Using(new ObjectInputStream(new FileInputStream(fname))) {
|
|
187 |
in => in.readObject.asInstanceOf[T]
|
|
188 |
}
|
644
|
189 |
}
|
|
190 |
|
|
191 |
def compile(class_name: String) : String = {
|
645
|
192 |
val ast = deserialise[List[Decl]](class_name ++ ".prs").getOrElse(Nil)
|
626
|
193 |
val instructions = ast.map(compile_decl).mkString
|
|
194 |
(library + instructions).replaceAllLiterally("XXX", class_name)
|
|
195 |
}
|
|
196 |
|
644
|
197 |
def compile_to_file(class_name: String) = {
|
|
198 |
val output = compile(class_name)
|
626
|
199 |
scala.tools.nsc.io.File(s"${class_name}.j").writeAll(output)
|
|
200 |
}
|
|
201 |
|
645
|
202 |
def compile_and_run(class_name: String) : Unit = {
|
644
|
203 |
compile_to_file(class_name)
|
626
|
204 |
(s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!!
|
625
|
205 |
println("Time: " + time_needed(2, (s"java ${class_name}/${class_name}").!))
|
220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
206 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
207 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
208 |
|
626
|
209 |
// some examples of .fun files
|
645
|
210 |
//compile_to_file("fact")
|
|
211 |
//compile_and_run("fact")
|
|
212 |
//compile_and_run("defs")
|
|
213 |
|
644
|
214 |
|
|
215 |
def main(args: Array[String]) =
|
645
|
216 |
compile_and_run(args(0))
|
644
|
217 |
|
|
218 |
|
|
219 |
} |