147 abstract class AInst |
147 abstract class AInst |
148 case class Inc(n: Int) extends AInst |
148 case class Inc(n: Int) extends AInst |
149 case class Dec(n: Int, l: Int) extends AInst |
149 case class Dec(n: Int, l: Int) extends AInst |
150 case class Goto(l: Int) extends AInst |
150 case class Goto(l: Int) extends AInst |
151 |
151 |
|
152 def ashift(ai: AInst, offset: Int, jump: Int) = ai match { |
|
153 case Inc(n) => Inc(n) |
|
154 case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset) |
|
155 case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset) |
|
156 } |
|
157 |
|
158 def aadjust(ai: AInst, old_jump: Int, jump: Int) = ai match { |
|
159 case Inc(n) => Inc(n) |
|
160 case Dec(n, l) => if (l == old_jump) Dec(n, jump) else Dec(n, l) |
|
161 case Goto(l) => if (l == old_jump) Goto(jump) else Goto(l) |
|
162 } |
|
163 |
|
164 |
|
165 |
152 type AProg = List[AInst] |
166 type AProg = List[AInst] |
153 type Regs = Map[Int, Int] |
167 type Regs = Map[Int, Int] |
154 |
168 |
155 case class AConfig(s: Int, regs: Regs) |
169 case class AConfig(s: Int, regs: Regs) |
156 |
170 |
157 case class Abacus(p: AProg) { |
171 case class Abacus(p: AProg) { |
158 |
172 |
|
173 def shift(offset: Int, jump: Int) = Abacus(p.map(ashift(_, offset, jump))) |
|
174 def adjust(old_jump: Int, jump: Int) = Abacus(p.map(aadjust(_, old_jump, jump))) |
|
175 |
159 def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match { |
176 def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match { |
160 case (None, _) => cf |
177 case (None, _) => cf |
161 case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1))) |
178 case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1))) |
162 case (Some(Dec(n, l)), s) => { |
179 case (Some(Dec(n, l)), s) => { |
163 if (dget(cf.regs, n) == 0) AConfig(l, cf.regs) |
180 if (dget(cf.regs, n) == 0) AConfig(l, cf.regs) |
179 |
196 |
180 def run(regs: Regs): Regs = run(AConfig(0, regs)).regs |
197 def run(regs: Regs): Regs = run(AConfig(0, regs)).regs |
181 } |
198 } |
182 |
199 |
183 // examples |
200 // examples |
184 class Copy(in: Int, out: Int) extends |
201 def Copy(in: Int, out: Int) = |
185 Abacus(List(Dec(in, -1), Inc(out), Goto(0))) |
202 Abacus(List(Dec(in, -1), Inc(out), Goto(0))) |
186 |
203 |
187 class Plus(in1: Int, in2: Int, out: Int) extends |
204 def Plus(m: Int, n: Int, tmp: Int, jump: Int) = |
188 Abacus(List(Dec(in1, 4), Inc(in2), Inc(out), |
205 Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), |
189 Goto(0), Dec(out, -1), Inc(in1), Goto(4))) |
206 Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) |
190 |
207 |
191 |
208 def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
192 println("Ab: " + (new Plus(0, 1, 2)).run(Map(0 -> 3, 1 -> 4))) |
209 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
|
210 Abacus(Dec(in1, jump) :: tm.p) |
|
211 } |
|
212 |
|
213 def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
|
214 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
|
215 Abacus(Dec(in1, jump) :: tm.p) |
|
216 } |
|
217 |
|
218 def Expo(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
|
219 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
|
220 Abacus(Dec(in1, jump) :: tm.p) |
|
221 } |
|
222 |
|
223 |
|
224 println("Copy: " + (Copy(0, 1).run(Map(0 -> 3, 1 -> 0)))) |
|
225 println("Plus: " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0)))) |
|
226 println("Mult: " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0)))) |
193 |
227 |
194 |
228 |
195 |
229 |
196 //Recursive Functions |
230 //Recursive Functions |
197 abstract class Rec { |
231 abstract class Rec { |