Mercurial Mercurial > hg > afl-material / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
progs/fun.scala
changeset 221 824ffbf66ab4
parent 220 141041fc76b5
child 223 e4b29b57f6a3
equal deleted inserted replaced
220:141041fc76b5 221:824ffbf66ab4 
     1 import scala.language.implicitConversions    
     1 import scala.language.implicitConversions    
     2 import scala.language.reflectiveCalls 
     2 import scala.language.reflectiveCalls 
     3 import scala.util._
 
     3 import scala.util._
 
     4 import scala.annotation.tailrec
 
     4 import scala.annotation.tailrec
 
     5 import scala.sys.process._
 
     5 import scala.sys.process._
 
       
     6 
       
     7 def fromFile(name: String) : String = 
       
     8   io.Source.fromFile(name).mkString
 
     6 
     9 
     7 abstract class Rexp 
    10 abstract class Rexp 
     8 case object NULL extends Rexp
 
    11 case object NULL extends Rexp
 
     9 case object EMPTY extends Rexp
 
    12 case object EMPTY extends Rexp
 
    10 case class CHAR(c: Char) extends Rexp
 
    13 case class CHAR(c: Char) extends Rexp
 
   114 // regular expressions for the While language
 
   117 // regular expressions for the While language
 
   115 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_")
 
   118 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_")
 
   116 val DIGIT = RANGE("0123456789")
 
   119 val DIGIT = RANGE("0123456789")
 
   117 val ID = SYM ~ (SYM | DIGIT).% 
   120 val ID = SYM ~ (SYM | DIGIT).% 
   118 val NUM = PLUS(DIGIT)
 
   121 val NUM = PLUS(DIGIT)
 
   119 val KEYWORD : Rexp = "if" | "then" | "else" | "read" | "write" | "def"
 
   122 val KEYWORD : Rexp = "if" | "then" | "else" | "write" | "def"
 
   120 val SEMI: Rexp = ";"
 
   123 val SEMI: Rexp = ";"
 
   121 val COMMA: Rexp = ","
 
   124 val COMMA: Rexp = ","
 
   122 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "%" | "=" | "/"
 
   125 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<=" | "=>" | "<" | ">" | "%" | "=" | "/"
 
   123 val WHITESPACE = PLUS(" " | "\n" | "\t")
 
   126 val WHITESPACE = PLUS(" " | "\n" | "\t")
 
   124 val RPAREN: Rexp = ")"
 
   127 val RPAREN: Rexp = ")"
 
   125 val LPAREN: Rexp = "("
 
   128 val LPAREN: Rexp = "("
 
   126 val BEGIN: Rexp = "{"
 
       
   127 val END: Rexp = "}"
 
       
   128 val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "\"" | "=" | "," | "(" | ")"
 
   129 val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "\"" | "=" | "," | "(" | ")"
 
   129 val ALL2 = ALL | "\n"
 
   130 val ALL2 = ALL | "\n"
 
   130 val COMMENT2 = ("/*" ~ NOT(ALL.% ~ "*/" ~ ALL.%) ~ "*/")
 
   131 //val COMMENT2 = ("/*" ~ NOT(ALL.% ~ "*/" ~ ALL.%) ~ "*/")
 
   131 val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n")
 
   132 val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n")
 
   132 val STRING = "\"" ~ ALL.% ~ "\""
 
   133 
   133 
   134 
   134 
   135 // token for While language
 
   135 // token for While languag
 
       
   136 abstract class Token
 
   136 abstract class Token
 
   137 case object T_WHITESPACE extends Token
 
   137 case object T_WHITESPACE extends Token
 
   138 case object T_SEMI extends Token
 
   138 case object T_SEMI extends Token
 
   139 case object T_COMMA extends Token
 
   139 case object T_COMMA extends Token
 
   140 case object T_LPAREN extends Token
 
   140 case object T_LPAREN extends Token
 
   141 case object T_RPAREN extends Token
 
   141 case object T_RPAREN extends Token
 
   142 case object T_BEGIN extends Token
 
       
   143 case object T_END extends Token
 
       
   144 case object T_COMMENT extends Token
 
   142 case object T_COMMENT extends Token
 
   145 case class T_ID(s: String) extends Token
 
   143 case class T_ID(s: String) extends Token
 
   146 case class T_OP(s: String) extends Token
 
   144 case class T_OP(s: String) extends Token
 
   147 case class T_NUM(s: String) extends Token
 
   145 case class T_NUM(s: String) extends Token
 
   148 case class T_KWD(s: String) extends Token
 
   146 case class T_KWD(s: String) extends Token
 
   149 case class T_STRING(s: String) extends Token
 
       
   150 case class T_ERR(s: String) extends Token // special error token
 
   147 case class T_ERR(s: String) extends Token // special error token
 
   151 
   148 
   152 
   149 
   153 type TokenFun = String => Token
 
   150 type TokenFun = String => Token
 
   154 type LexRules = List[(Rexp, TokenFun)]
 
   151 type LexRules = List[(Rexp, TokenFun)]
 
   160        (NUM, (s) => T_NUM(s)),
 
   157        (NUM, (s) => T_NUM(s)),
 
   161        (SEMI, (s) => T_SEMI),
 
   158        (SEMI, (s) => T_SEMI),
 
   162        (COMMA, (s) => T_COMMA),
 
   159        (COMMA, (s) => T_COMMA),
 
   163        (LPAREN, (s) => T_LPAREN),
 
   160        (LPAREN, (s) => T_LPAREN),
 
   164        (RPAREN, (s) => T_RPAREN),
 
   161        (RPAREN, (s) => T_RPAREN),
 
   165        (BEGIN, (s) => T_BEGIN),
 
       
   166        (END, (s) => T_END),
 
       
   167        (STRING, (s) => T_STRING(s.drop(1).dropRight(1))),
 
       
   168        (WHITESPACE, (s) => T_WHITESPACE))
 
   162        (WHITESPACE, (s) => T_WHITESPACE))
 
   169 
   163 
   170 
   164 
   171 // calculates derivatives until all of them are zeroable
 
   165 // calculates derivatives until all of them are zeroable
 
   172 @tailrec
 
   166 @tailrec
 
   202     case T_WHITESPACE => false
 
   196     case T_WHITESPACE => false
 
   203     case T_COMMENT => false
 
   197     case T_COMMENT => false
 
   204     case _ => true
 
   198     case _ => true
 
   205   } 
   199   } 
   206 
   200 
   207 def fromFile(name: String) : String = 
   201 
   208   io.Source.fromFile(name).mkString
 
       
   209 
       
   210 // tokenizer tests
 
       
   211 //println(tokenizer(fromFile("loops.while")).mkString("\n"))
 
       
   212 //println(tokenizer(fromFile("fib.while")).mkString("\n"))
 
       
   213 //println(tokenizer(fromFile("collatz.while")).mkString("\n"))
 
       
   214 //println(tokenizer(fromFile("defs.rec")).mkString("\n"))
 
       
   215 
   202 
   216 // Parser - Abstract syntax trees
 
   203 // Parser - Abstract syntax trees
 
   217 abstract class Exp
 
   204 abstract class Exp
 
   218 abstract class BExp 
   205 abstract class BExp 
   219 abstract class Decl
 
   206 abstract class Decl
 
   221 case class Def(name: String, args: List[String], body: Exp) extends Decl
 
   208 case class Def(name: String, args: List[String], body: Exp) extends Decl
 
   222 case class Main(e: Exp) extends Decl
 
   209 case class Main(e: Exp) extends Decl
 
   223 
   210 
   224 case class Call(name: String, args: List[Exp]) extends Exp
 
   211 case class Call(name: String, args: List[Exp]) extends Exp
 
   225 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
 
   212 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
 
   226 case class Read(s: String) extends Exp
 
   213 case class Write(e: Exp) extends Exp
 
   227 case class Write(s: String) extends Exp
 
       
   228 case class WriteS(s: String) extends Exp
 
       
   229 case class Var(s: String) extends Exp
 
   214 case class Var(s: String) extends Exp
 
   230 case class Num(i: Int) extends Exp
 
   215 case class Num(i: Int) extends Exp
 
   231 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
 
   216 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
 
   232 
   217 case class Sequ(e1: Exp, e2: Exp) extends Exp
 
   233 case object True extends BExp
 
   218 
   234 case object False extends BExp
 
       
   235 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
 
   219 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
 
       
   220 
       
   221 // calculating the maximal needed stack size
 
       
   222 def max_stack_exp(e: Exp): Int = e match {
 
       
   223   case Call(_, args) => args.map(max_stack_exp).sum
 
       
   224   case If(a, e1, e2) => max_stack_bexp(a) + (List(max_stack_exp(e1), max_stack_exp(e1)).max)
 
       
   225   case Write(e) => max_stack_exp(e) + 1
 
       
   226   case Var(_) => 1
 
       
   227   case Num(_) => 1
 
       
   228   case Aop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
 
       
   229   case Sequ(e1, e2) => List(max_stack_exp(e1), max_stack_exp(e2)).max
 
       
   230 }
 
       
   231 def max_stack_bexp(e: BExp): Int = e match {
 
       
   232   case Bop(_, a1, a2) => max_stack_exp(a1) + max_stack_exp(a2)
 
       
   233 }
 
       
   234 
       
   235 
   236 
   236 
   237 // Parser combinators
 
   237 // Parser combinators
 
   238 abstract class Parser[I <% Seq[_], T] {
 
   238 abstract class Parser[I <% Seq[_], T] {
 
   239   def parse(ts: I): Set[(T, I)]
 
   239   def parse(ts: I): Set[(T, I)]
 
   240 
   240 
   283     case T_ID(s)::ts => Set((s, ts)) 
   283     case T_ID(s)::ts => Set((s, ts)) 
   284     case _ => Set ()
 
   284     case _ => Set ()
 
   285   }
 
   285   }
 
   286 }
 
   286 }
 
   287 
   287 
   288 case object StringParser extends Parser[List[Token], String] {
 
       
   289   def parse(ts: List[Token]) = ts match {
 
       
   290     case T_STRING(s)::ts => Set((s, ts)) 
       
   291     case _ => Set ()
 
       
   292   }
 
       
   293 }
 
       
   294 
   288 
   295 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
 
   289 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
 
   296   def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
 
   290   def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
 
   297   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
 
   291   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
 
   298   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
 
   292   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
 
   307   (p ~ q ~ ListParser(p, q)) ==> { case ((x, y), z) => x :: z : List[T] } ||
 
   301   (p ~ q ~ ListParser(p, q)) ==> { case ((x, y), z) => x :: z : List[T] } ||
 
   308   (p ==> ((s) => List(s)))
 
   302   (p ==> ((s) => List(s)))
 
   309 }
 
   303 }
 
   310 
   304 
   311 
   305 
   312 // arithmetic expressions
 
   306 // expressions
 
   313 lazy val Exp: Parser[List[Token], Exp] = 
   307 lazy val Exp: Parser[List[Token], Exp] = 
   314   (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> 
       
   315     { case (((x, y), z), w) => Call(x, z): Exp } ||
 
       
   316   (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==>
 
   308   (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==>
 
   317     { case (((((x, y), z), u), v), w) => If(y, u, w): Exp } ||
 
   309     { case (((((x, y), z), u), v), w) => If(y, u, w): Exp } ||
 
       
   310   (M ~ T_SEMI ~ Exp) ==> { case ((x, y), z) => Sequ(x, z): Exp } || M
 
       
   311 lazy val M: Parser[List[Token], Exp] =
 
       
   312   (T_KWD("write") ~ L) ==> { case (x, y) => Write(y): Exp } || L
 
       
   313 lazy val L: Parser[List[Token], Exp] = 
   318   (T ~ T_OP("+") ~ Exp) ==> { case ((x, y), z) => Aop("+", x, z): Exp } ||
 
   314   (T ~ T_OP("+") ~ Exp) ==> { case ((x, y), z) => Aop("+", x, z): Exp } ||
 
   319   (T ~ T_OP("-") ~ Exp) ==> { case ((x, y), z) => Aop("-", x, z): Exp } || T  
   315   (T ~ T_OP("-") ~ Exp) ==> { case ((x, y), z) => Aop("-", x, z): Exp } || T  
   320 lazy val T: Parser[List[Token], Exp] = 
   316 lazy val T: Parser[List[Token], Exp] = 
   321   (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): Exp } || 
   317   (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): Exp } || 
   322   (F ~ T_OP("/") ~ T) ==> { case ((x, y), z) => Aop("/", x, z): Exp } || 
   318   (F ~ T_OP("/") ~ T) ==> { case ((x, y), z) => Aop("/", x, z): Exp } || 
   323   (F ~ T_OP("%") ~ T) ==> { case ((x, y), z) => Aop("%", x, z): Exp } || F
 
   319   (F ~ T_OP("%") ~ T) ==> { case ((x, y), z) => Aop("%", x, z): Exp } || F
 
   324 lazy val F: Parser[List[Token], Exp] = 
   320 lazy val F: Parser[List[Token], Exp] = 
       
   321   (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> 
       
   322     { case (((x, y), z), w) => Call(x, z): Exp } ||
 
   325   (T_LPAREN ~ Exp ~ T_RPAREN) ==> { case ((x, y), z) => y: Exp } || 
   323   (T_LPAREN ~ Exp ~ T_RPAREN) ==> { case ((x, y), z) => y: Exp } || 
   326   IdParser ==> { case x => Var(x): Exp } || 
   324   IdParser ==> { case x => Var(x): Exp } || 
   327   NumParser ==> { case x => Num(x): Exp }
 
   325   NumParser ==> { case x => Num(x): Exp }
 
   328 
   326 
   329 // boolean expressions
 
   327 // boolean expressions
 
   330 lazy val BExp: Parser[List[Token], BExp] = 
   328 lazy val BExp: Parser[List[Token], BExp] = 
   331   (Exp ~ T_OP("==") ~ Exp) ==> { case ((x, y), z) => Bop("==", x, z): BExp } || 
   329   (Exp ~ T_OP("==") ~ Exp) ==> { case ((x, y), z) => Bop("==", x, z): BExp } || 
   332   (Exp ~ T_OP("!=") ~ Exp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
   330   (Exp ~ T_OP("!=") ~ Exp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
   333   (Exp ~ T_OP("<") ~ Exp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
   331   (Exp ~ T_OP("<") ~ Exp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
   334   (Exp ~ T_OP(">") ~ Exp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } || 
   332   (Exp ~ T_OP(">") ~ Exp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } || 
   335   (T_KWD("true") ==> ((_) => True)) || 
   333   (Exp ~ T_OP("<=") ~ Exp) ==> { case ((x, y), z) => Bop("<=", x, z): BExp } || 
   336   (T_KWD("false") ==> ((_) => False: BExp))
 
   334   (Exp ~ T_OP("=>") ~ Exp) ==> { case ((x, y), z) => Bop("<=", z, x): BExp }  
   337 
   335 
   338 lazy val Defn: Parser[List[Token], Decl] =
 
   336 lazy val Defn: Parser[List[Token], Decl] =
 
   339    (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(IdParser, T_COMMA) ~ T_RPAREN ~ T_OP("=") ~ Exp) ==>
 
   337    (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(IdParser, T_COMMA) ~ T_RPAREN ~ T_OP("=") ~ Exp) ==>
 
   340      { case ((((((x, y), z), w), u), v), r) => Def(y, w, r): Decl }
 
   338      { case ((((((x, y), z), w), u), v), r) => Def(y, w, r): Decl }
 
   341 
   339 
   342 lazy val Prog: Parser[List[Token], List[Decl]] =
 
   340 lazy val Prog: Parser[List[Token], List[Decl]] =
 
   343   (Defn ~ T_SEMI ~ Prog) ==> { case ((x, y), z) => x :: z : List[Decl] } ||
 
   341   (Defn ~ T_SEMI ~ Prog) ==> { case ((x, y), z) => x :: z : List[Decl] } ||
 
   344   (Exp ==> ((s) => List(Main(s)) : List[Decl]))
 
   342   (Exp ==> ((s) => List(Main(s)) : List[Decl]))
 
   345 
   343 
   346 // parser examples
 
   344 // parser examples
 
   347 
       
   348 val p11 = """def zero(x) = 0"""
 
       
   349 val p11_toks = tokenizer(p11) 
       
   350 val p11_ast = Defn.parse_all(p11_toks)
 
       
   351 //println(p11_toks)
 
       
   352 //println(p11_ast)
 
       
   353 
       
   354 
   345 
   355 val p12_toks = tokenizer(fromFile("defs.rec"))
 
   346 val p12_toks = tokenizer(fromFile("defs.rec"))
 
   356 val p12_ast = Prog.parse_all(p12_toks)
 
   347 val p12_ast = Prog.parse_all(p12_toks)
 
   357 //println(p12_toks.mkString(","))
 
   348 //println(p12_toks.mkString(","))
 
   358 //println(p12_ast)
 
   349 //println(p12_ast)
 
   361 
   352 
   362 // compiler - built-in functions 
   353 // compiler - built-in functions 
   363 // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
 
   354 // copied from http://www.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html
 
   364 //
 
   355 //
 
   365 
   356 
   366 val beginning = """
 
   357 val library = """
 
   367 .class public XXX.XXX
 
   358 .class public XXX.XXX
 
   368 .super java/lang/Object
 
   359 .super java/lang/Object
 
   369 
   360 
   370 .method public <init>()V
 
   361 .method public <init>()V
 
   371         aload_0
 
   362         aload_0
 
   381         swap 
   372         swap 
   382         invokevirtual java/io/PrintStream/println(I)V 
   373         invokevirtual java/io/PrintStream/println(I)V 
   383         return 
   374         return 
   384 .end method
 
   375 .end method
 
   385 
   376 
   386 .method public static writes(Ljava/lang/String;)V
 
       
   387        .limit stack 2
 
       
   388        .limit locals 2
 
       
   389        getstatic java/lang/System/out Ljava/io/PrintStream;
 
       
   390        aload 0
 
       
   391        invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
 
       
   392        return
 
       
   393 .end method
 
       
   394 
       
   395 .method public static read()I 
       
   396       .limit locals 10 
       
   397       .limit stack 10
 
       
   398 
       
   399       ldc 0 
       
   400       istore 1  ; this will hold our final integer 
       
   401 Label1: 
       
   402       getstatic java/lang/System/in Ljava/io/InputStream; 
       
   403       invokevirtual java/io/InputStream/read()I 
       
   404       istore 2 
       
   405       iload 2 
       
   406       ldc 10   ; the newline delimiter 
       
   407       isub 
       
   408       ifeq Label2 
       
   409       iload 2 
       
   410       ldc 32   ; the space delimiter 
       
   411       isub 
       
   412       ifeq Label2
 
       
   413 
       
   414       iload 2 
       
   415       ldc 48   ; we have our digit in ASCII, have to subtract it from 48 
       
   416       isub 
       
   417       ldc 10 
       
   418       iload 1 
       
   419       imul 
       
   420       iadd 
       
   421       istore 1 
       
   422       goto Label1 
       
   423 Label2: 
       
   424       ;when we come here we have our integer computed in Local Variable 1 
       
   425       iload 1 
       
   426       ireturn 
       
   427 .end method
 
       
   428 
       
   429 .method public static main([Ljava/lang/String;)V
 
       
   430       .limit locals 200
 
       
   431       .limit stack 200
 
       
   432 
       
   433 """
 
       
   434 
       
   435 val ending = """
 
       
   436 
       
   437       return
 
       
   438 
       
   439 .end method
 
       
   440 """
 
   377 """
 
   441 
   378 
   442 // for generating new labels
 
   379 // for generating new labels
 
   443 var counter = -1
 
   380 var counter = -1
 
   444 
   381 
   445 def Fresh(x: String) = {
 
   382 def Fresh(x: String) = {
 
   446   counter += 1
 
   383   counter += 1
 
   447   x ++ "_" ++ counter.toString()
 
   384   x ++ "_" ++ counter.toString()
 
   448 }
 
   385 }
 
   449 
   386 
   450 type Mem = Map[String, String]
 
   387 type Mem = Map[String, Int]
 
   451 type Instrs = List[String]
 
   388 type Instrs = List[String]
 
   452 
   389 
   453 def compile_exp(a: Exp, env : Mem) : Instrs = a match {
 
   390 def compile_exp(a: Exp, env : Mem) : Instrs = a match {
 
   454   case Num(i) => List("ldc " + i.toString + "\n")
 
   391   case Num(i) => List("ldc " + i.toString + "\n")
 
   455   case Var(s) => List("iload " + env(s) + "\n")
 
   392   case Var(s) => List("iload " + env(s).toString + "\n")
 
   456   case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("iadd\n")
 
   393   case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("iadd\n")
 
   457   case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("isub\n")
 
   394   case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("isub\n")
 
   458   case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("imul\n")
 
   395   case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("imul\n")
 
       
   396   case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("idiv\n")
 
       
   397   case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("irem\n")
 
   459   case If(b, a1, a2) => {
 
   398   case If(b, a1, a2) => {
 
   460     val if_else = Fresh("If_else")
 
   399     val if_else = Fresh("If_else")
 
   461     val if_end = Fresh("If_end")
 
   400     val if_end = Fresh("If_end")
 
   462     compile_bexp(b, env, if_else) ++
 
   401     compile_bexp(b, env, if_else) ++
 
   463     compile_exp(a1, env) ++
 
   402     compile_exp(a1, env) ++
 
   464     List("goto " + if_end + "\n") ++
 
   403     List("goto " + if_end + "\n") ++
 
   465     List("\n" + if_else + ":\n\n") ++
 
   404     List("\n" + if_else + ":\n\n") ++
 
   466     compile_exp(a2, env) ++
 
   405     compile_exp(a2, env) ++
 
   467     List("\n" + if_end + ":\n\n")
 
   406     List("\n" + if_end + ":\n\n")
 
   468   }
 
   407   }
 
   469   case Call(n, args) => 
   408   case Call(n, args) => {
 
       
   409     val is = "I" * args.length
 
   470     args.flatMap(a => compile_exp(a, env)) ++
 
   410     args.flatMap(a => compile_exp(a, env)) ++
 
   471     List ("invokestatic XXX/XXX/" + n + "(I)I\n")
 
   411     List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
 
   472     
   412   }
 
       
   413   case Sequ(a1, a2) => {
 
       
   414     compile_exp(a1, env) ++ List("pop\n") ++ compile_exp(a2, env)
 
       
   415   }
 
       
   416   case Write(a1) => {
 
       
   417     compile_exp(a1, env) ++
 
       
   418     List("dup\n",
 
       
   419          "invokestatic XXX/XXX/write(I)V\n")
 
       
   420   }
 
   473 }
 
   421 }
 
   474 
   422 
   475 def compile_bexp(b: BExp, env : Mem, jmp: String) : Instrs = b match {
 
   423 def compile_bexp(b: BExp, env : Mem, jmp: String) : Instrs = b match {
 
   476   case True => Nil
 
   424   case Bop("==", a1, a2) => 
   477   case False => List("goto " + jmp + "\n")
 
       
   478   case Bop("=", a1, a2) => 
       
   479     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n")
 
   425     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n")
 
   480   case Bop("!=", a1, a2) => 
   426   case Bop("!=", a1, a2) => 
   481     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
 
   427     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
 
   482   case Bop("<", a1, a2) => 
   428   case Bop("<", a1, a2) => 
   483     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n")
 
   429     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n")
 
   484 }
 
   430   case Bop("<=", a1, a2) => 
   485 
   431     compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n")
 
       
   432 }
 
       
   433 
       
   434 
       
   435 def compile_expT(a: Exp, env : Mem, name: String) : Instrs = a match {
 
       
   436   case Num(i) => List("ldc " + i.toString + "\n")
 
       
   437   case Var(s) => List("iload " + env(s).toString + "\n")
 
       
   438   case Aop("+", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("iadd\n")
 
       
   439   case Aop("-", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("isub\n")
 
       
   440   case Aop("*", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("imul\n")
 
       
   441   case Aop("/", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("idiv\n")
 
       
   442   case Aop("%", a1, a2) => compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("irem\n")
 
       
   443   case If(b, a1, a2) => {
 
       
   444     val if_else = Fresh("If_else")
 
       
   445     val if_end = Fresh("If_end")
 
       
   446     compile_bexp(b, env, if_else) ++
 
       
   447     compile_expT(a1, env, name) ++
 
       
   448     List("goto " + if_end + "\n") ++
 
       
   449     List("\n" + if_else + ":\n\n") ++
 
       
   450     compile_expT(a2, env, name) ++
 
       
   451     List("\n" + if_end + ":\n\n")
 
       
   452   }
 
       
   453   case Call(n, args) => if (name == n) { 
       
   454     val stores = args.zipWithIndex.map { case (x, y) => "istore " + y.toString + "\n" } 
       
   455     args.flatMap(a => compile_expT(a, env, "")) ++
 
       
   456     stores.reverse ++ 
       
   457     List ("goto " + n + "_Start\n") 
       
   458   } else {
 
       
   459     val is = "I" * args.length
 
       
   460     args.flatMap(a => compile_expT(a, env, "")) ++
 
       
   461     List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
 
       
   462   }
 
       
   463   case Sequ(a1, a2) => {
 
       
   464     compile_expT(a1, env, "") ++ List("pop\n") ++ compile_expT(a2, env, name)
 
       
   465   }
 
       
   466   case Write(a1) => {
 
       
   467     compile_expT(a1, env, "") ++
 
       
   468     List("dup\n",
 
       
   469          "invokestatic XXX/XXX/write(I)V\n")
 
       
   470   }
 
       
   471 }
 
       
   472 
       
   473 def compile_bexpT(b: BExp, env : Mem, jmp: String) : Instrs = b match {
 
       
   474   case Bop("==", a1, a2) => 
       
   475     compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpne " + jmp + "\n")
 
       
   476   case Bop("!=", a1, a2) => 
       
   477     compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpeq " + jmp + "\n")
 
       
   478   case Bop("<", a1, a2) => 
       
   479     compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpge " + jmp + "\n")
 
       
   480   case Bop("<=", a1, a2) => 
       
   481     compile_expT(a1, env, "") ++ compile_expT(a2, env, "") ++ List("if_icmpgt " + jmp + "\n")
 
       
   482 }
 
   486 
   483 
   487 
   484 
   488 def compile_decl(d: Decl) : Instrs = d match {
 
   485 def compile_decl(d: Decl) : Instrs = d match {
 
   489   case Def(name, args, a) => Nil
 
   486   case Def(name, args, a) => { 
   490   case Main(a) => compile_exp(a, Map())
 
   487     val env = args.zipWithIndex.toMap
 
       
   488     val is = "I" * args.length
 
       
   489     List(".method public static " + name + "(" + is + ")I \n",
 
       
   490          ".limit locals " + args.length.toString + "\n",
 
       
   491          ".limit stack " + (1 + max_stack_exp(a)).toString + "\n",
 
       
   492          name + "_Start:\n") ++   
       
   493     //compile_exp(a, env) ++
 
       
   494     compile_expT(a, env, name) ++
 
       
   495     List("ireturn\n",
 
       
   496          ".end method \n\n")
 
       
   497   }
 
       
   498   case Main(a) => {
 
       
   499     val main_begin = 
       
   500       List(".method public static main([Ljava/lang/String;)V\n",
 
       
   501            ".limit locals 200\n",
 
       
   502            ".limit stack 200\n")
 
       
   503     val main_end = 
       
   504       List("invokestatic XXX/XXX/write(I)V\n",
 
       
   505            "return\n",
 
       
   506            ".end method\n")
 
       
   507     main_begin ++ compile_exp(a, Map()) ++ main_end
 
       
   508   }
 
   491 }
 
   509 }
 
   492 
   510 
   493 def compile(class_name: String, input: String) : String = {
 
   511 def compile(class_name: String, input: String) : String = {
 
   494   val tks = tokenizer(input)
 
   512   val tks = tokenizer(input)
 
       
   513   //println(Prog.parse(tks))
 
   495   val ast = Prog.parse_single(tks)
 
   514   val ast = Prog.parse_single(tks)
 
   496   val instructions = ast.flatMap(compile_decl).mkString
 
   515   val instructions = ast.flatMap(compile_decl).mkString
 
   497   (instructions).replaceAllLiterally("XXX", class_name)
 
   516   (library + instructions).replaceAllLiterally("XXX", class_name)
 
   498 }
 
   517 }
 
   499 
   518 
   500 
   519 
   501 def compile_file(file_name: String) = {
 
   520 def compile_file(file_name: String) = {
 
   502   val class_name = file_name.split('.')(0)
 
   521   val class_name = file_name.split('.')(0)
 
   511   for (j <- 1 to i) code
 
   530   for (j <- 1 to i) code
 
   512   val end = System.nanoTime()
 
   531   val end = System.nanoTime()
 
   513   (end - start)/(i * 1.0e9)
 
   532   (end - start)/(i * 1.0e9)
 
   514 }
 
   533 }
 
   515 
   534 
   516 
       
   517 def compile_run(file_name: String) : Unit = {
 
   535 def compile_run(file_name: String) : Unit = {
 
   518   val class_name = file_name.split('.')(0)
 
   536   val class_name = file_name.split('.')(0)
 
   519   compile_file(file_name)
 
   537   compile_file(file_name)
 
   520   println(fromFile("defs.j"))
 
   538   val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!!
 
   521   //val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!!
 
   539   println("Time: " + time_needed(2, ("java " + class_name + "/" + class_name).!))
 
   522   //("java " + class_name + "/" + class_name).!
 
       
   523 }
 
   540 }
 
   524 
   541 
   525 
   542 
   526 //examples
 
   543 //examples
 
   527 //println(compile("test", p9))
 
       
   528 //compile_run("loops.while")
 
       
   529 compile_run("defs.rec")
 
   544 compile_run("defs.rec")
 
   530 //compile_run("test.while")
 
   545 //compile_run("fact.rec")
afl-material