# HG changeset patch # User Christian Urban # Date 1572436262 0 # Node ID bd9d142d2cd8a2afe11d40a55ba4ecf69f9754c9 # Parent 9a04eb6a2291027fa986b3e3d412988f9adaab67 updated diff -r 9a04eb6a2291 -r bd9d142d2cd8 templates5/bf.scala --- a/templates5/bf.scala Wed Oct 30 11:28:44 2019 +0000 +++ b/templates5/bf.scala Wed Oct 30 11:51:02 2019 +0000 @@ -1,5 +1,9 @@ -// Part 1 about an Interpreter for the Brainf*** language -//======================================================== +// Core Part about an Interpreter for +// the Brainf*** language +//============================================== + + +object CW10a { // representation of Bf memory @@ -192,3 +196,4 @@ time_needed(1, run(b1)) */ +} diff -r 9a04eb6a2291 -r bd9d142d2cd8 templates5/bfc.scala --- 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-A] """>A+B[A-A]