|
1 // A simple Interpreter for BF*** Programs |
|
2 //========================================= |
|
3 // |
|
4 // Call |
|
5 // |
|
6 // amm bfi.sc <<bf_program.bf>> |
|
7 |
|
8 |
|
9 import scala.util._ |
|
10 |
|
11 // BF memory as a map |
|
12 type Mem = Map[Int, Int] |
|
13 |
|
14 // reading and writing BF memory |
|
15 def sread(mem: Mem, mp: Int) : Int = |
|
16 mem.getOrElse(mp, 0) |
|
17 |
|
18 def write(mem: Mem, mp: Int, v: Int) : Mem = |
|
19 mem.updated(mp, v) |
|
20 |
|
21 |
|
22 // Right and Left Jumps in BF loops |
|
23 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
24 if (prog.length <= pc) pc |
|
25 else (prog(pc), level) match { |
|
26 case (']', 0) => pc + 1 |
|
27 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
|
28 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
|
29 case (_, l) => jumpRight(prog, pc + 1, l) |
|
30 } |
|
31 } |
|
32 |
|
33 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
|
34 if (pc < 0) pc |
|
35 else (prog(pc), level) match { |
|
36 case ('[', 0) => pc + 1 |
|
37 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
|
38 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
|
39 case (_, l) => jumpLeft(prog, pc - 1, l) |
|
40 } |
|
41 } |
|
42 |
|
43 // main interpreter loop |
|
44 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
|
45 if (0 <= pc && pc < prog.length) { |
|
46 val (new_pc, new_mp, new_mem) = prog(pc) match { |
|
47 case '>' => (pc + 1, mp + 1, mem) |
|
48 case '<' => (pc + 1, mp - 1, mem) |
|
49 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
50 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
51 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
52 case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
|
53 case '[' => if (sread(mem, mp) == 0) |
|
54 (jumpRight(prog, pc + 1, 0), mp, mem) |
|
55 else (pc + 1, mp, mem) |
|
56 case ']' => if (sread(mem, mp) != 0) |
|
57 (jumpLeft(prog, pc - 1, 0), mp, mem) |
|
58 else (pc + 1, mp, mem) |
|
59 case _ => (pc + 1, mp, mem) |
|
60 } |
|
61 compute(prog, new_pc, new_mp, new_mem) |
|
62 } |
|
63 else mem |
|
64 } |
|
65 |
|
66 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
|
67 |
|
68 // helper code for timing information |
|
69 def time_needed[T](n: Int, code: => T) = { |
|
70 val start = System.nanoTime() |
|
71 for (i <- 0 until n) code |
|
72 val end = System.nanoTime() |
|
73 (end - start)/(n * 1.0e9) |
|
74 } |
|
75 |
|
76 // Testcases |
|
77 //=========== |
|
78 |
|
79 @doc(" the argument should be a BF program ") |
|
80 @main |
|
81 def main(fname: String) = { |
|
82 val bf_str = os.read(os.pwd / fname) |
|
83 println(s"${time_needed(1, run(bf_str))} secs") |
|
84 } |
|
85 |