|
1 // Part 1 about an Interpreter for the Brainf*** language |
|
2 //======================================================== |
|
3 |
|
4 object CW10a { // only for generating the Jar file |
|
5 |
|
6 |
|
7 type Mem = Map[Int, Int] |
|
8 |
|
9 |
|
10 import io.Source |
|
11 import scala.util._ |
|
12 |
|
13 // (1) Write a function that takes a file name as argument and |
|
14 // and requests the corresponding file from disk. It returns the |
|
15 // content of the file as a String. If the file does not exists, |
|
16 // the function should return the empty string. |
|
17 |
|
18 def load_bff(name: String) : String = |
|
19 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
|
20 |
|
21 |
|
22 // (2) Complete the functions for safely reading |
|
23 // and writing brainf*** memory. Safely read should |
|
24 // Return the value stored in the Map for a given memory |
|
25 // pointer, provided it exists; otherwise it Returns 0. The |
|
26 // writing function generates a new Map with the |
|
27 // same data, except at the given memory pointer the |
|
28 // value v is stored. |
|
29 |
|
30 |
|
31 def sread(mem: Mem, mp: Int) : Int = |
|
32 mem.getOrElse(mp, 0) |
|
33 |
|
34 def write(mem: Mem, mp: Int, v: Int) : Mem = |
|
35 mem.updated(mp, v) |
|
36 |
|
37 |
|
38 // (3) Implement the two jumping instructions in the |
|
39 // brainf*** language. In jumpRight, given a program and |
|
40 // a program counter move the program counter to the right |
|
41 // until after the *matching* ]-command. Similarly, |
|
42 // jumpLeft implements the move to the left to just after |
|
43 // the *matching* [-command. |
|
44 |
|
45 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
46 if (prog.length <= pc) pc |
|
47 else (prog(pc), level) match { |
|
48 case (']', 0) => pc + 1 |
|
49 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
|
50 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
|
51 case (_, l) => jumpRight(prog, pc + 1, l) |
|
52 } |
|
53 } |
|
54 |
|
55 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
|
56 if (pc < 0) pc |
|
57 else (prog(pc), level) match { |
|
58 case ('[', 0) => pc + 1 |
|
59 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
|
60 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
|
61 case (_, l) => jumpLeft(prog, pc - 1, l) |
|
62 } |
|
63 } |
|
64 |
|
65 // test cases |
|
66 //jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 |
|
67 //jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 |
|
68 //jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 |
|
69 //jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 |
|
70 //jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) |
|
71 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
|
72 |
|
73 // (4) Complete the compute function that interprets (runs) a brainf*** |
|
74 // program: the arguments are a program (represented as a string), a program |
|
75 // counter, a memory counter and a brainf*** memory. It Returns the |
|
76 // memory at the stage when the execution of the brainf*** program |
|
77 // finishes. The interpretation finishes once the program counter |
|
78 // pc is pointing to something outside the program string. |
|
79 // If the pc points to a character inside the program, the pc, |
|
80 // memory pointer and memory need to be updated according to |
|
81 // rules of the brainf*** language. Then, recursively, the compute |
|
82 // function continues with the command at the new program |
|
83 // counter. |
|
84 // Implement the run function that calls compute with the program |
|
85 // counter and memory counter set to 0. |
|
86 |
|
87 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
|
88 if (0 <= pc && pc < prog.length) { |
|
89 val (new_pc, new_mp, new_mem) = prog(pc) match { |
|
90 case '>' => (pc + 1, mp + 1, mem) |
|
91 case '<' => (pc + 1, mp - 1, mem) |
|
92 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
93 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
94 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
95 case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
|
96 case '[' => |
|
97 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
98 case ']' => |
|
99 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
100 case _ => (pc + 1, mp, mem) |
|
101 } |
|
102 compute(prog, new_pc, new_mp, new_mem) |
|
103 } |
|
104 else mem |
|
105 } |
|
106 |
|
107 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
|
108 |
|
109 |
|
110 /* |
|
111 |
|
112 // some sample bf-programs collected from the Internet |
|
113 //===================================================== |
|
114 |
|
115 |
|
116 // first some contrived (small) programs |
|
117 |
|
118 // clears the 0-cell |
|
119 run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
|
120 |
|
121 // copies content of the 0-cell to 1-cell |
|
122 run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
|
123 |
|
124 |
|
125 // copies content of the 0-cell to 2-cell and 4-cell |
|
126 run("[>>+>>+<<<<-]", Map(0 -> 42)) |
|
127 |
|
128 |
|
129 // prints out numbers 0 to 9 |
|
130 run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
|
131 |
|
132 |
|
133 // some more "useful" programs |
|
134 |
|
135 // hello world program 1 |
|
136 run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
|
137 ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
|
138 |
|
139 // hello world program 2 |
|
140 run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
|
141 +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
|
142 |
|
143 |
|
144 // draws the Sierpinski triangle |
|
145 run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ |
|
146 ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< |
|
147 ]>.>+[>>]>+]""") |
|
148 |
|
149 run(load_bff("sierpinski.bf")) |
|
150 |
|
151 |
|
152 //fibonacci numbers below 100 |
|
153 run("""+++++++++++ |
|
154 >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
|
155 >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
|
156 +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
|
157 <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
|
158 -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
|
159 >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ |
|
160 +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
|
161 ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
|
162 <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
|
163 [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
|
164 |
|
165 |
|
166 //outputs the square numbers up to 10000 |
|
167 run("""++++[>+++++<-]>[<+++++>-]+<+[ |
|
168 >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
|
169 >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
|
170 <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
|
171 |
|
172 //collatz numbers (needs a number to be typed in) |
|
173 run(""">,[[----------[ |
|
174 >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] |
|
175 ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ |
|
176 <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] |
|
177 >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] |
|
178 >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> |
|
179 ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""") |
|
180 |
|
181 |
|
182 // infinite collatz (never stops) |
|
183 run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< |
|
184 <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ |
|
185 +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< |
|
186 [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> |
|
187 [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ |
|
188 <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ |
|
189 ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< |
|
190 +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- |
|
191 ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- |
|
192 >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> |
|
193 -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ |
|
194 +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< |
|
195 <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ |
|
196 +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< |
|
197 <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- |
|
198 [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""") |
|
199 |
|
200 |
|
201 |
|
202 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
|
203 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
|
204 |
|
205 run(load_bff("mandelbrot.bf")) |
|
206 |
|
207 |
|
208 // a benchmark program (counts down from 'Z' to 'A') |
|
209 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
|
210 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |
|
211 ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ |
|
212 +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" |
|
213 |
|
214 |
|
215 def time_needed[T](n: Int, code: => T) = { |
|
216 val start = System.nanoTime() |
|
217 for (i <- 0 until n) code |
|
218 val end = System.nanoTime() |
|
219 (end - start)/(n * 1.0e9) |
|
220 } |
|
221 |
|
222 time_needed(1, run(b1)) |
|
223 */ |
|
224 |
|
225 } |