1 // Part 2 about a "Compiler" for the Brainf*** language |
1 // Main Part 5 about a "Compiler" for the Brainf*** language |
2 //====================================================== |
2 //============================================================ |
|
3 |
3 |
4 |
4 object M5b { |
5 object M5b { |
5 |
6 |
6 // !!! Copy any function you need from file bf.scala !!! |
7 // !!! Copy any function you need from file bf.scala !!! |
7 // |
8 // |
8 // If you need any auxiliary function, feel free to |
9 // If you need any auxiliary function, feel free to |
9 // implement it, but do not make any changes to the |
10 // implement it, but do not make any changes to the |
10 // templates below. |
11 // templates below. |
11 |
12 |
12 |
13 |
|
14 // DEBUGGING INFORMATION FOR COMPILERS!!! |
|
15 // |
|
16 // Compiler, even real ones, are fiendishly difficult to get |
|
17 // to produce correct code. One way to debug them is to run |
|
18 // example programs ``unoptimised''; and then optimised. Does |
|
19 // the optimised version still produce the same result? |
|
20 |
|
21 |
|
22 // for timing purposes |
13 def time_needed[T](n: Int, code: => T) = { |
23 def time_needed[T](n: Int, code: => T) = { |
14 val start = System.nanoTime() |
24 val start = System.nanoTime() |
15 for (i <- 0 until n) code |
25 for (i <- 0 until n) code |
16 val end = System.nanoTime() |
26 val end = System.nanoTime() |
17 (end - start)/(n * 1.0e9) |
27 (end - start)/(n * 1.0e9) |
18 } |
28 } |
19 |
29 |
|
30 |
20 type Mem = Map[Int, Int] |
31 type Mem = Map[Int, Int] |
21 |
|
22 |
32 |
23 import io.Source |
33 import io.Source |
24 import scala.util._ |
34 import scala.util._ |
25 |
35 |
26 def load_bff(name: String) : String = |
36 // ADD YOUR CODE BELOW |
27 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
37 //====================== |
28 |
38 |
29 def sread(mem: Mem, mp: Int) : Int = |
39 // (6) |
30 mem.getOrElse(mp, 0) |
40 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
41 if (pc >= prog.length) prog.length |
|
42 else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1) |
|
43 else if (prog(pc) == ']' && level == 0) pc + 1 |
|
44 else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1) |
|
45 else jumpRight(prog, pc + 1, level) |
|
46 } |
31 |
47 |
32 def write(mem: Mem, mp: Int, v: Int) : Mem = |
48 def jtable(pg: String) : Map[Int, Int] = { |
33 mem.updated(mp, v) |
49 val pairs = for { |
|
50 i <- 0 until pg.length |
|
51 if pg.charAt(i) == '[' |
|
52 j = jumpRight(pg, i+1, 0) |
|
53 } yield (i, j) |
|
54 pairs.flatMap { case (i, j) => |
|
55 List((i, j), (j-1, i+1)) |
|
56 }.toMap |
|
57 } |
34 |
58 |
35 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
59 def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) |
36 if (prog.length <= pc) pc |
60 |
37 else (prog(pc), level) match { |
61 // testcase |
38 case (']', 0) => pc + 1 |
62 // |
39 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
63 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
40 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
64 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
41 case (_, l) => jumpRight(prog, pc + 1, l) |
65 |
|
66 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
|
67 if (pc >= pg.length) mem |
|
68 else { |
|
69 val (npc, nmp, nmem) = pg(pc) match { |
|
70 case '>' => (pc + 1, mp + 1, mem) |
|
71 case '<' => (pc + 1, mp - 1, mem) |
|
72 case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) |
|
73 case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) |
|
74 case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} |
|
75 case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
76 case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
77 case _ => (pc + 1, mp, mem) |
|
78 } |
|
79 compute2(pg, tb, npc, nmp, nmem) |
42 } |
80 } |
43 } |
81 } |
44 |
82 |
45 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
83 def run2(pg: String, m: Mem = Map()) = |
46 if (pc < 0) pc |
84 compute2(pg, jtable(pg), 0, 0, m) |
47 else (prog(pc), level) match { |
85 |
48 case ('[', 0) => pc + 1 |
|
49 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
|
50 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
|
51 case (_, l) => jumpLeft(prog, pc - 1, l) |
|
52 } |
|
53 } |
|
54 |
86 |
55 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
87 // testcases |
56 if (0 <= pc && pc < prog.length) { |
88 // time_needed(1, run2(load_bff("benchmark.bf"))) |
57 val (new_pc, new_mp, new_mem) = prog(pc) match { |
89 // time_needed(1, run2(load_bff("sierpinski.bf"))) |
58 case '>' => (pc + 1, mp + 1, mem) |
|
59 case '<' => (pc + 1, mp - 1, mem) |
|
60 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
61 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
62 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
63 case '[' => |
|
64 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
65 case ']' => |
|
66 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
67 case _ => (pc + 1, mp, mem) |
|
68 } |
|
69 compute(prog, new_pc, new_mp, new_mem) |
|
70 } |
|
71 else mem |
|
72 } |
|
73 |
|
74 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
|
75 |
|
76 |
|
77 // The baseline to what we can compare our "compiler" |
|
78 // implemented below. It should require something like |
|
79 // 60 seconds for the calculation on my laptop |
|
80 // |
|
81 //time_needed(1, run(load_bff("benchmark.bf"))) |
|
82 |
90 |
83 |
91 |
84 |
92 |
85 // DEBUGGING INFORMATION!!! |
93 // (7) |
86 // |
|
87 // Compiler, even real ones, are fiedishly difficult to get |
|
88 // to prduce correct code. The point is that for example for |
|
89 // the sierpinski program, they need to still generate code |
|
90 // that displays such a triangle. If yes, then one usually |
|
91 // can take comfort that all is well. If not, then something |
|
92 // went wrong during the optimisations. |
|
93 |
94 |
|
95 def optimise(s: String) : String = |
|
96 s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0") |
94 |
97 |
95 |
98 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
96 // (5) Write a function jtable that precomputes the "jump |
99 if (pc >= pg.length) mem |
97 // table" for a bf-program. This function takes a bf-program |
100 else { |
98 // as an argument and Returns a Map[Int, Int]. The |
101 val (npc, nmp, nmem) = pg(pc) match { |
99 // purpose of this map is to record the information |
102 case '>' => (pc + 1, mp + 1, mem) |
100 // that given on the position pc is a '[' or a ']', |
103 case '<' => (pc + 1, mp - 1, mem) |
101 // then to which pc-position do we need to jump next? |
104 case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) |
102 // |
105 case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) |
103 // For example for the program |
106 case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} |
104 // |
107 case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
105 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
108 case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
106 // |
109 case _ => (pc + 1, mp, mem) |
107 // we obtain the map |
110 } |
108 // |
111 compute3(pg, tb, npc, nmp, nmem) |
109 // Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
112 } |
110 // |
|
111 // This states that for the '[' on position 5, we need to |
|
112 // jump to position 20, which is just after the corresponding ']'. |
|
113 // Similarly, for the ']' on position 19, we need to jump to |
|
114 // position 6, which is just after the '[' on position 5, and so |
|
115 // on. The idea is to not calculate this information each time |
|
116 // we hit a bracket, but just look up this information in the |
|
117 // jtable. You can use the jumpLeft and jumpRight functions |
|
118 // from Part 1 for calculating the jtable. |
|
119 // |
|
120 // Then adapt the compute and run functions from Part 1 in order |
|
121 // to take advantage of the information stored in the jtable. |
|
122 // This means whenever jumpLeft and jumpRight was called previously, |
|
123 // you should look up the jump address in the jtable. |
|
124 |
|
125 |
|
126 def jtable(pg: String) : Map[Int, Int] = |
|
127 (0 until pg.length).collect { pc => pg(pc) match { |
|
128 case '[' => (pc -> jumpRight(pg, pc + 1, 0)) |
|
129 case ']' => (pc -> jumpLeft(pg, pc - 1, 0)) |
|
130 }}.toMap |
|
131 |
|
132 |
|
133 // testcase |
|
134 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
|
135 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
|
136 |
|
137 |
|
138 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
|
139 if (0 <= pc && pc < pg.length) { |
|
140 val (new_pc, new_mp, new_mem) = pg(pc) match { |
|
141 case '>' => (pc + 1, mp + 1, mem) |
|
142 case '<' => (pc + 1, mp - 1, mem) |
|
143 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
144 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
145 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
146 case '[' => |
|
147 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
148 case ']' => |
|
149 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
150 case _ => (pc + 1, mp, mem) |
|
151 } |
|
152 compute2(pg, tb, new_pc, new_mp, new_mem) |
|
153 } |
|
154 else mem |
|
155 } |
113 } |
156 |
114 |
157 |
115 def run3(pg: String, m: Mem = Map()) = { |
158 def run2(pg: String, m: Mem = Map()) = |
116 val opt_pg = optimise(pg) |
159 compute2(pg, jtable(pg), 0, 0, m) |
117 val jt = jtable(opt_pg) |
160 |
118 compute3(opt_pg, jt, 0, 0, m) |
161 //time_needed(1, run2(load_bff("benchmark.bf"))) |
|
162 |
|
163 |
|
164 |
|
165 // (6) Write a function optimise which deletes "dead code" (everything |
|
166 // that is not a bf-command) and also replaces substrings of the form |
|
167 // [-] by a new command 0. The idea is that the loop [-] just resets the |
|
168 // memory at the current location to 0. In the compute3 and run3 functions |
|
169 // below you implement this command by writing the number 0 to mem(mp), |
|
170 // that is write(mem, mp, 0). |
|
171 // |
|
172 // The easiest way to modify a string in this way is to use the regular |
|
173 // expression """[^<>+-.\[\]""", which recognises everything that is |
|
174 // not a bf-command and replace it by the empty string. Similarly the |
|
175 // regular expression """\[-\]""" finds all occurences of [-] and |
|
176 // by using the Scala method .replaceAll you can repplace it with the |
|
177 // string "0" standing for the new bf-command. |
|
178 |
|
179 def optimise(s: String) : String = { |
|
180 s.replaceAll("""[^<>+-.\[\]]""","") |
|
181 .replaceAll("""\[-\]""", "0") |
|
182 } |
|
183 |
|
184 |
|
185 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
|
186 if (0 <= pc && pc < pg.length) { |
|
187 val (new_pc, new_mp, new_mem) = pg(pc) match { |
|
188 case '0' => (pc + 1, mp, write(mem, mp, 0)) |
|
189 case '>' => (pc + 1, mp + 1, mem) |
|
190 case '<' => (pc + 1, mp - 1, mem) |
|
191 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
192 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
193 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
194 case '[' => |
|
195 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
196 case ']' => |
|
197 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
198 case _ => (pc + 1, mp, mem) |
|
199 } |
|
200 compute3(pg, tb, new_pc, new_mp, new_mem) |
|
201 } |
|
202 else mem |
|
203 } |
|
204 |
|
205 def run3(pg: String, m: Mem = Map()) = { |
|
206 val pg_opt = optimise(pg) |
|
207 compute3(pg_opt, jtable(pg_opt), 0, 0, m) |
|
208 } |
119 } |
209 |
120 |
210 |
121 |
211 // testcases |
122 // testcases |
212 |
123 // |
213 //println(optimise(load_bff("collatz.bf"))) |
124 // optimise(load_bff("benchmark.bf")) // should have inserted 0's |
214 //optimise(load_bff("benchmark.bf")) // should have inserted 0's |
125 // optimise(load_bff("mandelbrot.bf")).length // => 11203 |
215 //optimise(load_bff("mandelbrot.bf")).length // => 11203 |
126 // optimise(load_bff("benchmark.bf")).length |
216 |
127 // time_needed(1, run3(load_bff("benchmark.bf"))) |
217 //time_needed(1, run3(load_bff("benchmark.bf"))) |
|
218 |
128 |
219 |
129 |
|
130 // (8) |
|
131 def combine(s: String): String = ??? |
220 |
132 |
221 // (7) Write a function combine which replaces sequences |
133 // testcase |
222 // of repated increment and decrement commands by appropriate |
134 // combine(load_bff("benchmark.bf")) |
223 // two-character commands. For example for sequences of + |
|
224 // |
|
225 // orig bf-cmds | replacement |
|
226 // ------------------------------ |
|
227 // + | +A |
|
228 // ++ | +B |
|
229 // +++ | +C |
|
230 // | |
|
231 // ... | |
|
232 // | |
|
233 // +++....+++ | +Z |
|
234 // (where length = 26) |
|
235 // |
|
236 // Similar for the bf-command -, > and <. All other commands should |
|
237 // be unaffected by this change. |
|
238 // |
|
239 // Adapt the compute4 and run4 functions such that they can deal |
|
240 // appropriately with such two-character commands. |
|
241 |
135 |
242 def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { |
136 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
243 case (Nil, acc) => acc |
137 if (pc >= pg.length) mem |
244 case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc) |
138 else { |
245 case (']' :: cs, acc) => splice(cs, (']', 1) :: acc) |
139 val (npc, nmp, nmem) = pg(pc) match { |
246 case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc) |
140 case '>' => (pc + 1, mp + 1, mem) |
247 case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc) |
141 case '<' => (pc + 1, mp - 1, mem) |
248 case (c :: cs, Nil) => splice(cs, List((c, 1))) |
142 case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) |
249 case (c :: cs, (d, n) :: acc) => |
143 case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) |
250 if (c == d && n < 26) splice(cs, (c, n + 1) :: acc) |
144 case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} |
251 else splice(cs, (c, 1) :: (d, n) :: acc) |
145 case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
146 case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
147 case _ => (pc + 1, mp, mem) |
|
148 } |
|
149 compute3(pg, tb, npc, nmp, nmem) |
|
150 } |
252 } |
151 } |
253 |
152 |
254 def spl(s: String) = splice(s.toList, Nil).reverse |
153 // should call first optimise and then combine on the input string |
255 |
154 // |
256 //spl(load_bff("benchmark.bf")) |
155 def run4(pg: String, m: Mem = Map()) = { |
257 |
156 val co_opt_pg = combine(optimise(pg)) |
258 def combine(s: String) : String = { |
157 val jt = jtable(co_opt_pg) |
259 (for ((c, n) <- spl(s)) yield c match { |
158 compute3(co_opt_pg, jt, 0, 0, m) |
260 case '>' => List('>', (n + '@').toChar) |
|
261 case '<' => List('<', (n + '@').toChar) |
|
262 case '+' => List('+', (n + '@').toChar) |
|
263 case '-' => List('-', (n + '@').toChar) |
|
264 case _ => List(c) |
|
265 }).flatten.mkString |
|
266 } |
|
267 |
|
268 |
|
269 //combine(load_bff("benchmark.bf")) |
|
270 |
|
271 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
|
272 if (0 <= pc && pc < pg.length) { |
|
273 val (new_pc, new_mp, new_mem) = pg(pc) match { |
|
274 case '0' => (pc + 1, mp, write(mem, mp, 0)) |
|
275 case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem) |
|
276 case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem) |
|
277 case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@'))) |
|
278 case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@'))) |
|
279 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
280 case '[' => |
|
281 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
282 case ']' => |
|
283 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
|
284 case _ => (pc + 1, mp, mem) |
|
285 } |
|
286 compute4(pg, tb, new_pc, new_mp, new_mem) |
|
287 } |
|
288 else mem |
|
289 } |
|
290 |
|
291 def run4(pg: String, m: Mem = Map()) = { |
|
292 val pg_opt = combine(optimise(pg)) |
|
293 compute4(pg_opt, jtable(pg_opt), 0, 0, m) |
|
294 } |
159 } |
295 |
160 |
296 // testcases |
161 // testcases |
297 //println(combine(optimise(load_bff("mandelbrot.bf").drop(123)))) |
162 // combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
298 |
163 |
299 //combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
164 // testcases (they should now run much faster) |
|
165 // time_needed(1, run4(load_bff("benchmark.bf"))) |
|
166 // time_needed(1, run4(load_bff("sierpinski.bf"))) |
|
167 // time_needed(1, run4(load_bff("mandelbrot.bf"))) |
300 |
168 |
301 //time_needed(1, run4(load_bff("benchmark.bf"))) |
|
302 |
169 |
303 //time_needed(1, run(load_bff("sierpinski.bf"))) |
170 } |
304 //time_needed(1, run4(load_bff("sierpinski.bf"))) |
|
305 |
|
306 //println(time_needed(1, run4(load_bff("mandelbrot.bf")))) |
|
307 |
171 |
308 |
172 |
309 |
173 |
310 |
174 |
311 |
175 |
312 } |
176 // This template code is subject to copyright |
313 |
177 // by King's College London, 2022. Do not |
314 /* |
178 // make the template code public in any shape |
315 import CW10b._ |
179 // or form, and do not exchange it with other |
316 println(time_needed(1, run(load_bff("collatz.bf")))) |
180 // students under any circumstance. |
317 println(time_needed(1, run2(load_bff("collatz.bf")))) |
|
318 println(time_needed(1, run3(load_bff("collatz.bf")))) |
|
319 println(time_needed(1, run4(load_bff("collatz.bf")))) |
|
320 */ |
|