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