|
460
|
1 |
// Main Part 5 about a "Compiler" for the Brainf*** language
|
|
|
2 |
//============================================================
|
|
|
3 |
|
|
235
|
4 |
|
|
404
|
5 |
object M5b {
|
|
384
|
6 |
|
|
235
|
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 |
|
|
460
|
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
|
|
235
|
23 |
def time_needed[T](n: Int, code: => T) = {
|
|
|
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 |
|
|
460
|
30 |
|
|
404
|
31 |
type Mem = Map[Int, Int]
|
|
235
|
32 |
|
|
404
|
33 |
import io.Source
|
|
|
34 |
import scala.util._
|
|
|
35 |
|
|
460
|
36 |
// ADD YOUR CODE BELOW
|
|
|
37 |
//======================
|
|
404
|
38 |
|
|
460
|
39 |
// (6)
|
|
404
|
40 |
def jumpRight(prog: String, pc: Int, level: Int) : Int = {
|
|
460
|
41 |
if (pc >= prog.length) prog.length
|
|
|
42 |
else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1)
|
|
|
43 |
else if (prog(pc) == ']' && level == 0) pc + 1
|
|
|
44 |
else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1)
|
|
|
45 |
else jumpRight(prog, pc + 1, level)
|
|
404
|
46 |
}
|
|
|
47 |
|
|
460
|
48 |
def jtable(pg: String) : Map[Int, Int] = {
|
|
|
49 |
val pairs = for {
|
|
|
50 |
i <- 0 until pg.length
|
|
|
51 |
if pg.charAt(i) == '['
|
|
|
52 |
j = jumpRight(pg, i+1, 0)
|
|
|
53 |
} yield (i, j)
|
|
|
54 |
pairs.flatMap { case (i, j) =>
|
|
|
55 |
List((i, j), (j-1, i+1))
|
|
|
56 |
}.toMap
|
|
|
57 |
}
|
|
|
58 |
|
|
|
59 |
def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v)
|
|
|
60 |
|
|
|
61 |
// testcase
|
|
|
62 |
//
|
|
|
63 |
// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
|
|
|
64 |
// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)
|
|
|
65 |
|
|
|
66 |
def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
|
67 |
if (pc >= pg.length) mem
|
|
|
68 |
else {
|
|
|
69 |
val (npc, nmp, nmem) = pg(pc) match {
|
|
|
70 |
case '>' => (pc + 1, mp + 1, mem)
|
|
|
71 |
case '<' => (pc + 1, mp - 1, mem)
|
|
|
72 |
case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
|
|
|
73 |
case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
|
|
|
74 |
case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
|
|
|
75 |
case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
76 |
case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
77 |
case _ => (pc + 1, mp, mem)
|
|
|
78 |
}
|
|
|
79 |
compute2(pg, tb, npc, nmp, nmem)
|
|
404
|
80 |
}
|
|
|
81 |
}
|
|
|
82 |
|
|
460
|
83 |
def run2(pg: String, m: Mem = Map()) =
|
|
|
84 |
compute2(pg, jtable(pg), 0, 0, m)
|
|
|
85 |
|
|
404
|
86 |
|
|
460
|
87 |
// testcases
|
|
|
88 |
// time_needed(1, run2(load_bff("benchmark.bf")))
|
|
|
89 |
// time_needed(1, run2(load_bff("sierpinski.bf")))
|
|
404
|
90 |
|
|
|
91 |
|
|
235
|
92 |
|
|
460
|
93 |
// (7)
|
|
|
94 |
|
|
|
95 |
def optimise(s: String) : String =
|
|
|
96 |
s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0")
|
|
235
|
97 |
|
|
460
|
98 |
def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
|
99 |
if (pc >= pg.length) mem
|
|
|
100 |
else {
|
|
|
101 |
val (npc, nmp, nmem) = pg(pc) match {
|
|
|
102 |
case '>' => (pc + 1, mp + 1, mem)
|
|
|
103 |
case '<' => (pc + 1, mp - 1, mem)
|
|
|
104 |
case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
|
|
|
105 |
case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
|
|
|
106 |
case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
|
|
|
107 |
case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
108 |
case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
109 |
case _ => (pc + 1, mp, mem)
|
|
|
110 |
}
|
|
|
111 |
compute3(pg, tb, npc, nmp, nmem)
|
|
|
112 |
}
|
|
235
|
113 |
}
|
|
|
114 |
|
|
460
|
115 |
def run3(pg: String, m: Mem = Map()) = {
|
|
|
116 |
val opt_pg = optimise(pg)
|
|
|
117 |
val jt = jtable(opt_pg)
|
|
|
118 |
compute3(opt_pg, jt, 0, 0, m)
|
|
235
|
119 |
}
|
|
|
120 |
|
|
|
121 |
|
|
|
122 |
// testcases
|
|
460
|
123 |
//
|
|
|
124 |
// optimise(load_bff("benchmark.bf")) // should have inserted 0's
|
|
|
125 |
// optimise(load_bff("mandelbrot.bf")).length // => 11203
|
|
|
126 |
// optimise(load_bff("benchmark.bf")).length
|
|
|
127 |
// time_needed(1, run3(load_bff("benchmark.bf")))
|
|
235
|
128 |
|
|
|
129 |
|
|
460
|
130 |
// (8)
|
|
|
131 |
def combine(s: String): String = ???
|
|
|
132 |
|
|
|
133 |
// testcase
|
|
|
134 |
// combine(load_bff("benchmark.bf"))
|
|
235
|
135 |
|
|
460
|
136 |
def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {
|
|
|
137 |
if (pc >= pg.length) mem
|
|
|
138 |
else {
|
|
|
139 |
val (npc, nmp, nmem) = pg(pc) match {
|
|
|
140 |
case '>' => (pc + 1, mp + 1, mem)
|
|
|
141 |
case '<' => (pc + 1, mp - 1, mem)
|
|
|
142 |
case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1)))
|
|
|
143 |
case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1)))
|
|
|
144 |
case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)}
|
|
|
145 |
case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
146 |
case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem)
|
|
|
147 |
case _ => (pc + 1, mp, mem)
|
|
|
148 |
}
|
|
|
149 |
compute3(pg, tb, npc, nmp, nmem)
|
|
|
150 |
}
|
|
384
|
151 |
}
|
|
|
152 |
|
|
460
|
153 |
// should call first optimise and then combine on the input string
|
|
|
154 |
//
|
|
|
155 |
def run4(pg: String, m: Mem = Map()) = {
|
|
|
156 |
val co_opt_pg = combine(optimise(pg))
|
|
|
157 |
val jt = jtable(co_opt_pg)
|
|
|
158 |
compute3(co_opt_pg, jt, 0, 0, m)
|
|
404
|
159 |
}
|
|
|
160 |
|
|
|
161 |
// testcases
|
|
460
|
162 |
// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""
|
|
404
|
163 |
|
|
460
|
164 |
// testcases (they should now run much faster)
|
|
|
165 |
// time_needed(1, run4(load_bff("benchmark.bf")))
|
|
|
166 |
// time_needed(1, run4(load_bff("sierpinski.bf")))
|
|
|
167 |
// time_needed(1, run4(load_bff("mandelbrot.bf")))
|
|
404
|
168 |
|
|
|
169 |
|
|
460
|
170 |
}
|
|
404
|
171 |
|
|
235
|
172 |
|
|
|
173 |
|
|
|
174 |
|
|
|
175 |
|
|
460
|
176 |
// This template code is subject to copyright
|
|
|
177 |
// by King's College London, 2022. Do not
|
|
|
178 |
// make the template code public in any shape
|
|
|
179 |
// or form, and do not exchange it with other
|
|
|
180 |
// students under any circumstance.
|