1 // An Interpreter for BF*** Programs |
1 // An Interpreter for BF*** Programs |
2 //=================================== |
2 //=================================== |
3 |
3 |
4 |
|
5 import io.Source |
4 import io.Source |
6 import scala.util._ |
5 import scala.util._ |
7 |
|
8 |
6 |
9 // loding a bf-file |
7 // loding a bf-file |
10 def load_bff(name: String) : String = |
8 def load_bff(name: String) : String = |
11 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
9 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
12 |
10 |
13 |
11 // BF memory as a map |
14 type Mem = Map[Int, Int] |
12 type Mem = Map[Int, Int] |
15 |
13 |
16 // reading and writing BF memory |
14 // reading and writing BF memory |
17 def sread(mem: Mem, mp: Int) : Int = |
15 def sread(mem: Mem, mp: Int) : Int = |
18 mem.getOrElse(mp, 0) |
16 mem.getOrElse(mp, 0) |
40 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
38 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
41 case (_, l) => jumpLeft(prog, pc - 1, l) |
39 case (_, l) => jumpLeft(prog, pc - 1, l) |
42 } |
40 } |
43 } |
41 } |
44 |
42 |
45 |
43 // main interpreter loop |
46 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
44 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
47 if (0 <= pc && pc < prog.length) { |
45 if (0 <= pc && pc < prog.length) { |
48 val (new_pc, new_mp, new_mem) = prog(pc) match { |
46 val (new_pc, new_mp, new_mem) = prog(pc) match { |
49 case '>' => (pc + 1, mp + 1, mem) |
47 case '>' => (pc + 1, mp + 1, mem) |
50 case '<' => (pc + 1, mp - 1, mem) |
48 case '<' => (pc + 1, mp - 1, mem) |
65 else mem |
63 else mem |
66 } |
64 } |
67 |
65 |
68 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
66 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
69 |
67 |
70 |
68 // helper code for timing information |
71 def time_needed[T](n: Int, code: => T) = { |
69 def time_needed[T](n: Int, code: => T) = { |
72 val start = System.nanoTime() |
70 val start = System.nanoTime() |
73 for (i <- 0 until n) code |
71 for (i <- 0 until n) code |
74 val end = System.nanoTime() |
72 val end = System.nanoTime() |
75 (end - start)/(n * 1.0e9) |
73 (end - start)/(n * 1.0e9) |
76 } |
74 } |
77 |
75 |
78 |
76 // Testcases |
|
77 //=========== |
79 |
78 |
80 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
79 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
81 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
80 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
|
81 val b0 = load_bff("mandelbrot.bf") |
82 |
82 |
83 println(s"${time_needed(1, run(load_bff("mandelbrot.bf")))} secs") |
83 println(s"${time_needed(1, run(b0))} secs") |
84 |
84 |
85 |
85 |
86 // a benchmark program (counts down from 'Z' to 'A') |
86 // a benchmark program (counts down from 'Z' to 'A') |
87 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
87 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
88 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |
88 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |