--- a/main_testing5/bfc.scala Thu Nov 02 13:53:37 2023 +0000
+++ b/main_testing5/bfc.scala Thu Nov 02 23:34:53 2023 +0000
@@ -1,6 +1,5 @@
-// Main Part 5 about a "Compiler" for the Brainf*** language
-//============================================================
-
+// Part 2 about a "Compiler" for the Brainf*** language
+//======================================================
object M5b {
@@ -11,15 +10,6 @@
// 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
@@ -27,154 +17,296 @@
(end - start)/(n * 1.0e9)
}
+type Mem = Map[Int, Int]
-type Mem = Map[Int, Int]
import io.Source
import scala.util._
-// ADD YOUR CODE BELOW
-//======================
+def load_bff(name: String) : String =
+ Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
-// (6)
+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 (pc >= prog.length) prog.length
- else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1)
- else if (prog(pc) == ']' && level == 0) pc + 1
- else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1)
- else jumpRight(prog, pc + 1, level)
+ 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 jtable(pg: String) : Map[Int, Int] = {
- val pairs = for {
- i <- 0 until pg.length
- if pg.charAt(i) == '['
- j = jumpRight(pg, i+1, 0)
- } yield (i, j)
- pairs.flatMap { case (i, j) =>
- List((i, j), (j-1, i+1))
- }.toMap
-}
-
-def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v)
-
-// 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 (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute2(pg, tb, npc, nmp, nmem)
+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 run2(pg: String, m: Mem = Map()) =
- compute2(pg, jtable(pg), 0, 0, m)
-
+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 '[' => 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
+}
-// testcases
-// time_needed(1, run2(load_bff("benchmark.bf")))
-// time_needed(1, run2(load_bff("sierpinski.bf")))
+def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
+
+
+// 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 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.
-// (7)
+// (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?
+//
+// 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 is to not calculate this information each time
+// we hit a bracket, but just look up this information in the
+// 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.
+// 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))
+ case ']' => (pc -> jumpLeft(pg, pc - 1, 0))
+ }}.toMap
+
+
+// testcase
+// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
+
-def optimise(s: String) : String =
- s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0")
+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 '[' => 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 loop [-] just resets the
+// memory at the current location to 0. In the compute3 and run3 functions
+// below you implement this command by writing the number 0 to mem(mp),
+// that is write(mem, mp, 0).
+//
+// The easiest way to modify a string in this way is to use the regular
+// 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-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 (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute3(pg, tb, npc, nmp, nmem)
- }
+ 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 '[' => 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 opt_pg = optimise(pg)
- val jt = jtable(opt_pg)
- compute3(opt_pg, jt, 0, 0, m)
+def run3(pg: String, m: Mem = Map()) = {
+ val pg_opt = optimise(pg)
+ compute3(pg_opt, jtable(pg_opt), 0, 0, m)
}
// testcases
-//
-// optimise(load_bff("benchmark.bf")) // should have inserted 0's
-// optimise(load_bff("mandelbrot.bf")).length // => 11203
-// optimise(load_bff("benchmark.bf")).length
-// time_needed(1, run3(load_bff("benchmark.bf")))
+
+//println(optimise(load_bff("collatz.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")))
+
-// (8)
-def combine(s: String): String = ???
+// (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.
-// testcase
-// combine(load_bff("benchmark.bf"))
+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 ('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(s: String) : String = {
+ (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(load_bff("benchmark.bf"))
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
- if (pc >= pg.length) mem
- else {
- val (npc, nmp, nmem) = pg(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
- case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
- case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
- case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- compute3(pg, tb, npc, nmp, nmem)
- }
+ 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 '[' => 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
}
-// should call first optimise and then combine on the input string
-//
-def run4(pg: String, m: Mem = Map()) = {
- val co_opt_pg = combine(optimise(pg))
- val jt = jtable(co_opt_pg)
- compute3(co_opt_pg, jt, 0, 0, m)
+def run4(pg: String, m: Mem = Map()) = {
+ val pg_opt = combine(optimise(pg))
+ compute4(pg_opt, jtable(pg_opt), 0, 0, m)
}
// testcases
-// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
+//println(combine(optimise(load_bff("mandelbrot.bf").drop(123))))
+
+//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")))
+//time_needed(1, run4(load_bff("benchmark.bf")))
+//time_needed(1, run(load_bff("sierpinski.bf")))
+//time_needed(1, run4(load_bff("sierpinski.bf")))
-}
+//println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
-// This template code is subject to copyright
-// by King's College London, 2022. Do not
-// make the template code public in any shape
-// or form, and do not exchange it with other
-// students under any circumstance.
+}
+
+/*
+import CW10b._
+println(time_needed(1, run(load_bff("collatz.bf"))))
+println(time_needed(1, run2(load_bff("collatz.bf"))))
+println(time_needed(1, run3(load_bff("collatz.bf"))))
+println(time_needed(1, run4(load_bff("collatz.bf"))))
+*/