--- 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+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")))
-
-//println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
+//
+// optimise(load_bff("benchmark.bf")) // should have inserted 0's
+// optimise(load_bff("mandelbrot.bf")).length // => 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+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")))
}
-@main def main() = {
- import M5b._
- println(time_needed(1, run(load_bff("mandelbrot.bf"))))
- println(time_needed(1, run2(load_bff("mandelbrot.bf"))))
- println(time_needed(1, run3(load_bff("mandelbrot.bf"))))
- println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
-}
-