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