diff -r c02929f2647c -r 6e1237691307 main_testing5/bfc.scala --- 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-A] 134 -//combine(optimise(load_bff("mandelbrot.bf"))).length // => 6509 +// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[A-A]