--- a/templates5/bfc.scala Wed Oct 30 11:28:44 2019 +0000
+++ b/templates5/bfc.scala Wed Oct 30 11:51:02 2019 +0000
@@ -1,12 +1,26 @@
-// Part 2 about a "Compiler" for the Brainf*** language
+// Core Part 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.
+
+// 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
@@ -14,53 +28,22 @@
(end - start)/(n * 1.0e9)
}
+
type Mem = Map[Int, Int]
import io.Source
import scala.util._
-// !! COPY from your bf.scala !!
-// def load_bff(name: String) : String = ...
-
-// def sread(mem: Mem, mp: Int) : Int = ...
-
-// def write(mem: Mem, mp: Int, v: Int) : Mem = ...
-
-// def jumpRight(prog: String, pc: Int, level: Int) : Int = ...
-
-// def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...
-
-// def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...
-
-// def run(prog: String, m: Mem = Map()) =
-
-// 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 fiendishly difficult to get
-// to produce 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.
-
-
-// ADVANCED TASKS
-//================
+// TASKS
+//=======
// (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?
+// purpose of this map is to record the information about
+// pc positions where '[' or a ']' are stored. The information
+// is to which pc-position do we need to jump next?
//
// For example for the program
//
@@ -79,26 +62,28 @@
// 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.
+// 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.
+// you should immediately look up the jump address in the jtable.
//def jtable(pg: String) : Map[Int, Int] = ...
+
// 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 = ...
-
//def run2(pg: String, m: Mem = Map()) = ...
-//testcase
-//time_needed(1, run2(load_bff("benchmark.bf")))
+// testcases
+// time_needed(1, run2(load_bff("benchmark.bf")))
+// time_needed(1, run2(load_bff("seirpinski.bf")))
@@ -124,11 +109,11 @@
// 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")))
+//
+// 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")))
@@ -156,24 +141,25 @@
//def combine(s: String) : String = ...
+// testcase
+// combine(load_bff("benchmark.bf"))
-// testcase
-//combine(load_bff("benchmark.bf"))
//def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ...
+
// should call first optimise and then combine on the input string
+//
//def run4(pg: String, m: Mem = Map()) = ...
// testcases
-//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-
-//time_needed(1, run4(load_bff("benchmark.bf")))
+// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-//time_needed(1, run(load_bff("sierpinski.bf")))
-//time_needed(1, run4(load_bff("sierpinski.bf")))
-
-//time_needed(1, run4(load_bff("mandelbrot.bf")))
+// testcases (they should now run much faster)
+// time_needed(1, run4(load_bff("benchmark.bf")))
+// time_needed(1, run4(load_bff("sierpinski.bf")))
+// time_needed(1, run4(load_bff("mandelbrot.bf")))
+}