diff -r 0855c4478f27 -r 38ea26f227af solutions5/bfc.scala --- 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-A]