--- a/main_testing5/bfc.scala Mon Dec 07 01:25:41 2020 +0000
+++ b/main_testing5/bfc.scala Fri Jan 15 02:40:57 2021 +0000
@@ -1,15 +1,71 @@
-// 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.
+type Mem = Map[Int, Int]
+import io.Source
+import scala.util._
+
+def load_bff(name: String) : String =
+ Try(scala.io.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 + (mp -> v)
+
+def jumpRight(prog: String, pc: Int, level: Int) : Int = {
+ pc match {
+ case pc: Int if (pc >= 0 && pc < prog.length) => {
+ prog(pc) match {
+ case '[' => jumpRight(prog, pc + 1, level + 1)
+ case ']' => if (level == 0) pc + 1 else jumpRight(prog, pc + 1, level - 1)
+ case _ => jumpRight(prog, pc + 1, level)
+ }
+ }
+ case _ => pc
+ }
+}
+
+def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
+ pc match {
+ case pc: Int if (pc >= 0 && pc < prog.length) => {
+ prog(pc) match {
+ case '[' => if (level == 0) pc + 1 else jumpLeft(prog, pc - 1, level - 1)
+ case ']' => jumpLeft(prog, pc - 1, level + 1)
+ case _ => jumpLeft(prog, pc - 1, level)
+ }
+ }
+ case _ => pc
+ }
+}
+
+def get_position(prog: String, pc: Int, level: Int) : Int = {
+ prog(pc) match {
+ case '[' => jumpRight(prog, pc + 1, level)
+ case ']' => jumpLeft(prog, pc - 1, level)
+ case _ => println("Something went horrible wrong, I am sorry"); 0
+ }
+}
+
+// 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
@@ -17,89 +73,17 @@
(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 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.
-
-
+// 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
//
@@ -118,49 +102,54 @@
// 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.
+// for ((char, index) <- str.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(str, index, 0))
-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
+def jtable(pg: String) : Map[Int, Int] = {
+ val table = for ((char, index) <- pg.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(pg, index, 0))
+ table.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)
+ pc match {
+ case pc: Int if (pc >= 0 && pc < pg.length) => {
+ pg(pc) match {
+ case '>' => compute2(pg, tb, pc + 1, mp + 1, mem)
+ case '<' => compute2(pg, tb, pc + 1, mp - 1, mem)
+ case '+' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => print(sread(mem, mp).toChar); compute2(pg, tb, pc + 1, mp, mem)
+ case '[' => if (sread(mem, mp) == 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem)
+ case '*' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
+ case '@' => compute2(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
+ case '#' => print(sread(mem, mp)); compute2(pg, tb, pc + 1, mp, mem)
+ case _ => compute2(pg, tb, pc + 1, mp, mem)
+ }
+ }
+ case _ => mem
}
- else mem
+}
+
+def run2(pg: String, m: Mem = Map()) = {
+ compute2(pg, jtable(pg), 0, 0, m)
}
-def run2(pg: String, m: Mem = Map()) =
- compute2(pg, jtable(pg), 0, 0, m)
-
-//time_needed(1, run2(load_bff("benchmark.bf")))
+// testcases
+// time_needed(1, run2(load_bff("./main5/benchmark.bf")))
+// time_needed(1, run2(load_bff("./main5/sierpinski.bf")))
@@ -174,53 +163,61 @@
// 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
+// regular expression """\[-\]""" finds all occurrences of [-] and
+// by using the Scala method .replaceAll you can replace it with the
// string "0" standing for the new bf-command.
+// load_bff("./main5/mandelbrot.bf").replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")
-def optimise(s: String) : String =
- s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""", "0")
+// "Correct" regex
+// s.replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")
+// s.replaceAll("""[^<>+-.,\[\]]""", "").replaceAll("""\[-\]""", "0")
+def optimise(s: String) : String = {
+ //s.replaceAll("""[^<>+-.\[\]@#*]""","")
+ // .replaceAll("""\[-\]""", "0")
+ 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)
+ pc match {
+ case pc: Int if (pc >= 0 && pc < pg.length) => {
+ pg(pc) match {
+ case '>' => compute3(pg, tb, pc + 1, mp + 1, mem)
+ case '<' => compute3(pg, tb, pc + 1, mp - 1, mem)
+ case '+' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => print(sread(mem, mp).toChar); compute3(pg, tb, pc + 1, mp, mem)
+ case '[' => if (sread(mem, mp) == 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem)
+ case '*' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
+ case '@' => compute3(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
+ case '#' => print(sread(mem, mp)); compute3(pg, tb, pc + 1, mp, mem)
+ case '0' => compute3(pg, tb, pc + 1, mp, write(mem, mp, 0))
+ case _ => compute3(pg, tb, pc + 1, mp, mem)
+ }
+ }
+ case _ => mem
}
- else mem
}
-def run3(pg: String, m: Mem = Map()) = {
- val pg_opt = optimise(pg)
- compute3(pg_opt, jtable(pg_opt), 0, 0, m)
+def run3(pg: String, m: Mem = Map()) = {
+ val optimised = optimise(pg)
+ compute3(optimised, jtable(optimised), 0, 0, m)
}
// testcases
-
-//optimise(load_bff("benchmark.bf")) // should have inserted 0's
-//optimise(load_bff("benchmark.bf")).length // => 181
-//optimise(load_bff("mandelbrot.bf")).length // => 11203
-
-//time_needed(1, run3(load_bff("benchmark.bf")))
+//
+// optimise(load_bff("./main5/benchmark.bf")) // should have inserted 0's
+// optimise(load_bff("./main5/mandelbrot.bf")).length // => 11205
+//
+// time_needed(1, run3(load_bff("./main5/benchmark.bf")))
+// time_needed(1, run3(load_bff("./main5/mandelbrot.bf")))
// (7) Write a function combine which replaces sequences
-// of repated increment and decrement commands by appropriate
+// of repeated increment and decrement commands by appropriate
// two-character commands. For example for sequences of +
//
// orig bf-cmds | replacement
@@ -240,73 +237,82 @@
// Adapt the compute4 and run4 functions such that they can deal
// appropriately with such two-character commands.
-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)
+// val alphabet = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"
+val alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+
+// Try any alphabet, it will work as long as the character is recognised and the characters are unique
+
+def get_number_from_character(char: Char) : Int = {
+ alphabet.indexOf(char) + 1
+}
+
+def get_character_from_number(int: Int) : Char = {
+ alphabet(int - 1)
+}
+
+@annotation.tailrec
+def split_by_repetition(string : String, list : List[String] = Nil) : List[String] = {
+ if(string.size == 0) list.reverse
+ else {
+ val (left_substring, right_substring) = string.span(_ == string(0))
+ split_by_repetition(right_substring, left_substring :: list)
+ }
}
-def spl(s: String) = splice(s.toList, Nil).reverse
+def combine(s: String) : String = {
+ val split_strings = split_by_repetition(s)
+ val lists = for (string <- split_strings) yield {
+ if (List("+"(0), "-"(0), "<"(0), ">"(0)).contains(string.head)) {
+ val long_repeat = s"${string.head}${alphabet.last}" * (string.size / alphabet.length)
+ val short_repeat = if ((string.size % alphabet.length) != 0) s"${string.head}${get_character_from_number(string.size % alphabet.length)}" else ""
+ long_repeat + short_repeat
+ } else string
+ }
+ lists.mkString("")
+}
-//spl(load_bff("benchmark.bf"))
+// testcase
+// combine(load_bff("./main5/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
+def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
+ pc match {
+ case pc: Int if (pc >= 0 && pc < pg.length) => {
+ pg(pc) match {
+ case '>' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp + number, mem)
+ case '<' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp - number, mem)
+ case '+' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) + number))
+ case '-' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) - number))
+ case '.' => print(sread(mem, mp).toChar); compute4(pg, tb, pc + 1, mp, mem)
+ case '[' => if (sread(mem, mp) == 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem)
+ case ']' => if (sread(mem, mp) != 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem)
+ case '*' => compute4(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
+ case '@' => compute4(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
+ case '#' => print(sread(mem, mp)); compute4(pg, tb, pc + 1, mp, mem)
+ case '0' => compute4(pg, tb, pc + 1, mp, write(mem, mp, 0))
+ case _ => compute4(pg, tb, pc + 1, mp, mem)
+ }
+ }
+ case _ => mem
+ }
}
-//combine(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
+// should call first optimise and then combine on the input string
+//
+def run4(pg: String, m: Mem = Map()) = {
+ val processed_prog = combine(optimise(pg))
+ compute4(processed_prog, jtable(processed_prog), 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[[....."""
-//combine(optimise(load_bff("benchmark.bf"))).length // => 134
-//combine(optimise(load_bff("mandelbrot.bf"))).length // => 6509
+// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-//time_needed(1, run4(load_bff("benchmark.bf")))
-
-//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("./main5/benchmark.bf")))
+// time_needed(1, run4(load_bff("./main5/sierpinski.bf")))
+// time_needed(1, run4(load_bff("./main5/mandelbrot.bf")))
}