|
384
|
1 |
// Core Part about a "Compiler" for the Brainf*** language
|
|
235
|
2 |
//======================================================
|
|
|
3 |
|
|
384
|
4 |
|
|
286
|
5 |
object CW10b {
|
|
235
|
6 |
|
|
384
|
7 |
|
|
235
|
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 |
|
|
384
|
14 |
type Mem = Map[Int, Int]
|
|
235
|
15 |
|
|
384
|
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
|
|
235
|
69 |
def time_needed[T](n: Int, code: => T) = {
|
|
|
70 |
val start = System.nanoTime()
|
|
|
71 |
for (i <- 0 until n) code
|
|
|
72 |
val end = System.nanoTime()
|
|
|
73 |
(end - start)/(n * 1.0e9)
|
|
|
74 |
}
|
|
|
75 |
|
|
|
76 |
|
|
|
77 |
|
|
384
|
78 |
// TASKS
|
|
|
79 |
//=======
|
|
235
|
80 |
|
|
|
81 |
// (5) Write a function jtable that precomputes the "jump
|
|
|
82 |
// table" for a bf-program. This function takes a bf-program
|
|
|
83 |
// as an argument and Returns a Map[Int, Int]. The
|
|
384
|
84 |
// purpose of this map is to record the information about
|
|
|
85 |
// pc positions where '[' or a ']' are stored. The information
|
|
|
86 |
// is to which pc-position do we need to jump next?
|
|
235
|
87 |
//
|
|
|
88 |
// For example for the program
|
|
|
89 |
//
|
|
|
90 |
// "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"
|
|
|
91 |
//
|
|
|
92 |
// we obtain the map
|
|
|
93 |
//
|
|
|
94 |
// Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
|
|
|
95 |
//
|
|
|
96 |
// This states that for the '[' on position 5, we need to
|
|
|
97 |
// jump to position 20, which is just after the corresponding ']'.
|
|
|
98 |
// Similarly, for the ']' on position 19, we need to jump to
|
|
|
99 |
// position 6, which is just after the '[' on position 5, and so
|
|
|
100 |
// on. The idea is to not calculate this information each time
|
|
|
101 |
// we hit a bracket, but just look up this information in the
|
|
|
102 |
// jtable. You can use the jumpLeft and jumpRight functions
|
|
|
103 |
// from Part 1 for calculating the jtable.
|
|
|
104 |
//
|
|
384
|
105 |
// Then adapt the compute and run functions from Part 1
|
|
|
106 |
// in order to take advantage of the information stored in the jtable.
|
|
235
|
107 |
// This means whenever jumpLeft and jumpRight was called previously,
|
|
384
|
108 |
// you should immediately 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))
|
|
235
|
110 |
|
|
|
111 |
|
|
384
|
112 |
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))
|
|
|
114 |
table.toMap
|
|
|
115 |
}
|
|
235
|
116 |
|
|
|
117 |
|
|
|
118 |
// testcase
|
|
384
|
119 |
//
|
|
235
|
120 |
// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
|
|
|
121 |
// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
|
|
|
122 |
|
|
|
123 |
|
|
|
124 |
def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
384
|
125 |
pc match {
|
|
|
126 |
case pc: Int if (pc >= 0 && pc < pg.length) => {
|
|
|
127 |
pg(pc) match {
|
|
|
128 |
case '>' => compute2(pg, tb, pc + 1, mp + 1, mem)
|
|
|
129 |
case '<' => compute2(pg, tb, pc + 1, mp - 1, mem)
|
|
|
130 |
case '+' => compute2(pg, tb, 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))
|
|
|
132 |
case '.' => print(sread(mem, mp).toChar); compute2(pg, tb, pc + 1, mp, mem)
|
|
|
133 |
case '[' => if (sread(mem, mp) == 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, 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)
|
|
|
135 |
case '*' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
|
|
|
136 |
case '@' => compute2(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
|
|
|
137 |
case '#' => print(sread(mem, mp)); compute2(pg, tb, pc + 1, mp, mem)
|
|
|
138 |
case _ => compute2(pg, tb, pc + 1, mp, mem)
|
|
|
139 |
}
|
|
|
140 |
}
|
|
|
141 |
case _ => mem
|
|
235
|
142 |
}
|
|
384
|
143 |
}
|
|
|
144 |
|
|
|
145 |
def run2(pg: String, m: Mem = Map()) = {
|
|
|
146 |
compute2(pg, jtable(pg), 0, 0, m)
|
|
235
|
147 |
}
|
|
|
148 |
|
|
|
149 |
|
|
384
|
150 |
// testcases
|
|
|
151 |
// time_needed(1, run2(load_bff("./main5/benchmark.bf")))
|
|
|
152 |
// time_needed(1, run2(load_bff("./main5/sierpinski.bf")))
|
|
235
|
153 |
|
|
|
154 |
|
|
|
155 |
|
|
|
156 |
// (6) Write a function optimise which deletes "dead code" (everything
|
|
|
157 |
// that is not a bf-command) and also replaces substrings of the form
|
|
|
158 |
// [-] by a new command 0. The idea is that the loop [-] just resets the
|
|
|
159 |
// 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),
|
|
|
161 |
// that is write(mem, mp, 0).
|
|
|
162 |
//
|
|
|
163 |
// The easiest way to modify a string in this way is to use the regular
|
|
|
164 |
// expression """[^<>+-.,\[\]]""", which recognises everything that is
|
|
|
165 |
// not a bf-command and replace it by the empty string. Similarly the
|
|
384
|
166 |
// regular expression """\[-\]""" finds all occurrences of [-] and
|
|
|
167 |
// by using the Scala method .replaceAll you can replace it with the
|
|
235
|
168 |
// string "0" standing for the new bf-command.
|
|
384
|
169 |
// load_bff("./main5/mandelbrot.bf").replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")
|
|
235
|
170 |
|
|
384
|
171 |
// "Correct" regex
|
|
|
172 |
// s.replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")
|
|
|
173 |
// s.replaceAll("""[^<>+-.,\[\]]""", "").replaceAll("""\[-\]""", "0")
|
|
235
|
174 |
|
|
384
|
175 |
def optimise(s: String) : String = {
|
|
|
176 |
//s.replaceAll("""[^<>+-.\[\]@#*]""","")
|
|
|
177 |
// .replaceAll("""\[-\]""", "0")
|
|
|
178 |
s.replaceAll("""[^<>+-.\[\]]""", "").replaceAll("""\[-\]""", "0")
|
|
|
179 |
}
|
|
235
|
180 |
|
|
|
181 |
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
384
|
182 |
pc match {
|
|
|
183 |
case pc: Int if (pc >= 0 && pc < pg.length) => {
|
|
|
184 |
pg(pc) match {
|
|
|
185 |
case '>' => compute3(pg, tb, pc + 1, mp + 1, mem)
|
|
|
186 |
case '<' => compute3(pg, tb, pc + 1, mp - 1, mem)
|
|
|
187 |
case '+' => compute3(pg, tb, 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))
|
|
|
189 |
case '.' => print(sread(mem, mp).toChar); compute3(pg, tb, 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)
|
|
|
191 |
case ']' => if (sread(mem, mp) != 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem)
|
|
|
192 |
case '*' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
|
|
|
193 |
case '@' => compute3(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
|
|
|
194 |
case '#' => print(sread(mem, mp)); compute3(pg, tb, pc + 1, mp, mem)
|
|
|
195 |
case '0' => compute3(pg, tb, pc + 1, mp, write(mem, mp, 0))
|
|
|
196 |
case _ => compute3(pg, tb, pc + 1, mp, mem)
|
|
|
197 |
}
|
|
|
198 |
}
|
|
|
199 |
case _ => mem
|
|
235
|
200 |
}
|
|
|
201 |
}
|
|
|
202 |
|
|
384
|
203 |
def run3(pg: String, m: Mem = Map()) = {
|
|
|
204 |
val optimised = optimise(pg)
|
|
|
205 |
compute3(optimised, jtable(optimised), 0, 0, m)
|
|
235
|
206 |
}
|
|
|
207 |
|
|
|
208 |
|
|
|
209 |
// testcases
|
|
384
|
210 |
//
|
|
|
211 |
// optimise(load_bff("./main5/benchmark.bf")) // should have inserted 0's
|
|
|
212 |
// optimise(load_bff("./main5/mandelbrot.bf")).length // => 11205
|
|
|
213 |
//
|
|
|
214 |
// time_needed(1, run3(load_bff("./main5/benchmark.bf")))
|
|
|
215 |
// time_needed(1, run3(load_bff("./main5/mandelbrot.bf")))
|
|
235
|
216 |
|
|
|
217 |
|
|
|
218 |
|
|
|
219 |
// (7) Write a function combine which replaces sequences
|
|
384
|
220 |
// of repeated increment and decrement commands by appropriate
|
|
235
|
221 |
// two-character commands. For example for sequences of +
|
|
|
222 |
//
|
|
|
223 |
// orig bf-cmds | replacement
|
|
|
224 |
// ------------------------------
|
|
|
225 |
// + | +A
|
|
|
226 |
// ++ | +B
|
|
|
227 |
// +++ | +C
|
|
|
228 |
// |
|
|
|
229 |
// ... |
|
|
|
230 |
// |
|
|
|
231 |
// +++....+++ | +Z
|
|
|
232 |
// (where length = 26)
|
|
|
233 |
//
|
|
|
234 |
// Similar for the bf-command -, > and <. All other commands should
|
|
|
235 |
// be unaffected by this change.
|
|
|
236 |
//
|
|
|
237 |
// Adapt the compute4 and run4 functions such that they can deal
|
|
|
238 |
// appropriately with such two-character commands.
|
|
|
239 |
|
|
384
|
240 |
// val alphabet = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"
|
|
|
241 |
val alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
|
|
|
242 |
|
|
|
243 |
// Try any alphabet, it will work as long as the character is recognised and the characters are unique
|
|
|
244 |
|
|
|
245 |
def get_number_from_character(char: Char) : Int = {
|
|
|
246 |
alphabet.indexOf(char) + 1
|
|
|
247 |
}
|
|
|
248 |
|
|
|
249 |
def get_character_from_number(int: Int) : Char = {
|
|
|
250 |
alphabet(int - 1)
|
|
|
251 |
}
|
|
|
252 |
|
|
|
253 |
@annotation.tailrec
|
|
|
254 |
def split_by_repetition(string : String, list : List[String] = Nil) : List[String] = {
|
|
|
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 |
}
|
|
235
|
260 |
}
|
|
|
261 |
|
|
384
|
262 |
def combine(s: String) : String = {
|
|
|
263 |
val split_strings = split_by_repetition(s)
|
|
|
264 |
val lists = for (string <- split_strings) yield {
|
|
|
265 |
if (List("+"(0), "-"(0), "<"(0), ">"(0)).contains(string.head)) {
|
|
|
266 |
val long_repeat = s"${string.head}${alphabet.last}" * (string.size / alphabet.length)
|
|
|
267 |
val short_repeat = if ((string.size % alphabet.length) != 0) s"${string.head}${get_character_from_number(string.size % alphabet.length)}" else ""
|
|
|
268 |
long_repeat + short_repeat
|
|
|
269 |
} else string
|
|
|
270 |
}
|
|
|
271 |
lists.mkString("")
|
|
|
272 |
}
|
|
235
|
273 |
|
|
384
|
274 |
// testcase
|
|
|
275 |
// combine(load_bff("./main5/benchmark.bf"))
|
|
|
276 |
|
|
235
|
277 |
|
|
384
|
278 |
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
|
279 |
pc match {
|
|
|
280 |
case pc: Int if (pc >= 0 && pc < pg.length) => {
|
|
|
281 |
pg(pc) match {
|
|
|
282 |
case '>' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp + number, mem)
|
|
|
283 |
case '<' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp - number, 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))
|
|
|
285 |
case '-' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) - number))
|
|
|
286 |
case '.' => print(sread(mem, mp).toChar); compute4(pg, tb, 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)
|
|
|
288 |
case ']' => if (sread(mem, mp) != 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem)
|
|
|
289 |
case '*' => compute4(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))
|
|
|
290 |
case '@' => compute4(pg, tb, pc + 1, mp, write(mem, mem(mp), sread(mem, mp - 1)))
|
|
|
291 |
case '#' => print(sread(mem, mp)); compute4(pg, tb, pc + 1, mp, mem)
|
|
|
292 |
case '0' => compute4(pg, tb, pc + 1, mp, write(mem, mp, 0))
|
|
|
293 |
case _ => compute4(pg, tb, pc + 1, mp, mem)
|
|
|
294 |
}
|
|
|
295 |
}
|
|
|
296 |
case _ => mem
|
|
|
297 |
}
|
|
235
|
298 |
}
|
|
|
299 |
|
|
|
300 |
|
|
384
|
301 |
// should call first optimise and then combine on the input string
|
|
|
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)
|
|
235
|
306 |
}
|
|
|
307 |
|
|
|
308 |
|
|
|
309 |
// testcases
|
|
384
|
310 |
// combine(optimise(load_bff("./main5/benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
|
|
235
|
311 |
|
|
384
|
312 |
// testcases (they should now run much faster)
|
|
|
313 |
// time_needed(1, run4(load_bff("./main5/benchmark.bf")))
|
|
|
314 |
// time_needed(1, run4(load_bff("./main5/sierpinski.bf")))
|
|
|
315 |
// time_needed(1, run4(load_bff("./main5/mandelbrot.bf")))
|
|
235
|
316 |
|
|
|
317 |
|
|
286
|
318 |
}
|