diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf.scala --- a/main_testing5/bf.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,164 +1,166 @@ -// Main Part 5 about an Interpreter for -// the Brainf*** language +// Core Part about an Interpreter for +// the Brainf***++ language //============================================== +object M5a { + -object M5a { - -// representation of BF memory +// 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._ -// ADD YOUR CODE BELOW -//====================== - -// (1) -def load_bff(name: String) : String = { - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -} - -// (2) +def load_bff(name: String) : String = + Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -def sread(mem: Mem, mp: Int) : Int = { - Try(mem.apply(mp)).getOrElse(0) -} - -def write(mem: Mem, mp: Int, v: Int) : Mem = { - mem + (mp -> v) -} - -// sread(Map(), 2) == 0 -// sread(Map(2 -> 1), 2) == 1 -// write(Map(), 1, 2) == Map(1 -> 2) -// write(Map(1 -> 0), 1, 2) == Map(1 -> 2) -// val current = sread(Map(2 -> 1), 2) -// write(Map(2 -> 1), 2, current+1) - -// (3) +// (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 jumpRight(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ - case '[' => jumpRight(prog, pc+1, level+1) - case ']' => level match { - case 0 => pc+1 - case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level-1) - } - case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level) -} -def jumpLeft(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ - case ']' => jumpLeft(prog, pc-1, level+1) - case '[' => level match { - case 0 => pc+1 - case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level-1) - } - case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level) -} +def sread(mem: Mem, mp: Int) : Int = + mem.getOrElse(mp, 0) + +def write(mem: Mem, mp: Int, v: Int) : Mem = + mem.updated(mp, v) -// 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) +// (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) -// (4) -def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = (pc >= 0 && pc < prog.length) match { - case false => mem - case true => prog.toList.apply(pc) match{ - case '>' => compute(prog, pc+1, mp+1, mem) - case '<' => compute(prog, pc+1, mp-1, mem) - case '+' => { - val current = sread(mem, mp) - compute(prog, pc+1, mp, write(mem, mp, current+1)) - } - case '-' => { - val current = sread(mem, mp) - compute(prog, pc+1, mp, write(mem, mp, current-1)) - } - case '.' => { - print(mem.apply(mp).toChar) - compute(prog, pc+1, mp, mem) - } - case '[' => { - if (mem.apply(mp) == 0) compute(prog, jumpRight(prog, pc+1, 0), mp, mem) - else compute(prog, pc+1, mp, mem) - } - case ']' => { - if (mem.apply(mp) != 0) compute(prog, jumpLeft(prog, pc-1, 0), mp, mem) - else compute(prog, pc+1, mp, mem) - } - case _ => compute(prog, pc, mp, mem) - } +def generate(msg: List[Char]) : String = msg match { + case Nil => "" + case c::cs => s"${"+" * c.toInt}.[-]" ++ generate(cs) } -def run(prog: String, m: Mem = Map()) = { - compute(prog, 0, 0, m) -} +//println(generate("Hello World\n".toList)) -// run("[-]", Map(0 -> 100)) == Map(0 -> 0) -// run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10) -// run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42) -// run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(0 -> 0, 1 -> 58, 2 -> 32) -// (5) -def generate(msg: List[Char]) : String = msg match { - case Nil => "" - case c => "+"*c.head.toInt + ".[-]" + generate(msg.tail) -} - -// generate("ABC".toList) - -// run("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]", Map()) - -// some sample bf-programs collected from the Internet -//===================================================== +// 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 +// 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 +// 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) +// 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("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") +// prints out numbers 0 to 9 +//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") -// // some more "useful" programs -// //----------------------------- +// some more "useful" programs +//----------------------------- -// // hello world program 1 -// run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""") +// hello world program 1 +//run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ +// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") -// // hello world program 2 -// run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.""") +// hello world program 2 +//run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ +// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") -// // hello world program 3 -// run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") +// hello world program 3 +//run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. +// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") -// // draws the Sierpinski triangle -// run(load_bff("sierpinski.bf")) +// draws the Sierpinski triangle +//run(load_bff("sierpinski.bf")) -// //fibonacci numbers below 100 -// run("""+++++++++++ +//fibonacci numbers below 100 +//run("""+++++++++++ // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- @@ -170,15 +172,15 @@ // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") -// //outputs the square numbers up to 10000 -// 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(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] +// calculates 2 to the power of 6 +//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) +//run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] @@ -195,28 +197,25 @@ -// // a Mandelbrot set generator in brainf*** written by Erik Bosman +// a Mandelbrot set generator in brainf*** written by Erik Bosman // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) - -// run(load_bff("mandelbrot.bf")) +// +//run(load_bff("mandelbrot.bf")) -// // a benchmark program (counts down from 'Z' to 'A') -// // -// run(load_bff("benchmark.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")) +// calculates the Collatz series for numbers from 1 to 30 +// +//run(load_bff("collatz.bf")) } - - +//M5a.run(M5a.load_bff("mandelbrot.bf")) +//M5a.run(M5a.load_bff("collatz.bf")) -// This template code is subject to copyright -// by King's College London, 2022. Do not -// make the template code public in any shape -// or form, and do not exchange it with other -// students under any circumstance. +//println(M5a.generate("ABC".toList)) +//M5a.run(M5a.generate("Hello World\n".toList))