1 // A Small Compiler for a Simple Functional Language |
1 // A Small LLVM Compiler for a Simple Functional Language |
2 // (includes an external lexer and parser) |
2 // (includes an external lexer and parser) |
3 // |
3 // |
4 // call with |
4 // call with |
5 // |
5 // |
6 // scala fun.scala fact |
6 // scala fun_llvm.scala fact |
7 // |
7 // |
8 // scala fun.scala defs |
8 // scala fun_llvm.scala defs |
9 // |
9 // |
10 // this will generate a .j file and run the jasmin |
10 // this will generate a .ll file |
11 // assembler (installed at jvm/jasmin-2.4/jasmin.jar) |
|
12 // it runs the resulting JVM file twice for timing |
|
13 // purposes. |
|
14 |
|
15 |
|
16 |
11 |
17 |
12 |
18 object Compiler { |
13 object Compiler { |
19 |
14 |
20 import java.io._ |
15 import java.io._ |
70 case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { |
63 case class KLet(x: String, e1: KVal, e2: KExp) extends KExp { |
71 override def toString = s"let $x = $e1 in \n$e2" |
64 override def toString = s"let $x = $e1 in \n$e2" |
72 } |
65 } |
73 case class KReturn(v: KVal) extends KExp |
66 case class KReturn(v: KVal) extends KExp |
74 |
67 |
|
68 |
|
69 // CPS translation from Exp's to KExp's using a |
|
70 // continuation k. |
75 def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { |
71 def CPS(e: Exp)(k: KVal => KExp) : KExp = e match { |
76 case Var(s) => k(KVar(s)) |
72 case Var(s) => k(KVar(s)) |
77 case Num(i) => k(KNum(i)) |
73 case Num(i) => k(KNum(i)) |
78 case Aop(o, e1, e2) => { |
74 case Aop(o, e1, e2) => { |
79 val z = Fresh("tmp") |
75 val z = Fresh("tmp") |
102 } |
98 } |
103 } |
99 } |
104 |
100 |
105 def CPSi(e: Exp) = CPS(e)(KReturn) |
101 def CPSi(e: Exp) = CPS(e)(KReturn) |
106 |
102 |
|
103 // some testcases |
107 val e1 = Aop("*", Var("a"), Num(3)) |
104 val e1 = Aop("*", Var("a"), Num(3)) |
108 CPS(e1)(KReturn) |
105 CPSi(e1) |
109 |
106 |
110 val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4)) |
107 val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4)) |
111 CPS(e2)(KReturn) |
108 CPSi(e2) |
112 |
109 |
113 val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3))) |
110 val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3))) |
114 CPS(e3)(KReturn) |
111 CPSi(e3) |
115 |
112 |
116 val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3))) |
113 val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3))) |
117 CPS(e4)(KReturn) |
114 CPSi(e4) |
118 |
115 |
119 val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4)) |
116 val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4)) |
120 CPS(e5)(KReturn) |
117 CPSi(e5) |
121 |
118 |
122 val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40)) |
119 val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40)) |
123 CPS(e6)(KReturn) |
120 CPSi(e6) |
124 |
121 |
125 val e7 = Call("foo", List(Num(3))) |
122 val e7 = Call("foo", List(Num(3))) |
126 CPS(e7)(KReturn) |
123 CPSi(e7) |
127 |
124 |
128 val e8 = Call("foo", List(Num(3), Num(4), Aop("+", Num(5), Num(6)))) |
125 val e8 = Call("foo", List(Num(3), Num(4), Aop("+", Num(5), Num(6)))) |
129 CPS(e8)(KReturn) |
126 CPSi(e8) |
130 |
127 |
131 val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6))) |
128 val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6))) |
132 CPS(e9)(KReturn) |
129 CPSi(e9) |
133 |
130 |
134 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
131 val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4)) |
135 CPS(e)(KReturn) |
132 CPSi(e) |
136 |
133 |
137 |
134 |
138 |
135 |
139 |
136 |
140 // convenient string interpolations |
137 // convenient string interpolations |
193 |
190 |
194 |
191 |
195 // compile function for declarations and main |
192 // compile function for declarations and main |
196 def compile_decl(d: Decl) : String = d match { |
193 def compile_decl(d: Decl) : String = d match { |
197 case Def(name, args, body) => { |
194 case Def(name, args, body) => { |
198 //println(s"DEF\n $name ($args) = \nBODY:") |
|
199 //println(CPSi(body)) |
|
200 //println() |
|
201 //counter = -1 |
|
202 m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ |
195 m"define i32 @$name (${args.mkString("i32 %", ", i32 %", "")}) {" ++ |
203 compile_exp(CPSi(body)) ++ |
196 compile_exp(CPSi(body)) ++ |
204 m"}\n" |
197 m"}\n" |
205 } |
198 } |
206 case Main(body) => { |
199 case Main(body) => { |