--- 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")))
-}
+//}