# HG changeset patch # User Christian Urban # Date 1574075471 0 # Node ID b6ed836ce59bb381cc1e423ef9d46714800848a4 # Parent 605d971e98fd175436f1bbacba7c09bf66b3ff91 updated diff -r 605d971e98fd -r b6ed836ce59b progs/compile_arr.scala --- a/progs/compile_arr.scala Sun Nov 17 23:53:54 2019 +0000 +++ b/progs/compile_arr.scala Mon Nov 18 11:11:11 2019 +0000 @@ -1,5 +1,6 @@ // A Small Compiler for the WHILE Language -// (stub for including arrays) +// - includes arrays and a small parser for +// translated BF programs // the abstract syntax trees abstract class Stmt @@ -9,18 +10,19 @@ // statements case object Skip extends Stmt +case class Array(s: String, n: Int) extends Stmt case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt case class While(b: BExp, bl: Block) extends Stmt case class Assign(s: String, a: AExp) extends Stmt case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt -case class Write(s: String) extends Stmt // writes out a variable -case class Array(s: String, n: Int) extends Stmt +case class Write(s: String) extends Stmt +case class Read(s: String) extends Stmt // arithmetic expressions case class Var(s: String) extends AExp case class Num(i: Int) extends AExp case class Aop(o: String, a1: AExp, a2: AExp) extends AExp -case class Ref(s: String, a1: AExp) extends AExp +case class Ref(s: String, a: AExp) extends AExp // boolean expressions case object True extends BExp @@ -45,11 +47,45 @@ .limit stack 2 getstatic java/lang/System/out Ljava/io/PrintStream; iload 0 - i2c - invokevirtual java/io/PrintStream/print(C)V + i2c ; Int => Char + invokevirtual java/io/PrintStream/print(C)V ; println(I)V => print(C)V return .end method +.method public static read()I + .limit locals 10 + .limit stack 10 + + ldc 0 + istore 1 ; this will hold our final integer +Label1: + getstatic java/lang/System/in Ljava/io/InputStream; + invokevirtual java/io/InputStream/read()I + istore 2 + iload 2 + ldc 10 ; the newline delimiter + isub + ifeq Label2 + iload 2 + ldc 32 ; the space delimiter + isub + ifeq Label2 + + iload 2 + ldc 48 ; we have our digit in ASCII, have to subtract it from 48 + isub + ldc 10 + iload 1 + imul + iadd + istore 1 + goto Label1 +Label2: + ;when we come here we have our integer computed in local variable 1 + iload 1 + ireturn +.end method + .method public static main([Ljava/lang/String;)V .limit locals 200 .limit stack 200 @@ -63,7 +99,7 @@ .end method """ -println("Start compilation") + // for generating new labels @@ -75,47 +111,52 @@ } // environments and instructions -type Env = Map[String, String] -type Instrs = List[String] +type Env = Map[String, Int] + +// convenient string interpolations +// for instructions and labels +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +implicit def sring_inters(sc: StringContext) = new { + def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" + def l(args: Any*): String = sc.s(args:_*) ++ ":\n" +} + +def compile_op(op: String) = op match { + case "+" => i"iadd" + case "-" => i"isub" + case "*" => i"imul" +} // arithmetic expression compilation -def compile_aexp(a: AExp, env : Env) : Instrs = a match { - case Num(i) => List("ldc " + i.toString + "\n") - case Var(s) => List("iload " + env(s) + "\n") - case Aop("+", a1, a2) => - compile_aexp(a1, env) ++ - compile_aexp(a2, env) ++ List("iadd\n") - case Aop("-", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n") - case Aop("*", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n") - case Ref(s, a1) => - List("aload " + env(s) + "\n") ++ compile_aexp(a1, env) ++ List("iaload \n") +def compile_aexp(a: AExp, env : Env) : String = a match { + case Num(i) => i"ldc $i" + case Var(s) => i"iload ${env(s)} \t\t; $s" + case Aop(op, a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op) + case Ref(s, a) => + i"aload ${env(s)}" ++ compile_aexp(a, env) ++ i"iaload" } // boolean expression compilation -def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match { - case True => Nil - case False => List("goto " + jmp + "\n") - case Bop("=", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ - List("if_icmpne " + jmp + "\n") +def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { + case True => "" + case False => i"goto $jmp" + case Bop("==", a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp" case Bop("!=", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ - List("if_icmpeq " + jmp + "\n") + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp" case Bop("<", a1, a2) => - compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ - List("if_icmpge " + jmp + "\n") + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp" } // statement compilation -def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match { - case Skip => (Nil, env) +def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { + case Skip => ("", env) case Assign(x, a) => { - val index = if (env.isDefinedAt(x)) env(x) else - env.keys.size.toString - (compile_aexp(a, env) ++ - List("istore " + index + "\n"), env + (x -> index)) + val index = env.getOrElse(x, env.keys.size) + (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index)) } case If(b, bl1, bl2) => { val if_else = Fresh("If_else") @@ -124,44 +165,49 @@ val (instrs2, env2) = compile_block(bl2, env1) (compile_bexp(b, env, if_else) ++ instrs1 ++ - List("goto " + if_end + "\n") ++ - List("\n" + if_else + ":\n\n") ++ + i"goto $if_end" ++ + l"$if_else" ++ instrs2 ++ - List("\n" + if_end + ":\n\n"), env2) + l"$if_end", env2) } case While(b, bl) => { val loop_begin = Fresh("Loop_begin") val loop_end = Fresh("Loop_end") val (instrs1, env1) = compile_block(bl, env) - (List("\n" + loop_begin + ":\n\n") ++ + (l"$loop_begin" ++ compile_bexp(b, env, loop_end) ++ instrs1 ++ - List("goto " + loop_begin + "\n") ++ - List("\n" + loop_end + ":\n\n"), env1) + i"goto $loop_begin" ++ + l"$loop_end", env1) } case Write(x) => - (List("iload " + env(x) + "\n" + - "invokestatic XXX/XXX/write(I)V\n"), env) - case Array(s, n) => { - val index = if (env.isDefinedAt(s)) throw new Exception("Array already defined") else - env.keys.size.toString - (List("ldc " ++ n.toString ++ "\n", - "newarray int \n", - "astore " ++ index ++ "\n"), env + (s -> index)) - } + (i"iload ${env(x)} \t\t; $x" ++ + i"invokestatic XXX/XXX/write(I)V", env) + case Read(x) => { + val index = env.getOrElse(x, env.keys.size) + (i"invokestatic XXX/XXX/read()I" ++ + i"istore $index \t\t; $x", env + (x -> index)) + } + case Array(s: String, n: Int) => { + val index = if (env.isDefinedAt(s)) throw new Exception("array def error") else + env.keys.size + (i"ldc $n" ++ + i"newarray int" ++ + i"astore $index", env + (s -> index)) + } case AssignA(s, a1, a2) => { val index = if (env.isDefinedAt(s)) env(s) else - throw new Exception("Array not yet defined") - (List("aload " + index + "\n") ++ + throw new Exception("array not defined") + (i"aload ${env(s)}" ++ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ - List("iastore \n"), env) + i"iastore", env) } } // compilation of a block (i.e. list of instructions) -def compile_block(bl: Block, env: Env) : (Instrs, Env) = bl match { - case Nil => (Nil, env) +def compile_block(bl: Block, env: Env) : (String, Env) = bl match { + case Nil => ("", env) case s::bl => { val (instrs1, env1) = compile_stmt(s, env) val (instrs2, env2) = compile_block(bl, env1) @@ -169,6 +215,7 @@ } } + // main compilation function for blocks def compile(bl: Block, class_name: String) : String = { val instructions = compile_block(bl, Map.empty)._1 @@ -176,9 +223,25 @@ } -// compiling and running files -// -// JVM files can be assembled with +// Fibonacci numbers as a test-case +val fib_test = + List(Read("n"), // read n; + Assign("minus1",Num(0)), // minus1 := 0; + Assign("minus2",Num(1)), // minus2 := 1; + Assign("temp",Num(0)), // temp := 0; + While(Bop("<",Num(0),Var("n")), // while n > 0 do { + List(Assign("temp",Var("minus2")), // temp := minus2; + Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))), + // minus2 := minus1 + minus2; + Assign("minus1",Var("temp")), // minus1 := temp; + Assign("n",Aop("-",Var("n"),Num(1))))), // n := n - 1 }; + Write("minus1")) // write minus1 + +// prints out the JVM-assembly program + +// println(compile(fib_test, "fib")) + +// can be assembled with // // java -jar jvm/jasmin-2.4/jasmin.jar fib.j // @@ -186,8 +249,6 @@ // // java fib/fib - - import scala.util._ import scala.sys.process._ import scala.io @@ -221,36 +282,19 @@ } -// Fibonacci numbers as a test-case -val fib_test = - List(Assign("n", Num(10)), // n := 10; - Assign("minus1",Num(0)), // minus1 := 0; - Assign("minus2",Num(1)), // minus2 := 1; - Assign("temp",Num(0)), // temp := 0; - While(Bop("<",Num(0),Var("n")), // while n > 0 do { - List(Assign("temp",Var("minus2")), // temp := minus2; - Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))), - // minus2 := minus1 + minus2; - Assign("minus1",Var("temp")), // minus1 := temp; - Assign("n",Aop("-",Var("n"),Num(1))))), // n := n - 1 }; - Write("minus1")) // write minus1 + +val arr_test = + List(Array("a", 10), + Array("b", 2), + AssignA("a", Num(0), Num(10)), + Assign("x", Ref("a", Num(0))), + Write("x"), + AssignA("b", Num(1), Num(5)), + Assign("x", Ref("b", Num(1))), + Write("x")) -compile_run(fib_test, "fib") - - -val arr_test = - List(Array("a", 10), // a[10] - Array("b", 2), // b[2] - AssignA("a", Num(0), Num(10)), // a[0] := 10 - Assign("x", Ref("a", Num(0))), // x := a[0] - Write("x"), // write x - AssignA("b", Num(1), Num(5)), // b[1] := 5 - Assign("x", Ref("b", Num(1))), // x := b[1] - Write("x")) // write x - -compile_run(arr_test, "a") - +//compile_run(arr_test, "a") //==================== // Parser Combinators @@ -259,25 +303,26 @@ import scala.language.implicitConversions import scala.language.reflectiveCalls +type IsSeq[A] = A => Seq[_] -abstract class Parser[I <% Seq[_], T] { +abstract class Parser[I : IsSeq, T] { def parse(ts: I): Set[(T, I)] def parse_all(ts: I) : Set[T] = for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head } -class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { +class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { def parse(sb: I) = for ((head1, tail1) <- p.parse(sb); (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) } -class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { +class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { def parse(sb: I) = p.parse(sb) ++ q.parse(sb) } -class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { +class FunParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { def parse(sb: I) = for ((head, tail) <- p.parse(sb)) yield (f(head), tail) } @@ -296,7 +341,7 @@ implicit def string2parser(s : String) = StringParser(s) -implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { +implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) @@ -361,11 +406,11 @@ ("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} | (Stmt ==> (s => List(s))) -Stmts.parse_all("x2:=5+a") -Stmts.parse_all("x2:=5+a[3+a]") -Stmts.parse_all("a[x2+3]:=5+a[3+a]") -Block.parse_all("{x:=5;y:=8}") -Block.parse_all("if(false)then{x:=5}else{x:=10}") +//Stmts.parse_all("x2:=5+a") +//Stmts.parse_all("x2:=5+a[3+a]") +//Stmts.parse_all("a[x2+3]:=5+a[3+a]") +//Block.parse_all("{x:=5;y:=8}") +//Block.parse_all("if(false)then{x:=5}else{x:=10}") @@ -436,19 +481,28 @@ "\n" ++ //"new field[30000];\n" ++ "ptr := 15000;" ++ - instrs2(prog) ++ + instrs(prog) ++ "skip" } def bf_run(prog: String, name: String) = { println("BF processing start") val bf_string = bf_str(prog).replaceAll("\\s", "") + println(s"BF parsing start (string length ${bf_string.length})") val bf_prog = Stmts.parse_all(bf_string).toList.head - println("BF Compile start") + println(s"BF Compile start ${bf_string.toList.length} characters") compile_run(Array("field", 30000) :: bf_prog, name) } +// a benchmark program (counts down from 'Z' to 'A') +val bf0 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ + [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ + ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ + +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" + +bf_run(bf0, "bench") + val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ @@ -460,7 +514,8 @@ bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello") -bf_run("""+++++++++++ + +val bf2 = """+++++++++++ >+>>>>++++++++++++++++++++++++++++++++++++++++++++ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- @@ -470,4 +525,154 @@ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ ++++++++++++++++++++++++++++++++++++++++++++.[-]<< <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< - [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", "fibs") + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""" + +bf_run(bf2, "fibs") + + +bf_run(""" A mandelbrot set fractal viewer in brainf*** written by Erik Bosman ++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+ +<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>> +>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>> +>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>> +>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>> +>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>> +[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<< +<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[ +>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[ +-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<< +<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<< +[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>> +>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+ +<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>> +>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<< ++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<< +<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<< +<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[-> +>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<< +<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++ ++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>- +<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>> +[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<< +<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[- +]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<< +<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]< +<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>> +>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>> +[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-< +<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>> +]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> +]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+> +>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++ ++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+ +>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[ +-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-< +<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<< +[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-] ++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<< +[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<< +<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<< +<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<< +<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<< +<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<< +]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<< +[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<< ++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<< +<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-< +<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[ +[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+ +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->> +[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<< +<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[ +>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[ +>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]> +>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<< +<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<< +<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[- +<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>> +>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>> +[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<< ++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]> +[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>> +>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>> +>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<< +]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<< +<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>> +>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<< +<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<< +<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]< +<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]< +<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+ +<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<< +]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+> +>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[ +->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>> +>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<< +<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+ +>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>> +]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>> +>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<< +<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>> +>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+ +<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>> +>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<] +>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<< +]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+< +<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]> +>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<< +->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[ +>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<< +[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<< +<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<< +<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<< +<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>> +>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<< +<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]< ++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>> +>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<< +<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<< +<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<< +<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-< +<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<< +<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<< +<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<< +<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>> +>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<< +<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>> +>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<< +<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>> +>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<- +>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<< +<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>> +>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<< +<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>> ++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+< +<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<< +<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>> +-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>> +>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++ ++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<< +<<<<<]]>>>]""", "mand") +