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