pep-material: comparison solutions5/bfc.scala

equal deleted inserted replaced

-:0855c4478f27
+:38ea26f227af
 }
 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
-// The baseline to what we compare our "compiler";
+// The baseline to what we can compare our "compiler"
-// it requires something like 60 seconds on my laptop
+// 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 ']',
+//     that given on the position pc is a '[' or a ']',
-//     then to which pc-position do we need to jump?
+//     then to which pc-position do we need to jump next?
 //
 //     For example for the program
 //
 //       "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"
 //
 //
 //     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 to not calculate this information each time
+//     on. The idea is to not calculate this information each time
-//     we hit a bracket, but just loop uu this information in the
+//     we hit a bracket, but just look up this information in the
-//     jtable.
+//     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] =
 (0 until pg.length).collect { pc => pg(pc) match {
 case '[' => (pc -> jumpRight(pg, pc + 1, 0))
 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 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
+// below you implement this command by writing the number 0 to mem(mp),
-// write(mem, mp, 0).
+// 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 {
 case '0' => (pc + 1, mp, write(mem, mp, 0))
 val pg_opt = optimise(pg)
 compute3(pg_opt, jtable(pg_opt), 0, 0, m)
 }
-time_needed(1, run3(load_bff("benchmark.bf")))
+// testcases
+//optimise(load_bff("benchmark.bf"))          // should have inserted 0's
-// (7)
+//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)
 def spl(s: String) = splice(s.toList, Nil).reverse
 spl(load_bff("benchmark.bf"))
-def combine(cs: List[(Char, Int)]) : String = {
+def combine(s: String) : String = {
-(for ((c, n) <- cs) yield c match {
+(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(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) {
 val (new_pc, new_mp, new_mem) = pg(pc) match {
 case '0' => (pc + 1, mp, write(mem, mp, 0))
 }
 else mem
 }
 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")))
-}
+//}

changeset 233	38ea26f227af
parent 232	0855c4478f27
child 234	c51305a2217f