1 // Core Part about a "Compiler" for the Brainf*** language |
1 // Part 2 about a "Compiler" for the Brainf*** language |
2 //====================================================== |
2 //====================================================== |
3 |
3 |
4 |
4 object M5b { |
5 object CW10b { |
|
6 |
|
7 |
5 |
8 // !!! Copy any function you need from file bf.scala !!! |
6 // !!! Copy any function you need from file bf.scala !!! |
9 // |
7 // |
10 // If you need any auxiliary function, feel free to |
8 // If you need any auxiliary function, feel free to |
11 // implement it, but do not make any changes to the |
9 // implement it, but do not make any changes to the |
12 // templates below. |
10 // templates below. |
13 |
11 |
14 type Mem = Map[Int, Int] |
12 |
15 |
|
16 import io.Source |
|
17 import scala.util._ |
|
18 |
|
19 def load_bff(name: String) : String = |
|
20 Try(scala.io.Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
|
21 |
|
22 def sread(mem: Mem, mp: Int) : Int = mem.getOrElse(mp, 0) |
|
23 |
|
24 def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) |
|
25 |
|
26 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
27 pc match { |
|
28 case pc: Int if (pc >= 0 && pc < prog.length) => { |
|
29 prog(pc) match { |
|
30 case '[' => jumpRight(prog, pc + 1, level + 1) |
|
31 case ']' => if (level == 0) pc + 1 else jumpRight(prog, pc + 1, level - 1) |
|
32 case _ => jumpRight(prog, pc + 1, level) |
|
33 } |
|
34 } |
|
35 case _ => pc |
|
36 } |
|
37 } |
|
38 |
|
39 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
|
40 pc match { |
|
41 case pc: Int if (pc >= 0 && pc < prog.length) => { |
|
42 prog(pc) match { |
|
43 case '[' => if (level == 0) pc + 1 else jumpLeft(prog, pc - 1, level - 1) |
|
44 case ']' => jumpLeft(prog, pc - 1, level + 1) |
|
45 case _ => jumpLeft(prog, pc - 1, level) |
|
46 } |
|
47 } |
|
48 case _ => pc |
|
49 } |
|
50 } |
|
51 |
|
52 def get_position(prog: String, pc: Int, level: Int) : Int = { |
|
53 prog(pc) match { |
|
54 case '[' => jumpRight(prog, pc + 1, level) |
|
55 case ']' => jumpLeft(prog, pc - 1, level) |
|
56 case _ => println("Something went horrible wrong, I am sorry"); 0 |
|
57 } |
|
58 } |
|
59 |
|
60 // DEBUGGING INFORMATION FOR COMPILERS!!! |
|
61 // |
|
62 // Compiler, even real ones, are fiendishly difficult to get |
|
63 // to produce correct code. One way to debug them is to run |
|
64 // example programs ``unoptimised''; and then optimised. Does |
|
65 // the optimised version still produce the same result? |
|
66 |
|
67 |
|
68 // for timing purposes |
|
69 def time_needed[T](n: Int, code: => T) = { |
13 def time_needed[T](n: Int, code: => T) = { |
70 val start = System.nanoTime() |
14 val start = System.nanoTime() |
71 for (i <- 0 until n) code |
15 for (i <- 0 until n) code |
72 val end = System.nanoTime() |
16 val end = System.nanoTime() |
73 (end - start)/(n * 1.0e9) |
17 (end - start)/(n * 1.0e9) |
74 } |
18 } |
75 |
19 |
76 |
20 type Mem = Map[Int, Int] |
77 |
21 |
78 // TASKS |
22 |
79 //======= |
23 import io.Source |
|
24 import scala.util._ |
|
25 |
|
26 def load_bff(name: String) : String = |
|
27 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
|
28 |
|
29 def sread(mem: Mem, mp: Int) : Int = |
|
30 mem.getOrElse(mp, 0) |
|
31 |
|
32 def write(mem: Mem, mp: Int, v: Int) : Mem = |
|
33 mem.updated(mp, v) |
|
34 |
|
35 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
36 if (prog.length <= pc) pc |
|
37 else (prog(pc), level) match { |
|
38 case (']', 0) => pc + 1 |
|
39 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
|
40 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
|
41 case (_, l) => jumpRight(prog, pc + 1, l) |
|
42 } |
|
43 } |
|
44 |
|
45 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
|
46 if (pc < 0) pc |
|
47 else (prog(pc), level) match { |
|
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 |
|
55 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
|
56 if (0 <= pc && pc < prog.length) { |
|
57 val (new_pc, new_mp, new_mem) = prog(pc) match { |
|
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 |
|
83 |
|
84 |
|
85 // DEBUGGING INFORMATION!!! |
|
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 |
80 |
95 |
81 // (5) Write a function jtable that precomputes the "jump |
96 // (5) Write a function jtable that precomputes the "jump |
82 // table" for a bf-program. This function takes a bf-program |
97 // table" for a bf-program. This function takes a bf-program |
83 // as an argument and Returns a Map[Int, Int]. The |
98 // as an argument and Returns a Map[Int, Int]. The |
84 // purpose of this map is to record the information about |
99 // purpose of this map is to record the information |
85 // pc positions where '[' or a ']' are stored. The information |
100 // that given on the position pc is a '[' or a ']', |
86 // is to which pc-position do we need to jump next? |
101 // then to which pc-position do we need to jump next? |
87 // |
102 // |
88 // For example for the program |
103 // For example for the program |
89 // |
104 // |
90 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
105 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
91 // |
106 // |
100 // on. The idea is to not calculate this information each time |
115 // on. The idea is to not calculate this information each time |
101 // we hit a bracket, but just look up this information in the |
116 // we hit a bracket, but just look up this information in the |
102 // jtable. You can use the jumpLeft and jumpRight functions |
117 // jtable. You can use the jumpLeft and jumpRight functions |
103 // from Part 1 for calculating the jtable. |
118 // from Part 1 for calculating the jtable. |
104 // |
119 // |
105 // Then adapt the compute and run functions from Part 1 |
120 // Then adapt the compute and run functions from Part 1 in order |
106 // in order to take advantage of the information stored in the jtable. |
121 // to take advantage of the information stored in the jtable. |
107 // This means whenever jumpLeft and jumpRight was called previously, |
122 // This means whenever jumpLeft and jumpRight was called previously, |
108 // you should immediately look up the jump address in the jtable. |
123 // you should look up the jump address in the jtable. |
109 // for ((char, index) <- str.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(str, index, 0)) |
|
110 |
124 |
111 |
125 |
112 def jtable(pg: String) : Map[Int, Int] = { |
126 def jtable(pg: String) : Map[Int, Int] = |
113 val table = for ((char, index) <- pg.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(pg, index, 0)) |
127 (0 until pg.length).collect { pc => pg(pc) match { |
114 table.toMap |
128 case '[' => (pc -> jumpRight(pg, pc + 1, 0)) |
115 } |
129 case ']' => (pc -> jumpLeft(pg, pc - 1, 0)) |
|
130 }}.toMap |
116 |
131 |
117 |
132 |
118 // testcase |
133 // testcase |
119 // |
|
120 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
134 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
121 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
135 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
122 |
136 |
123 |
137 |
124 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
138 def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
125 pc match { |
139 if (0 <= pc && pc < pg.length) { |
126 case pc: Int if (pc >= 0 && pc < pg.length) => { |
140 val (new_pc, new_mp, new_mem) = pg(pc) match { |
127 pg(pc) match { |
141 case '>' => (pc + 1, mp + 1, mem) |
128 case '>' => compute2(pg, tb, pc + 1, mp + 1, mem) |
142 case '<' => (pc + 1, mp - 1, mem) |
129 case '<' => compute2(pg, tb, pc + 1, mp - 1, mem) |
143 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
130 case '+' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
144 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
131 case '-' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
145 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
132 case '.' => print(sread(mem, mp).toChar); compute2(pg, tb, pc + 1, mp, mem) |
146 case '[' => |
133 case '[' => if (sread(mem, mp) == 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem) |
147 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
134 case ']' => if (sread(mem, mp) != 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem) |
148 case ']' => |
135 case '*' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) |
149 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
136 case '@' => compute2(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) |
150 case _ => (pc + 1, mp, mem) |
137 case '#' => print(sread(mem, mp)); compute2(pg, tb, pc + 1, mp, mem) |
151 } |
138 case _ => compute2(pg, tb, pc + 1, mp, mem) |
152 compute2(pg, tb, new_pc, new_mp, new_mem) |
139 } |
153 } |
140 } |
154 else mem |
141 case _ => mem |
155 } |
142 } |
156 |
143 } |
157 |
144 |
158 def run2(pg: String, m: Mem = Map()) = |
145 def run2(pg: String, m: Mem = Map()) = { |
|
146 compute2(pg, jtable(pg), 0, 0, m) |
159 compute2(pg, jtable(pg), 0, 0, m) |
147 } |
160 |
148 |
161 //time_needed(1, run2(load_bff("benchmark.bf"))) |
149 |
|
150 // testcases |
|
151 // time_needed(1, run2(load_bff("./main5/benchmark.bf"))) |
|
152 // time_needed(1, run2(load_bff("./main5/sierpinski.bf"))) |
|
153 |
162 |
154 |
163 |
155 |
164 |
156 // (6) Write a function optimise which deletes "dead code" (everything |
165 // (6) Write a function optimise which deletes "dead code" (everything |
157 // that is not a bf-command) and also replaces substrings of the form |
166 // that is not a bf-command) and also replaces substrings of the form |
159 // memory at the current location to 0. In the compute3 and run3 functions |
168 // memory at the current location to 0. In the compute3 and run3 functions |
160 // below you implement this command by writing the number 0 to mem(mp), |
169 // below you implement this command by writing the number 0 to mem(mp), |
161 // that is write(mem, mp, 0). |
170 // that is write(mem, mp, 0). |
162 // |
171 // |
163 // The easiest way to modify a string in this way is to use the regular |
172 // The easiest way to modify a string in this way is to use the regular |
164 // expression """[^<>+-.,\[\]]""", which recognises everything that is |
173 // expression """[^<>+-.\[\]""", which recognises everything that is |
165 // not a bf-command and replace it by the empty string. Similarly the |
174 // not a bf-command and replace it by the empty string. Similarly the |
166 // regular expression """\[-\]""" finds all occurrences of [-] and |
175 // regular expression """\[-\]""" finds all occurences of [-] and |
167 // by using the Scala method .replaceAll you can replace it with the |
176 // by using the Scala method .replaceAll you can repplace it with the |
168 // string "0" standing for the new bf-command. |
177 // string "0" standing for the new bf-command. |
169 // load_bff("./main5/mandelbrot.bf").replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0") |
|
170 |
|
171 // "Correct" regex |
|
172 // s.replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0") |
|
173 // s.replaceAll("""[^<>+-.,\[\]]""", "").replaceAll("""\[-\]""", "0") |
|
174 |
178 |
175 def optimise(s: String) : String = { |
179 def optimise(s: String) : String = { |
176 //s.replaceAll("""[^<>+-.\[\]@#*]""","") |
180 s.replaceAll("""[^<>+-.\[\]]""","") |
177 // .replaceAll("""\[-\]""", "0") |
181 .replaceAll("""\[-\]""", "0") |
178 s.replaceAll("""[^<>+-.\[\]]""", "").replaceAll("""\[-\]""", "0") |
182 } |
179 } |
183 |
180 |
184 |
181 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
185 def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
182 pc match { |
186 if (0 <= pc && pc < pg.length) { |
183 case pc: Int if (pc >= 0 && pc < pg.length) => { |
187 val (new_pc, new_mp, new_mem) = pg(pc) match { |
184 pg(pc) match { |
188 case '0' => (pc + 1, mp, write(mem, mp, 0)) |
185 case '>' => compute3(pg, tb, pc + 1, mp + 1, mem) |
189 case '>' => (pc + 1, mp + 1, mem) |
186 case '<' => compute3(pg, tb, pc + 1, mp - 1, mem) |
190 case '<' => (pc + 1, mp - 1, mem) |
187 case '+' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
191 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
188 case '-' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
192 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
189 case '.' => print(sread(mem, mp).toChar); compute3(pg, tb, pc + 1, mp, mem) |
193 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
190 case '[' => if (sread(mem, mp) == 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem) |
194 case '[' => |
191 case ']' => if (sread(mem, mp) != 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem) |
195 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
192 case '*' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) |
196 case ']' => |
193 case '@' => compute3(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) |
197 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
194 case '#' => print(sread(mem, mp)); compute3(pg, tb, pc + 1, mp, mem) |
198 case _ => (pc + 1, mp, mem) |
195 case '0' => compute3(pg, tb, pc + 1, mp, write(mem, mp, 0)) |
199 } |
196 case _ => compute3(pg, tb, pc + 1, mp, mem) |
200 compute3(pg, tb, new_pc, new_mp, new_mem) |
197 } |
201 } |
198 } |
202 else mem |
199 case _ => mem |
203 } |
200 } |
204 |
201 } |
205 def run3(pg: String, m: Mem = Map()) = { |
202 |
206 val pg_opt = optimise(pg) |
203 def run3(pg: String, m: Mem = Map()) = { |
207 compute3(pg_opt, jtable(pg_opt), 0, 0, m) |
204 val optimised = optimise(pg) |
|
205 compute3(optimised, jtable(optimised), 0, 0, m) |
|
206 } |
208 } |
207 |
209 |
208 |
210 |
209 // testcases |
211 // testcases |
210 // |
212 |
211 // optimise(load_bff("./main5/benchmark.bf")) // should have inserted 0's |
213 //println(optimise(load_bff("collatz.bf"))) |
212 // optimise(load_bff("./main5/mandelbrot.bf")).length // => 11205 |
214 //optimise(load_bff("benchmark.bf")) // should have inserted 0's |
213 // |
215 //optimise(load_bff("mandelbrot.bf")).length // => 11203 |
214 // time_needed(1, run3(load_bff("./main5/benchmark.bf"))) |
216 |
215 // time_needed(1, run3(load_bff("./main5/mandelbrot.bf"))) |
217 //time_needed(1, run3(load_bff("benchmark.bf"))) |
216 |
218 |
217 |
219 |
218 |
220 |
219 // (7) Write a function combine which replaces sequences |
221 // (7) Write a function combine which replaces sequences |
220 // of repeated increment and decrement commands by appropriate |
222 // of repated increment and decrement commands by appropriate |
221 // two-character commands. For example for sequences of + |
223 // two-character commands. For example for sequences of + |
222 // |
224 // |
223 // orig bf-cmds | replacement |
225 // orig bf-cmds | replacement |
224 // ------------------------------ |
226 // ------------------------------ |
225 // + | +A |
227 // + | +A |
235 // be unaffected by this change. |
237 // be unaffected by this change. |
236 // |
238 // |
237 // Adapt the compute4 and run4 functions such that they can deal |
239 // Adapt the compute4 and run4 functions such that they can deal |
238 // appropriately with such two-character commands. |
240 // appropriately with such two-character commands. |
239 |
241 |
240 // val alphabet = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ" |
242 def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { |
241 val alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" |
243 case (Nil, acc) => acc |
242 |
244 case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc) |
243 // Try any alphabet, it will work as long as the character is recognised and the characters are unique |
245 case (']' :: cs, acc) => splice(cs, (']', 1) :: acc) |
244 |
246 case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc) |
245 def get_number_from_character(char: Char) : Int = { |
247 case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc) |
246 alphabet.indexOf(char) + 1 |
248 case (c :: cs, Nil) => splice(cs, List((c, 1))) |
247 } |
249 case (c :: cs, (d, n) :: acc) => |
248 |
250 if (c == d && n < 26) splice(cs, (c, n + 1) :: acc) |
249 def get_character_from_number(int: Int) : Char = { |
251 else splice(cs, (c, 1) :: (d, n) :: acc) |
250 alphabet(int - 1) |
252 } |
251 } |
253 |
252 |
254 def spl(s: String) = splice(s.toList, Nil).reverse |
253 @annotation.tailrec |
255 |
254 def split_by_repetition(string : String, list : List[String] = Nil) : List[String] = { |
256 //spl(load_bff("benchmark.bf")) |
255 if(string.size == 0) list.reverse |
|
256 else { |
|
257 val (left_substring, right_substring) = string.span(_ == string(0)) |
|
258 split_by_repetition(right_substring, left_substring :: list) |
|
259 } |
|
260 } |
|
261 |
257 |
262 def combine(s: String) : String = { |
258 def combine(s: String) : String = { |
263 val split_strings = split_by_repetition(s) |
259 (for ((c, n) <- spl(s)) yield c match { |
264 val lists = for (string <- split_strings) yield { |
260 case '>' => List('>', (n + '@').toChar) |
265 if (List("+"(0), "-"(0), "<"(0), ">"(0)).contains(string.head)) { |
261 case '<' => List('<', (n + '@').toChar) |
266 val long_repeat = s"${string.head}${alphabet.last}" * (string.size / alphabet.length) |
262 case '+' => List('+', (n + '@').toChar) |
267 val short_repeat = if ((string.size % alphabet.length) != 0) s"${string.head}${get_character_from_number(string.size % alphabet.length)}" else "" |
263 case '-' => List('-', (n + '@').toChar) |
268 long_repeat + short_repeat |
264 case _ => List(c) |
269 } else string |
265 }).flatten.mkString |
270 } |
266 } |
271 lists.mkString("") |
267 |
272 } |
268 |
273 |
269 //combine(load_bff("benchmark.bf")) |
274 // testcase |
|
275 // combine(load_bff("./main5/benchmark.bf")) |
|
276 |
|
277 |
270 |
278 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
271 def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { |
279 pc match { |
272 if (0 <= pc && pc < pg.length) { |
280 case pc: Int if (pc >= 0 && pc < pg.length) => { |
273 val (new_pc, new_mp, new_mem) = pg(pc) match { |
281 pg(pc) match { |
274 case '0' => (pc + 1, mp, write(mem, mp, 0)) |
282 case '>' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp + number, mem) |
275 case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem) |
283 case '<' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp - number, mem) |
276 case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem) |
284 case '+' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) + number)) |
277 case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@'))) |
285 case '-' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) - number)) |
278 case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@'))) |
286 case '.' => print(sread(mem, mp).toChar); compute4(pg, tb, pc + 1, mp, mem) |
279 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
287 case '[' => if (sread(mem, mp) == 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem) |
280 case '[' => |
288 case ']' => if (sread(mem, mp) != 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem) |
281 if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
289 case '*' => compute4(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1))) |
282 case ']' => |
290 case '@' => compute4(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1))) |
283 if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) |
291 case '#' => print(sread(mem, mp)); compute4(pg, tb, pc + 1, mp, mem) |
284 case _ => (pc + 1, mp, mem) |
292 case '0' => compute4(pg, tb, pc + 1, mp, write(mem, mp, 0)) |
285 } |
293 case _ => compute4(pg, tb, pc + 1, mp, mem) |
286 compute4(pg, tb, new_pc, new_mp, new_mem) |
294 } |
287 } |
295 } |
288 else mem |
296 case _ => mem |
289 } |
297 } |
290 |
298 } |
291 def run4(pg: String, m: Mem = Map()) = { |
299 |
292 val pg_opt = combine(optimise(pg)) |
300 |
293 compute4(pg_opt, jtable(pg_opt), 0, 0, m) |
301 // should call first optimise and then combine on the input string |
294 } |
302 // |
|
303 def run4(pg: String, m: Mem = Map()) = { |
|
304 val processed_prog = combine(optimise(pg)) |
|
305 compute4(processed_prog, jtable(processed_prog), 0, 0, m) |
|
306 } |
|
307 |
|
308 |
295 |
309 // testcases |
296 // testcases |
310 // combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
297 //println(combine(optimise(load_bff("mandelbrot.bf").drop(123)))) |
311 |
298 |
312 // testcases (they should now run much faster) |
299 //combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
313 // time_needed(1, run4(load_bff("./main5/benchmark.bf"))) |
300 |
314 // time_needed(1, run4(load_bff("./main5/sierpinski.bf"))) |
301 //time_needed(1, run4(load_bff("benchmark.bf"))) |
315 // time_needed(1, run4(load_bff("./main5/mandelbrot.bf"))) |
302 |
316 |
303 //time_needed(1, run(load_bff("sierpinski.bf"))) |
317 |
304 //time_needed(1, run4(load_bff("sierpinski.bf"))) |
318 } |
305 |
|
306 //println(time_needed(1, run4(load_bff("mandelbrot.bf")))) |
|
307 |
|
308 |
|
309 |
|
310 |
|
311 |
|
312 } |
|
313 |
|
314 /* |
|
315 import CW10b._ |
|
316 println(time_needed(1, run(load_bff("collatz.bf")))) |
|
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 */ |