1 // Core Part about an Interpreter for |
1 // Main Part 5 about an Interpreter for |
2 // the Brainf***++ language |
2 // the Brainf*** language |
3 //============================================== |
3 //============================================== |
4 |
4 |
5 object M5a { |
5 |
6 |
6 object M5a { |
7 |
7 |
8 // representation of Bf memory |
8 // representation of BF memory |
9 |
9 |
10 type Mem = Map[Int, Int] |
10 type Mem = Map[Int, Int] |
11 |
|
12 |
|
13 // (1) Write a function that takes a file name as argument and |
|
14 // and requests the corresponding file from disk. It Returns the |
|
15 // content of the file as a String. If the file does not exists, |
|
16 // the function should Return the empty string. |
|
17 |
11 |
18 import io.Source |
12 import io.Source |
19 import scala.util._ |
13 import scala.util._ |
20 |
14 |
21 def load_bff(name: String) : String = |
15 // ADD YOUR CODE BELOW |
22 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
16 //====================== |
23 |
17 |
24 |
18 // (1) |
25 // (2) Complete the functions for safely reading |
19 def load_bff(name: String) : String = { |
26 // and writing brainf***++ memory. Safely read should |
20 Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") |
27 // Return the value stored in the Map for a given memory |
21 } |
28 // pointer, provided it exists; otherwise it Returns 0. The |
22 |
29 // writing function generates a new Map with the |
23 // (2) |
30 // same data, except at the given memory pointer the |
24 |
31 // value v is stored. |
25 def sread(mem: Mem, mp: Int) : Int = { |
32 |
26 Try(mem.apply(mp)).getOrElse(0) |
33 |
27 } |
34 def sread(mem: Mem, mp: Int) : Int = |
28 |
35 mem.getOrElse(mp, 0) |
29 def write(mem: Mem, mp: Int, v: Int) : Mem = { |
36 |
30 mem + (mp -> v) |
37 def write(mem: Mem, mp: Int, v: Int) : Mem = |
31 } |
38 mem.updated(mp, v) |
32 |
39 |
33 // sread(Map(), 2) == 0 |
40 |
34 // sread(Map(2 -> 1), 2) == 1 |
41 // (3) Implement the two jumping instructions in the |
35 // write(Map(), 1, 2) == Map(1 -> 2) |
42 // brainf***++ language. In jumpRight, given a program and |
36 // write(Map(1 -> 0), 1, 2) == Map(1 -> 2) |
43 // a program counter move the program counter to the right |
37 |
44 // until after the *matching* ]-command. Similarly, |
38 // val current = sread(Map(2 -> 1), 2) |
45 // jumpLeft implements the move to the left to just after |
39 // write(Map(2 -> 1), 2, current+1) |
46 // the *matching* [-command. |
40 |
47 |
41 // (3) |
48 def jumpRight(prog: String, pc: Int, level: Int) : Int = { |
42 |
49 if (prog.length <= pc) pc |
43 def jumpRight(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ |
50 else (prog(pc), level) match { |
44 case '[' => jumpRight(prog, pc+1, level+1) |
51 case (']', 0) => pc + 1 |
45 case ']' => level match { |
52 case (']', l) => jumpRight(prog, pc + 1, l - 1) |
46 case 0 => pc+1 |
53 case ('[', l) => jumpRight(prog, pc + 1, l + 1) |
47 case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level-1) |
54 case (_, l) => jumpRight(prog, pc + 1, l) |
48 } |
55 } |
49 case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level) |
56 } |
50 } |
57 |
51 |
58 def jumpLeft(prog: String, pc: Int, level: Int) : Int = { |
52 def jumpLeft(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ |
59 if (pc < 0) pc |
53 case ']' => jumpLeft(prog, pc-1, level+1) |
60 else (prog(pc), level) match { |
54 case '[' => level match { |
61 case ('[', 0) => pc + 1 |
55 case 0 => pc+1 |
62 case ('[', l) => jumpLeft(prog, pc - 1, l - 1) |
56 case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level-1) |
63 case (']', l) => jumpLeft(prog, pc - 1, l + 1) |
57 } |
64 case (_, l) => jumpLeft(prog, pc - 1, l) |
58 case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level) |
65 } |
59 } |
66 } |
60 |
67 |
61 |
68 // test cases |
62 // testcases |
69 //jumpRight("""--[..+>--].>.++""", 3, 0) // => 10 |
63 // jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 |
70 //jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3 |
64 // jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 |
71 //jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12 |
65 // jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 |
72 //jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18 |
66 // jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 |
73 //jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside) |
67 // jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) |
74 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
68 // jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
75 |
69 |
76 // (4) Complete the compute function that interprets (runs) a brainf***++ |
70 |
77 // program: the arguments are a program (represented as a string), a program |
71 |
78 // counter, a memory counter and a brainf***++ memory. It Returns the |
72 // (4) |
79 // memory at the stage when the execution of the brainf***++ program |
73 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = (pc >= 0 && pc < prog.length) match { |
80 // finishes. The interpretation finishes once the program counter |
74 case false => mem |
81 // pc is pointing to something outside the program string. |
75 case true => prog.toList.apply(pc) match{ |
82 // If the pc points to a character inside the program, the pc, |
76 case '>' => compute(prog, pc+1, mp+1, mem) |
83 // memory pointer and memory need to be updated according to |
77 case '<' => compute(prog, pc+1, mp-1, mem) |
84 // rules of the brainf***++ language. Then, recursively, the compute |
78 case '+' => { |
85 // function continues with the command at the new program |
79 val current = sread(mem, mp) |
86 // counter. |
80 compute(prog, pc+1, mp, write(mem, mp, current+1)) |
87 // |
81 } |
88 // Implement the run function that calls compute with the program |
82 case '-' => { |
89 // counter and memory counter set to 0. |
83 val current = sread(mem, mp) |
90 |
84 compute(prog, pc+1, mp, write(mem, mp, current-1)) |
91 def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { |
85 } |
92 if (0 <= pc && pc < prog.length) { |
86 case '.' => { |
93 val (new_pc, new_mp, new_mem) = prog(pc) match { |
87 print(mem.apply(mp).toChar) |
94 case '>' => (pc + 1, mp + 1, mem) |
88 compute(prog, pc+1, mp, mem) |
95 case '<' => (pc + 1, mp - 1, mem) |
89 } |
96 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
90 case '[' => { |
97 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
91 if (mem.apply(mp) == 0) compute(prog, jumpRight(prog, pc+1, 0), mp, mem) |
98 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
92 else compute(prog, pc+1, mp, mem) |
99 case '[' => |
93 } |
100 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
94 case ']' => { |
101 case ']' => |
95 if (mem.apply(mp) != 0) compute(prog, jumpLeft(prog, pc-1, 0), mp, mem) |
102 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
96 else compute(prog, pc+1, mp, mem) |
103 |
97 } |
104 case _ => (pc + 1, mp, mem) |
98 case _ => compute(prog, pc, mp, mem) |
105 } |
99 } |
106 compute(prog, new_pc, new_mp, new_mem) |
100 } |
107 } |
101 |
108 else mem |
102 def run(prog: String, m: Mem = Map()) = { |
109 } |
103 compute(prog, 0, 0, m) |
110 |
104 } |
111 def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) |
105 |
112 |
106 // run("[-]", Map(0 -> 100)) == Map(0 -> 0) |
113 |
107 // run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10) |
114 |
108 // run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42) |
115 |
109 // run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(0 -> 0, 1 -> 58, 2 -> 32) |
116 |
110 |
117 // some sample bf/bf++-programs collected from the Internet |
111 // (5) |
118 //========================================================== |
112 def generate(msg: List[Char]) : String = msg match { |
|
113 case Nil => "" |
|
114 case c => "+"*c.head.toInt + ".[-]" + generate(msg.tail) |
|
115 } |
|
116 |
|
117 // generate("ABC".toList) |
|
118 |
|
119 // run("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]", Map()) |
|
120 |
|
121 // some sample bf-programs collected from the Internet |
|
122 //===================================================== |
119 |
123 |
120 |
124 |
121 // some contrived (small) programs |
125 // some contrived (small) programs |
122 //--------------------------------- |
126 //--------------------------------- |
123 |
127 |
124 // clears the 0-cell |
128 // // clears the 0-cell |
125 //run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
129 // run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
126 |
130 |
127 // moves content of the 0-cell to 1-cell |
131 // // moves content of the 0-cell to 1-cell |
128 //run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
132 // run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
129 |
133 |
130 |
134 |
131 // copies content of the 0-cell to 2-cell and 4-cell |
135 // // copies content of the 0-cell to 2-cell and 4-cell |
132 //run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42) |
136 // run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42) |
133 |
137 |
134 |
138 |
135 // prints out numbers 0 to 9 |
139 // // prints out numbers 0 to 9 |
136 //run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
140 // run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
137 |
141 |
138 |
142 |
139 // some more "useful" programs |
143 // // some more "useful" programs |
140 //----------------------------- |
144 // //----------------------------- |
141 |
145 |
142 // hello world program 1 |
146 // // hello world program 1 |
143 //run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
147 // run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
144 // ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
148 |
145 |
149 // // hello world program 2 |
146 // hello world program 2 |
150 // run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
147 //run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ |
151 |
148 // +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") |
152 // // hello world program 3 |
149 |
153 // run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") |
150 // hello world program 3 |
|
151 //run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. |
|
152 // +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") |
|
153 |
154 |
154 |
155 |
155 // draws the Sierpinski triangle |
156 // // draws the Sierpinski triangle |
156 //run(load_bff("sierpinski.bf")) |
157 // run(load_bff("sierpinski.bf")) |
157 |
158 |
158 |
159 |
159 //fibonacci numbers below 100 |
160 // //fibonacci numbers below 100 |
160 //run("""+++++++++++ |
161 // run("""+++++++++++ |
161 // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
162 // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
162 // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
163 // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
163 // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
164 // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
164 // <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
165 // <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
165 // -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
166 // -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |