|
632
|
1 |
// An Interpreter for BF*** Programs
|
|
|
2 |
//===================================
|
|
|
3 |
|
|
|
4 |
import io.Source
|
|
|
5 |
import scala.util._
|
|
|
6 |
|
|
|
7 |
// loding a bf-file
|
|
|
8 |
def load_bff(name: String) : String =
|
|
|
9 |
Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")
|
|
|
10 |
|
|
636
|
11 |
// BF memory as a map
|
|
632
|
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 |
|
|
636
|
43 |
// main interpreter loop
|
|
632
|
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 |
|
|
636
|
68 |
// helper code for timing information
|
|
632
|
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 |
|
|
636
|
76 |
// Testcases
|
|
|
77 |
//===========
|
|
632
|
78 |
|
|
|
79 |
// a Mandelbrot set generator in brainf*** written by Erik Bosman
|
|
|
80 |
// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
|
|
636
|
81 |
val b0 = load_bff("mandelbrot.bf")
|
|
632
|
82 |
|
|
636
|
83 |
println(s"${time_needed(1, run(b0))} secs")
|
|
632
|
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 |
|