|
494
|
1 |
// Main Part 5 about a "Compiler" for the Brainf*** language
|
|
|
2 |
//============================================================
|
|
|
3 |
|
|
232
|
4 |
|
|
404
|
5 |
object M5b {
|
|
232
|
6 |
|
|
|
7 |
// !!! Copy any function you need from file bf.scala !!!
|
|
|
8 |
//
|
|
|
9 |
// If you need any auxiliary function, feel free to
|
|
|
10 |
// implement it, but do not make any changes to the
|
|
|
11 |
// templates below.
|
|
|
12 |
|
|
|
13 |
|
|
494
|
14 |
// DEBUGGING INFORMATION FOR COMPILERS!!!
|
|
|
15 |
//
|
|
|
16 |
// Compiler, even real ones, are fiendishly difficult to get
|
|
|
17 |
// to produce correct code. One way to debug them is to run
|
|
|
18 |
// example programs ``unoptimised''; and then optimised. Does
|
|
|
19 |
// the optimised version still produce the same result?
|
|
|
20 |
|
|
|
21 |
|
|
|
22 |
// for timing purposes
|
|
|
23 |
def time_needed[T](n: Int, code: => T) ={
|
|
232
|
24 |
val start = System.nanoTime()
|
|
|
25 |
for (i <- 0 until n) code
|
|
|
26 |
val end = System.nanoTime()
|
|
|
27 |
(end - start)/(n * 1.0e9)
|
|
|
28 |
}
|
|
|
29 |
|
|
494
|
30 |
|
|
232
|
31 |
type Mem = Map[Int, Int]
|
|
|
32 |
|
|
|
33 |
import io.Source
|
|
|
34 |
import scala.util._
|
|
|
35 |
|
|
494
|
36 |
// ADD YOUR CODE BELOW
|
|
|
37 |
//======================
|
|
232
|
38 |
|
|
494
|
39 |
def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem =
|
|
232
|
40 |
|
|
494
|
41 |
if(pc<0 || pc>= prog.length())
|
|
|
42 |
mem
|
|
|
43 |
else
|
|
|
44 |
prog.charAt(pc) match
|
|
|
45 |
case '>' => compute(prog, pc+1, mp+1, mem)
|
|
232
|
46 |
|
|
494
|
47 |
case '<' => compute(prog, pc+1, mp-1, mem)
|
|
232
|
48 |
|
|
494
|
49 |
case '+' => compute(prog, pc+1, mp, write(mem, mp, sread(mem, mp)+1))
|
|
232
|
50 |
|
|
494
|
51 |
case '-' => compute(prog, pc+1, mp, write(mem, mp, sread(mem, mp)-1))
|
|
233
|
52 |
|
|
494
|
53 |
case '.' =>
|
|
|
54 |
compute(prog, pc+1, mp, mem)
|
|
232
|
55 |
|
|
494
|
56 |
case '[' =>
|
|
|
57 |
if(sread(mem, mp) == 0)
|
|
|
58 |
compute(prog, jumpRight(prog, pc+1, 0), mp, mem)
|
|
|
59 |
else
|
|
|
60 |
compute(prog, pc+1, mp, mem)
|
|
232
|
61 |
|
|
494
|
62 |
case ']' =>
|
|
|
63 |
if(sread(mem, mp) == 0)
|
|
|
64 |
compute(prog, pc+1, mp, mem)
|
|
|
65 |
else
|
|
|
66 |
compute(prog, jumpLeft(prog, pc-1, 0), mp, mem)
|
|
232
|
67 |
|
|
494
|
68 |
case _ => compute(prog, pc + 1, mp, mem)
|
|
232
|
69 |
|
|
|
70 |
|
|
233
|
71 |
|
|
494
|
72 |
def run(prog: String, m: Mem = Map()) =
|
|
|
73 |
compute(prog, 0, 0, m)
|
|
|
74 |
|
|
|
75 |
|
|
|
76 |
// (6)
|
|
|
77 |
def jumpRight(prog: String, pc: Int, level: Int) : Int =
|
|
|
78 |
if (pc<0 || pc>= prog.length() )
|
|
|
79 |
pc
|
|
|
80 |
else
|
|
|
81 |
prog(pc) match
|
|
|
82 |
case '[' => jumpRight(prog, pc+1, level+1)
|
|
|
83 |
|
|
|
84 |
case ']' =>
|
|
|
85 |
{
|
|
|
86 |
if (level == 0)
|
|
|
87 |
pc+1
|
|
|
88 |
else
|
|
|
89 |
jumpRight(prog, pc+1, level-1)
|
|
|
90 |
|
|
|
91 |
}
|
|
|
92 |
|
|
|
93 |
case _ => jumpRight(prog, pc+1, level)
|
|
|
94 |
|
|
232
|
95 |
|
|
494
|
96 |
def jumpLeft(prog: String, pc: Int, level: Int) : Int =
|
|
|
97 |
if (pc<0 || pc>= prog.length() )
|
|
|
98 |
pc
|
|
|
99 |
else
|
|
|
100 |
prog(pc) match
|
|
|
101 |
case '[' =>
|
|
|
102 |
{
|
|
|
103 |
if (level == 0)
|
|
|
104 |
pc+1
|
|
|
105 |
else
|
|
|
106 |
jumpLeft(prog, pc-1, level-1)
|
|
|
107 |
|
|
|
108 |
}
|
|
|
109 |
|
|
|
110 |
case ']' => jumpLeft(prog, pc-1, level+1)
|
|
|
111 |
|
|
|
112 |
case _ => jumpLeft(prog, pc-1, level)
|
|
|
113 |
|
|
|
114 |
|
|
|
115 |
def jtable(pg: String) : Map[Int, Int] =
|
|
|
116 |
val b1 = (0 until pg.length)
|
|
|
117 |
.filter(n => pg.substring(n, n+1) == "[")
|
|
|
118 |
.map(n => n -> jumpRight(pg, n + 1, 0)).toMap
|
|
|
119 |
|
|
|
120 |
val b2 = (0 until pg.length)
|
|
|
121 |
.filter(n => pg.substring(n, n+1) == "]")
|
|
|
122 |
.map(n => n -> jumpLeft(pg, n-1, 0)).toMap
|
|
|
123 |
|
|
|
124 |
b1++b2
|
|
232
|
125 |
|
|
233
|
126 |
|
|
494
|
127 |
// testcase
|
|
|
128 |
//
|
|
|
129 |
// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
|
|
|
130 |
// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
|
|
|
131 |
|
|
|
132 |
def load_bff(name: String) : String =
|
|
|
133 |
try
|
|
|
134 |
Source.fromFile(name).mkString
|
|
|
135 |
catch
|
|
|
136 |
case e: Exception => ""
|
|
|
137 |
|
|
|
138 |
def sread(mem: Mem, mp: Int) : Int =
|
|
|
139 |
mem.getOrElse(mp,0)
|
|
|
140 |
|
|
|
141 |
def write(mem: Mem, mp: Int, v: Int) : Mem =
|
|
|
142 |
mem + (mp -> v)
|
|
|
143 |
|
|
|
144 |
def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem =
|
|
|
145 |
|
|
|
146 |
if(pc<0 || pc>= pg.length())
|
|
|
147 |
mem
|
|
|
148 |
else
|
|
|
149 |
pg.charAt(pc) match
|
|
|
150 |
case '>' => compute2(pg,tb, pc+1, mp+1, mem)
|
|
232
|
151 |
|
|
494
|
152 |
case '<' => compute2(pg,tb, pc+1, mp-1, mem)
|
|
|
153 |
|
|
|
154 |
case '+' => compute2(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)+1))
|
|
|
155 |
|
|
|
156 |
case '-' => compute2(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)-1))
|
|
|
157 |
|
|
|
158 |
case '.' =>
|
|
|
159 |
compute2(pg,tb, pc+1, mp, mem)
|
|
232
|
160 |
|
|
494
|
161 |
case '[' =>
|
|
|
162 |
if(sread(mem, mp) == 0)
|
|
|
163 |
compute2(pg, tb, tb(pc), mp, mem)
|
|
|
164 |
else
|
|
|
165 |
compute2(pg, tb, pc+1, mp, mem)
|
|
|
166 |
|
|
|
167 |
case ']' =>
|
|
|
168 |
if(sread(mem, mp) == 0)
|
|
|
169 |
compute2(pg, tb, pc+1, mp, mem)
|
|
|
170 |
else
|
|
|
171 |
compute2(pg, tb, tb(pc), mp, mem)
|
|
|
172 |
|
|
|
173 |
case _ => compute2(pg,tb,pc + 1, mp, mem)
|
|
|
174 |
|
|
|
175 |
def run2(pg: String, m: Mem = Map()) =
|
|
|
176 |
compute2(pg, jtable(pg), 0, 0, m)
|
|
232
|
177 |
|
|
233
|
178 |
// testcases
|
|
494
|
179 |
// time_needed(1, run2(load_bff("benchmark.bf")))
|
|
|
180 |
// time_needed(1, run2(load_bff("sierpinski.bf")))
|
|
233
|
181 |
|
|
232
|
182 |
|
|
|
183 |
|
|
494
|
184 |
// (7)
|
|
232
|
185 |
|
|
494
|
186 |
def optimise(s: String) : String =
|
|
|
187 |
val notCommand = """[^<>+\-.\[\]]""".r
|
|
|
188 |
val occurrence = """\[-\]""".r
|
|
232
|
189 |
|
|
494
|
190 |
val deleted = notCommand.replaceAllIn(s, "")
|
|
|
191 |
occurrence.replaceAllIn(deleted, "0")
|
|
232
|
192 |
|
|
|
193 |
|
|
494
|
194 |
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem =
|
|
|
195 |
|
|
|
196 |
if(pc<0 || pc>= pg.length())
|
|
|
197 |
mem
|
|
|
198 |
else
|
|
|
199 |
pg.charAt(pc) match
|
|
|
200 |
case '>' => compute3(pg,tb, pc+1, mp+1, mem)
|
|
|
201 |
|
|
|
202 |
case '<' => compute3(pg,tb, pc+1, mp-1, mem)
|
|
|
203 |
|
|
|
204 |
case '+' => compute3(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)+1))
|
|
|
205 |
|
|
|
206 |
case '-' => compute3(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)-1))
|
|
|
207 |
|
|
|
208 |
case '.' =>
|
|
|
209 |
compute3(pg,tb, pc+1, mp, mem)
|
|
232
|
210 |
|
|
494
|
211 |
case '[' =>
|
|
|
212 |
if(sread(mem, mp) == 0)
|
|
|
213 |
compute3(pg, tb, tb(pc), mp, mem)
|
|
|
214 |
else
|
|
|
215 |
compute3(pg, tb, pc+1, mp, mem)
|
|
232
|
216 |
|
|
494
|
217 |
case ']' =>
|
|
|
218 |
if(sread(mem, mp) == 0)
|
|
|
219 |
compute3(pg, tb, pc+1, mp, mem)
|
|
|
220 |
else
|
|
|
221 |
compute3(pg, tb, tb(pc), mp, mem)
|
|
|
222 |
|
|
|
223 |
case _ => compute3(pg,tb,pc + 1, mp, mem)
|
|
|
224 |
|
|
|
225 |
def run3(pg: String, m: Mem = Map()) =
|
|
|
226 |
val opt = optimise(pg)
|
|
|
227 |
compute3(opt, jtable(opt), 0, 0, m)
|
|
|
228 |
|
|
|
229 |
|
|
232
|
230 |
|
|
234
|
231 |
// testcases
|
|
494
|
232 |
//
|
|
|
233 |
// optimise(load_bff("benchmark.bf")) // should have inserted 0's
|
|
|
234 |
// optimise(load_bff("mandelbrot.bf")).length // => 11205
|
|
|
235 |
//
|
|
|
236 |
// time_needed(1, run3(load_bff("benchmark.bf")))
|
|
232
|
237 |
|
|
|
238 |
|
|
384
|
239 |
|
|
494
|
240 |
// (8)
|
|
|
241 |
// consider if the char does not exist\\
|
|
|
242 |
|
|
|
243 |
def counterHelper(chars: List[Char], consec: Int, charToCount: Char): Int =
|
|
|
244 |
chars match
|
|
|
245 |
case head :: tail if ((head == charToCount && head == tail.headOption.getOrElse(' ')) )=>
|
|
|
246 |
counterHelper(tail, consec + 1, charToCount)
|
|
|
247 |
|
|
|
248 |
case head :: tail if (head == charToCount && head != tail.headOption.getOrElse(' '))=>
|
|
|
249 |
consec+1
|
|
|
250 |
|
|
|
251 |
case head :: tail if (head != charToCount && head != tail.headOption.getOrElse(' '))=>
|
|
|
252 |
consec
|
|
|
253 |
|
|
|
254 |
|
|
|
255 |
def counter(input: String, charToCount: Char): Int =
|
|
|
256 |
counterHelper(input.toList, 0, charToCount)
|
|
|
257 |
|
|
|
258 |
def handleCharacter(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char], charToCount: Char): String =
|
|
|
259 |
val num = counter(orgin.substring(sindex), charToCount)
|
|
|
260 |
val lett = letterMap.getOrElse(num, "")
|
|
|
261 |
combineHelper(orgin, newstr + charToCount + lett, sindex + num, letterMap)
|
|
|
262 |
|
|
|
263 |
def combineHelper(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char] ): String =
|
|
|
264 |
if (sindex >= orgin.length())
|
|
|
265 |
newstr
|
|
|
266 |
else
|
|
|
267 |
val result =
|
|
|
268 |
orgin.charAt(sindex) match
|
|
|
269 |
case '>' => handleCharacter(orgin, newstr, sindex, letterMap, '>')
|
|
|
270 |
case '<' => handleCharacter(orgin, newstr, sindex, letterMap, '<')
|
|
|
271 |
case '+' => handleCharacter(orgin, newstr, sindex, letterMap, '+')
|
|
|
272 |
case '-' => handleCharacter(orgin, newstr, sindex, letterMap, '-')
|
|
|
273 |
case _ => combineHelper(orgin, newstr + orgin.charAt(sindex), sindex + 1, letterMap)
|
|
|
274 |
|
|
|
275 |
result
|
|
|
276 |
|
|
|
277 |
def combine(s: String) : String =
|
|
|
278 |
val letterMap = (1 to 26).zip('A' to 'Z').toMap
|
|
|
279 |
combineHelper(s,"",0, letterMap)
|
|
|
280 |
|
|
|
281 |
// testcase
|
|
|
282 |
// combine(load_bff("benchmark.bf"))
|
|
|
283 |
|
|
|
284 |
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem =
|
|
|
285 |
|
|
|
286 |
if(pc<0 || pc>= pg.length())
|
|
|
287 |
mem
|
|
|
288 |
else
|
|
|
289 |
pg.charAt(pc) match
|
|
|
290 |
case '>' => compute4(pg,tb, pc+1, mp+1, mem)
|
|
|
291 |
|
|
|
292 |
case '<' => compute4(pg,tb, pc+1, mp-1, mem)
|
|
|
293 |
|
|
|
294 |
case '+' => compute4(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)+1))
|
|
|
295 |
|
|
|
296 |
case '-' => compute4(pg,tb, pc+1, mp, write(mem, mp, sread(mem, mp)-1))
|
|
|
297 |
|
|
|
298 |
case '.' =>
|
|
|
299 |
compute4(pg,tb, pc+1, mp, mem)
|
|
|
300 |
|
|
|
301 |
case '[' =>
|
|
|
302 |
if(sread(mem, mp) == 0)
|
|
|
303 |
compute4(pg, tb, tb(pc), mp, mem)
|
|
|
304 |
else
|
|
|
305 |
compute4(pg, tb, pc+1, mp, mem)
|
|
|
306 |
|
|
|
307 |
case ']' =>
|
|
|
308 |
if(sread(mem, mp) == 0)
|
|
|
309 |
compute4(pg, tb, pc+1, mp, mem)
|
|
|
310 |
else
|
|
|
311 |
compute4(pg, tb, tb(pc), mp, mem)
|
|
|
312 |
|
|
|
313 |
case _ => compute4(pg,tb,pc + 1, mp, mem)
|
|
|
314 |
|
|
|
315 |
// should call first optimise and then combine on the input string
|
|
|
316 |
//
|
|
|
317 |
def run4(pg: String, m: Mem = Map()) =
|
|
|
318 |
val opt = optimise(pg)
|
|
|
319 |
val com= combine(opt)
|
|
|
320 |
compute4(com, jtable(com), 0, 0, m)
|
|
|
321 |
|
|
|
322 |
|
|
|
323 |
// testcases
|
|
|
324 |
// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
|
|
|
325 |
|
|
|
326 |
// testcases (they should now run much faster)
|
|
|
327 |
// time_needed(1, run4(load_bff("benchmark.bf")))
|
|
|
328 |
// time_needed(1, run4(load_bff("sierpinski.bf")))
|
|
|
329 |
// time_needed(1, run4(load_bff("mandelbrot.bf")))
|
|
384
|
330 |
|
|
|
331 |
|
|
290
|
332 |
}
|
|
336
|
333 |
|
|
482
|
334 |
|