// Part 2 about a "Compiler" for the Brainf*** language//======================================================object CW10b {// !!! 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.Sourceimport scala.util._def load_bff(name: String) : String = Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")def sread(mem: Mem, mp: Int) : Int = mem.getOrElse(mp, 0)def write(mem: Mem, mp: Int, v: Int) : Mem = mem.updated(mp, v)def jumpRight(prog: String, pc: Int, level: Int) : Int = { if (prog.length <= pc) pc else (prog(pc), level) match { case (']', 0) => pc + 1 case (']', l) => jumpRight(prog, pc + 1, l - 1) case ('[', l) => jumpRight(prog, pc + 1, l + 1) case (_, l) => jumpRight(prog, pc + 1, l) }}def jumpLeft(prog: String, pc: Int, level: Int) : Int = { if (pc < 0) pc else (prog(pc), level) match { case ('[', 0) => pc + 1 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) case (']', l) => jumpLeft(prog, pc - 1, l + 1) case (_, l) => jumpLeft(prog, pc - 1, l) }}def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { if (0 <= pc && pc < prog.length) { val (new_pc, new_mp, new_mem) = prog(pc) match { case '>' => (pc + 1, mp + 1, mem) case '<' => (pc + 1, mp - 1, mem) case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) case '[' => if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) case ']' => if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) case _ => (pc + 1, mp, mem) } compute(prog, new_pc, new_mp, new_mem) } else mem}def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)// 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 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] = (0 until pg.length).collect { pc => pg(pc) match { case '[' => (pc -> jumpRight(pg, pc + 1, 0)) case ']' => (pc -> jumpLeft(pg, pc - 1, 0)) }}.toMap// 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 = { if (0 <= pc && pc < pg.length) { val (new_pc, new_mp, new_mem) = pg(pc) match { case '>' => (pc + 1, mp + 1, mem) case '<' => (pc + 1, mp - 1, mem) case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case _ => (pc + 1, mp, mem) } compute2(pg, tb, new_pc, new_mp, new_mem) } else mem}def run2(pg: String, m: Mem = Map()) = compute2(pg, jtable(pg), 0, 0, m)//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 occurences of [-] and // by using the Scala method .replaceAll you can repplace it with the // 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 { case '0' => (pc + 1, mp, write(mem, mp, 0)) case '>' => (pc + 1, mp + 1, mem) case '<' => (pc + 1, mp - 1, mem) case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case _ => (pc + 1, mp, mem) } compute3(pg, tb, new_pc, new_mp, new_mem) } else mem}def run3(pg: String, m: Mem = Map()) = { val pg_opt = optimise(pg) compute3(pg_opt, jtable(pg_opt), 0, 0, m)}// testcases//optimise(load_bff("benchmark.bf")) // should have inserted 0's//optimise(load_bff("benchmark.bf")).length // => 181 //optimise(load_bff("mandelbrot.bf")).length // => 11203//time_needed(1, run3(load_bff("benchmark.bf")))// (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 case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc) case (']' :: cs, acc) => splice(cs, (']', 1) :: acc) case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc) case (',' :: cs, acc) => splice(cs, (',', 1) :: acc) case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc) case (c :: cs, Nil) => splice(cs, List((c, 1))) case (c :: cs, (d, n) :: acc) => if (c == d && n < 26) splice(cs, (c, n + 1) :: acc) else splice(cs, (c, 1) :: (d, n) :: acc)}def spl(s: String) = splice(s.toList, Nil).reverse//spl(load_bff("benchmark.bf"))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) case '-' => List('-', (n + '@').toChar) case _ => List(c) }).flatten.mkString}//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) { val (new_pc, new_mp, new_mem) = pg(pc) match { case '0' => (pc + 1, mp, write(mem, mp, 0)) case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem) case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem) case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@'))) case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@'))) case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) case _ => (pc + 1, mp, mem) } compute4(pg, tb, new_pc, new_mp, new_mem) } else mem}def run4(pg: String, m: Mem = Map()) = { val pg_opt = combine(optimise(pg)) compute4(pg_opt, jtable(pg_opt), 0, 0, m)}// testcases//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""//combine(optimise(load_bff("benchmark.bf"))).length // => 134//combine(optimise(load_bff("mandelbrot.bf"))).length // => 6509//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")))}