42 // writing function generates a new Map with the |
29 // writing function generates a new Map with the |
43 // same data, except at the given memory pointer the |
30 // same data, except at the given memory pointer the |
44 // value v is stored. |
31 // value v is stored. |
45 |
32 |
46 |
33 |
47 def sread(mem: Mem, mp: Int) : Int = { |
34 def sread(mem: Mem, mp: Int) : Int = |
48 mem.getOrElse(mp,0) |
35 mem.getOrElse(mp, 0) |
49 } |
36 |
50 |
37 def write(mem: Mem, mp: Int, v: Int) : Mem = |
51 def write(mem: Mem, mp: Int, v: Int) : Mem = { |
38 mem.updated(mp, v) |
52 val newMem = mem + (mp -> v) |
|
53 newMem |
|
54 } |
|
55 |
|
56 |
39 |
57 |
40 |
58 // (3) Implement the two jumping instructions in the |
41 // (3) Implement the two jumping instructions in the |
59 // brainf***++ language. In jumpRight, given a program and |
42 // brainf***++ language. In jumpRight, given a program and |
60 // a program counter move the program counter to the right |
43 // a program counter move the program counter to the right |
61 // until after the *matching* ]-command. Similarly, |
44 // until after the *matching* ]-command. Similarly, |
62 // jumpLeft implements the move to the left to just after |
45 // jumpLeft implements the move to the left to just after |
63 // the *matching* [-command. |
46 // the *matching* [-command. |
64 @tailrec |
47 |
65 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
48 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
66 if (pc > prog.length-1) pc |
49 if (prog.length <= pc) pc |
67 else { |
50 else (prog(pc), level) match { |
68 prog(pc) match{ |
51 case (']', 0) => pc + 1 |
69 case '[' => jumpRight(prog, pc+1, level+1) |
52 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
70 case ']' => if (level == 0) pc+1 |
53 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
71 else jumpRight(prog, pc+1, level-1) |
54 case (_, l) => jumpRight(prog, pc + 1, l) |
72 case _ => jumpRight(prog, pc+1, level) |
55 } |
73 } |
56 } |
74 } |
57 |
75 } |
|
76 @tailrec |
|
77 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
58 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
78 if (pc < 0) pc |
59 if (pc < 0) pc |
79 else { |
60 else (prog(pc), level) match { |
80 prog(pc) match{ |
61 case ('[', 0) => pc + 1 |
81 case ']' => jumpLeft(prog, pc-1, level+1) |
62 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
82 case '[' => if (level == 0) pc+1 |
63 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
83 else jumpLeft(prog, pc-1, level-1) |
64 case (_, l) => jumpLeft(prog, pc - 1, l) |
84 case _ => jumpLeft(prog, pc-1, level) |
65 } |
85 } |
66 } |
86 } |
67 |
87 } |
68 // test cases |
88 |
69 //jumpRight("""--[..+>--].>.++""", 3, 0) // => 10 |
89 |
70 //jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3 |
90 // testcases |
71 //jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12 |
91 //jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 |
72 //jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18 |
92 //jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 |
73 //jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside) |
93 // jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 |
|
94 // jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 |
|
95 //jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) |
|
96 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
74 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
97 |
|
98 |
|
99 |
75 |
100 // (4) Complete the compute function that interprets (runs) a brainf***++ |
76 // (4) Complete the compute function that interprets (runs) a brainf***++ |
101 // program: the arguments are a program (represented as a string), a program |
77 // program: the arguments are a program (represented as a string), a program |
102 // counter, a memory counter and a brainf***++ memory. It Returns the |
78 // counter, a memory counter and a brainf***++ memory. It Returns the |
103 // memory at the stage when the execution of the brainf***++ program |
79 // memory at the stage when the execution of the brainf***++ program |
110 // counter. |
86 // counter. |
111 // |
87 // |
112 // Implement the run function that calls compute with the program |
88 // Implement the run function that calls compute with the program |
113 // counter and memory counter set to 0. |
89 // counter and memory counter set to 0. |
114 |
90 |
115 @tailrec |
|
116 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
91 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
117 if (pc > prog.length-1) mem |
92 if (0 <= pc && pc < prog.length) { |
118 else { |
93 val (new_pc, new_mp, new_mem) = prog(pc) match { |
119 prog(pc) match{ |
94 case '>' => (pc + 1, mp + 1, mem) |
120 case '>' => compute(prog, pc+1, mp+1, mem) |
95 case '<' => (pc + 1, mp - 1, mem) |
121 case '<' => compute(prog, pc+1, mp-1, mem) |
96 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
122 case '+' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)+1)) |
97 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
123 case '-' => compute(prog, pc+1, mp,write(mem,mp,sread(mem,mp)-1)) |
98 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
124 case '.' => print(sread(mem,mp).toChar) |
99 case '[' => |
125 compute(prog, pc+1, mp, mem) |
100 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
126 case '[' => if (sread(mem,mp) == 0) compute(prog,jumpRight(prog,pc+1,0),mp,mem) |
101 case ']' => |
127 else compute(prog,pc+1,mp,mem) |
102 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
128 case ']' => if (sread(mem,mp) != 0) compute(prog,jumpLeft(prog,pc-1,0),mp,mem) |
103 |
129 else compute(prog,pc+1,mp,mem) |
104 case _ => (pc + 1, mp, mem) |
130 case '*' => compute(prog, pc+1,mp, write(mem,mp,sread(mem,mp)*sread(mem,mp-1))) |
105 } |
131 case '@' => compute(prog,pc+1,mp, write(mem,sread(mem,mp),sread(mem,mp-1))) |
106 compute(prog, new_pc, new_mp, new_mem) |
132 case '#' => print(sread(mem,mp)) |
107 } |
133 compute(prog,pc+1, mp, mem) |
108 else mem |
134 case _ => compute(prog,pc+1,mp,mem) |
109 } |
135 } |
110 |
136 } |
111 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
137 } |
112 |
138 |
113 |
139 def run(prog: String, m: Mem = Map()) : Mem = { |
|
140 compute(prog, 0, 0, m) |
|
141 } |
|
142 |
114 |
143 |
115 |
144 |
116 |
145 // some sample bf/bf++-programs collected from the Internet |
117 // some sample bf/bf++-programs collected from the Internet |
146 //========================================================== |
118 //========================================================== |
161 |
133 |
162 |
134 |
163 // prints out numbers 0 to 9 |
135 // prints out numbers 0 to 9 |
164 //run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
136 //run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
165 |
137 |
166 // bf++ program calculating the cube-function, 10 * 10 * 10 = 1000 |
|
167 //run("""++++++++++#>+***#""") // Map(0 -> 10, 1 -> 1000) |
|
168 |
|
169 |
|
170 // bf++ program copies 3 from 0-cell to to cells 1, 4, 5, 6 and 7 |
|
171 // (note that because of how the program wprks cell 1 will contain 7) |
|
172 //run("""+++>+@+@+@+@+@""") // Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3) |
|
173 |
|
174 |
|
175 |
138 |
176 // some more "useful" programs |
139 // some more "useful" programs |
177 //----------------------------- |
140 //----------------------------- |
178 |
141 |
179 // hello world program 1 |
142 // hello world program 1 |
180 // run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
143 //run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
181 // ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
144 // ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
182 |
145 |
183 // hello world program 2 |
146 // hello world program 2 |
184 // run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
147 //run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
185 // +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
148 // +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
186 |
149 |
187 // hello world program 3 |
150 // hello world program 3 |
188 // run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. |
151 //run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. |
189 // +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") |
152 // +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") |
190 |
153 |
191 |
154 |
192 // draws the Sierpinski triangle |
155 // draws the Sierpinski triangle |
193 //run(load_bff("sierpinski.bf")) |
156 //run(load_bff("sierpinski.bf")) |
194 |
157 |
195 |
158 |
196 //fibonacci numbers below 100 |
159 //fibonacci numbers below 100 |
197 // run("""+++++++++++ |
160 //run("""+++++++++++ |
198 // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
161 // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
199 // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
162 // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
200 // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
163 // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
201 // <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
164 // <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
202 // -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
165 // -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
205 // ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
168 // ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
206 // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
169 // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
207 // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
170 // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
208 |
171 |
209 //outputs the square numbers up to 10000 |
172 //outputs the square numbers up to 10000 |
210 // run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
173 //run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
211 // >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
174 // >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
212 // <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
175 // <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
213 |
176 |
214 |
177 |
215 // calculates 2 to the power of 6 |
178 // calculates 2 to the power of 6 |
216 //(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) |
179 //(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) |
217 // run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] |
180 //run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] |
218 // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] |
181 // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] |
219 // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> |
182 // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> |
220 // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] |
183 // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] |
221 // <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] |
184 // <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] |
222 // >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] |
185 // >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] |