--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing5/bf.scala Thu Dec 06 18:56:26 2018 +0000
@@ -0,0 +1,225 @@
+// Part 1 about an Interpreter for the Brainf*** language
+//========================================================
+
+object CW10a { // only for generating the Jar file
+
+
+type Mem = Map[Int, Int]
+
+
+import io.Source
+import scala.util._
+
+// (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.
+
+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 ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+ 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-programs collected from the Internet
+//=====================================================
+
+
+// first some contrived (small) programs
+
+// clears the 0-cell
+run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
+
+// copies 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))
+
+
+// prints out numbers 0 to 9
+run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+
+
+// some more "useful" programs
+
+// hello world program 1
+run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+// hello world program 2
+run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+ +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
+
+
+// draws the Sierpinski triangle
+run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]""")
+
+run(load_bff("sierpinski.bf"))
+
+
+//fibonacci numbers below 100
+run("""+++++++++++
+ >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
+
+
+//outputs the square numbers up to 10000
+run("""++++[>+++++<-]>[<+++++>-]+<+[
+ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
+
+//collatz numbers (needs a number to be typed in)
+run(""">,[[----------[
+ >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
+ ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
+ <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
+ >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
+ >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
+ ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""")
+
+
+// infinite collatz (never stops)
+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')
+val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+ [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+ ++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+ +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
+
+
+def time_needed[T](n: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val end = System.nanoTime()
+ (end - start)/(n * 1.0e9)
+}
+
+time_needed(1, run(b1))
+*/
+
+}