progs/fun-bare.scala
changeset 624 8d0af38389bc
parent 323 4ce07c4abdb4
child 625 6709fa87410b
equal deleted inserted replaced
623:47a299e7010f 624:8d0af38389bc
     1 // A Small Compiler for a simple functional language
     1 // A Small Compiler for a Simple Functional Language
       
     2 // (it does not use a parser and lexer)
     2 
     3 
     3 // Abstract syntax trees
     4 // Abstract syntax trees
     4 abstract class Exp
     5 abstract class Exp
     5 abstract class BExp 
     6 abstract class BExp 
     6 abstract class Decl
     7 abstract class Decl
    67 def Fresh(x: String) = {
    68 def Fresh(x: String) = {
    68   counter += 1
    69   counter += 1
    69   x ++ "_" ++ counter.toString()
    70   x ++ "_" ++ counter.toString()
    70 }
    71 }
    71 
    72 
       
    73 // convenient string interpolations 
       
    74 // for instructions, labels and methods
       
    75 import scala.language.implicitConversions
       
    76 import scala.language.reflectiveCalls
       
    77 
       
    78 implicit def sring_inters(sc: StringContext) = new {
       
    79     def i(args: Any*): String = "   " ++ sc.s(args:_*) ++ "\n"
       
    80     def l(args: Any*): String = sc.s(args:_*) ++ ":\n"
       
    81     def m(args: Any*): String = sc.s(args:_*) ++ "\n"
       
    82 }
    72 
    83 
    73 type Env = Map[String, Int]
    84 type Env = Map[String, Int]
    74 type Instrs = List[String]
       
    75 
    85 
    76 // compile expressions
    86 // compile expressions
    77 def compile_exp(a: Exp, env : Env) : Instrs = a match {
    87 def compile_exp(a: Exp, env : Env) : String = a match {
    78   case Num(i) => List("ldc " + i.toString + "\n")
    88   case Num(i) => i"ldc $i"
    79   case Var(s) => List("iload " + env(s).toString + "\n")
    89   case Var(s) => i"iload ${env(s)}"
    80   case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("iadd\n")
    90   case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd"
    81   case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("isub\n")
    91   case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub"
    82   case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("imul\n")
    92   case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul"
    83   case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("idiv\n")
    93   case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv"
    84   case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("irem\n")
    94   case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem"
    85   case If(b, a1, a2) => {
    95   case If(b, a1, a2) => {
    86     val if_else = Fresh("If_else")
    96     val if_else = Fresh("If_else")
    87     val if_end = Fresh("If_end")
    97     val if_end = Fresh("If_end")
    88     compile_bexp(b, env, if_else) ++
    98     compile_bexp(b, env, if_else) ++
    89     compile_exp(a1, env) ++
    99     compile_exp(a1, env) ++
    90     List("goto " + if_end + "\n") ++
   100     i"goto $if_end" ++
    91     List("\n" + if_else + ":\n\n") ++
   101     l"$if_else" ++
    92     compile_exp(a2, env) ++
   102     compile_exp(a2, env) ++
    93     List("\n" + if_end + ":\n\n")
   103     l"$if_end"
    94   }
   104   }
    95   case Call(n, args) => {
   105   case Call(name, args) => {
    96     val is = "I" * args.length
   106     val is = "I" * args.length
    97     args.flatMap(a => compile_exp(a, env)) ++
   107     args.map(a => compile_exp(a, env)).mkString ++
    98     List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
   108     i"invokestatic XXX/XXX/$name($is)I"
    99   }
   109   }
   100   case Sequ(a1, a2) => {
   110   case Sequ(a1, a2) => {
   101     compile_exp(a1, env) ++ List("pop\n") ++ compile_exp(a2, env)
   111     compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env)
   102   }
   112   }
   103   case Write(a1) => {
   113   case Write(a1) => {
   104     compile_exp(a1, env) ++
   114     compile_exp(a1, env) ++
   105     List("dup\n",
   115     i"dup" ++
   106          "invokestatic XXX/XXX/write(I)V\n")
   116     i"invokestatic XXX/XXX/write(I)V"
   107   }
   117   }
   108 }
   118 }
   109 
   119 
   110 // compile boolean expressions
   120 // compile boolean expressions
   111 def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match {
   121 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
   112   case Bop("==", a1, a2) => 
   122   case Bop("==", a1, a2) => 
   113     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n")
   123     compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp"
   114   case Bop("!=", a1, a2) => 
   124   case Bop("!=", a1, a2) => 
   115     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
   125     compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp"
   116   case Bop("<", a1, a2) => 
   126   case Bop("<", a1, a2) => 
   117     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n")
   127     compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp"
   118   case Bop("<=", a1, a2) => 
   128   case Bop("<=", a1, a2) => 
   119     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n")
   129     compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp"
   120 }
   130 }
   121 
   131 
   122 // compile function for declarations and main
   132 // compile function for declarations and main
   123 def compile_decl(d: Decl) : Instrs = d match {
   133 def compile_decl(d: Decl) : String = d match {
   124   case Def(name, args, a) => { 
   134   case Def(name, args, a) => { 
   125     val env = args.zipWithIndex.toMap
   135     val env = args.zipWithIndex.toMap
   126     val is = "I" * args.length
   136     val is = "I" * args.length
   127     List(".method public static " + name + "(" + is + ")I \n",
   137     m".method public static $name($is)I" ++
   128          ".limit locals " + args.length.toString + "\n",
   138     m".limit locals ${args.length.toString}" ++
   129          ".limit stack " + (1 + max_stack_exp(a)).toString + "\n",
   139     m".limit stack ${1 + max_stack_exp(a)}" ++
   130          name + "_Start:\n") ++   
   140     l"${name}_Start" ++   
   131     compile_exp(a, env) ++
   141     compile_exp(a, env) ++
   132     List("ireturn\n",
   142     i"ireturn" ++
   133          ".end method \n\n")
   143     m".end method\n"
   134   }
   144   }
   135   case Main(a) => {
   145   case Main(a) => {
   136     List(".method public static main([Ljava/lang/String;)V\n",
   146     m".method public static main([Ljava/lang/String;)V" ++
   137          ".limit locals 200\n",
   147     m".limit locals 200" ++
   138          ".limit stack 200\n") ++
   148     m".limit stack 200" ++
   139     compile_exp(a, Map()) ++
   149     compile_exp(a, Map()) ++
   140     List("invokestatic XXX/XXX/write(I)V\n",
   150     i"invokestatic XXX/XXX/write(I)V" ++
   141          "return\n",
   151     i"return" ++
   142          ".end method\n")
   152     m".end method\n"
   143   }
   153   }
   144 }
   154 }
   145 
   155 
   146 // main compilation function
   156 // main compilation function
   147 def compile(prog: List[Decl], class_name: String) : String = {
   157 def compile(prog: List[Decl], class_name: String) : String = {
   148   val instructions = prog.flatMap(compile_decl).mkString
   158   val instructions = prog.map(compile_decl).mkString
   149   (library + instructions).replaceAllLiterally("XXX", class_name)
   159   (library + instructions).replaceAllLiterally("XXX", class_name)
   150 }
   160 }
   151 
   161 
   152 
   162 
   153 
   163 
   169 
   179 
   170        Main(Sequ(Write(Call("fact",List(Num(10)))),
   180        Main(Sequ(Write(Call("fact",List(Num(10)))),
   171                  Write(Call("facT",List(Num(10), Num(1)))))))
   181                  Write(Call("facT",List(Num(10), Num(1)))))))
   172 
   182 
   173 // prints out the JVM instructions
   183 // prints out the JVM instructions
   174 println(compile(test, "fact"))
   184 println(compile(test_prog, "fact"))