// Main Part 5 about a "Compiler" for the Brainf*** language+ −
//============================================================+ −
+ −
+ −
object M5b {+ −
+ −
// !!! 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+ −
val end = System.nanoTime()+ −
(end - start)/(n * 1.0e9)+ −
}+ −
+ −
+ −
type Mem = Map[Int, Int]+ −
+ −
import io.Source+ −
import scala.util._+ −
+ −
// ADD YOUR CODE BELOW+ −
//======================+ −
+ −
// (6) + −
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()) = ???+ −
+ −
// testcases+ −
// time_needed(1, run2(load_bff("benchmark.bf")))+ −
// time_needed(1, run2(load_bff("sierpinski.bf")))+ −
+ −
+ −
+ −
// (7) + −
+ −
def optimise(s: String) : String = ???+ −
+ −
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ???+ −
+ −
def run3(pg: String, m: Mem = Map()) = ???+ −
+ −
+ −
// 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")))+ −
+ −
+ −
+ −
// (8) + −
def combine(s: String) : String = ???+ −
+ −
// 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[[....."""+ −
+ −
// 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")))+ −
+ −
+ −
}+ −