|
1 // Part 1 about an Interpreter for the Brainf*** language |
|
2 //======================================================== |
|
3 |
|
4 |
|
5 // representation of Bf memory |
|
6 |
|
7 type Mem = Map[Int, Int] |
|
8 |
|
9 |
|
10 // (1) Write a function that takes a file name as argument and |
|
11 // and requests the corresponding file from disk. It returns the |
|
12 // content of the file as a String. If the file does not exists, |
|
13 // the function should return the empty string. |
|
14 |
|
15 import io.Source |
|
16 import scala.util._ |
|
17 |
|
18 //def load_bff(name: String) : String = ... |
|
19 |
|
20 |
|
21 |
|
22 // (2) Complete the functions for safely reading |
|
23 // and writing brainf*** memory. Safely read should |
|
24 // Return the value stored in the Map for a given memory |
|
25 // pointer, provided it exists; otherwise it Returns 0. The |
|
26 // writing function generates a new Map with the |
|
27 // same data, except at the given memory pointer the |
|
28 // value v is stored. |
|
29 |
|
30 |
|
31 //def sread(mem: Mem, mp: Int) : Int = ... |
|
32 |
|
33 //def write(mem: Mem, mp: Int, v: Int) : Mem = ... |
|
34 |
|
35 |
|
36 |
|
37 // (3) Implement the two jumping instructions in the |
|
38 // brainf*** language. In jumpRight, given a program and |
|
39 // a program counter move the program counter to the right |
|
40 // until after the *matching* ]-command. Similarly, |
|
41 // jumpLeft implements the move to the left to just after |
|
42 // the *matching* [-command. |
|
43 |
|
44 //def jumpRight(prog: String, pc: Int, level: Int) : Int = ... |
|
45 |
|
46 //def jumpLeft(prog: String, pc: Int, level: Int) : Int = ... |
|
47 |
|
48 |
|
49 // testcases |
|
50 //jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 |
|
51 //jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 |
|
52 //jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 |
|
53 //jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 |
|
54 //jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) |
|
55 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
|
56 |
|
57 |
|
58 |
|
59 // (4) Complete the compute function that interprets (runs) a brainf*** |
|
60 // program: the arguments are a program (represented as a string), a program |
|
61 // counter, a memory counter and a brainf*** memory. It Returns the |
|
62 // memory at the stage when the execution of the brainf*** program |
|
63 // finishes. The interpretation finishes once the program counter |
|
64 // pc is pointing to something outside the program string. |
|
65 // If the pc points to a character inside the program, the pc, |
|
66 // memory pointer and memory need to be updated according to |
|
67 // rules of the brainf*** language. Then, recursively, the compute |
|
68 // function continues with the command at the new program |
|
69 // counter. |
|
70 // |
|
71 // Implement the run function that calls compute with the program |
|
72 // counter and memory counter set to 0. |
|
73 |
|
74 |
|
75 //def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ... |
|
76 |
|
77 //def run(prog: String, m: Mem = Map()) = ... |
|
78 |
|
79 |
|
80 /* |
|
81 |
|
82 // some sample bf-programs collected from the Internet |
|
83 //===================================================== |
|
84 |
|
85 |
|
86 // first some contrived (small) programs |
|
87 |
|
88 // clears the 0-cell |
|
89 run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
|
90 |
|
91 // copies content of the 0-cell to 1-cell |
|
92 run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
|
93 |
|
94 |
|
95 // copies content of the 0-cell to 2-cell and 4-cell |
|
96 run("[>>+>>+<<<<-]", Map(0 -> 42)) |
|
97 |
|
98 |
|
99 // prints out numbers 0 to 9 |
|
100 run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
|
101 |
|
102 |
|
103 // some more "useful" programs |
|
104 |
|
105 // hello world program 1 |
|
106 run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
|
107 ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
|
108 |
|
109 // hello world program 2 |
|
110 run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
|
111 +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
|
112 |
|
113 |
|
114 // draws the Sierpinski triangle |
|
115 run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ |
|
116 ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< |
|
117 ]>.>+[>>]>+]""") |
|
118 |
|
119 run(load_bff("sierpinski.bf")) |
|
120 |
|
121 |
|
122 //fibonacci numbers below 100 |
|
123 run("""+++++++++++ |
|
124 >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
|
125 >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
|
126 +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
|
127 <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
|
128 -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
|
129 >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ |
|
130 +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
|
131 ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
|
132 <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
|
133 [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
|
134 |
|
135 |
|
136 //outputs the square numbers up to 10000 |
|
137 run("""++++[>+++++<-]>[<+++++>-]+<+[ |
|
138 >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
|
139 >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
|
140 <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
|
141 |
|
142 //collatz numbers (needs a number to be typed in) |
|
143 run(""">,[[----------[ |
|
144 >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] |
|
145 ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ |
|
146 <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] |
|
147 >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] |
|
148 >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> |
|
149 ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""") |
|
150 |
|
151 |
|
152 // infinite collatz (never stops) |
|
153 run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< |
|
154 <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ |
|
155 +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< |
|
156 [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> |
|
157 [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ |
|
158 <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ |
|
159 ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< |
|
160 +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- |
|
161 ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- |
|
162 >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> |
|
163 -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ |
|
164 +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< |
|
165 <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ |
|
166 +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< |
|
167 <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- |
|
168 [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""") |
|
169 |
|
170 |
|
171 |
|
172 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
|
173 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
|
174 |
|
175 run(load_bff("mandelbrot.bf")) |
|
176 |
|
177 |
|
178 // a benchmark program (counts down from 'Z' to 'A') |
|
179 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
|
180 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |
|
181 ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ |
|
182 +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" |
|
183 |
|
184 |
|
185 def time_needed[T](n: Int, code: => T) = { |
|
186 val start = System.nanoTime() |
|
187 for (i <- 0 until n) code |
|
188 val end = System.nanoTime() |
|
189 (end - start)/1.0e9 |
|
190 } |
|
191 |
|
192 time_needed(1, run(b1)) |
|
193 */ |
|
194 |