# HG changeset patch # User Christian Urban # Date 1361900387 0 # Node ID 8dde2e46c69de42bf2eb0168fbb958164d03436c # Parent fdfd921ad2e295e7df577b6bbe1e34c5a9ad3e5a added all recursive functions needed for the UF diff -r fdfd921ad2e2 -r 8dde2e46c69d scala/README --- a/scala/README Tue Feb 26 17:38:37 2013 +0000 +++ b/scala/README Tue Feb 26 17:39:47 2013 +0000 @@ -22,5 +22,5 @@ The directory can be cleaned with - rm -rf *~ lib turing abacus comp1 recs + rm -rf *~ lib turing abacus comp1 comp2 recs diff -r fdfd921ad2e2 -r 8dde2e46c69d scala/ex.scala --- a/scala/ex.scala Tue Feb 26 17:38:37 2013 +0000 +++ b/scala/ex.scala Tue Feb 26 17:39:47 2013 +0000 @@ -20,18 +20,18 @@ // Abacus machine examples def Copy(in: Int, out: Int, jump: Int) = - Abacus(List(Dec(in, jump), Inc(out), Goto(0))) + Abacus(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(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) + Abacus(Dec(in1, jump)) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = { - Abacus(List(Inc(out), Dec(in1, jump))) ++ + Abacus(Inc(out), Dec(in1, jump)) ++ Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++ - Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1) + Copy(tmp2, out, -1).shift(10, -1).adjust(-1, 1) } println("Copy 3: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0)))) @@ -46,76 +46,45 @@ 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(Add).eval(List(2,3))) +// Recursive function examples +println("Add 3 4: " + Add.eval(3, 4)) +println("Mult 3 4: " + recs.Mult.eval(3, 4)) +println("Twice 4: " + Twice.eval(4)) +println("FourTm 4: " + Fourtimes.eval(4)) +println("Pred 9: " + Pred.eval(9)) +println("Pred 0: " + Pred.eval(0)) +println("Minus 6 2: " + Minus.eval(6, 2)) +println("Minus 6 8: " + Minus.eval(6, 8)) +println("Const 8: " + Const(8).eval(67)) +println("Power 2 3: " + Power.eval(2, 3)) +println("Sign 8: " + Sign.eval(8)) +println("Sign 0: " + Sign.eval(0)) +println("Less 4 4: " + Less.eval(4, 4)) +println("Less 4 6: " + Less.eval(4, 6)) +println("Less 6 4: " + Less.eval(6, 4)) +println("Not 0: " + Not.eval(0)) +println("Not 6: " + Not.eval(6)) +println("Eq 4 4: " + Eq.eval(4, 4)) +println("Eq 4 6: " + Eq.eval(4, 6)) +println("Eq 6 4: " + Eq.eval(6, 4)) +println("Conj 0 6: " + Conj.eval(0, 6)) +println("Conj 6 4: " + Conj.eval(6, 4)) +println("Conj 0 0: " + Conj.eval(0, 0)) +println("Disj 0 6: " + Disj.eval(0, 6)) +println("Disj 6 4: " + Disj.eval(6, 4)) +println("Disj 0 0: " + Disj.eval(0, 0)) +println("Sigma Add 2 3 -> 14: " + Sigma(Add).eval(2,3)) +println("Accum Add 2 3 -> 120: " + Accum(Add).eval(2,3)) +println("Accum Mult 2 3 -> 0: " + Accum(recs.Mult).eval(2,3)) +println("Fact 5: " + Fact.eval(5)) +println("Prime 0..15: " + (0 to 15).map(n => (n, Prime.eval(n)))) +println("NextPrime 3: " + NextPrime.eval(3)) +println("NthPrime 1: " + NthPrime.eval(1)) +println("Listsum [2, 3, 4 , 5, 6]: " + Listsum(5, 4).eval(2, 3, 4, 5, 6)) +// Ask Jian +println("Strt: " + Strt(2).eval(2, 3)) - -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) +val ABCZero = Abacus(Goto(1)) +val ABCSucc = Plus(0, 1, 2, 7) ++ Abacus(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 fdfd921ad2e2 -r 8dde2e46c69d scala/recs.scala --- a/scala/recs.scala Tue Feb 26 17:38:37 2013 +0000 +++ b/scala/recs.scala Tue Feb 26 17:39:47 2013 +0000 @@ -4,6 +4,7 @@ abstract class Rec { def eval(ns: List[Int]) : Int + def eval(ns: Int*) : Int = eval(ns.toList) } case object Z extends Rec { @@ -53,4 +54,152 @@ else throw new IllegalArgumentException("Mn: args") } + + +// 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 Twice = Cn(1, Mult, List(Id(1, 0), Const(2))) +val Fourtimes = Cn(1, Mult, List(Id(1, 0), Const(4))) +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 Power = Pr(1, Const(1), Cn(3, Mult, List(Id(3, 0), Id(3, 2)))) +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 Noteq = Cn(2, Not, List(Cn(2, Eq, List(Id(2, 0), Id(2, 1))))) +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)))))))) +} + +def Accum(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, Mult, 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)))))))) +} + +def All(t: Rec, f: Rec) = { + val ar = arity(f) + Cn(ar - 1, Sign, List(Cn(ar - 1, Accum(f), Nargs(ar - 1, ar - 1) ::: List(t)))) +} + +def Ex(t: Rec, f: Rec) = { + val ar = arity(f) + Cn(ar - 1, Sign, List(Cn(ar - 1, Sigma(f), Nargs(ar - 1, ar - 1) ::: List(t)))) +} + +//Definition on page 77 of Boolos's book. +def Minr(f: Rec) = { + val ar = arity(f) + val rq = All(Id(ar, ar - 1), + Cn(ar + 1, Not, List(Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: List(Id(ar + 1, ar)))))) + Sigma(rq) +} + +//Definition on page 77 of Boolos's book. +def Maxr(f: Rec) = { + val ar = arity(f) + val rt = Id(ar + 1, ar - 1) + val rf1 = Cn(ar + 2, Less, List(Id(ar + 2, ar + 1), Id(ar + 2, ar))) + val rf2 = Cn(ar + 2, Not, List(Cn (ar + 2, f, Nargs(ar + 2, ar - 1) ::: List(Id(ar + 2, ar + 1))))) + val rf = Cn(ar + 2, Disj, List(rf1, rf2)) + val rq = All(rt, rf) + val Qf = Cn(ar + 1, Not, List(rq)) + Cn(ar, Sigma(Qf), Nargs(ar, ar) ::: List(Id(ar, ar - 1))) +} + +//Mutli-way branching statement on page 79 of Boolos's book +def Branch(rs: List[(Rec, Rec)]) = { + val ar = arity(rs.head._1) + + def Branch_aux(rs: List[(Rec, Rec)], l: Int) : Rec = rs match { + case Nil => Cn(l, Z, List(Id(l, l - 1))) + case (rg, rc)::recs => Cn(l, Add, List(Cn(l, Mult, List(rg, rc)), Branch_aux(recs, l))) + } + + Branch_aux(rs, ar) +} + +//Factorial +val Fact = { + val Fact_aux = Pr(1, Const(1), Cn(3, Mult, List(Id(3, 2), Cn(3, S, List(Id(3, 1)))))) + Cn(1, Fact_aux, List(Id(1, 0), Id(1, 0))) +} + +//Prime test +val Prime = Cn(1, Conj, List(Cn(1, Less, List(Const(1), Id(1, 0))), + All(Cn(1, Minus, List(Id(1, 0), Const(1))), + All(Cn(2, Minus, List(Id(2, 0), Cn(2, Const(1), List(Id(2, 0))))), + Cn(3, Noteq, List(Cn(3, Mult, List(Id(3, 1), Id(3, 2))), Id(3, 0))))))) + +//Returns the first prime number after n +val NextPrime = { + val R = Cn(2, Conj, List(Cn(2, Less, List(Id(2, 0), Id(2, 1))), + Cn(2, Prime, List(Id(2, 1))))) + Cn(1, Minr(R), List(Id(1, 0), Cn(1, S, List(Fact)))) +} + +val NthPrime = { + val NthPrime_aux = Pr(1, Const(2), Cn(3, NextPrime, List(Id(3, 2)))) + Cn(1, NthPrime_aux, List(Id(1, 0), Id(1, 0))) +} + +def Listsum(k: Int, m: Int) : Rec = m match { + case 0 => Cn(k, Z, List(Id(k, 0))) + case n => Cn(k, Add, List(Listsum(k, n - 1), Id(k, n - 1))) +} + +//strt-function on page 90 of Boolos, but our definition generalises +//the original one in order to deal with multiple input-arguments + +def Strt(n: Int) = { + def Strt_aux(l: Int, k: Int) : Rec = k match { + case 0 => Cn(l, Z, List(Id(l, 0))) + case n => { + val rec_dbound = Cn(l, Add, List(Listsum(l, n - 1), Cn(l, Const(n - 1), List(Id(l, 0))))) + Cn(l, Add, List(Strt_aux(l, n - 1), + Cn(l, Minus, List(Cn(l, Power, List(Cn(l, Const(2), List(Id(l, 0))), + Cn(l, Add, List(Id(l, n - 1), rec_dbound)))), + Cn(l, Power, List(Cn(l, Const(2), List(Id(l, 0))), rec_dbound)))))) + } + } + + def Rmap(f: Rec, k: Int) = (0 until k).map{i => Cn(k, f, List(Id(k, i)))}.toList + + Cn(n, Strt_aux(n, n), Rmap(S, n)) +} + +}