Binary file cws/cw05.pdf has changed
--- a/cws/cw05.tex Thu Dec 06 16:08:11 2018 +0000
+++ b/cws/cw05.tex Thu Dec 06 18:37:17 2018 +0000
@@ -319,11 +319,152 @@
\end{figure}
\end{itemize}\bigskip
+\newpage
+
\subsection*{Part 2 (4 Marks)}
-While it is fun to look at bf-programs, like the Sierpinski triangle or the Mandelbrot
-program, being interpreted, it is much more fun to write a compiler for the bf-language.
+I am sure you agree while it is fun to look at bf-programs, like the
+Sierpinski triangle or the Mandelbrot program, being interpreted, it
+is much more fun to write a compiler for the bf-language.
+
+
+\subsubsection*{Tasks (file bfc.scala)}
+
+\begin{itemize}
+\item[(5)] Compilers in general attempt to make programs run
+ faster by precomputing as much information as possible
+ before running the program. In our case we can precompute the
+ addresses where we need to jump at the beginning and end of
+ loops.
+
+ For this write a function \texttt{jtable} that precomputes the ``jump
+ table'' for a bf-program. This function takes a bf-program
+ as an argument and returns a \texttt{Map[Int, Int]}. The
+ purpose of this Map is to record the information
+ that given on the pc-position $pc$ is a '\texttt{[}' or a '\texttt{]}',
+ then to which pc-position do we need to jump next?
+
+ For example for the program
+
+ \begin{center}
+ \texttt{+++++[->++++++++++<]>--<+++[->>++++++++++}
+ \texttt{<<]>>++<<----------[+>.>.<+<]}
+ \end{center}
+
+ we obtain the Map (note the precise numbers might differ depending on white
+ spaces etc.~in the bf-program):
+
+ \begin{center}
+ \texttt{Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)}
+ \end{center}
+
+ This Map states that for the '\texttt{[}' on position 5, we need to
+ jump to position 20, which is just after the corresponding '\texttt{]}'.
+ Similarly, for the '\texttt{]}' on position 19, we need to jump to
+ position 6, which is just after the '\texttt{[}' on position 5, and so
+ on. The idea is to not calculate this information each time
+ we hit a bracket, but just look up this information in the
+ \texttt{jtable}.
+
+ Then adapt the \texttt{compute} and \texttt{run} functions
+ from Part 1 in order to take advantage of the information
+ stored in the \texttt{jtable}. This means whenever \texttt{jumpLeft}
+ and \texttt{jumpRight} was called previously, you should look
+ up the jump address in the \texttt{jtable}. Feel free to reuse
+ the function \texttt{jumpLeft} and \texttt{jumpRight} for
+ calculating the \texttt{jtable}.\hfill{[1 Mark]}
+
+\item[(6)] Compilers try to eliminate any ``dead'' code that could slow
+ down programs and also perform what is often called
+ \emph{peephole optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} While it is difficult for compilers to comprehend what
+ is intended with whole programs, they are very good at finding out
+ what small snippets of code do, and then try to generate
+ faster code for such snippets.
+
+ In our case, dead code is everything that is not a bf-command.
+ Therefore write a function \texttt{optimise} which deletes such
+ dead code. Moreover this function should replace every substring
+ of the form \pcode{[-]} by a new command \texttt{0}.
+ The idea is that the loop \pcode{[-]} just resets the
+ memory at the current location to 0. It is more efficient
+ to do this in a single step, rather than incrementally as in
+ the original bf-programs.
+ In the extended \texttt{compute3} and \texttt{run3} functions you should
+ implement this command by writing 0 to \pcode{mem(mp)}, that is use
+ \pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}.
+ The easiest way to modify a string in this way is to use the regular
+ expression \pcode{"""[^<>+-.,\\[\\]]"""}, which recognises everything that is
+ not a bf-command. Similarly, the
+ regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]} and
+ by using the Scala method \pcode{.replaceAll} you can replace it with the
+ string \pcode{"0"} standing for the new bf-command.\hfill{[1 Mark]}
+
+\item[(7)] Finally, real compilers try to take advantage of CPUs which often
+ provide complex operations in hardware that can combine many smaller
+ instructions into a single faster instruction.
+
+ In our case we can optimise the several single increments of a
+ memory cell, for example \pcode{++++}, by a single ``increment by
+ 4''. For this optimisation we just have to make sure these single
+ increments are all next to each other. Similarly optimisations should apply
+ for the bf-commands \pcode{-}, \pcode{<} and
+ \pcode{>}, which can all be replaced by extended versions that take
+ the amount of the increment (decrement) into account. We will do
+ this by introducing two-character bf-commands. For example
+
+ \begin{center}
+ \begin{tabular}{l|l}
+ original bf-cmds & replacement\\
+ \hline
+ \pcode{+} & \pcode{+A}\\
+ \pcode{++} & \pcode{+B}\\
+ \pcode{+++} & \pcode{+C}\\
+ \ldots{} & \ldots{}\\
+ \pcode{+++....++} & \pcode{+Z}\\
+ \hspace{5mm}(these are 26 \pcode{+}'s)\\
+ \end{tabular}
+ \end{center}
+
+
+ Similarly for \pcode{-}, \pcode{<} and \pcode{>}. If there are more
+ than 26 \pcode{+}'s in a row, then more than on ``two-character''
+ bf-commands need to be generated (the idea is that more than
+ 26 copies of a single bf-command in a row is a rare occurrence in
+ actual bf-programs). All other bf-commands should be unaffected by this
+ change.
+
+ For this write a function \texttt{combine} which replaces sequences
+ of repeated increment and decrement commands by appropriate
+ two-character commands. In the functions \pcode{compute4} and
+ \pcode{run4}, the ``combine'' and the optimisation from (6) should
+ be performed. Make sure that when a two-character bf-command is
+ encountered you need to increase the \pcode{pc}-counter by two in
+ order to process the next command. For example
+
+ \begin{center}
+ \pcode{combine(optimise(load_bff("benchmark.bf")))}
+ \end{center}
+
+ generates the improved program
+
+ \begin{center}
+ \pcode{>A+B[<A+M>A-A]<A[[}\hspace{3mm}\ldots{}
+ \end{center}
+
+ for the original benchmark program
+
+ \begin{center}
+ \pcode{>++[<+++++++++++++>-]<[[}\hspace{3mm}\ldots
+ \end{center}
+
+ As you can see, the compiler bets on saving so much time on the
+ \pcode{+B} and \pcode{+M} steps so that the optimisations is
+ worthwhile overall (of course for the \pcode{>A}'s and so on, the compiler incurs a
+ penalty). Luckily, after you have performed all
+ optimisations in (5) - (7), you can expect that the
+ \pcode{benchmark.bf} program runs four to five times faster.\hfill{[2 Marks]}
+\end{itemize}
\end{document}
--- a/solutions5/bfc.scala Thu Dec 06 16:08:11 2018 +0000
+++ b/solutions5/bfc.scala Thu Dec 06 18:37:17 2018 +0000
@@ -75,20 +75,31 @@
def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
-// The baseline to what we compare our "compiler";
-// it requires something like 60 seconds on my laptop
+// The baseline to what we can compare our "compiler"
+// implemented below. It should require something like
+// 60 seconds for the calculation on my laptop
//
//time_needed(1, run(load_bff("benchmark.bf")))
+// DEBUGGING INFORMATION!!!
+//
+// Compiler, even real ones, are fiedishly difficult to get
+// to prduce correct code. The point is that for example for
+// the sierpinski program, they need to still generate code
+// that displays such a triangle. If yes, then one usually
+// can take comfort that all is well. If not, then something
+// went wrong during the optimisations.
+
+
// (5) Write a function jtable that precomputes the "jump
// table" for a bf-program. This function takes a bf-program
// as an argument and Returns a Map[Int, Int]. The
// purpose of this map is to record the information
-// that given on the pc-position, say n, is a '[' or a ']',
-// then to which pc-position do we need to jump?
+// that given on the position pc is a '[' or a ']',
+// then to which pc-position do we need to jump next?
//
// For example for the program
//
@@ -102,12 +113,15 @@
// jump to position 20, which is just after the corresponding ']'.
// Similarly, for the ']' on position 19, we need to jump to
// position 6, which is just after the '[' on position 5, and so
-// on. The idea to not calculate this information each time
-// we hit a bracket, but just loop uu this information in the
-// jtable.
+// on. The idea is to not calculate this information each time
+// we hit a bracket, but just look up this information in the
+// jtable. You can use the jumpLeft and jumpRight functions
+// from Part 1 for calculating the jtable.
//
-// Adapt the compute and run functions from Part 1 in order to
-// take advantage of the information in the jtable.
+// Then adapt the compute and run functions from Part 1 in order
+// to take advantage of the information stored in the jtable.
+// This means whenever jumpLeft and jumpRight was called previously,
+// you should look up the jump address in the jtable.
def jtable(pg: String) : Map[Int, Int] =
@@ -149,23 +163,25 @@
//time_needed(1, run2(load_bff("benchmark.bf")))
+
// (6) Write a function optimise which deletes "dead code" (everything
// that is not a bf-command) and also replaces substrings of the form
-// [-] by a new command 0. The idea is that the the loop [-] resets the
+// [-] by a new command 0. The idea is that the loop [-] just resets the
// memory at the current location to 0. In the compute3 and run3 functions
-// below we implement this command by writing 0 to mem(mp), then is
-// write(mem, mp, 0).
+// below you implement this command by writing the number 0 to mem(mp),
+// that is write(mem, mp, 0).
//
// The easiest way to modify a string in this way is to use the regular
-// expression """[^<>+-.,\[\]]""", whcih recognises everything that is
+// expression """[^<>+-.,\[\]]""", which recognises everything that is
// not a bf-command and replace it by the empty string. Similarly the
// regular expression """\[-\]""" finds all occurences of [-] and
// by using the Scala method .replaceAll you can repplace it with the
-// string "0" standing for the new bf-program.
+// string "0" standing for the new bf-command.
def optimise(s: String) : String =
s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""", "0")
+
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
if (0 <= pc && pc < pg.length) {
val (new_pc, new_mp, new_mem) = pg(pc) match {
@@ -193,10 +209,35 @@
}
-time_needed(1, run3(load_bff("benchmark.bf")))
+// testcases
+
+//optimise(load_bff("benchmark.bf")) // should have inserted 0's
+//optimise(load_bff("mandelbrot.bf")).length // => 11203
+
+//time_needed(1, run3(load_bff("benchmark.bf")))
+
-// (7)
+// (7) Write a function combine which replaces sequences
+// of repated increment and decrement commands by appropriate
+// two-character commands. For example for sequences of +
+//
+// orig bf-cmds | replacement
+// ------------------------------
+// + | +A
+// ++ | +B
+// +++ | +C
+// |
+// ... |
+// |
+// +++....+++ | +Z
+// (where length = 26)
+//
+// Similar for the bf-command -, > and <. All other commands should
+// be unaffected by this change.
+//
+// Adapt the compute4 and run4 functions such that they can deal
+// appropriately with such two-character commands.
def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
case (Nil, acc) => acc
@@ -215,8 +256,8 @@
spl(load_bff("benchmark.bf"))
-def combine(cs: List[(Char, Int)]) : String = {
- (for ((c, n) <- cs) yield c match {
+def combine(s: String) : String = {
+ (for ((c, n) <- spl(s)) yield c match {
case '>' => List('>', (n + '@').toChar)
case '<' => List('<', (n + '@').toChar)
case '+' => List('+', (n + '@').toChar)
@@ -226,8 +267,7 @@
}
-combine(spl(load_bff("benchmark.bf")))
-
+combine(load_bff("benchmark.bf"))
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
if (0 <= pc && pc < pg.length) {
@@ -251,13 +291,19 @@
}
def run4(pg: String, m: Mem = Map()) = {
- val pg_opt = combine(spl(optimise(pg)))
+ val pg_opt = combine(optimise(pg))
compute4(pg_opt, jtable(pg_opt), 0, 0, m)
}
+combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
+
//time_needed(1, run4(load_bff("benchmark.bf")))
+
+//time_needed(1, run(load_bff("sierpinski.bf")))
+//time_needed(1, run4(load_bff("sierpinski.bf")))
+
//time_needed(1, run4(load_bff("mandelbrot.bf")))
-}
+//}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates5/benchmark.bf Thu Dec 06 18:37:17 2018 +0000
@@ -0,0 +1,4 @@
+>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+++++++++[>++++++++++[>++++++++++[>++++++++++[>+
++++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.
\ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates5/bfc.scala Thu Dec 06 18:37:17 2018 +0000
@@ -0,0 +1,179 @@
+// Part 2 about a "Compiler" for the Brainf*** language
+//======================================================
+
+// !!! Copy any function you need from file bf.scala !!!
+//
+// If you need any auxiliary function, feel free to
+// implement it, but do not make any changes to the
+// templates below.
+
+def time_needed[T](n: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val end = System.nanoTime()
+ (end - start)/(n * 1.0e9)
+}
+
+type Mem = Map[Int, Int]
+
+import io.Source
+import scala.util._
+
+// !! COPY from your bf.scala !!
+
+// def load_bff(name: String) : String = ...
+
+// def sread(mem: Mem, mp: Int) : Int = ...
+
+// def write(mem: Mem, mp: Int, v: Int) : Mem = ...
+
+// def jumpRight(prog: String, pc: Int, level: Int) : Int = ...
+
+// def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...
+
+// def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+// def run(prog: String, m: Mem = Map()) =
+
+// The baseline to what we can compare our "compiler"
+// implemented below. It should require something like
+// 60 seconds for the calculation on my laptop
+//
+//time_needed(1, run(load_bff("benchmark.bf")))
+
+
+// DEBUGGING INFORMATION!!!
+//
+// Compiler, even real ones, are fiendishly difficult to get
+// to produce correct code. The point is that for example for
+// the Sierpinski program, they need to still generate code
+// that displays such a triangle. If yes, then one usually
+// can take comfort that all is well. If not, then something
+// went wrong during the optimisations.
+
+
+// ADVANCED TASKS
+//================
+
+// (5) Write a function jtable that precomputes the "jump
+// table" for a bf-program. This function takes a bf-program
+// as an argument and Returns a Map[Int, Int]. The
+// purpose of this map is to record the information
+// that given on the position pc is a '[' or a ']',
+// then to which pc-position do we need to jump next?
+//
+// For example for the program
+//
+// "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"
+//
+// we obtain the map
+//
+// Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+//
+// This states that for the '[' on position 5, we need to
+// jump to position 20, which is just after the corresponding ']'.
+// Similarly, for the ']' on position 19, we need to jump to
+// position 6, which is just after the '[' on position 5, and so
+// on. The idea is to not calculate this information each time
+// we hit a bracket, but just look up this information in the
+// jtable. You can use the jumpLeft and jumpRight functions
+// from Part 1 for calculating the jtable.
+//
+// Then adapt the compute and run functions from Part 1 in order
+// to take advantage of the information stored in the jtable.
+// This means whenever jumpLeft and jumpRight was called previously,
+// you should look up the jump address in the jtable.
+
+
+//def jtable(pg: String) : Map[Int, Int] = ...
+
+// testcase
+// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+
+
+//def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+//def run2(pg: String, m: Mem = Map()) = ...
+
+
+//testcase
+//time_needed(1, run2(load_bff("benchmark.bf")))
+
+
+
+// (6) Write a function optimise which deletes "dead code" (everything
+// that is not a bf-command) and also replaces substrings of the form
+// [-] by a new command 0. The idea is that the loop [-] just resets the
+// memory at the current location to 0. In the compute3 and run3 functions
+// below you implement this command by writing the number 0 to mem(mp),
+// that is write(mem, mp, 0).
+//
+// The easiest way to modify a string in this way is to use the regular
+// expression """[^<>+-.,\[\]]""", which recognises everything that is
+// not a bf-command and replace it by the empty string. Similarly the
+// regular expression """\[-\]""" finds all occurrences of [-] and
+// by using the Scala method .replaceAll you can replace it with the
+// string "0" standing for the new bf-command.
+
+//def optimise(s: String) : String = ...
+
+//def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+//def run3(pg: String, m: Mem = Map()) = ...
+
+
+// testcases
+
+//optimise(load_bff("benchmark.bf")) // should have inserted 0's
+//optimise(load_bff("mandelbrot.bf")).length // => 11203
+
+//time_needed(1, run3(load_bff("benchmark.bf")))
+
+
+
+// (7) Write a function combine which replaces sequences
+// of repeated increment and decrement commands by appropriate
+// two-character commands. For example for sequences of +
+//
+// orig bf-cmds | replacement
+// ------------------------------
+// + | +A
+// ++ | +B
+// +++ | +C
+// |
+// ... |
+// |
+// +++....+++ | +Z
+// (where length = 26)
+//
+// Similar for the bf-command -, > and <. All other commands should
+// be unaffected by this change.
+//
+// Adapt the compute4 and run4 functions such that they can deal
+// appropriately with such two-character commands.
+
+
+//def combine(s: String) : String = ...
+
+
+// testcase
+//combine(load_bff("benchmark.bf"))
+
+//def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+// should call first optimise and then combine on the input string
+//def run4(pg: String, m: Mem = Map()) = ...
+
+
+// testcases
+//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
+
+//time_needed(1, run4(load_bff("benchmark.bf")))
+
+//time_needed(1, run(load_bff("sierpinski.bf")))
+//time_needed(1, run4(load_bff("sierpinski.bf")))
+
+//time_needed(1, run4(load_bff("mandelbrot.bf")))
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates5/mandelbrot.bf Thu Dec 06 18:37:17 2018 +0000
@@ -0,0 +1,145 @@
+ A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
+<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
+>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
+>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
+>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
+>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
+[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
+<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
+>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
+-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
+<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
+[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
+>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
+<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
+>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
+<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
+<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
+>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
+<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
+[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
+<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
+]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
+<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
+<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
+>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
+[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
+<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
+]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
+-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
+<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
+[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
+[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
+<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
+<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
+<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
+<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
+]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
+[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
+<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
+<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
+[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
+[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
+<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
+>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
+>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
+>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
+<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
+<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
+<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
+>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
+[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
+[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
+>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
+>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
+]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
+<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
+>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
+<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
+<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
+<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
+<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
+<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
+]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
+>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
+->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
+>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
+<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
+]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
+>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
+<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
+>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
+>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
+>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
+]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
+<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
+>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
+->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
+>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
+[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
+<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
+<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
+<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
+>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
+<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
+>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
+<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
+<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
+<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
+<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
+<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
+<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
+<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
+>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
+<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
+>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
+>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
+>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
+<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
+>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
+<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
+<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
+<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
+-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
+>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
+<<<<<]]>>>]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates5/sierpinski.bf Thu Dec 06 18:37:17 2018 +0000
@@ -0,0 +1,3 @@
+++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+]>.>+[>>]>+]