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