diff -r 244df77507c2 -r 253d1ccb65de main_solution5/bfc.scala --- a/main_solution5/bfc.scala Sun Sep 15 12:57:59 2024 +0100 +++ b/main_solution5/bfc.scala Mon Jul 21 16:38:07 2025 +0100 @@ -1,5 +1,6 @@ -// Part 2 about a "Compiler" for the Brainf*** language -//====================================================== +// Main Part 5 about a "Compiler" for the Brainf*** language +//============================================================ + object M5b { @@ -10,306 +11,324 @@ // templates below. -def time_needed[T](n: Int, code: => T) = { +// 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._ -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) +// ADD YOUR CODE BELOW +//====================== -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 = -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 -} + if(pc<0 || pc>= prog.length()) + mem + else + prog.charAt(pc) match + case '>' => compute(prog, pc+1, mp+1, 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"))) - + case '<' => compute(prog, pc+1, mp-1, mem) + case '+' => compute(prog, pc+1, mp, write(mem, mp, sread(mem, mp)+1)) -// 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. + case '-' => compute(prog, pc+1, mp, write(mem, mp, sread(mem, mp)-1)) - - -// (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. - + case '.' => + compute(prog, pc+1, mp, mem) -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) - + case '[' => + if(sread(mem, mp) == 0) + compute(prog, jumpRight(prog, pc+1, 0), mp, mem) + else + compute(prog, pc+1, mp, mem) -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 -} + case ']' => + if(sread(mem, mp) == 0) + compute(prog, pc+1, mp, mem) + else + compute(prog, jumpLeft(prog, pc-1, 0), mp, mem) - -def run2(pg: String, m: Mem = Map()) = - compute2(pg, jtable(pg), 0, 0, m) - -//time_needed(1, run2(load_bff("benchmark.bf"))) + case _ => compute(prog, pc + 1, mp, mem) -// (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 run(prog: String, m: Mem = Map()) = + compute(prog, 0, 0, m) + + +// (6) +def jumpRight(prog: String, pc: Int, level: Int) : Int = + if (pc<0 || pc>= prog.length() ) + pc + else + 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) + -def optimise(s: String) : String = { - s.replaceAll("""[^<>+-.\[\]]""","") - .replaceAll("""\[-\]""", "0") -} +def jumpLeft(prog: String, pc: Int, level: Int) : Int = + if (pc<0 || pc>= prog.length() ) + pc + else + 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) + + +def jtable(pg: String) : Map[Int, Int] = + val b1 = (0 until pg.length) + .filter(n => pg.substring(n, n+1) == "[") + .map(n => n -> jumpRight(pg, n + 1, 0)).toMap + + val b2 = (0 until pg.length) + .filter(n => pg.substring(n, n+1) == "]") + .map(n => n -> jumpLeft(pg, n-1, 0)).toMap + + b1++b2 -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 '[' => 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 -} +// testcase +// +// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") +// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) + +def load_bff(name: String) : String = + try + Source.fromFile(name).mkString + catch + case e: Exception => "" + +def sread(mem: Mem, mp: Int) : Int = + mem.getOrElse(mp,0) + +def write(mem: Mem, mp: Int, v: Int) : Mem = + mem + (mp -> v) + +def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = + + if(pc<0 || pc>= pg.length()) + mem + else + pg.charAt(pc) match + case '>' => compute2(pg,tb, pc+1, mp+1, mem) -def run3(pg: String, m: Mem = Map()) = { - val pg_opt = optimise(pg) - compute3(pg_opt, jtable(pg_opt), 0, 0, m) -} + 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 '.' => + 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, pc+1, mp, mem) + else + compute2(pg, tb, tb(pc), mp, mem) + + case _ => compute2(pg,tb,pc + 1, mp, mem) + +def run2(pg: String, m: Mem = Map()) = + compute2(pg, jtable(pg), 0, 0, m) // testcases - -//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"))) -//time_needed(1, run3(load_bff("mandelbrot.bf"))) +// time_needed(1, run2(load_bff("benchmark.bf"))) +// time_needed(1, run2(load_bff("sierpinski.bf"))) -// (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. +// (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 ('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 optimise(s: String) : String = + val notCommand = """[^<>+\-.\[\]]""".r + val occurrence = """\[-\]""".r -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 -} + val deleted = notCommand.replaceAllIn(s, "") + occurrence.replaceAllIn(deleted, "0") -//combine(load_bff("benchmark.bf")) +def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = + + if(pc<0 || pc>= pg.length()) + mem + else + pg.charAt(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 '.' => + compute3(pg,tb, pc+1, mp, mem) -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 '[' => 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 -} + case '[' => + if(sread(mem, mp) == 0) + compute3(pg, tb, tb(pc), mp, mem) + else + compute3(pg, tb, pc+1, mp, mem) -def run4(pg: String, m: Mem = Map()) = { - val pg_opt = combine(optimise(pg)) - compute4(pg_opt, jtable(pg_opt), 0, 0, m) -} + case ']' => + if(sread(mem, mp) == 0) + compute3(pg, tb, pc+1, mp, mem) + else + compute3(pg, tb, tb(pc), mp, mem) + + case _ => compute3(pg,tb,pc + 1, mp, mem) + +def run3(pg: String, m: Mem = Map()) = + val opt = optimise(pg) + compute3(opt, jtable(opt), 0, 0, m) + + // testcases -//println(combine(optimise(load_bff("mandelbrot.bf").drop(123)))) - -//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[A-A] 11205 +// +// time_needed(1, run3(load_bff("benchmark.bf"))) +// (8) +// consider if the char does not exist\\ + +def counterHelper(chars: List[Char], consec: Int, charToCount: Char): Int = + chars match + case head :: tail if ((head == charToCount && head == tail.headOption.getOrElse(' ')) )=> + counterHelper(tail, consec + 1, charToCount) + + case head :: tail if (head == charToCount && head != tail.headOption.getOrElse(' '))=> + consec+1 + + case head :: tail if (head != charToCount && head != tail.headOption.getOrElse(' '))=> + consec + + +def counter(input: String, charToCount: Char): Int = + counterHelper(input.toList, 0, charToCount) + +def handleCharacter(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char], charToCount: Char): String = + val num = counter(orgin.substring(sindex), charToCount) + val lett = letterMap.getOrElse(num, "") + combineHelper(orgin, newstr + charToCount + lett, sindex + num, letterMap) + +def combineHelper(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char] ): String = + if (sindex >= orgin.length()) + newstr + else + val result = + orgin.charAt(sindex) match + case '>' => handleCharacter(orgin, newstr, sindex, letterMap, '>') + case '<' => handleCharacter(orgin, newstr, sindex, letterMap, '<') + case '+' => handleCharacter(orgin, newstr, sindex, letterMap, '+') + case '-' => handleCharacter(orgin, newstr, sindex, letterMap, '-') + case _ => combineHelper(orgin, newstr + orgin.charAt(sindex), sindex + 1, letterMap) + + result + +def combine(s: String) : String = + val letterMap = (1 to 26).zip('A' to 'Z').toMap + combineHelper(s,"",0, letterMap) + +// testcase +// combine(load_bff("benchmark.bf")) + +def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = + + if(pc<0 || pc>= pg.length()) + mem + else + pg.charAt(pc) match + case '>' => compute4(pg,tb, pc+1, mp+1, mem) + + case '<' => compute4(pg,tb, pc+1, mp-1, mem) + + case '+' => compute4(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)+1)) + + case '-' => compute4(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)-1)) + + case '.' => + 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, pc+1, mp, mem) + else + compute4(pg, tb, tb(pc), mp, mem) + + case _ => compute4(pg,tb,pc + 1, mp, mem) + +// should call first optimise and then combine on the input string +// +def run4(pg: String, m: Mem = Map()) = + val opt = optimise(pg) + val com= combine(opt) + compute4(com, jtable(com), 0, 0, m) + + +// testcases +// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[A-A]