# HG changeset patch # User Christian Urban # Date 1361805168 0 # Node ID f06aa4e1c25b8298907cd98ffb978c8a82801309 # Parent fc2a5e9fbb97a4a880fcf149e160a33728278330 tuned diff -r fc2a5e9fbb97 -r f06aa4e1c25b scala/abacus.scala --- a/scala/abacus.scala Fri Feb 22 14:31:34 2013 +0000 +++ b/scala/abacus.scala Mon Feb 25 15:12:48 2013 +0000 @@ -18,7 +18,9 @@ case class Abacus(p: AProg) { //simple composition - def ++ (that: Abacus) = Abacus(this.p ::: that.p) + def ++ (that: Abacus) = Abacus(p ::: that.p) + + def :+ (that: Abacus) = this ++ that.shift(p.length, -1) def shift(offset: Int, jump: Int) = Abacus(p.map(_ match { case Inc(n) => Inc(n) @@ -56,5 +58,11 @@ def run(regs: Regs): Regs = run(AConfig(0, regs)).regs } +// some syntactical convenience +object Abacus { + def apply(is: AInst*) : Abacus = Abacus(is.toList) } + +} + diff -r fc2a5e9fbb97 -r f06aa4e1c25b scala/comp2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scala/comp2.scala Mon Feb 25 15:12:48 2013 +0000 @@ -0,0 +1,19 @@ +package object comp2 { + +// Recusive function to Abacus translation + +import lib._ +import abacus._ +import recs._ + +def arity(f: Rec) = f match { + case Z => 1 + case S => 1 + case Id(n, _) => n + case Cn(n, _, _) => n + case Pr(n, _, _) => n + case Mn(n, _) => n +} + +} + diff -r fc2a5e9fbb97 -r f06aa4e1c25b scala/ex.scala --- a/scala/ex.scala Fri Feb 22 14:31:34 2013 +0000 +++ b/scala/ex.scala Mon Feb 25 15:12:48 2013 +0000 @@ -1,7 +1,9 @@ import lib._ import turing._ import abacus._ +import recs._ import comp1._ +//import comp2._ // Turing machine examples val TMCopy = TM((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), @@ -21,7 +23,7 @@ Abacus(List(Dec(in, jump), Inc(out), Goto(0))) def Plus(m: Int, n: Int, tmp: Int, jump: Int) = - Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) + Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = Abacus(List(Dec(in1, jump))) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) @@ -44,4 +46,76 @@ println("Compiled Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(Tape(3,5,0,0))) println("Compiled Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(Tape(3,4,0,0,0))) +// Recursive Function examples +def arity(f: Rec) = f match { + case Z => 1 + case S => 1 + case Id(n, _) => n + case Cn(n, _, _) => n + case Pr(n, _, _) => n + 1 + case Mn(n, _) => n +} +val Add = Pr(1, Id(1, 0), Cn(3, S, List(Id(3, 2)))) +val Mult = Pr(1, Z, Cn(3, Add, List(Id(3, 0), Id(3, 2)))) +val Pred = Cn(1, Pr(1, Z, Id(3, 1)), List(Id(1, 0), Id(1, 0))) +val Minus = Pr(1, Id(1, 0), Cn(3, Pred, List(Id(3, 2)))) + +def Const(n: Int) : Rec = n match { + case 0 => Z + case n => Cn(1, S, List(Const(n - 1))) +} + +val Sign = Cn(1, Minus, List(Const(1), Cn(1, Minus, List(Const(1), Id(1, 0))))) +val Less = Cn(2, Sign, List(Cn(2, Minus, List(Id(2, 1), Id(2, 0))))) +val Not = Cn(1, Minus, List(Const(1), Id(1, 0))) +val Eq = Cn(2, Minus, List(Cn(2, Const(1), List(Id(2, 0))), + Cn(2, Add, List(Cn(2, Minus, List(Id(2, 0), Id(2, 1))), + Cn(2, Minus, List(Id(2, 1), Id(2, 0))))))) +val Conj = Cn(2, Sign, List(Cn(2, Mult, List(Id(2, 0), Id(2, 1))))) +val Disj = Cn(2, Sign, List(Cn(2, Add, List(Id(2, 0), Id(2, 1))))) + +def Nargs(n: Int, m: Int) : List[Rec] = m match { + case 0 => Nil + case m => Nargs(n, m - 1) ::: List(Id(n, m - 1)) +} + +def Sigma(f: Rec) = { + val ar = arity(f) + Pr(ar - 1, Cn(ar - 1, f, Nargs(ar - 1, ar - 1) ::: + List(Cn(ar - 1, Const(0), List(Id(ar - 1, 0))))), + Cn(ar + 1, Add, List(Id(ar + 1, ar), + Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: + List(Cn(ar + 1, S, List(Id(ar + 1, ar - 1)))))))) +} + +println("Add 3 4: " + Add.eval(List(3, 4))) +println("Mult 3 4: " + Mult.eval(List(3, 4))) +println("Pred 9: " + Pred.eval(List(9))) +println("Pred 0: " + Pred.eval(List(0))) +println("Minus 6 2: " + Minus.eval(List(6, 2))) +println("Minus 6 8: " + Minus.eval(List(6, 8))) +println("Const 8: " + Const(8).eval(List(67))) +println("Sign 8: " + Sign.eval(List(8))) +println("Sign 0: " + Sign.eval(List(0))) +println("Less 4 4: " + Less.eval(List(4, 4))) +println("Less 4 6: " + Less.eval(List(4, 6))) +println("Less 6 4: " + Less.eval(List(6, 4))) +println("Not 0: " + Not.eval(List(0))) +println("Not 6: " + Not.eval(List(6))) +println("Eq 4 4: " + Eq.eval(List(4, 4))) +println("Eq 4 6: " + Eq.eval(List(4, 6))) +println("Eq 6 4: " + Eq.eval(List(6, 4))) +println("Conj 0 6: " + Conj.eval(List(0, 6))) +println("Conj 6 4: " + Conj.eval(List(6, 4))) +println("Conj 0 0: " + Conj.eval(List(0, 0))) +println("Disj 0 6: " + Disj.eval(List(0, 6))) +println("Disj 6 4: " + Disj.eval(List(6, 4))) +println("Disj 0 0: " + Disj.eval(List(0, 0))) +//println("Sigma: " + Sigma(S).eval(List(0,1,2))) +//println("Sigma: " + Sigma(S).eval(List(0,1,2,3,4,5))) + + +val ABCZero = Abacus(List(Goto(1))) +val ABCSucc = Plus(0, 1, 2, 7) ++ Abacus(List(Inc(1))).shift(Plus(0, 1, 2, 7).p.length, -1) +def ABCId(n: Int, m: Int) = Plus(m, n, n + 1, 7) diff -r fc2a5e9fbb97 -r f06aa4e1c25b scala/recs.scala --- a/scala/recs.scala Fri Feb 22 14:31:34 2013 +0000 +++ b/scala/recs.scala Mon Feb 25 15:12:48 2013 +0000 @@ -34,19 +34,23 @@ case class Pr(n: Int, f: Rec, g: Rec) extends Rec { override def eval(ns: List[Int]) = - if (ns.length == n - 1) { + if (ns.length == n + 1) { if (ns.last == 0) f.eval(ns.init) else { val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1)) g.eval(ns.init ::: List(ns.last - 1, r)) } } - else throw new IllegalArgumentException("Cn: args") + else throw new IllegalArgumentException("Pr: args") } case class Mn(n: Int, f: Rec) extends Rec { - override def eval(ns: List[Int]) = 0 - + def evaln(ns: List[Int], n: Int) : Int = + if (f.eval(ns ::: List(n)) == 0) n else evaln(ns, n + 1) + + override def eval(ns: List[Int]) = + if (ns.length == n) evaln(ns, 0) + else throw new IllegalArgumentException("Mn: args") } }