|
1 // Part 2 about a "Compiler" for the Brainf*** language |
|
2 //====================================================== |
|
3 |
|
4 // !!! Copy any function you need from file bf.scala !!! |
|
5 // |
|
6 // If you need any auxiliary function, feel free to |
|
7 // implement it, but do not make any changes to the |
|
8 // templates below. |
|
9 |
|
10 def time_needed[T](n: Int, code: => T) = { |
|
11 val start = System.nanoTime() |
|
12 for (i <- 0 until n) code |
|
13 val end = System.nanoTime() |
|
14 (end - start)/(n * 1.0e9) |
|
15 } |
|
16 |
|
17 type Mem = Map[Int, Int] |
|
18 |
|
19 import io.Source |
|
20 import scala.util._ |
|
21 |
|
22 // !! COPY from your bf.scala !! |
|
23 |
|
24 // def load_bff(name: String) : String = ... |
|
25 |
|
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 |
|
58 // (5) Write a function jtable that precomputes the "jump |
|
59 // table" for a bf-program. This function takes a bf-program |
|
60 // as an argument and Returns a Map[Int, Int]. The |
|
61 // purpose of this map is to record the information |
|
62 // that given on the position pc is a '[' or a ']', |
|
63 // then to which pc-position do we need to jump next? |
|
64 // |
|
65 // For example for the program |
|
66 // |
|
67 // "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" |
|
68 // |
|
69 // we obtain the map |
|
70 // |
|
71 // Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
|
72 // |
|
73 // This states that for the '[' on position 5, we need to |
|
74 // jump to position 20, which is just after the corresponding ']'. |
|
75 // Similarly, for the ']' on position 19, we need to jump to |
|
76 // position 6, which is just after the '[' on position 5, and so |
|
77 // on. The idea is to not calculate this information each time |
|
78 // we hit a bracket, but just look up this information in the |
|
79 // jtable. You can use the jumpLeft and jumpRight functions |
|
80 // from Part 1 for calculating the jtable. |
|
81 // |
|
82 // Then adapt the compute and run functions from Part 1 in order |
|
83 // to take advantage of the information stored in the jtable. |
|
84 // This means whenever jumpLeft and jumpRight was called previously, |
|
85 // you should look up the jump address in the jtable. |
|
86 |
|
87 |
|
88 //def jtable(pg: String) : Map[Int, Int] = ... |
|
89 |
|
90 // testcase |
|
91 // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
|
92 // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) |
|
93 |
|
94 |
|
95 //def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
|
96 |
|
97 //def run2(pg: String, m: Mem = Map()) = ... |
|
98 |
|
99 |
|
100 //testcase |
|
101 //time_needed(1, run2(load_bff("benchmark.bf"))) |
|
102 |
|
103 |
|
104 |
|
105 // (6) Write a function optimise which deletes "dead code" (everything |
|
106 // that is not a bf-command) and also replaces substrings of the form |
|
107 // [-] by a new command 0. The idea is that the loop [-] just resets the |
|
108 // memory at the current location to 0. In the compute3 and run3 functions |
|
109 // below you implement this command by writing the number 0 to mem(mp), |
|
110 // that is write(mem, mp, 0). |
|
111 // |
|
112 // The easiest way to modify a string in this way is to use the regular |
|
113 // expression """[^<>+-.,\[\]]""", which recognises everything that is |
|
114 // not a bf-command and replace it by the empty string. Similarly the |
|
115 // regular expression """\[-\]""" finds all occurrences of [-] and |
|
116 // by using the Scala method .replaceAll you can replace it with the |
|
117 // string "0" standing for the new bf-command. |
|
118 |
|
119 //def optimise(s: String) : String = ... |
|
120 |
|
121 //def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
|
122 |
|
123 //def run3(pg: String, m: Mem = Map()) = ... |
|
124 |
|
125 |
|
126 // testcases |
|
127 |
|
128 //optimise(load_bff("benchmark.bf")) // should have inserted 0's |
|
129 //optimise(load_bff("mandelbrot.bf")).length // => 11203 |
|
130 |
|
131 //time_needed(1, run3(load_bff("benchmark.bf"))) |
|
132 |
|
133 |
|
134 |
|
135 // (7) Write a function combine which replaces sequences |
|
136 // of repeated increment and decrement commands by appropriate |
|
137 // two-character commands. For example for sequences of + |
|
138 // |
|
139 // orig bf-cmds | replacement |
|
140 // ------------------------------ |
|
141 // + | +A |
|
142 // ++ | +B |
|
143 // +++ | +C |
|
144 // | |
|
145 // ... | |
|
146 // | |
|
147 // +++....+++ | +Z |
|
148 // (where length = 26) |
|
149 // |
|
150 // Similar for the bf-command -, > and <. All other commands should |
|
151 // be unaffected by this change. |
|
152 // |
|
153 // Adapt the compute4 and run4 functions such that they can deal |
|
154 // appropriately with such two-character commands. |
|
155 |
|
156 |
|
157 //def combine(s: String) : String = ... |
|
158 |
|
159 |
|
160 // testcase |
|
161 //combine(load_bff("benchmark.bf")) |
|
162 |
|
163 //def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = ... |
|
164 |
|
165 // should call first optimise and then combine on the input string |
|
166 //def run4(pg: String, m: Mem = Map()) = ... |
|
167 |
|
168 |
|
169 // testcases |
|
170 //combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[.....""" |
|
171 |
|
172 //time_needed(1, run4(load_bff("benchmark.bf"))) |
|
173 |
|
174 //time_needed(1, run(load_bff("sierpinski.bf"))) |
|
175 //time_needed(1, run4(load_bff("sierpinski.bf"))) |
|
176 |
|
177 //time_needed(1, run4(load_bff("mandelbrot.bf"))) |
|
178 |
|
179 |