|
1 // An Interpreter for BF*** Programs |
|
2 //=================================== |
|
3 |
|
4 |
|
5 import io.Source |
|
6 import scala.util._ |
|
7 |
|
8 |
|
9 // loding a bf-file |
|
10 def load_bff(name: String) : String = |
|
11 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
|
12 |
|
13 |
|
14 type Mem = Map[Int, Int] |
|
15 |
|
16 // reading and writing BF memory |
|
17 def sread(mem: Mem, mp: Int) : Int = |
|
18 mem.getOrElse(mp, 0) |
|
19 |
|
20 def write(mem: Mem, mp: Int, v: Int) : Mem = |
|
21 mem.updated(mp, v) |
|
22 |
|
23 |
|
24 // Right and Left Jumps in BF loops |
|
25 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
26 if (prog.length <= pc) pc |
|
27 else (prog(pc), level) match { |
|
28 case (']', 0) => pc + 1 |
|
29 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
|
30 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
|
31 case (_, l) => jumpRight(prog, pc + 1, l) |
|
32 } |
|
33 } |
|
34 |
|
35 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
|
36 if (pc < 0) pc |
|
37 else (prog(pc), level) match { |
|
38 case ('[', 0) => pc + 1 |
|
39 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
|
40 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
|
41 case (_, l) => jumpLeft(prog, pc - 1, l) |
|
42 } |
|
43 } |
|
44 |
|
45 |
|
46 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
|
47 if (0 <= pc && pc < prog.length) { |
|
48 val (new_pc, new_mp, new_mem) = prog(pc) match { |
|
49 case '>' => (pc + 1, mp + 1, mem) |
|
50 case '<' => (pc + 1, mp - 1, mem) |
|
51 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
52 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
53 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
54 case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
|
55 case '[' => if (sread(mem, mp) == 0) |
|
56 (jumpRight(prog, pc + 1, 0), mp, mem) |
|
57 else (pc + 1, mp, mem) |
|
58 case ']' => if (sread(mem, mp) != 0) |
|
59 (jumpLeft(prog, pc - 1, 0), mp, mem) |
|
60 else (pc + 1, mp, mem) |
|
61 case _ => (pc + 1, mp, mem) |
|
62 } |
|
63 compute(prog, new_pc, new_mp, new_mem) |
|
64 } |
|
65 else mem |
|
66 } |
|
67 |
|
68 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
|
69 |
|
70 |
|
71 def time_needed[T](n: Int, code: => T) = { |
|
72 val start = System.nanoTime() |
|
73 for (i <- 0 until n) code |
|
74 val end = System.nanoTime() |
|
75 (end - start)/(n * 1.0e9) |
|
76 } |
|
77 |
|
78 |
|
79 |
|
80 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
|
81 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
|
82 |
|
83 println(s"${time_needed(1, run(load_bff("mandelbrot.bf")))} secs") |
|
84 |
|
85 |
|
86 // a benchmark program (counts down from 'Z' to 'A') |
|
87 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
|
88 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |
|
89 ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ |
|
90 +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" |
|
91 |
|
92 println(s"${time_needed(1, run(b1))} secs") |
|
93 |