1 // Part 2 about a "Compiler" for the Brainf*** language |
1 // Core Part about a "Compiler" for the Brainf*** language |
2 //====================================================== |
2 //====================================================== |
|
3 |
|
4 |
|
5 object CW10b { |
|
6 |
3 |
7 |
4 // !!! Copy any function you need from file bf.scala !!! |
8 // !!! Copy any function you need from file bf.scala !!! |
5 // |
9 // |
6 // If you need any auxiliary function, feel free to |
10 // If you need any auxiliary function, feel free to |
7 // implement it, but do not make any changes to the |
11 // implement it, but do not make any changes to the |
8 // templates below. |
12 // templates below. |
9 |
13 |
|
14 |
|
15 // DEBUGGING INFORMATION FOR COMPILERS!!! |
|
16 // |
|
17 // Compiler, even real ones, are fiendishly difficult to get |
|
18 // to produce correct code. One way to debug them is to run |
|
19 // example programs ``unoptimised''; and then optimised. Does |
|
20 // the optimised version still produce the same result? |
|
21 |
|
22 |
|
23 // for timing purposes |
10 def time_needed[T](n: Int, code: => T) = { |
24 def time_needed[T](n: Int, code: => T) = { |
11 val start = System.nanoTime() |
25 val start = System.nanoTime() |
12 for (i <- 0 until n) code |
26 for (i <- 0 until n) code |
13 val end = System.nanoTime() |
27 val end = System.nanoTime() |
14 (end - start)/(n * 1.0e9) |
28 (end - start)/(n * 1.0e9) |
15 } |
29 } |
16 |
30 |
|
31 |
17 type Mem = Map[Int, Int] |
32 type Mem = Map[Int, Int] |
18 |
33 |
19 import io.Source |
34 import io.Source |
20 import scala.util._ |
35 import scala.util._ |
21 |
36 |
22 // !! COPY from your bf.scala !! |
|
23 |
37 |
24 // def load_bff(name: String) : String = ... |
38 // TASKS |
25 |
39 //======= |
26 // def sread(mem: Mem, mp: Int) : Int = ... |
|
27 |
|
28 // def write(mem: Mem, mp: Int, v: Int) : Mem = ... |
|
29 |
|
30 // def jumpRight(prog: String, pc: Int, level: Int) : Int = ... |
|
31 |
|
32 // def jumpLeft(prog: String, pc: Int, level: Int) : Int = ... |
|
33 |
|
34 // def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ... |
|
35 |
|
36 // def run(prog: String, m: Mem = Map()) = |
|
37 |
|
38 // The baseline to what we can compare our "compiler" |
|
39 // implemented below. It should require something like |
|
40 // 60 seconds for the calculation on my laptop |
|
41 // |
|
42 //time_needed(1, run(load_bff("benchmark.bf"))) |
|
43 |
|
44 |
|
45 // DEBUGGING INFORMATION!!! |
|
46 // |
|
47 // Compiler, even real ones, are fiendishly difficult to get |
|
48 // to produce correct code. The point is that for example for |
|
49 // the Sierpinski program, they need to still generate code |
|
50 // that displays such a triangle. If yes, then one usually |
|
51 // can take comfort that all is well. If not, then something |
|
52 // went wrong during the optimisations. |
|
53 |
|
54 |
|
55 // ADVANCED TASKS |
|
56 //================ |
|
57 |
40 |
58 // (5) Write a function jtable that precomputes the "jump |
41 // (5) Write a function jtable that precomputes the "jump |
59 // table" for a bf-program. This function takes a bf-program |
42 // table" for a bf-program. This function takes a bf-program |
60 // as an argument and Returns a Map[Int, Int]. The |
43 // as an argument and Returns a Map[Int, Int]. The |
61 // purpose of this map is to record the information |
44 // purpose of this map is to record the information about |
62 // that given on the position pc is a '[' or a ']', |
45 // pc positions where '[' or a ']' are stored. The information |
63 // then to which pc-position do we need to jump next? |
46 // is to which pc-position do we need to jump next? |
64 // |
47 // |
65 // For example for the program |
48 // For example for the program |
66 // |
49 // |
67 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
50 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
68 // |
51 // |
77 // on. The idea is to not calculate this information each time |
60 // on. The idea is to not calculate this information each time |
78 // we hit a bracket, but just look up this information in the |
61 // we hit a bracket, but just look up this information in the |
79 // jtable. You can use the jumpLeft and jumpRight functions |
62 // jtable. You can use the jumpLeft and jumpRight functions |
80 // from Part 1 for calculating the jtable. |
63 // from Part 1 for calculating the jtable. |
81 // |
64 // |
82 // Then adapt the compute and run functions from Part 1 in order |
65 // Then adapt the compute and run functions from Part 1 |
83 // to take advantage of the information stored in the jtable. |
66 // in order to take advantage of the information stored in the jtable. |
84 // This means whenever jumpLeft and jumpRight was called previously, |
67 // This means whenever jumpLeft and jumpRight was called previously, |
85 // you should look up the jump address in the jtable. |
68 // you should immediately look up the jump address in the jtable. |
86 |
69 |
87 |
70 |
88 //def jtable(pg: String) : Map[Int, Int] = ... |
71 //def jtable(pg: String) : Map[Int, Int] = ... |
89 |
72 |
|
73 |
90 // testcase |
74 // testcase |
|
75 // |
91 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
76 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
92 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
77 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
93 |
78 |
94 |
79 |
95 //def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
80 //def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
96 |
|
97 //def run2(pg: String, m: Mem = Map()) = ... |
81 //def run2(pg: String, m: Mem = Map()) = ... |
98 |
82 |
99 |
83 |
100 //testcase |
84 // testcases |
101 //time_needed(1, run2(load_bff("benchmark.bf"))) |
85 // time_needed(1, run2(load_bff("benchmark.bf"))) |
|
86 // time_needed(1, run2(load_bff("seirpinski.bf"))) |
102 |
87 |
103 |
88 |
104 |
89 |
105 // (6) Write a function optimise which deletes "dead code" (everything |
90 // (6) Write a function optimise which deletes "dead code" (everything |
106 // that is not a bf-command) and also replaces substrings of the form |
91 // that is not a bf-command) and also replaces substrings of the form |
154 // appropriately with such two-character commands. |
139 // appropriately with such two-character commands. |
155 |
140 |
156 |
141 |
157 //def combine(s: String) : String = ... |
142 //def combine(s: String) : String = ... |
158 |
143 |
|
144 // testcase |
|
145 // combine(load_bff("benchmark.bf")) |
159 |
146 |
160 // testcase |
|
161 //combine(load_bff("benchmark.bf")) |
|
162 |
147 |
163 //def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
148 //def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
164 |
149 |
|
150 |
165 // should call first optimise and then combine on the input string |
151 // should call first optimise and then combine on the input string |
|
152 // |
166 //def run4(pg: String, m: Mem = Map()) = ... |
153 //def run4(pg: String, m: Mem = Map()) = ... |
167 |
154 |
168 |
155 |
169 // testcases |
156 // testcases |
170 //combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
157 // combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
171 |
158 |
172 //time_needed(1, run4(load_bff("benchmark.bf"))) |
159 // testcases (they should now run much faster) |
173 |
160 // time_needed(1, run4(load_bff("benchmark.bf"))) |
174 //time_needed(1, run(load_bff("sierpinski.bf"))) |
161 // time_needed(1, run4(load_bff("sierpinski.bf"))) |
175 //time_needed(1, run4(load_bff("sierpinski.bf"))) |
162 // time_needed(1, run4(load_bff("mandelbrot.bf"))) |
176 |
|
177 //time_needed(1, run4(load_bff("mandelbrot.bf"))) |
|
178 |
163 |
179 |
164 |
|
165 } |