--- a/handouts/ho07.tex Tue Feb 04 09:31:18 2020 +0000
+++ b/handouts/ho07.tex Fri Feb 07 11:32:47 2020 +0000
@@ -52,15 +52,15 @@
\noindent
The input will be WHILE-programs; the output will be assembly files
(with the file extension .j). Assembly files essentially contain
-human-readable machine code, meaning they are not just bits and bytes,
+human-readable low-level code, meaning they are not just bits and bytes,
but rather something you can read and understand---with a bit of
practice of course. An \emph{assembler} will then translate the assembly
-files into unreadable class- or binary-files the JVM can run.
+files into unreadable class- or binary-files the JVM or CPU can run.
Unfortunately, the Java ecosystem does not come with an assembler which
would be handy for our compiler-endeavour (unlike Microsoft's Common
Language Infrastructure for the .Net platform which has an assembler
-out-of-the-box). As a substitute we shall use the 3rd-party
-programs Jasmin and Krakatau
+out-of-the-box). As a substitute we shall use the 3rd-party programs
+Jasmin and Krakatau
\begin{itemize}
\item \url{http://jasmin.sourceforge.net}
@@ -116,7 +116,7 @@
\noindent where \meta{Id} stands for variables and \meta{Num}
for numbers. For the moment let us omit variables from arithmetic
expressions. Our parser will take this grammar and given an input
-program produce an abstract syntax tree. For example we will obtain for
+program produce an abstract syntax tree. For example we obtain for
the expression $1 + ((2 * 3) + (4 - 3))$ the following tree.
\begin{center}
@@ -248,7 +248,7 @@
time, we need to allocate a new index and if it has been used
before, then we need to be able to retrieve the associated index.
This is reflected in the clause for compiling assignments, say
-$\textit{x := a}$:
+$x := a$:
\begin{center}
\begin{tabular}{lcl}
@@ -261,7 +261,7 @@
assignment (that is the arithmetic expression $a$) and then add an
\instr{istore}-instruction at the end. By convention running the code
for the arithmetic expression $a$ will leave the result on top of the
-stack. After that the \instr{istore} instruction, the result will be
+stack. After that the \instr{istore}-instruction, the result will be
stored in the index corresponding to the variable $x$. If the variable
$x$ has been used before in the program, we just need to look up what
the index is and return the environment unchanged (that is in this case
@@ -376,8 +376,8 @@
addresses, but can just attach (symbolic) labels to our code.
These labels specify a target for a jump. Therefore the labels
need to be unique, as otherwise it would be ambiguous where a
-jump should go to. A label, say \pcode{L}, is attached to code
-like
+jump should go to. A label, say \pcode{L}, is attached to assembly
+code like
\begin{lstlisting}[mathescape,numbers=none]
L:
@@ -468,7 +468,7 @@
the two branches, $is_1$ and $is_2$. The final code will
be first the code for $b$ (including the label
just-before-the-else-branch), then the \pcode{goto} for after
-the else-branch, the label $L_\textit{ifesle}$, followed by
+the else-branch, the label $L_\textit{ifelse}$, followed by
the instructions for the else-branch, followed by the
after-the-else-branch label. Consider for example the
if-statement:
@@ -503,15 +503,15 @@
\noindent The first three lines correspond to the the boolean
expression $1 = 1$. The jump for when this boolean expression
is false is in Line~3. Lines 4-6 corresponds to the if-branch;
-the else-branch is in Lines 8 and 9. Note carefully how the
-environment $E$ is threaded through the recursive calls of
-\textit{compile}. The function receives an environment $E$,
-but it might extend it when compiling the if-branch, yielding
-$E'$. This happens for example in the if-statement above
-whenever the variable \code{x} has not been used before.
-Similarly with the environment $E''$ for the second call to
-\textit{compile}. $E''$ is also the environment that needs to
-be returned as part of the answer.
+the else-branch is in Lines 8 and 9.
+
+Note carefully how the environment $E$ is threaded through the recursive
+calls of \textit{compile}. The function receives an environment $E$, but
+it might extend it when compiling the if-branch, yielding $E'$. This
+happens for example in the if-statement above whenever the variable
+\code{x} has not been used before. Similarly with the environment $E''$
+for the second call to \textit{compile}. $E''$ is also the environment
+that needs to be returned as part of the answer.
The compilation of the while-loops, say
\pcode{while} $b$ \pcode{do} $cs$, is very similar. In case
@@ -640,7 +640,7 @@
void). Since the method has only one argument, we only need a single
local variable (Line~2) and a stack with two cells will be sufficient
(Line 3). Line 4 instructs the JVM to get the value of the member
-\pcode{out} of the class \pcode{java/lang/System}. It expects the value
+\pcode{out} from the class \pcode{java/lang/System}. It expects the value
to be of type \pcode{java/io/PrintStream}. A reference to this value
will be placed on the stack.\footnote{Note the syntax \texttt{L
\ldots{};} for the \texttt{PrintStream} type is not an typo. Somehow the
@@ -757,7 +757,7 @@
inside an arithmetic expression---we need to be able to look up the
contents of an array at an index determined by an arithmetic expression.
Similarly in the line below, we need to be able to update the content of
-an array at an calculated index.
+an array at a calculated index.
For creating a new array we can generate the following three JVM
instructions:
@@ -835,7 +835,7 @@
\end{plstx}
With this in place we can turn back to the idea of creating
-WHILE-programs by translating BF programs. This is a relatively easy
+WHILE-programs by translating BF-programs. This is a relatively easy
task because BF has only eight instructions (we will actually implement
seven because we can omit the read-in instruction from BF). What makes
this translation easy is that BF-loops can be straightforwardly
@@ -886,23 +886,24 @@
\subsection*{Optimisations \& Co}
-Every compiler that deserves its name performs optimisations on the
-code. If we make the extra effort of writing a compiler for a language,
-then obviously we want to have our code to run as fast as possible.
-So we should look into this.
+Every compiler that deserves its name has to perform some optimisations
+on the code: if we put in the extra effort of writing a compiler for a
+language, then obviously we want to have our code to run as fast as
+possible. So we should look into this in more detail.
There is actually one aspect in our generated code where we can make
-easily efficiency gains: this has to do with some of the quirks of the
+easily efficiency gains. This has to do with some of the quirks of the
JVM. Whenever we push a constant onto the stack, we used the JVM
instruction \instr{ldc some_const}. This is a rather generic instruction
in the sense that it works not just for integers but also for strings,
objects and so on. What this instruction does is putting the constant
-into a \emph{constant pool} and then to use an index into this constant
+into a \emph{constant pool} and then uses an index into this constant
pool. This means \instr{ldc} will be represented by at least two bytes
-in the class file. While this is sensible for ``large'' constants like
-strings, it is a bit of overkill for small integers (which many integers
-will be when compiling a BF-program). To counter this ``waste'', the JVM
-has specific instructions for small integers, for example
+in the class file. While this is a sensible strategy for ``large''
+constants like strings, it is a bit of overkill for small integers
+(which many integers will be when compiling a BF-program). To counter
+this ``waste'', the JVM has specific instructions for small integers,
+for example
\begin{itemize}
\item \instr{iconst_0},\ldots, \instr{iconst_5}
@@ -918,25 +919,31 @@
the constant pool). While in theory the use of such special instructions
should make the code only smaller, it actually makes the code also run
faster. Probably because the JVM has to process less code and uses a
-specific instruction in the underlying CPU. The story with
+specific instruction for the underlying CPU. The story with
\instr{bipush} is slightly different, because it also uses two
-bytes---so it does not result in a reduction in code size. But againm,
-it probably uses a specific instruction in the underlying CPU that make
-the JVM code run faster. This means when generating code we can use
-the following helper function
+bytes---so it does not necessarily result in a reduction of code size.
+Instead, it probably uses a specific instruction in the underlying CPU
+that makes the JVM code run faster.\footnote{This is all ``probable''
+because I have not read the 700 pages of JVM documentation by Oracle and
+also have no clue how the JVM is implemented.} This means when
+generating code for pushing constants onto the stack, we can use the
+following Scala helper-function
\begin{lstlisting}[language=Scala]
def compile_num(i: Int) =
if (0 <= i && i <= 5) i"iconst_$i" else
- if (-128 <= i && i <= 127) i"bipush $i" else i"ldc $i"
+ if (-128 <= i && i <= 127) i"bipush $i"
+ else i"ldc $i"
\end{lstlisting}
\noindent
-that generates the more efficient instructions for pushing a constant
-onto the stack. Note the JVM also has special instructions that
-load and store the first three local variables. The assumption is that
-most operations and arguments in a method will only use very few
-local variables. So the JVM has the following instructions:
+It generates the more efficient instructions when pushing a small integer
+constant onto the stack. The default is \instr{ldc} for any other constants.
+
+The JVM also has such special instructions for
+loading and storing the first three local variables. The assumption is
+that most operations and arguments in a method will only use very few
+local variables. So we can use the following instructions:
\begin{itemize}
\item \instr{iload_0},\ldots, \instr{iload_3}
@@ -947,8 +954,9 @@
\noindent Having implemented these optimisations, the code size of the
-BF-Mandelbrot program reduces and also it runs faster. According to my
-very rough experiments:
+BF-Mandelbrot program reduces and also the class-file runs faster (the
+parsing part is still very slow). According to my very rough
+experiments:
\begin{center}
\begin{tabular}{lll}
@@ -961,11 +969,11 @@
\noindent
Quite good! Such optimisations are called \emph{peephole optimisations},
-because it is type of optimisations that involve changing a small set of
-instructions into an equivalent set that has better performance.
+because they involve changing one or a small set of instructions into an
+equivalent set that has better performance.
-If you look careful at our code you will quickly find another source of
-inefficiency in programs like
+If you look careful at our generated code you will quickly find another
+source of inefficiency in programs like
\begin{lstlisting}[mathescape,language=While]
x := ...;
@@ -976,24 +984,32 @@
where our code first calculates the new result the for \texttt{x} on the
stack, then pops off the result into a local variable, and after that
loads the local variable back onto the stack for writing out a number.
+
+\begin{lstlisting}[mathescape,language=JVMIS]
+...
+istore 0
+iload 0
+...
+\end{lstlisting}
+
+\noindent
If we can detect such situations, then we can leave the value of
\texttt{x} on the stack with for example the much cheaper instruction
\instr{dup}. Now the problem with this optimisation is that it is quite
easy for the snippet above, but what about instances where there is
further WHILE-code in \emph{between} these two statements? Sometimes we
will be able to optimise, sometimes we will not. The compiler needs to
-find out which situation applies. This can become quickly much more
+find out which situation applies. This can quickly become much more
complicated. So we leave this kind of optimisations here and look at
something more interesting and possibly surprising.
-
-As you have probably seen, the compiler writer has a lot of freedom
-about how to generate code from what the programmer wrote as program.
-The only condition is that generated code should behave as expected by
-the programmer. Then all is fine\ldots mission accomplished! But
-sometimes the compiler writer is expected to go an extra mile, or even
-miles and change the meaning of a program in unexpected ways. Suppose we
-are given the following WHILE-program:
+As you might have seen, the compiler writer has a lot of freedom about
+how to generate code from what the programmer wrote as program. The only
+condition is that generated code should behave as expected by the
+programmer. Then all is fine with the code above\ldots mission
+accomplished! But sometimes the compiler writer is expected to go an
+extra mile, or even miles and change(!) the meaning of a program.
+Suppose we are given the following WHILE-program:
\begin{lstlisting}[mathescape,language=While]
new(arr[10]);
@@ -1003,29 +1019,60 @@
\noindent
Admittedly this is a contrived program, and probably not meant to be
like this by any sane programmer, but it is supposed to make the
-following point: We generate an array of size 10, and then try to access
-the non-existing element at index 13 and even updating element with
-index 14. Obviously this is baloney. Still, our compiler generates code
-for this program without any questions asked. We can even run this code
-on the JVM\ldots of course the result is an exception trace where the
-JVM yells at us for doing naughty things. (This is much better than C,
-for example, where such errors are not prevented and as a result
-insidious attacks can be mounted against such kind C-programs. I assume
-everyone has heard about \emph{Buffer Overflow Attacks}.) Now what
-should we do in such situations? Index over- or underflows are
-notoriously difficult to detect statically (at compiletime), so it seem
-raising an exception at run-time like the JVM is the best compromise.
+following point: The program generates an array of size 10, and then
+tries to access the non-existing element at index 13 and even updating
+the element with index 14. Obviously this is baloney. Still, our
+compiler generates code for this program without any questions asked. We
+can even run this code on the JVM\ldots of course the result is an
+exception trace where the JVM yells at us for doing naughty
+things.\footnote{Still this is much better than C, for example, where
+such errors are not prevented and as a result insidious attacks can be
+mounted against such kind C-programs. I assume everyone has heard about
+\emph{Buffer Overflow Attacks}.} Now what should we do in such
+situations? Over- and underflows of indices are notoriously difficult to
+detect statically (at compiletime). So it might seem raising an
+exception at run-time like the JVM is the best compromise.
Well, imagine we do not want to rely in our compiler on the JVM for
producing an annoying, but safe exception trace, rather we want to
-handle such situations ourselves according to what we thing should
-happen in such cases. Let's assume we want to handle them in the
+handle such situations ourselves according to what we think should
+happen in such cases. Let us assume we want to handle them in the
following way: if the programmer access a field out-of-bounds, we just
-return a default 0, and if a programmer wants to update an
-out-of-bounds field, we want to ``quietly'' ignore this update.
+return a default 0, and if a programmer wants to update an out-of-bounds
+field, we want to ``quietly'' ignore this update. One way to achieve
+this would be to rewrite the WHILE-programs and insert the necessary
+if-conditions for safely reading and writing arrays. Another way
+is to modify the code we generate.
+\begin{lstlisting}[mathescape,language=JVMIS2]
+ $\textit{index\_aexp}$
+ aload loc_var
+ dup2
+ arraylength
+ if_icmple L1
+ pop2
+ iconst_0
+ goto L2
+L1:
+ swap
+ iaload
+L2:
+\end{lstlisting}
-arraylength
+ \begin{lstlisting}[mathescape,language=JVMIS2]
+ $\textit{index\_aexp}$
+ aload loc_var
+ dup2
+ arraylength
+ if_icmple L1
+ pop2
+ goto L2
+L1:
+ swap
+ $\textit{value\_aexp}$
+ iastore
+L2:
+\end{lstlisting}
\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/compile_arr3.scala Fri Feb 07 11:32:47 2020 +0000
@@ -0,0 +1,709 @@
+// A Small Compiler for the WHILE Language
+//
+// - includes arrays and a small parser for
+// WHILE programs
+//
+// - transpiles BF programs into WHILE programs
+// and compiles and runs them
+//
+// Call with
+//
+// scala compile_arr.scala
+
+// Mandelbrot
+// mand.j size 232266
+// mand.class size 21787
+// running time 16 secs
+
+// the abstract syntax trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp
+type Block = List[Stmt]
+
+// statements
+case object Skip extends Stmt
+case class ArrayDef(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 // var := exp
+case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt // arr[exp1] := exp2
+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, a: AExp) extends AExp
+
+// boolean expressions
+case object True extends BExp
+case object False extends BExp
+case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+
+
+// compiler headers needed for the JVM
+// (contains an init method, as well as methods for read and write)
+val beginning = """
+.class public XXX.XXX
+.super java/lang/Object
+
+.method public static write(I)V
+ .limit locals 1
+ .limit stack 2
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ iload 0
+ i2c ; Int => Char
+ invokevirtual java/io/PrintStream/print(C)V ; println(I)V => print(C)V
+ return
+.end method
+
+.method public static main([Ljava/lang/String;)V
+ .limit locals 200
+ .limit stack 200
+
+; COMPILED CODE STARTS
+
+"""
+
+val ending = """
+; COMPILED CODE ENDS
+ return
+
+.end method
+"""
+
+
+
+
+// for generating new labels
+var counter = -1
+
+def Fresh(x: String) = {
+ counter += 1
+ x ++ "_" ++ counter.toString()
+}
+
+// environments and instructions
+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"
+}
+
+
+def compile_num(i: Int) =
+ if (0 <= i && i <= 5) i"iconst_$i" else
+ if (-128 <= i && i <= 127) i"bipush $i" else i"ldc $i"
+
+def compile_aload(i: Int) =
+ if (0 <= i && i <= 3) i"aload_$i" else i"aload $i"
+
+def compile_iload(i: Int) =
+ if (0 <= i && i <= 3) i"iload_$i" else i"iload $i"
+
+def compile_istore(i: Int) =
+ if (0 <= i && i <= 3) i"istore_$i" else i"istore $i"
+
+// arithmetic expression compilation
+def compile_aexp(a: AExp, env : Env) : String = a match {
+ case Num(i) => compile_num(i)
+ case Var(s) => compile_iload(env(s))
+ case Aop(op, a1, a2) =>
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op)
+ case Ref(s, a) => {
+ val arr_safe = Fresh("Arr_safe")
+ val arr_end = Fresh("Arr_end_")
+ compile_aexp(a, env) ++
+ compile_aload(env(s)) ++
+ i"dup2" ++
+ i"arraylength" ++
+ i"if_icmple $arr_safe" ++
+ i"pop2" ++
+ i"iconst_0" ++
+ i"goto $arr_end" ++
+ l"$arr_safe" ++
+ i"swap" ++
+ i"iaload" ++
+ l"$arr_end"
+ }
+}
+
+def compile_bop(op: String, jmp: String) = op match {
+ case "==" => i"if_icmpne $jmp"
+ case "!=" => i"if_icmpeq $jmp"
+ case "<" => i"if_icmpge $jmp"
+}
+
+
+// boolean expression compilation
+def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
+ case True => ""
+ case False => i"goto $jmp"
+ case Bop(op, a1, a2) =>
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_bop(op, jmp)
+}
+
+// statement compilation
+def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match {
+ case Skip => ("", env)
+ case Assign(x, a) => {
+ val index = env.getOrElse(x, env.keys.size) //
+ (compile_aexp(a, env) ++ compile_istore(index), env + (x -> index))
+ }
+ case If(b, bl1, bl2) => {
+ val if_else = Fresh("If_else")
+ val if_end = Fresh("If_end")
+ val (instrs1, env1) = compile_block(bl1, env)
+ val (instrs2, env2) = compile_block(bl2, env1)
+ (compile_bexp(b, env, if_else) ++
+ instrs1 ++
+ i"goto $if_end" ++
+ l"$if_else" ++
+ instrs2 ++
+ 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)
+ (l"$loop_begin" ++
+ compile_bexp(b, env, loop_end) ++
+ instrs1 ++
+ i"goto $loop_begin" ++
+ l"$loop_end", env1)
+ }
+ case Write(x) =>
+ (compile_iload(env(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" ++
+ compile_istore(index), env + (x -> index))
+ }
+ case ArrayDef(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 arr_safe = Fresh("Arr_safe")
+ val arr_end = Fresh("Arr_end_")
+ val index = if (env.isDefinedAt(s)) env(s) else
+ throw new Exception("array not defined")
+ (compile_aexp(a1, env) ++
+ compile_aload(env(s)) ++
+ i"dup2" ++
+ i"arraylength" ++
+ i"if_icmple $arr_safe" ++
+ i"pop2" ++
+ i"goto $arr_end" ++
+ l"$arr_safe" ++
+ i"swap" ++
+ compile_aexp(a2, env) ++
+ i"iastore" ++
+ l"$arr_end", env)
+ }
+}
+
+// compilation of a block (i.e. list of statements)
+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)
+ (instrs1 ++ instrs2, env2)
+ }
+}
+
+
+// main compilation function for blocks
+def compile(bl: Block, class_name: String) : String = {
+ val instructions = compile_block(bl, Map())._1
+ (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name)
+}
+
+
+// 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 instructions for fib
+//
+// println(compile(fib_test, "fib"))
+//
+// can be assembled by hand with
+//
+// java -jar jvm/jasmin-2.4/jasmin.jar fib.j
+//
+// and started with
+//
+// java fib/fib
+
+import scala.util._
+import scala.sys.process._
+
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 2 to i) code
+ val result = code
+ val end = System.nanoTime()
+ ((end - start) / (i * 1.0e9), result)
+}
+
+def compile_to_file(bl: Block, class_name: String) : Unit =
+ Using(new java.io.FileWriter(class_name + ".j")) {
+ _.write(compile(bl, class_name))
+ }
+
+def compile_and_run(bl: Block, class_name: String) : Unit = {
+ println(s"Start compilation of $class_name")
+ compile_to_file(bl, class_name)
+ println("generated .j file")
+ (s"java -jar jvm/jasmin-2.4/jasmin.jar ${class_name}.j").!!
+ println("generated .class file ")
+ println("Time: " + time_needed(3, (s"java ${class_name}/${class_name}").!)._1)
+}
+
+
+val arr_test =
+ List(ArrayDef("a", 10),
+ ArrayDef("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_and_run(arr_test, "a")
+
+//====================
+// Parser Combinators
+//====================
+
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+// more convenience for the semantic actions later on
+case class ~[+A, +B](_1: A, _2: B)
+
+type IsSeq[A] = A => Seq[_]
+
+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 : 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 (new ~(head1, head2), tail2)
+}
+
+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 : 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)
+}
+
+
+import scala.util.matching.Regex
+case class RegexParser(reg: Regex) extends Parser[String, String] {
+ def parse(sb: String) = reg.findPrefixMatchOf(sb) match {
+ case None => Set()
+ case Some(m) => Set((m.matched, m.after.toString))
+ }
+}
+
+def StringParser(s: String) = RegexParser(Regex.quote(s).r)
+
+
+implicit def string2parser(s : String) = StringParser(s)
+
+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)
+}
+
+implicit def StringOps(s: String) = new {
+ def | (q : => Parser[String, String]) = new AltParser[String, String](s, q)
+ def | (r: String) = new AltParser[String, String](s, r)
+ def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)
+ def ~[S](q : => Parser[String, S]) =
+ new SeqParser[String, String, S](s, q)
+ def ~ (r: String) =
+ new SeqParser[String, String, String](s, r)
+}
+
+
+val NumParser = RegexParser("[0-9]+".r) ==> (s => s.toInt : Int)
+val IdParser = RegexParser("[a-z][a-z,0-9]*".r)
+
+
+
+// Grammar Rules for WHILE with arrays
+
+lazy val AExp: Parser[String, AExp] =
+ (Te ~ "+" ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z):AExp } |
+ (Te ~ "-" ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z):AExp } | Te
+lazy val Te: Parser[String, AExp] =
+ (Fa ~ "*" ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z):AExp } | Fa
+lazy val Fa: Parser[String, AExp] =
+ ("(" ~ AExp ~ ")") ==> { case _ ~ y ~ _ => y } |
+ (IdParser ~ "[" ~ AExp ~ "]") ==> { case x ~ _ ~ y ~ _ => Ref(x, y) } |
+ IdParser ==> Var |
+ NumParser ==> Num
+
+// boolean expressions
+lazy val BExp: Parser[String, BExp] =
+ (AExp ~ "=" ~ AExp) ==> { case x ~ y ~ z => Bop("=", x, z):BExp } |
+ (AExp ~ "!=" ~ AExp) ==> { case x ~ y ~ z => Bop("!=", x, z):BExp } |
+ (AExp ~ "<" ~ AExp) ==> { case x ~ y ~ z => Bop("<", x, z):BExp } |
+ (AExp ~ ">" ~ AExp) ==> { case x ~ y ~ z => Bop("<", z, x):BExp } |
+ ("true" ==> ((_) => True:BExp )) |
+ ("false" ==> ((_) => False:BExp )) |
+ ("(" ~ BExp ~ ")") ==> { case x ~ y ~ z => y}
+
+lazy val Stmt: Parser[String, Stmt] =
+ ("skip" ==> (_ => Skip: Stmt)) |
+ (IdParser ~ ":=" ~ AExp) ==> { case x ~ y ~z => Assign(x, z): Stmt } |
+ (IdParser ~ "[" ~ AExp ~ "]" ~ ":=" ~ AExp) ==> {
+ case x ~ _ ~ z ~ _ ~ _ ~ u => AssignA(x, z, u): Stmt } |
+ ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==>
+ { case _ ~ y ~ _ ~ u ~ _ ~w => If(y, u, w): Stmt } |
+ ("while" ~ BExp ~ "do" ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) } |
+ ("new(" ~ IdParser ~ "[" ~ NumParser ~ "])") ==> {
+ case _ ~ y ~ _ ~ u ~ _ => ArrayDef(y, u) } |
+ ("write" ~ IdParser) ==> { case _ ~ y => Write(y) }
+
+lazy val Stmts: Parser[String, Block] =
+ (Stmt ~ ";" ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } |
+ (Stmt ==> ((s) => List(s) : Block))
+
+
+lazy val Block: Parser[String, Block] =
+ ("{" ~ Stmts ~ "}") ==> { case _ ~ y ~ _ => 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}")
+
+
+
+val fib = """
+ n := 10;
+ minus1 := 0;
+ minus2 := 1;
+ temp:=0;
+ while (n > 0) do {
+ temp := minus2;
+ minus2 := minus1 + minus2;
+ minus1 := temp;
+ n := n - 1};
+ result := minus2;
+ write result
+ """.replaceAll("\\s+", "")
+
+val fib_prog = Stmts.parse_all(fib).toList
+//compile_and_run(fib_prog.head, "fib")
+
+//======================================
+// BF transpiler into WHILE with arrays
+//======================================
+
+// simple BF instructions translation
+def instr(c: Char) : String = c match {
+ case '>' => "ptr := ptr + 1;"
+ case '<' => "ptr := ptr - 1;"
+ case '+' => "mem[ptr] := mem[ptr] + 1;"
+ case '-' => "mem[ptr] := mem[ptr] - 1;"
+ case '.' => "x := mem[ptr]; write x;"
+ //case ',' => "XXX" // "ptr = getchar();\n"
+ case '[' => "while (mem[ptr] != 0) do {"
+ case ']' => "skip};"
+ case _ => ""
+}
+
+def instrs(prog: String) : String =
+ prog.toList.map(instr).mkString
+
+
+// Note: the mandelbrot.bf program is so large that
+// it does not fit inside the limitations of what the
+// JVM imposes on methods (only 64K of instructions).
+// Therefore some optimisations are first applied to
+// BF programs before WHILE programs are created. The
+// optimisations are
+//
+// - replacing BF-loops of the form [-]
+// - combining single increment/decrement instructions
+//
+// The size of the resulting .j-file is 270K.
+
+def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
+ case (Nil, acc) => acc
+ case (c :: cs, Nil) => splice(cs, List((c, 1)))
+ case (c :: cs, (d, n) :: acc) =>
+ if (c == d) splice(cs, (c, n + 1) :: acc)
+ else splice(cs, (c, 1) :: (d, n) :: acc)
+}
+
+def spl(s: String) = splice(s.toList, Nil).reverse
+
+def instr2(c: Char, n: Int) : String = c match {
+ case '>' => s"ptr := ptr + $n;"
+ case '<' => s"ptr := ptr - $n;"
+ case '0' => s"mem[ptr] := 0;"
+ case '+' => s"mem[ptr] := mem[ptr] + $n;"
+ case '-' => s"mem[ptr] := mem[ptr] - $n;"
+ case '.' => s"x := mem[ptr]; write x;"
+ case '[' => "while (mem[ptr] != 0) do {" * n
+ case ']' => "skip};" * n
+ case _ => ""
+}
+
+def instrs2(prog: String) : String =
+ spl(prog.replaceAll("""\[-\]""", "0")).map{ case (c, n) => instr2(c, n) }.mkString
+
+def bf_str(prog: String) : String = {
+ "new(mem[30000]);" ++
+ "ptr := 15000;" ++
+ instrs2(prog) ++
+ "skip"
+}
+
+def bf_run(prog: String, name: String) = {
+ println(s"BF pre-processing of $name")
+ val bf_string = bf_str(prog).replaceAll("\\s", "")
+ println(s"BF parsing (program length ${bf_string.length} characters)")
+ val (time, bf_prog) = time_needed(1, Stmts.parse_all(bf_string).toList.head)
+ println(s"BF generated WHILE program (needed $time for parsing)")
+ compile_and_run(bf_prog, name)
+}
+
+// a benchmark program (counts down from 'Z' to 'A')
+val bf0 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+ [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+ ++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+ +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
+
+bf_run(bf0, "bench")
+
+// Sierpinski triangle
+val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]"""
+
+bf_run(bf1, "sier")
+
+// Helo World!
+bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello")
+
+// Fibonacci
+val bf2 = """+++++++++++
+ >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]
+ [-]++++++++++."""
+
+bf_run(bf2, "fibs")
+
+// Mandelbrot Set
+//----------------
+//
+// Note: Parsing of the generated WHILE program (around 60K in size)
+// takes approximately 10 minutes
+
+
+
+bf_run("""A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
+<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
+>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
+>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
+>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
+>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
+[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
+<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
+>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
+-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
+<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
+[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
+>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
+<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
+>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
+<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
+<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
+>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
+<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
+[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
+<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
+]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
+<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
+<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
+>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
+[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
+<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
+]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
+-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
+<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
+[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
+[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
+<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
+<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
+<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
+<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
+]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
+[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
+<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
+<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
+[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
+[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
+<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
+>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
+>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
+>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
+<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
+<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
+<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
+>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
+[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
+[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
+>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
+>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
+]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
+<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
+>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
+<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
+<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
+<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
+<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
+<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
+]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
+>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
+->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
+>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
+<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
+]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
+>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
+<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
+>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
+>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
+>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
+]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
+<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
+>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
+->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
+>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
+[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
+<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
+<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
+<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
+>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
+<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
+>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
+<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
+<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
+<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
+<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
+<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
+<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
+<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
+>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
+<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
+>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
+>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
+>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
+<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
+>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
+<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
+<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
+<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
+-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
+>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
+<<<<<]]>>>]""", "mand")
+
+