diff -r 34feeb53c0ba -r 0315d9983cd0 main_testing5/bf.scala --- a/main_testing5/bf.scala Sun Jan 15 10:58:13 2023 +0000 +++ b/main_testing5/bf.scala Sat Mar 11 22:01:53 2023 +0000 @@ -1,163 +1,164 @@ -// Core Part about an Interpreter for -// the Brainf***++ language +// Main Part 5 about an Interpreter for +// the Brainf*** language //============================================== -object M5a { - -// representation of Bf memory +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("") - +// ADD YOUR CODE BELOW +//====================== -// (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) +// (1) +def load_bff(name: String) : String = { + Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") +} -def write(mem: Mem, mp: Int, v: Int) : Mem = - mem.updated(mp, v) - +// (2) -// (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 sread(mem: Mem, mp: Int) : Int = { + Try(mem.apply(mp)).getOrElse(0) +} -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 write(mem: Mem, mp: Int, v: Int) : Mem = { + mem + (mp -> v) } -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) - } +// 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) + +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) } -// 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 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 run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) + +// 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) +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) + } +} -// some sample bf/bf++-programs collected from the Internet -//========================================================== +def run(prog: String, m: Mem = Map()) = { + compute(prog, 0, 0, m) +} + +// 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 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("""+++++++++++ // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- @@ -169,15 +170,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(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] @@ -194,18 +195,28 @@ -// 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")) } + + + + + +// 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.