# HG changeset patch # User Christian Urban # Date 1636336168 0 # Node ID bf20a9fa5c29b5b060b5a3c2075bf0cb4ff3d31e # Parent ffce7b61b44693ccc8484be77cf129cc577005bd updated diff -r ffce7b61b446 -r bf20a9fa5c29 main_solution5/bfc.scala --- a/main_solution5/bfc.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_solution5/bfc.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,7 +1,7 @@ // Part 2 about a "Compiler" for the Brainf*** language //====================================================== -object CW10b { +object M5b { // !!! Copy any function you need from file bf.scala !!! // diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf.scala --- 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")) + +} diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test.sh --- a/main_testing5/bf_test.sh Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test.sh Mon Nov 08 01:49:28 2021 +0000 @@ -5,7 +5,7 @@ echo -e "" > $out -echo -e "Below is the feedback for your submission of CW 10." >> $out +echo -e "Below is the feedback for your submission of bf.scala." >> $out echo -e "" >> $out @@ -119,8 +119,6 @@ echo -e " run(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" >> $out echo -e " run(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" >> $out echo -e " run(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" >> $out - echo -e " run(\"++++++++++#>+***#\") == Map(0 -> 10, 1 -> 1000)" >> $out - echo -e " run(\"+++>+@+@+@+@+@\") == Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3)" >> $out echo -e " run(\"\"\"+++++[->++++++++++<]>--<+++[->>++++++++++" >> $out echo -e " <<]>>++<<----------[+>.>.<+<]\"\"\") == Map(0 -> 0, 1 -> 58, 2 -> 32)" >> $out diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test1.scala --- a/main_testing5/bf_test1.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test1.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10a._ +import M5a._ assert(load_bff("benchmark.bf").length == 188) assert(load_bff("foobar.bf") == "") diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test2.scala --- a/main_testing5/bf_test2.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test2.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10a._ +import M5a._ assert(sread(Map(), 2) == 0) assert(sread(Map(2 -> 1), 2) == 1) diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test3.scala --- a/main_testing5/bf_test3.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test3.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10a._ +import M5a._ assert(jumpRight("[xxxxxx]xxx", 1, 0) == 8) assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8) diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test4.scala --- a/main_testing5/bf_test4.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test4.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,10 +1,9 @@ -import CW10a._ +import M5a._ assert(run("[-]", Map(0 -> 100)) == Map(0 -> 0)) assert(run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)) assert(run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)) -assert(run("++++++++++#>+***#") == Map(0 -> 10, 1 -> 1000)) -assert(run("+++>+@+@+@+@+@") == Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3)) + diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test5.scala --- a/main_testing5/bf_test5.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test5.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10b._ +import M5b._ assert(jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)) diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test6.scala --- a/main_testing5/bf_test6.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test6.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10b._ +import M5b._ //println(optimise(load_bff("benchmark.bf")).length) //println(optimise(load_bff("mandelbrot.bf")).length) diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bf_test7.scala --- a/main_testing5/bf_test7.scala Mon Nov 08 01:39:00 2021 +0000 +++ b/main_testing5/bf_test7.scala Mon Nov 08 01:49:28 2021 +0000 @@ -1,4 +1,4 @@ -import CW10b._ +import M5b._ //println(combine(optimise(load_bff("benchmark.bf"))).length) //println(combine(optimise(load_bff("mandelbrot.bf"))).length) diff -r ffce7b61b446 -r bf20a9fa5c29 main_testing5/bfc.scala --- 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-A] """>A+B[A-A] $out -echo -e "Below is the feedback for your submission of CW 10, Part 2." >> $out +echo -e "Below is the feedback for your submission of bfc.scala" >> $out echo -e "" >> $out # compilation tests