--- 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)
--- 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))
+}
+
+}