--- a/main_testing5/bf.scala Mon Nov 08 01:39:00 2021 +0000
+++ b/main_testing5/bf.scala Mon Nov 08 01:49:28 2021 +0000
@@ -1,248 +1,211 @@
-// Core Part about an Interpreter for
-// the Brainf***++ language
-//==============================================
-
-
-object CW10a {
-
-
-// representation of Bf memory
-
-type Mem = Map[Int, Int]
-
-
-// (1) Write a function that takes a file name as argument and
-// and requests the corresponding file from disk. It Returns the
-// content of the file as a String. If the file does not exists,
-// the function should Return the empty string.
-
-import io.Source
-import scala.util._
-import java.io.FileNotFoundException
-import scala.annotation.tailrec
-
-def load_bff(name: String) : String = {
- try {
- val bff = io.Source.fromFile(name).getLines().mkString(" ")
- bff
- }
- catch {
- case ex: FileNotFoundException =>
- val bff = ""
- bff
- }
-}
-
-
-
-// (2) Complete the functions for safely reading
-// and writing brainf***++ memory. Safely read should
-// Return the value stored in the Map for a given memory
-// pointer, provided it exists; otherwise it Returns 0. The
-// writing function generates a new Map with the
-// same data, except at the given memory pointer the
-// value v is stored.
-
-
-def sread(mem: Mem, mp: Int) : Int = {
- mem.getOrElse(mp,0)
-}
-
-def write(mem: Mem, mp: Int, v: Int) : Mem = {
- val newMem = mem + (mp -> v)
- newMem
-}
-
-
-
-// (3) Implement the two jumping instructions in the
-// brainf***++ language. In jumpRight, given a program and
-// a program counter move the program counter to the right
-// until after the *matching* ]-command. Similarly,
-// jumpLeft implements the move to the left to just after
-// the *matching* [-command.
-@tailrec
-def jumpRight(prog: String, pc: Int, level: Int) : Int = {
- if (pc > prog.length-1) 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)
- }
- }
-}
-@tailrec
-def jumpLeft(prog: String, pc: Int, level: Int) : Int = {
- if (pc < 0) pc
- else {
- prog(pc) match{
- case ']' => jumpLeft(prog, pc-1, level+1)
- case '[' => if (level == 0) pc+1
- else jumpLeft(prog, pc-1, level-1)
- case _ => jumpLeft(prog, pc-1, level)
- }
- }
-}
-
-
-// testcases
-//jumpRight("""--[..+>--],>,++""", 3, 0) // => 10
-//jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3
-// jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12
-// jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18
-//jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside)
-//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
-
-
-
-// (4) Complete the compute function that interprets (runs) a brainf***++
-// program: the arguments are a program (represented as a string), a program
-// counter, a memory counter and a brainf***++ memory. It Returns the
-// memory at the stage when the execution of the brainf***++ program
-// finishes. The interpretation finishes once the program counter
-// pc is pointing to something outside the program string.
-// If the pc points to a character inside the program, the pc,
-// memory pointer and memory need to be updated according to
-// rules of the brainf***++ language. Then, recursively, the compute
-// function continues with the command at the new program
-// counter.
-//
-// Implement the run function that calls compute with the program
-// counter and memory counter set to 0.
-
-@tailrec
-def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
- if (pc > prog.length-1) mem
- else {
- prog(pc) match{
- case '>' => compute(prog, pc+1, mp+1, mem)
- case '<' => compute(prog, pc+1, mp-1, mem)
- case '+' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)+1))
- case '-' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)-1))
- case '.' => print(sread(mem,mp).toChar)
- compute(prog, pc+1, mp, mem)
- case '[' => if (sread(mem,mp) == 0) compute(prog,jumpRight(prog,pc+1,0),mp,mem)
- else compute(prog,pc+1,mp,mem)
- case ']' => if (sread(mem,mp) != 0) compute(prog,jumpLeft(prog,pc-1,0),mp,mem)
- else compute(prog,pc+1,mp,mem)
- case '*' => compute(prog, pc+1,mp, write(mem,mp,sread(mem,mp)*sread(mem,mp-1)))
- case '@' => compute(prog,pc+1,mp, write(mem,sread(mem,mp),sread(mem,mp-1)))
- case '#' => print(sread(mem,mp))
- compute(prog,pc+1, mp, mem)
- case _ => compute(prog,pc+1,mp,mem)
- }
- }
-}
-
-def run(prog: String, m: Mem = Map()) : Mem = {
- compute(prog, 0, 0, m)
-}
-
-
-
-// some sample bf/bf++-programs collected from the Internet
-//==========================================================
-
-
-// some contrived (small) programs
-//---------------------------------
-
-// clears the 0-cell
-//run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
-
-// moves content of the 0-cell to 1-cell
-//run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
-
-
-// copies content of the 0-cell to 2-cell and 4-cell
-//run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42)
-
-
-// prints out numbers 0 to 9
-//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
-
-// bf++ program calculating the cube-function, 10 * 10 * 10 = 1000
-//run("""++++++++++#>+***#""") // Map(0 -> 10, 1 -> 1000)
-
-
-// bf++ program copies 3 from 0-cell to to cells 1, 4, 5, 6 and 7
-// (note that because of how the program wprks cell 1 will contain 7)
-//run("""+++>+@+@+@+@+@""") // Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3)
-
-
-
-// some more "useful" programs
-//-----------------------------
-
-// hello world program 1
-// run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
-// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
-
-// hello world program 2
-// run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
-// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
-
-// hello world program 3
-// run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..
-// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""")
-
-
-// draws the Sierpinski triangle
-//run(load_bff("sierpinski.bf"))
-
-
-//fibonacci numbers below 100
-// run("""+++++++++++
-// >+>>>>++++++++++++++++++++++++++++++++++++++++++++
-// >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
-// +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
-// <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
-// -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
-// >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
-// +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
-// ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
-// <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
-// [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
-
-//outputs the square numbers up to 10000
-// run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
-// >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
-// <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
-
-
-// calculates 2 to the power of 6
-//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it)
-// run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-]
-// <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]
-// <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+>
-// +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
-// <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-]
-// >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-]
-// <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]>
-// [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+>
-// >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<>
-// <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]>
-// [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+
-// >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<
-// ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++
-// ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""")
-
-
-
-// a Mandelbrot set generator in brainf*** written by Erik Bosman
-// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
-//
-//run(load_bff("mandelbrot.bf"))
-
-
-// a benchmark program (counts down from 'Z' to 'A')
-//
-//run(load_bff("benchmark.bf"))
-
-// calculates the Collatz series for numbers from 1 to 30
-//
-//run(load_bff("collatz.bf"))
-
-}
+// Core Part about an Interpreter for
+// the Brainf***++ language
+//==============================================
+
+object M5a {
+
+
+// representation of Bf memory
+
+type Mem = Map[Int, Int]
+
+
+// (1) Write a function that takes a file name as argument and
+// and requests the corresponding file from disk. It Returns the
+// content of the file as a String. If the file does not exists,
+// the function should Return the empty string.
+
+import io.Source
+import scala.util._
+
+def load_bff(name: String) : String =
+ Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
+
+
+// (2) Complete the functions for safely reading
+// and writing brainf***++ memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, provided it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
+
+
+def sread(mem: Mem, mp: Int) : Int =
+ mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+ mem.updated(mp, v)
+
+
+// (3) Implement the two jumping instructions in the
+// brainf***++ language. In jumpRight, given a program and
+// a program counter move the program counter to the right
+// until after the *matching* ]-command. Similarly,
+// jumpLeft implements the move to the left to just after
+// the *matching* [-command.
+
+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)
+ }
+}
+
+// test cases
+//jumpRight("""--[..+>--].>.++""", 3, 0) // => 10
+//jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3
+//jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12
+//jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18
+//jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside)
+//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
+
+// (4) Complete the compute function that interprets (runs) a brainf***++
+// program: the arguments are a program (represented as a string), a program
+// counter, a memory counter and a brainf***++ memory. It Returns the
+// memory at the stage when the execution of the brainf***++ program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc,
+// memory pointer and memory need to be updated according to
+// rules of the brainf***++ language. Then, recursively, the compute
+// function continues with the command at the new program
+// counter.
+//
+// Implement the run function that calls compute with the program
+// counter and memory counter set to 0.
+
+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
+}
+
+def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)
+
+
+
+
+
+// some sample bf/bf++-programs collected from the Internet
+//==========================================================
+
+
+// some contrived (small) programs
+//---------------------------------
+
+// clears the 0-cell
+//run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
+
+// moves content of the 0-cell to 1-cell
+//run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
+
+
+// copies content of the 0-cell to 2-cell and 4-cell
+//run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42)
+
+
+// prints out numbers 0 to 9
+//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+
+
+// some more "useful" programs
+//-----------------------------
+
+// hello world program 1
+//run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+// hello world program 2
+//run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
+
+// hello world program 3
+//run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..
+// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""")
+
+
+// draws the Sierpinski triangle
+//run(load_bff("sierpinski.bf"))
+
+
+//fibonacci numbers below 100
+//run("""+++++++++++
+// >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+// >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+// +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+// <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+// -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+// >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+// +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+// ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+// <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+// [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
+
+//outputs the square numbers up to 10000
+//run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+// >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+// <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
+
+
+// calculates 2 to the power of 6
+//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it)
+//run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-]
+// <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]
+// <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+>
+// +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
+// <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-]
+// >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-]
+// <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]>
+// [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+>
+// >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<>
+// <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]>
+// [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+
+// >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<
+// ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++
+// ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""")
+
+
+
+// a Mandelbrot set generator in brainf*** written by Erik Bosman
+// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
+//
+//run(load_bff("mandelbrot.bf"))
+
+
+// a benchmark program (counts down from 'Z' to 'A')
+//
+//run(load_bff("benchmark.bf"))
+
+// calculates the Collatz series for numbers from 1 to 30
+//
+//run(load_bff("collatz.bf"))
+
+}
--- a/main_testing5/bfc.scala Mon Nov 08 01:39:00 2021 +0000
+++ b/main_testing5/bfc.scala Mon Nov 08 01:49:28 2021 +0000
@@ -1,9 +1,7 @@
-// Core Part about a "Compiler" for the Brainf*** language
+// Part 2 about a "Compiler" for the Brainf*** language
//======================================================
-
-object CW10b {
-
+object M5b {
// !!! Copy any function you need from file bf.scala !!!
//
@@ -11,61 +9,7 @@
// 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
@@ -73,17 +17,88 @@
(end - start)/(n * 1.0e9)
}
+type Mem = Map[Int, Int]
-// TASKS
-//=======
+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 '[' =>
+ 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.
+
+
// (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 about
-// pc positions where '[' or a ']' are stored. The information
-// is to which pc-position do we need to jump next?
+// 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
//
@@ -102,54 +117,48 @@
// 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 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))
+// you should look up the jump address in the jtable.
-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
-}
+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 compute2(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 '>' => 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
+ 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)
}
-}
-
-def run2(pg: String, m: Mem = Map()) = {
- compute2(pg, jtable(pg), 0, 0, m)
+ else mem
}
-// testcases
-// time_needed(1, run2(load_bff("./main5/benchmark.bf")))
-// time_needed(1, run2(load_bff("./main5/sierpinski.bf")))
+def run2(pg: String, m: Mem = Map()) =
+ compute2(pg, jtable(pg), 0, 0, m)
+
+//time_needed(1, run2(load_bff("benchmark.bf")))
@@ -161,63 +170,56 @@
// 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
+// expression """[^<>+-.\[\]""", which recognises everything that is
// not a bf-command and replace it by the empty string. Similarly the
-// regular expression """\[-\]""" finds all occurrences of [-] and
-// by using the Scala method .replaceAll you can replace it with 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.
-// load_bff("./main5/mandelbrot.bf").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")
+ s.replaceAll("""[^<>+-.\[\]]""","")
+ .replaceAll("""\[-\]""", "0")
}
+
def compute3(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 '>' => 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
+ 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 optimised = optimise(pg)
- compute3(optimised, jtable(optimised), 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("./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")))
+
+//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")))
// (7) Write a function combine which replaces sequences
-// of repeated increment and decrement commands by appropriate
+// of repated increment and decrement commands by appropriate
// two-character commands. For example for sequences of +
//
// orig bf-cmds | replacement
@@ -237,82 +239,82 @@
// Adapt the compute4 and run4 functions such that they can deal
// appropriately with such two-character commands.
-// 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 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 get_character_from_number(int: Int) : Char = {
- alphabet(int - 1)
-}
+def spl(s: String) = splice(s.toList, Nil).reverse
-@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)
- }
-}
+//spl(load_bff("benchmark.bf"))
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("")
-}
-
-// testcase
-// combine(load_bff("./main5/benchmark.bf"))
-
-
-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
- }
+ (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
}
-// 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)
+//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 '[' =>
+ 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
}
+def run4(pg: String, m: Mem = Map()) = {
+ val pg_opt = combine(optimise(pg))
+ compute4(pg_opt, jtable(pg_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"))))
+
-// testcases
-// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
-// 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")))
}
+
+/*
+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"))))
+*/