1 // A Small Compiler for the WHILE Language  | 
         | 
     2 //  - includes arrays and a small parser for  | 
         | 
     3 //    translated BF programs  | 
         | 
     4   | 
         | 
     5 // the abstract syntax trees  | 
         | 
     6 abstract class Stmt  | 
         | 
     7 abstract class AExp  | 
         | 
     8 abstract class BExp   | 
         | 
     9 type Block = List[Stmt]  | 
         | 
    10   | 
         | 
    11 // statements  | 
         | 
    12 case object Skip extends Stmt  | 
         | 
    13 case class Array(s: String, n: Int) extends Stmt  | 
         | 
    14 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt  | 
         | 
    15 case class While(b: BExp, bl: Block) extends Stmt  | 
         | 
    16 case class Assign(s: String, a: AExp) extends Stmt  | 
         | 
    17 case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt  | 
         | 
    18 case class Write(s: String) extends Stmt  | 
         | 
    19 case class Read(s: String) extends Stmt  | 
         | 
    20   | 
         | 
    21 // arithmetic expressions  | 
         | 
    22 case class Var(s: String) extends AExp  | 
         | 
    23 case class Num(i: Int) extends AExp  | 
         | 
    24 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp  | 
         | 
    25 case class Ref(s: String, a: AExp) extends AExp  | 
         | 
    26   | 
         | 
    27 // boolean expressions  | 
         | 
    28 case object True extends BExp  | 
         | 
    29 case object False extends BExp  | 
         | 
    30 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp  | 
         | 
    31   | 
         | 
    32   | 
         | 
    33 // compiler headers needed for the JVM  | 
         | 
    34 // (contains an init method, as well as methods for read and write)  | 
         | 
    35 val beginning = """  | 
         | 
    36 .class public XXX.XXX  | 
         | 
    37 .super java/lang/Object  | 
         | 
    38   | 
         | 
    39 .method public <init>()V  | 
         | 
    40    aload_0  | 
         | 
    41    invokenonvirtual java/lang/Object/<init>()V  | 
         | 
    42    return  | 
         | 
    43 .end method  | 
         | 
    44   | 
         | 
    45 .method public static write(I)V   | 
         | 
    46     .limit locals 1   | 
         | 
    47     .limit stack 2   | 
         | 
    48     getstatic java/lang/System/out Ljava/io/PrintStream;   | 
         | 
    49     iload 0  | 
         | 
    50     i2c       ; Int => Char  | 
         | 
    51     invokevirtual java/io/PrintStream/print(C)V   ; println(I)V => print(C)V      | 
         | 
    52     return   | 
         | 
    53 .end method  | 
         | 
    54   | 
         | 
    55 .method public static read()I   | 
         | 
    56     .limit locals 10   | 
         | 
    57     .limit stack 10  | 
         | 
    58   | 
         | 
    59     ldc 0   | 
         | 
    60     istore 1  ; this will hold our final integer   | 
         | 
    61 Label1:   | 
         | 
    62     getstatic java/lang/System/in Ljava/io/InputStream;   | 
         | 
    63     invokevirtual java/io/InputStream/read()I   | 
         | 
    64     istore 2   | 
         | 
    65     iload 2   | 
         | 
    66     ldc 10   ; the newline delimiter   | 
         | 
    67     isub   | 
         | 
    68     ifeq Label2   | 
         | 
    69     iload 2   | 
         | 
    70     ldc 32   ; the space delimiter   | 
         | 
    71     isub   | 
         | 
    72     ifeq Label2  | 
         | 
    73   | 
         | 
    74     iload 2   | 
         | 
    75     ldc 48   ; we have our digit in ASCII, have to subtract it from 48   | 
         | 
    76     isub   | 
         | 
    77     ldc 10   | 
         | 
    78     iload 1   | 
         | 
    79     imul   | 
         | 
    80     iadd   | 
         | 
    81     istore 1   | 
         | 
    82     goto Label1   | 
         | 
    83 Label2:   | 
         | 
    84     ;when we come here we have our integer computed in local variable 1   | 
         | 
    85     iload 1   | 
         | 
    86     ireturn   | 
         | 
    87 .end method  | 
         | 
    88   | 
         | 
    89 .method public static main([Ljava/lang/String;)V  | 
         | 
    90    .limit locals 200  | 
         | 
    91    .limit stack 200  | 
         | 
    92   | 
         | 
    93 """  | 
         | 
    94   | 
         | 
    95 val ending = """  | 
         | 
    96   | 
         | 
    97    return  | 
         | 
    98   | 
         | 
    99 .end method  | 
         | 
   100 """  | 
         | 
   101   | 
         | 
   102   | 
         | 
   103   | 
         | 
   104   | 
         | 
   105 // for generating new labels  | 
         | 
   106 var counter = -1  | 
         | 
   107   | 
         | 
   108 def Fresh(x: String) = { | 
         | 
   109   counter += 1  | 
         | 
   110   x ++ "_" ++ counter.toString()  | 
         | 
   111 }  | 
         | 
   112   | 
         | 
   113 // environments and instructions  | 
         | 
   114 type Env = Map[String, Int]  | 
         | 
   115   | 
         | 
   116 // convenient string interpolations   | 
         | 
   117 // for instructions and labels  | 
         | 
   118 import scala.language.implicitConversions  | 
         | 
   119 import scala.language.reflectiveCalls  | 
         | 
   120   | 
         | 
   121 implicit def sring_inters(sc: StringContext) = new { | 
         | 
   122     def i(args: Any*): String = "   " ++ sc.s(args:_*) ++ "\n"  | 
         | 
   123     def l(args: Any*): String = sc.s(args:_*) ++ ":\n"  | 
         | 
   124 }  | 
         | 
   125   | 
         | 
   126 def compile_op(op: String) = op match { | 
         | 
   127   case "+" => i"iadd"  | 
         | 
   128   case "-" => i"isub"  | 
         | 
   129   case "*" => i"imul"  | 
         | 
   130 }  | 
         | 
   131   | 
         | 
   132 // arithmetic expression compilation  | 
         | 
   133 def compile_aexp(a: AExp, env : Env) : String = a match { | 
         | 
   134   case Num(i) => i"ldc $i"  | 
         | 
   135   case Var(s) => i"iload ${env(s)} \t\t; $s" | 
         | 
   136   case Aop(op, a1, a2) =>   | 
         | 
   137     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op)  | 
         | 
   138   case Ref(s, a) =>  | 
         | 
   139     i"aload ${env(s)}" ++ compile_aexp(a, env) ++  i"iaload" | 
         | 
   140 }  | 
         | 
   141   | 
         | 
   142 // boolean expression compilation  | 
         | 
   143 def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { | 
         | 
   144     case True => ""  | 
         | 
   145   case False => i"goto $jmp"  | 
         | 
   146   case Bop("==", a1, a2) =>  | 
         | 
   147     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp"  | 
         | 
   148   case Bop("!=", a1, a2) =>  | 
         | 
   149     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp"  | 
         | 
   150   case Bop("<", a1, a2) =>  | 
         | 
   151     compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp"  | 
         | 
   152 }  | 
         | 
   153   | 
         | 
   154 // statement compilation  | 
         | 
   155 def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { | 
         | 
   156   case Skip => ("", env) | 
         | 
   157   case Assign(x, a) => { | 
         | 
   158      val index = env.getOrElse(x, env.keys.size)  | 
         | 
   159     (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index))   | 
         | 
   160   }   | 
         | 
   161   case If(b, bl1, bl2) => { | 
         | 
   162     val if_else = Fresh("If_else") | 
         | 
   163     val if_end = Fresh("If_end") | 
         | 
   164     val (instrs1, env1) = compile_block(bl1, env)  | 
         | 
   165     val (instrs2, env2) = compile_block(bl2, env1)  | 
         | 
   166     (compile_bexp(b, env, if_else) ++  | 
         | 
   167      instrs1 ++  | 
         | 
   168      i"goto $if_end" ++  | 
         | 
   169      l"$if_else" ++  | 
         | 
   170      instrs2 ++  | 
         | 
   171      l"$if_end", env2)  | 
         | 
   172   }  | 
         | 
   173   case While(b, bl) => { | 
         | 
   174     val loop_begin = Fresh("Loop_begin") | 
         | 
   175     val loop_end = Fresh("Loop_end") | 
         | 
   176     val (instrs1, env1) = compile_block(bl, env)  | 
         | 
   177     (l"$loop_begin" ++  | 
         | 
   178      compile_bexp(b, env, loop_end) ++  | 
         | 
   179      instrs1 ++  | 
         | 
   180      i"goto $loop_begin" ++  | 
         | 
   181      l"$loop_end", env1)  | 
         | 
   182   }  | 
         | 
   183   case Write(x) =>   | 
         | 
   184     (i"iload ${env(x)} \t\t; $x" ++  | 
         | 
   185      i"invokestatic XXX/XXX/write(I)V", env)  | 
         | 
   186   case Read(x) => { | 
         | 
   187     val index = env.getOrElse(x, env.keys.size)   | 
         | 
   188     (i"invokestatic XXX/XXX/read()I" ++   | 
         | 
   189      i"istore $index \t\t; $x", env + (x -> index))  | 
         | 
   190   }  | 
         | 
   191   case Array(s: String, n: Int) => { | 
         | 
   192     val index = if (env.isDefinedAt(s)) throw new Exception("array def error") else  | 
         | 
   193                     env.keys.size  | 
         | 
   194     (i"ldc $n" ++  | 
         | 
   195      i"newarray int" ++  | 
         | 
   196      i"astore $index", env + (s -> index))  | 
         | 
   197   }  | 
         | 
   198   case AssignA(s, a1, a2) => { | 
         | 
   199     val index = if (env.isDefinedAt(s)) env(s) else   | 
         | 
   200                     throw new Exception("array not defined") | 
         | 
   201     (i"aload ${env(s)}" ++ | 
         | 
   202      compile_aexp(a1, env) ++  | 
         | 
   203      compile_aexp(a2, env) ++  | 
         | 
   204      i"iastore", env)  | 
         | 
   205   }   | 
         | 
   206 }  | 
         | 
   207   | 
         | 
   208 // compilation of a block (i.e. list of instructions)  | 
         | 
   209 def compile_block(bl: Block, env: Env) : (String, Env) = bl match { | 
         | 
   210   case Nil => ("", env) | 
         | 
   211   case s::bl => { | 
         | 
   212     val (instrs1, env1) = compile_stmt(s, env)  | 
         | 
   213     val (instrs2, env2) = compile_block(bl, env1)  | 
         | 
   214     (instrs1 ++ instrs2, env2)  | 
         | 
   215   }  | 
         | 
   216 }  | 
         | 
   217   | 
         | 
   218   | 
         | 
   219 // main compilation function for blocks  | 
         | 
   220 def compile(bl: Block, class_name: String) : String = { | 
         | 
   221   val instructions = compile_block(bl, Map.empty)._1  | 
         | 
   222   (beginning ++ instructions.mkString ++ ending).replaceAllLiterally("XXX", class_name) | 
         | 
   223 }  | 
         | 
   224   | 
         | 
   225   | 
         | 
   226 // Fibonacci numbers as a test-case  | 
         | 
   227 val fib_test =   | 
         | 
   228   List(Read("n"),                       //  read n;                      | 
         | 
   229        Assign("minus1",Num(0)),         //  minus1 := 0; | 
         | 
   230        Assign("minus2",Num(1)),         //  minus2 := 1; | 
         | 
   231        Assign("temp",Num(0)),           //  temp := 0; | 
         | 
   232        While(Bop("<",Num(0),Var("n")),  //  while n > 0 do  { | 
         | 
   233           List(Assign("temp",Var("minus2")),    //  temp := minus2; | 
         | 
   234                Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))),  | 
         | 
   235                                         //  minus2 := minus1 + minus2;  | 
         | 
   236                Assign("minus1",Var("temp")), //  minus1 := temp; | 
         | 
   237                Assign("n",Aop("-",Var("n"),Num(1))))), //  n := n - 1 }; | 
         | 
   238        Write("minus1"))                 //  write minus1 | 
         | 
   239   | 
         | 
   240 // prints out the JVM-assembly program  | 
         | 
   241   | 
         | 
   242 // println(compile(fib_test, "fib"))  | 
         | 
   243   | 
         | 
   244 // can be assembled with   | 
         | 
   245 //  | 
         | 
   246 //    java -jar jvm/jasmin-2.4/jasmin.jar fib.j  | 
         | 
   247 //  | 
         | 
   248 // and started with  | 
         | 
   249 //  | 
         | 
   250 //    java fib/fib  | 
         | 
   251   | 
         | 
   252 import scala.util._  | 
         | 
   253 import scala.sys.process._  | 
         | 
   254 import scala.io  | 
         | 
   255   | 
         | 
   256 def compile_tofile(bl: Block, class_name: String) = { | 
         | 
   257   val output = compile(bl, class_name)  | 
         | 
   258   val fw = new java.io.FileWriter(class_name + ".j")   | 
         | 
   259   fw.write(output)   | 
         | 
   260   fw.close()  | 
         | 
   261 }  | 
         | 
   262   | 
         | 
   263 def compile_all(bl: Block, class_name: String) : Unit = { | 
         | 
   264   compile_tofile(bl, class_name)  | 
         | 
   265   println("compiled ") | 
         | 
   266   val test = ("java -jar jvm/jasmin-2.4/jasmin.jar " + class_name + ".j").!! | 
         | 
   267   println("assembled ") | 
         | 
   268 }  | 
         | 
   269   | 
         | 
   270 def time_needed[T](i: Int, code: => T) = { | 
         | 
   271   val start = System.nanoTime()  | 
         | 
   272   for (j <- 1 to i) code  | 
         | 
   273   val end = System.nanoTime()  | 
         | 
   274   (end - start)/(i * 1.0e9)  | 
         | 
   275 }  | 
         | 
   276   | 
         | 
   277   | 
         | 
   278 def compile_run(bl: Block, class_name: String) : Unit = { | 
         | 
   279   println("Start compilation") | 
         | 
   280   compile_all(bl, class_name)  | 
         | 
   281   println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!)) | 
         | 
   282 }  | 
         | 
   283   | 
         | 
   284   | 
         | 
   285   | 
         | 
   286 val arr_test =   | 
         | 
   287   List(Array("a", 10), | 
         | 
   288        Array("b", 2), | 
         | 
   289        AssignA("a", Num(0), Num(10)), | 
         | 
   290        Assign("x", Ref("a", Num(0))), | 
         | 
   291        Write("x"), | 
         | 
   292        AssignA("b", Num(1), Num(5)), | 
         | 
   293        Assign("x", Ref("b", Num(1))), | 
         | 
   294        Write("x"))        | 
         | 
   295   | 
         | 
   296   | 
         | 
   297 //compile_run(arr_test, "a")  | 
         | 
   298   | 
         | 
   299 //====================  | 
         | 
   300 // Parser Combinators  | 
         | 
   301 //====================  | 
         | 
   302   | 
         | 
   303 import scala.language.implicitConversions  | 
         | 
   304 import scala.language.reflectiveCalls  | 
         | 
   305   | 
         | 
   306 type IsSeq[A] = A => Seq[_]  | 
         | 
   307   | 
         | 
   308 abstract class Parser[I : IsSeq, T] { | 
         | 
   309   def parse(ts: I): Set[(T, I)]  | 
         | 
   310   | 
         | 
   311   def parse_all(ts: I) : Set[T] =  | 
         | 
   312     for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head  | 
         | 
   313 }  | 
         | 
   314   | 
         | 
   315 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { | 
         | 
   316   def parse(sb: I) =   | 
         | 
   317     for ((head1, tail1) <- p.parse(sb);   | 
         | 
   318          (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)  | 
         | 
   319 }  | 
         | 
   320   | 
         | 
   321 class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { | 
         | 
   322   def parse(sb: I) = p.parse(sb) ++ q.parse(sb)     | 
         | 
   323 }  | 
         | 
   324   | 
         | 
   325 class FunParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { | 
         | 
   326   def parse(sb: I) =   | 
         | 
   327     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)  | 
         | 
   328 }  | 
         | 
   329   | 
         | 
   330   | 
         | 
   331 import scala.util.matching.Regex  | 
         | 
   332 case class RegexParser(reg: Regex) extends Parser[String, String] { | 
         | 
   333   def parse(sb: String) = reg.findPrefixMatchOf(sb) match { | 
         | 
   334     case None => Set()  | 
         | 
   335     case Some(m) => Set((m.matched, m.after.toString))    | 
         | 
   336   }  | 
         | 
   337 }  | 
         | 
   338   | 
         | 
   339 def StringParser(s: String) = RegexParser(Regex.quote(s).r)  | 
         | 
   340   | 
         | 
   341   | 
         | 
   342 implicit def string2parser(s : String) = StringParser(s)  | 
         | 
   343   | 
         | 
   344 implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { | 
         | 
   345   def | (q : => Parser[I, T]) = new AltParser[I, T](p, q)  | 
         | 
   346   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)  | 
         | 
   347   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)  | 
         | 
   348 }  | 
         | 
   349   | 
         | 
   350 implicit def StringOps(s: String) = new { | 
         | 
   351   def | (q : => Parser[String, String]) = new AltParser[String, String](s, q)  | 
         | 
   352   def | (r: String) = new AltParser[String, String](s, r)  | 
         | 
   353   def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)  | 
         | 
   354   def ~[S](q : => Parser[String, S]) =   | 
         | 
   355     new SeqParser[String, String, S](s, q)  | 
         | 
   356   def ~ (r: String) =   | 
         | 
   357     new SeqParser[String, String, String](s, r)  | 
         | 
   358 }  | 
         | 
   359   | 
         | 
   360   | 
         | 
   361 val NumParser = RegexParser("[0-9]+".r) ==> (s => s.toInt : Int) | 
         | 
   362 val IdParser = RegexParser("[a-z][a-z,0-9]*".r) | 
         | 
   363   | 
         | 
   364   | 
         | 
   365   | 
         | 
   366 // Grammar Rules  | 
         | 
   367   | 
         | 
   368 lazy val AExp: Parser[String, AExp] =   | 
         | 
   369   (Te ~ "+" ~ AExp) ==> { case ((x, _), z) => Aop("+", x, z):AExp } | | 
         | 
   370   (Te ~ "-" ~ AExp) ==> { case ((x, _), z) => Aop("-", x, z):AExp } | Te | 
         | 
   371 lazy val Te: Parser[String, AExp] =   | 
         | 
   372   (Fa ~ "*" ~ Te) ==> { case ((x, _), z) => Aop("*", x, z):AExp } | Fa | 
         | 
   373 lazy val Fa: Parser[String, AExp] =   | 
         | 
   374    ("(" ~ AExp ~ ")") ==> { case ((_, y), _) => y } |  | 
         | 
   375    (IdParser ~ "[" ~ AExp ~ "]") ==> { case (((x, _), y), _) => Ref(x, y) } | | 
         | 
   376    IdParser ==> Var |   | 
         | 
   377    NumParser ==> Num  | 
         | 
   378   | 
         | 
   379 // boolean expressions  | 
         | 
   380 lazy val BExp: Parser[String, BExp] =   | 
         | 
   381    (AExp ~ "=" ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z):BExp } |  | 
         | 
   382    (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z):BExp } |  | 
         | 
   383    (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z):BExp } |  | 
         | 
   384    (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x):BExp } |  | 
         | 
   385    ("true" ==> ((_) => True:BExp )) |  | 
         | 
   386    ("false" ==> ((_) => False:BExp )) | | 
         | 
   387    ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y} | 
         | 
   388   | 
         | 
   389 lazy val Stmt: Parser[String, Stmt] =  | 
         | 
   390    ("skip" ==> (_ => Skip: Stmt)) | | 
         | 
   391    (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } | | 
         | 
   392    (IdParser ~ "[" ~ AExp ~ "]" ~ ":=" ~ AExp) ==> {  | 
         | 
   393      case (((((x, y), z), v), w), u) => AssignA(x, z, u): Stmt } |  | 
         | 
   394    ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==> | 
         | 
   395     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } | | 
         | 
   396    ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) } | | 
         | 
   397    ("new" ~ IdParser ~ "[" ~ NumParser ~ "]") ==> { case ((((x, y), z), u), v) => Array(y, u) } | | 
         | 
   398    ("write" ~ IdParser) ==> { case (_, y) => Write(y) }  | 
         | 
   399    | 
         | 
   400 lazy val Stmts: Parser[String, Block] =  | 
         | 
   401   (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } | | 
         | 
   402   (Stmt ==> ((s) => List(s) : Block))   | 
         | 
   403   | 
         | 
   404   | 
         | 
   405 lazy val Block: Parser[String, Block] =  | 
         | 
   406    ("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} |  | 
         | 
   407    (Stmt ==> (s => List(s)))  | 
         | 
   408   | 
         | 
   409 //Stmts.parse_all("x2:=5+a") | 
         | 
   410 //Stmts.parse_all("x2:=5+a[3+a]") | 
         | 
   411 //Stmts.parse_all("a[x2+3]:=5+a[3+a]") | 
         | 
   412 //Block.parse_all("{x:=5;y:=8}") | 
         | 
   413 //Block.parse_all("if(false)then{x:=5}else{x:=10}") | 
         | 
   414   | 
         | 
   415   | 
         | 
   416   | 
         | 
   417 val fib = """  | 
         | 
   418    n := 10;  | 
         | 
   419    minus1 := 0;  | 
         | 
   420    minus2 := 1;  | 
         | 
   421    temp:=0;  | 
         | 
   422    while (n > 0) do { | 
         | 
   423      temp := minus2;   | 
         | 
   424      minus2 := minus1 + minus2;  | 
         | 
   425      minus1 := temp;  | 
         | 
   426      n := n - 1};  | 
         | 
   427    result := minus2;  | 
         | 
   428    write result  | 
         | 
   429    """.replaceAll("\\s+", "") | 
         | 
   430   | 
         | 
   431 val fib_prog = Stmts.parse_all(fib).toList  | 
         | 
   432 //compile_run(fib_prog.head, "fib")  | 
         | 
   433   | 
         | 
   434   | 
         | 
   435 // BF   | 
         | 
   436   | 
         | 
   437 // simple instructions  | 
         | 
   438 def instr(c: Char) : String = c match { | 
         | 
   439   case '>' => "ptr := ptr + 1;"  | 
         | 
   440   case '<' => "ptr := ptr - 1;"  | 
         | 
   441   case '+' => "field[ptr] := field[ptr] + 1;"  | 
         | 
   442   case '-' => "field[ptr] := field[ptr] - 1;"  | 
         | 
   443   case '.' => "x := field[ptr]; write x;"  | 
         | 
   444   //case ',' => "XXX" // "ptr = getchar();\n"  | 
         | 
   445   case '['  => "while (field[ptr] != 0) do {" | 
         | 
   446   case ']'  => "skip};"  | 
         | 
   447   case _ => ""  | 
         | 
   448 }  | 
         | 
   449   | 
         | 
   450 def instrs(prog: String) : String =  | 
         | 
   451   prog.toList.map(instr).mkString  | 
         | 
   452   | 
         | 
   453   | 
         | 
   454 def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { | 
         | 
   455   case (Nil, acc) => acc  | 
         | 
   456   case (c :: cs, Nil) => splice(cs, List((c, 1)))  | 
         | 
   457   case (c :: cs, (d, n) :: acc) =>   | 
         | 
   458     if (c == d) splice(cs, (c, n + 1) :: acc)  | 
         | 
   459     else splice(cs, (c, 1) :: (d, n) :: acc)  | 
         | 
   460 }  | 
         | 
   461   | 
         | 
   462 def spl(s: String) = splice(s.toList, Nil).reverse  | 
         | 
   463   | 
         | 
   464 def instr2(c: Char, n: Int) : String = c match { | 
         | 
   465   case '>' => "ptr := ptr + " + n.toString + ";"  | 
         | 
   466   case '<' => "ptr := ptr - " + n.toString + ";"  | 
         | 
   467   case '+' => "field[ptr] := field[ptr] + " + n.toString + ";"  | 
         | 
   468   case '-' => "field[ptr] := field[ptr] - " + n.toString + ";"  | 
         | 
   469   case '.' => "x := field[ptr]; write x;" //* n  | 
         | 
   470   //case ',' => "*ptr = getchar();\n" * n  | 
         | 
   471   case '['  => "while (field[ptr] != 0) do {" * n  | 
         | 
   472   case ']'  => "skip};" * n  | 
         | 
   473   case _ => ""  | 
         | 
   474 }  | 
         | 
   475   | 
         | 
   476 def instrs2(prog: String) : String =  | 
         | 
   477   spl(prog).map{ case (c, n) => instr2(c, n) }.mkString | 
         | 
   478   | 
         | 
   479   | 
         | 
   480 def bf_str(prog: String) : String = { | 
         | 
   481   "\n" ++  | 
         | 
   482   //"new field[30000];\n" ++  | 
         | 
   483   "ptr := 15000;" ++  | 
         | 
   484   instrs(prog) ++  | 
         | 
   485   "skip"  | 
         | 
   486 }  | 
         | 
   487   | 
         | 
   488 def bf_run(prog: String, name: String) = { | 
         | 
   489   println("BF processing start") | 
         | 
   490   val bf_string = bf_str(prog).replaceAll("\\s", "") | 
         | 
   491     | 
         | 
   492   println(s"BF parsing start (string length ${bf_string.length})") | 
         | 
   493   val bf_prog = Stmts.parse_all(bf_string).toList.head  | 
         | 
   494   println(s"BF Compile start ${bf_string.toList.length} characters") | 
         | 
   495   compile_run(Array("field", 30000) :: bf_prog, name) | 
         | 
   496 }  | 
         | 
   497   | 
         | 
   498 // a benchmark program (counts down from 'Z' to 'A')  | 
         | 
   499 val bf0 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++  | 
         | 
   500             [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++  | 
         | 
   501             ++++++++[>++++++++++[>++++++++++[>++++++++++[>+  | 
         | 
   502             +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""  | 
         | 
   503   | 
         | 
   504 bf_run(bf0, "bench")  | 
         | 
   505   | 
         | 
   506   | 
         | 
   507   | 
         | 
   508 val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[  | 
         | 
   509       ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<  | 
         | 
   510       ]>.>+[>>]>+]"""  | 
         | 
   511   | 
         | 
   512 bf_run(bf1, "sier")  | 
         | 
   513   | 
         | 
   514 bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ | 
         | 
   515        ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello")  | 
         | 
   516   | 
         | 
   517   | 
         | 
   518 val bf2 = """+++++++++++  | 
         | 
   519       >+>>>>++++++++++++++++++++++++++++++++++++++++++++  | 
         | 
   520       >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>  | 
         | 
   521       +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-  | 
         | 
   522       <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<  | 
         | 
   523       -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]  | 
         | 
   524       >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++  | 
         | 
   525       +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++  | 
         | 
   526       ++++++++++++++++++++++++++++++++++++++++++++.[-]<<  | 
         | 
   527       <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<  | 
         | 
   528       [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]"""  | 
         | 
   529   | 
         | 
   530 bf_run(bf2, "fibs")  | 
         | 
   531   | 
         | 
   532   | 
         | 
   533 bf_run("""      A mandelbrot set fractal viewer in brainf*** written by Erik Bosman | 
         | 
   534 +++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[  | 
         | 
   535 >>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+  | 
         | 
   536 <<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>  | 
         | 
   537 >+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>  | 
         | 
   538 >>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>  | 
         | 
   539 >>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>  | 
         | 
   540 >>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>  | 
         | 
   541 [>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<  | 
         | 
   542 <<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[  | 
         | 
   543 >>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[  | 
         | 
   544 >+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[  | 
         | 
   545 -<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<  | 
         | 
   546 <<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<  | 
         | 
   547 [>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>  | 
         | 
   548 >>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+  | 
         | 
   549 <<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>  | 
         | 
   550 >>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<  | 
         | 
   551 +>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<  | 
         | 
   552 <]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>  | 
         | 
   553 >>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>  | 
         | 
   554 >>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<  | 
         | 
   555 <<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<  | 
         | 
   556 <<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->  | 
         | 
   557 >>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<  | 
         | 
   558 <<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++  | 
         | 
   559 +++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-  | 
         | 
   560 <<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>  | 
         | 
   561 [-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<  | 
         | 
   562 <+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-  | 
         | 
   563 ]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<  | 
         | 
   564 <<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<  | 
         | 
   565 <[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>  | 
         | 
   566 >>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>  | 
         | 
   567 [-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<  | 
         | 
   568 <<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>  | 
         | 
   569 ]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+  | 
         | 
   570 >>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>  | 
         | 
   571 [->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-  | 
         | 
   572 ]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>  | 
         | 
   573 [>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  | 
         | 
   574 ]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>  | 
         | 
   575 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++  | 
         | 
   576 +++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+  | 
         | 
   577 >>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[  | 
         | 
   578 -]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<  | 
         | 
   579 <<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<  | 
         | 
   580 [->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]  | 
         | 
   581 +>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<  | 
         | 
   582 <<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<  | 
         | 
   583 [<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<  | 
         | 
   584 <<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<  | 
         | 
   585 <<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<  | 
         | 
   586 <<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<  | 
         | 
   587 <<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<  | 
         | 
   588 <<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<  | 
         | 
   589 ]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<  | 
         | 
   590 [>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<  | 
         | 
   591 +>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<  | 
         | 
   592 <<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<  | 
         | 
   593 <<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[  | 
         | 
   594 [>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+  | 
         | 
   595 [>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>  | 
         | 
   596 [-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<  | 
         | 
   597 <[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[  | 
         | 
   598 >[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[  | 
         | 
   599 >>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>  | 
         | 
   600 >>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<  | 
         | 
   601 <<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<  | 
         | 
   602 <<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-  | 
         | 
   603 <<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>  | 
         | 
   604 >>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>  | 
         | 
   605 [-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<  | 
         | 
   606 +>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>  | 
         | 
   607 [-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>  | 
         | 
   608 >>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>  | 
         | 
   609 >>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<  | 
         | 
   610 ]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<  | 
         | 
   611 <+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>  | 
         | 
   612 >]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<  | 
         | 
   613 <<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<  | 
         | 
   614 <<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<  | 
         | 
   615 <<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<  | 
         | 
   616 <<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+  | 
         | 
   617 <]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-  | 
         | 
   618 <<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<  | 
         | 
   619 ]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>  | 
         | 
   620 >>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-  | 
         | 
   621 <<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[  | 
         | 
   622 ->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>  | 
         | 
   623 >>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>  | 
         | 
   624 >>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<  | 
         | 
   625 <<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<  | 
         | 
   626 <<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+  | 
         | 
   627 >>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>  | 
         | 
   628 ]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>  | 
         | 
   629 >>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>  | 
         | 
   630 >>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+  | 
         | 
   631 >>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>  | 
         | 
   632 [->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-  | 
         | 
   633 ]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>  | 
         | 
   634 [>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<  | 
         | 
   635 <<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>  | 
         | 
   636 >>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>  | 
         | 
   637 >>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+  | 
         | 
   638 <<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>  | 
         | 
   639 >>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>  | 
         | 
   640 >]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]  | 
         | 
   641 >>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<  | 
         | 
   642 ]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<  | 
         | 
   643 <<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>  | 
         | 
   644 >>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<  | 
         | 
   645 ->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[  | 
         | 
   646 >[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<  | 
         | 
   647 [<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<  | 
         | 
   648 <<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<  | 
         | 
   649 <<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<  | 
         | 
   650 <<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>  | 
         | 
   651 >+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<  | 
         | 
   652 <<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<  | 
         | 
   653 +<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>  | 
         | 
   654 >>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<  | 
         | 
   655 <<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<  | 
         | 
   656 <<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<  | 
         | 
   657 <<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<  | 
         | 
   658 <<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<  | 
         | 
   659 <<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<  | 
         | 
   660 <<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<  | 
         | 
   661 <<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>  | 
         | 
   662 >+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<  | 
         | 
   663 <<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>  | 
         | 
   664 >]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<  | 
         | 
   665 <<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>  | 
         | 
   666 >>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-  | 
         | 
   667 >>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<  | 
         | 
   668 <<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>  | 
         | 
   669 >>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<  | 
         | 
   670 <<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>  | 
         | 
   671 +>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<  | 
         | 
   672 <<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<  | 
         | 
   673 <<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>  | 
         | 
   674 -<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>  | 
         | 
   675 >>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++  | 
         | 
   676 +[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<  | 
         | 
   677 <<<<<]]>>>]""", "mand")  | 
         | 
   678   | 
         |