diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bfc.scala --- a/main_testing5/bfc.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bfc.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,6 +1,5 @@ -// Main Part 5 about a "Compiler" for the Brainf*** language -//============================================================ - +// Part 2 about a "Compiler" for the Brainf*** language +//====================================================== object M5b { @@ -11,15 +10,6 @@ // templates below. -// DEBUGGING INFORMATION FOR COMPILERS!!! -// -// Compiler, even real ones, are fiendishly difficult to get -// to produce correct code. One way to debug them is to run -// example programs ``unoptimised''; and then optimised. Does -// the optimised version still produce the same result? - - -// for timing purposes def time_needed[T](n: Int, code: => T) = { val start = System.nanoTime() for (i <- 0 until n) code @@ -27,154 +17,296 @@ (end - start)/(n * 1.0e9) } +type Mem = Map[Int, Int] -type Mem = Map[Int, Int] import io.Source import scala.util._ -// ADD YOUR CODE BELOW -//====================== +def load_bff(name: String) : String = + Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -// (6) +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 (pc >= prog.length) prog.length - else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1) - else if (prog(pc) == ']' && level == 0) pc + 1 - else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1) - else jumpRight(prog, pc + 1, level) + 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 jtable(pg: String) : Map[Int, Int] = { - val pairs = for { - i <- 0 until pg.length - if pg.charAt(i) == '[' - j = jumpRight(pg, i+1, 0) - } yield (i, j) - pairs.flatMap { case (i, j) => - List((i, j), (j-1, i+1)) - }.toMap -} - -def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) - -// 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 (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute2(pg, tb, npc, nmp, nmem) +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 run2(pg: String, m: Mem = Map()) = - compute2(pg, jtable(pg), 0, 0, m) - +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 '[' => 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 +} -// testcases -// time_needed(1, run2(load_bff("benchmark.bf"))) -// time_needed(1, run2(load_bff("sierpinski.bf"))) +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. -// (7) +// (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 optimise(s: String) : String = - s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0") +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 '[' => 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 (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute3(pg, tb, npc, nmp, nmem) - } + 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 '[' => 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 opt_pg = optimise(pg) - val jt = jtable(opt_pg) - compute3(opt_pg, jt, 0, 0, m) +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("mandelbrot.bf")).length // => 11203 -// optimise(load_bff("benchmark.bf")).length -// time_needed(1, run3(load_bff("benchmark.bf"))) + +//println(optimise(load_bff("collatz.bf"))) +//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"))) + -// (8) -def combine(s: String): String = ??? +// (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. -// testcase -// combine(load_bff("benchmark.bf")) +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 ('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 (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute3(pg, tb, npc, nmp, nmem) - } + 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 '[' => 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 } -// should call first optimise and then combine on the input string -// -def run4(pg: String, m: Mem = Map()) = { - val co_opt_pg = combine(optimise(pg)) - val jt = jtable(co_opt_pg) - compute3(co_opt_pg, jt, 0, 0, m) +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-A] """>A+B[A-A]