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