|
1 // Part 2 about an Interpreter for the Brainf*** language |
|
2 //======================================================== |
|
3 |
|
4 object CW8b { |
|
5 |
|
6 type Mem = Map[Int, Int] |
|
7 |
|
8 // (2a) Complete the functions for safely reading |
|
9 // and writing brainf*** memory. Safely read should |
|
10 // Return the value stored in the Map for a given memory |
|
11 // pointer, if it exists; otherwise Returns 0. The |
|
12 // writing function generates a new Map with the |
|
13 // same data, except at the given memory pointer the |
|
14 // a value v is stored. |
|
15 |
|
16 |
|
17 def sread(mem: Mem, mp: Int) : Int = |
|
18 mem.getOrElse(mp, 0) |
|
19 |
|
20 def write(mem: Mem, mp: Int, v: Int) : Mem = |
|
21 mem.updated(mp, v) |
|
22 |
|
23 |
|
24 // (2b) Implement the two jumping instructions in the |
|
25 // brainf*** language. In jumpRight, given a program and |
|
26 // a program counter move the program counter to the right |
|
27 // until after the *matching* ]-command. Similarly, |
|
28 // jumpLeft implements the move to the left to just after |
|
29 // the *matching* [--command. |
|
30 |
|
31 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
|
32 if (prog.length <= pc) pc |
|
33 else (prog(pc), level) match { |
|
34 case (']', 0) => pc + 1 |
|
35 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
|
36 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
|
37 case (_, l) => jumpRight(prog, pc + 1, l) |
|
38 } |
|
39 } |
|
40 |
|
41 def jumpLeft(prog: String, p: Int, level: Int) : Int = { |
|
42 if (p < 0) p |
|
43 else (prog(p), level) match { |
|
44 case ('[', 0) => p + 1 |
|
45 case ('[', l) => jumpLeft(prog, p - 1, l - 1) |
|
46 case (']', l) => jumpLeft(prog, p - 1, l + 1) |
|
47 case (_, l) => jumpLeft(prog, p - 1, l) |
|
48 } |
|
49 } |
|
50 |
|
51 |
|
52 // (2c) Complete the run function that interpretes (runs) a brainf*** |
|
53 // program: the arguments are a program, a program counter, |
|
54 // a memory counter and a brainf*** memory. It Returns the |
|
55 // memory at the stage when the excution of the brainf*** program |
|
56 // finishes. The interpretation finishes once the program counter |
|
57 // pc is pointing to something outside the program string. |
|
58 // If the pc points to a character inside the program, the pc, |
|
59 // memory pointer and memory need to be updated according to |
|
60 // rules of the brainf*** language. Then, recursively, run |
|
61 // function continues with the command at the new program |
|
62 // counter. |
|
63 // Implement the start function that calls run with the program |
|
64 // counter and memory counter set to 0. |
|
65 |
|
66 def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
|
67 if (0 <= pc && pc < prog.length) { |
|
68 val (new_pc, new_mp, new_mem) = prog(pc) match { |
|
69 case '>' => (pc + 1, mp + 1, mem) |
|
70 case '<' => (pc + 1, mp - 1, mem) |
|
71 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
|
72 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
|
73 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
|
74 case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
|
75 case '[' => |
|
76 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
77 case ']' => |
|
78 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
|
79 case _ => (pc + 1, mp, mem) |
|
80 } |
|
81 run(prog, new_pc, new_mp, new_mem) |
|
82 } |
|
83 else mem |
|
84 } |
|
85 |
|
86 def start(prog: String, m: Mem) = run(prog, 0, 0, m) |
|
87 |
|
88 // some sample programs collected from the Internet |
|
89 //================================================== |
|
90 |
|
91 |
|
92 /* |
|
93 // first some contrived (small) programs |
|
94 |
|
95 // clears the 0-cell |
|
96 start("[-]", Map(0 -> 100)) |
|
97 |
|
98 // copies content of the 0-cell to 1-cell |
|
99 start("[->+<]", Map(0 -> 10)) |
|
100 |
|
101 // copies content of the 0-cell to 2-cell and 4-cell |
|
102 start("[>>+>>+<<<<-]", Map(0 -> 42)) |
|
103 |
|
104 |
|
105 // prints out numbers 0 to 9 |
|
106 start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map()) |
|
107 |
|
108 |
|
109 // some more "useful" programs |
|
110 |
|
111 // hello world program 1 |
|
112 start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
|
113 ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) |
|
114 |
|
115 // hello world program 2 |
|
116 start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
|
117 +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map()) |
|
118 |
|
119 |
|
120 // draws the Sierpinski triangle |
|
121 start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ |
|
122 ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< |
|
123 ]>.>+[>>]>+]""", Map()) |
|
124 |
|
125 //fibonacci numbers below 100 |
|
126 start("""+++++++++++ |
|
127 >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
|
128 >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
|
129 +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
|
130 <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
|
131 -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
|
132 >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ |
|
133 +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
|
134 ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
|
135 <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
|
136 [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map()) |
|
137 |
|
138 |
|
139 //outputs the square numbers up to 10000 |
|
140 start("""++++[>+++++<-]>[<+++++>-]+<+[ |
|
141 >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
|
142 >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
|
143 <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map()) |
|
144 |
|
145 |
|
146 //collatz numbers (need to be typed in) |
|
147 start(""">,[[----------[ |
|
148 >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] |
|
149 ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ |
|
150 <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] |
|
151 >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] |
|
152 >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> |
|
153 ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map()) |
|
154 |
|
155 |
|
156 // infinite collatz (never stops) |
|
157 start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< |
|
158 <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ |
|
159 +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< |
|
160 [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> |
|
161 [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ |
|
162 <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ |
|
163 ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< |
|
164 +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- |
|
165 ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- |
|
166 >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> |
|
167 -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ |
|
168 +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< |
|
169 <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ |
|
170 +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< |
|
171 <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- |
|
172 [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map()) |
|
173 |
|
174 |
|
175 */ |
|
176 |
|
177 } |