# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1544112491 0
# Node ID 0855c4478f27e2e7b6675f607fb99b1dd357fb9c
# Parent  eecbc9ae73c23fcd1431dd03fba25e15f2b8355e
updated

diff -r eecbc9ae73c2 -r 0855c4478f27 solutions5/bfc.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solutions5/bfc.scala	Thu Dec 06 16:08:11 2018 +0000
@@ -0,0 +1,263 @@
+// Part 2 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.
+
+
+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._
+
+def load_bff(name: String) : String = 
+  Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
+
+def sread(mem: Mem, mp: Int) : Int = 
+  mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+  mem.updated(mp, v)
+
+def jumpRight(prog: String, pc: Int, level: Int) : Int = {
+  if (prog.length <= pc) pc 
+  else (prog(pc), level) match {
+    case (']', 0) => pc + 1
+    case (']', l) => jumpRight(prog, pc + 1, l - 1)
+    case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+    case (_, l) => jumpRight(prog, pc + 1, l)
+  }
+}
+
+def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
+  if (pc < 0) pc 
+  else (prog(pc), level) match {
+    case ('[', 0) => pc + 1
+    case ('[', l) => jumpLeft(prog, pc - 1, l - 1)
+    case (']', l) => jumpLeft(prog, pc - 1, l + 1)
+    case (_, l) => jumpLeft(prog, pc - 1, l)
+  }
+}
+
+def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
+  if (0 <= pc && pc < prog.length) { 
+    val (new_pc, new_mp, new_mem) = prog(pc) match {
+      case '>' => (pc + 1, mp + 1, mem)
+      case '<' => (pc + 1, mp - 1, mem)
+      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+      case '['  => 
+	if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) 
+      case ']'  => 
+	if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) 
+      case _ => (pc + 1, mp, mem)
+    }		     
+    compute(prog, new_pc, new_mp, new_mem)	
+  }
+  else mem
+}
+
+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
+//
+//time_needed(1, run(load_bff("benchmark.bf")))
+
+
+
+
+// (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?
+// 
+//     For example for the program
+//    
+//       "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"
+//
+//     we obtain the map
+//
+//       Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+//  
+//     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
+//     we hit a bracket, but just loop uu this information in the 
+//     jtable.
+//
+//     Adapt the compute and run functions from Part 1 in order to
+//     take advantage of the information 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))
+      case ']' => (pc -> jumpLeft(pg, pc - 1, 0))
+    }}.toMap
+
+
+// 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 = {
+  if (0 <= pc && pc < pg.length) { 
+    val (new_pc, new_mp, new_mem) = pg(pc) match {
+      case '>' => (pc + 1, mp + 1, mem)
+      case '<' => (pc + 1, mp - 1, mem)
+      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+      case '['  => 
+	if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case ']'  => 
+	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case _ => (pc + 1, mp, mem)
+    }		     
+    compute2(pg, tb, new_pc, new_mp, new_mem)	
+  }
+  else mem
+}
+
+
+def run2(pg: String, m: Mem = Map()) = 
+  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
+// 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). 
+//
+// The easiest way to modify a string in this way is to use the regular
+// expression """[^<>+-.,\[\]]""", whcih 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.
+
+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))
+      case '>' => (pc + 1, mp + 1, mem)
+      case '<' => (pc + 1, mp - 1, mem)
+      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+      case '['  => 
+	if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case ']'  => 
+	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case _ => (pc + 1, mp, mem)
+    }		     
+    compute3(pg, tb, new_pc, new_mp, new_mem)	
+  }
+  else mem
+}
+
+def run3(pg: String, m: Mem = Map()) = { 
+  val pg_opt = optimise(pg)
+  compute3(pg_opt, jtable(pg_opt), 0, 0, m)
+}
+
+
+time_needed(1, run3(load_bff("benchmark.bf")))
+
+
+// (7) 
+
+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)
+  case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc)
+  case (',' :: cs, acc) => splice(cs, (',', 1) :: acc)
+  case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc)
+  case (c :: cs, Nil) => splice(cs, List((c, 1)))
+  case (c :: cs, (d, n) :: acc) => 
+    if (c == d && n < 26) splice(cs, (c, n + 1) :: acc)
+    else splice(cs, (c, 1) :: (d, n) :: acc)
+}
+
+def spl(s: String) = splice(s.toList, Nil).reverse
+
+spl(load_bff("benchmark.bf"))
+
+def combine(cs: List[(Char, Int)]) : String = {
+  (for ((c, n) <- cs) 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")))
+
+
+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))
+      case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem)
+      case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem)
+      case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@')))
+      case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@')))
+      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+      case '['  => 
+	if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case ']'  => 
+	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 
+      case _ => (pc + 1, mp, mem)
+    }		     
+    compute4(pg, tb, new_pc, new_mp, new_mem)	
+  }
+  else mem
+}
+
+def run4(pg: String, m: Mem = Map()) = { 
+  val pg_opt = combine(spl(optimise(pg)))
+  compute4(pg_opt, jtable(pg_opt), 0, 0, m)
+}
+
+
+//time_needed(1, run4(load_bff("benchmark.bf")))
+//time_needed(1, run4(load_bff("mandelbrot.bf")))
+
+
+}