Mercurial Mercurial > hg > tm / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
scala/recs.scala
changeset 201 09befdf4fc99
parent 200 8dde2e46c69d
child 238 6ea1062da89a
equal deleted inserted replaced
200:8dde2e46c69d 201:09befdf4fc99 
     3 //Recursive Functions
 
     3 //Recursive Functions
 
     4 
     4 
     5 abstract class Rec {
 
     5 abstract class Rec {
 
     6   def eval(ns: List[Int]) : Int
 
     6   def eval(ns: List[Int]) : Int
 
     7   def eval(ns: Int*) : Int = eval(ns.toList)
 
     7   def eval(ns: Int*) : Int = eval(ns.toList)
 
       
     8 
       
     9   //syntactic convenience for composition
 
       
    10   def o(r: Rec) = Cn(r.arity, this, List(r))
 
       
    11   def o(r: Rec, f: Rec) = Cn(r.arity, this, List(r, f))
 
       
    12   def o(r: Rec, f: Rec, g: Rec) = Cn(r.arity, this, List(r, f, g))
 
       
    13 
       
    14   def arity : Int
 
     8 }
 
    15 }
 
     9 
    16 
    10 case object Z extends Rec {
 
    17 case object Z extends Rec {
 
    11   override def eval(ns: List[Int]) = ns match {
 
    18   override def eval(ns: List[Int]) = ns match {
 
    12     case n::Nil => 0
 
    19     case n::Nil => 0
 
    13     case _ => throw new IllegalArgumentException("Z args: " + ns)
 
    20     case _ => throw new IllegalArgumentException("Z args: " + ns)
 
    14   }
 
    21   }
 
       
    22   override def arity = 1
 
    15 } 
    23 } 
    16 
    24 
    17 case object S extends Rec {
 
    25 case object S extends Rec {
 
    18   override def eval(ns: List[Int]) = ns match {
 
    26   override def eval(ns: List[Int]) = ns match {
 
    19     case n::Nil => n + 1
 
    27     case n::Nil => n + 1
 
    20     case _ => throw new IllegalArgumentException("S args: " + ns)
 
    28     case _ => throw new IllegalArgumentException("S args: " + ns)
 
    21   }
 
    29   }
 
       
    30   override def arity = 1 
    22 } 
    31 } 
    23 
    32 
    24 case class Id(n: Int, m: Int) extends Rec {
 
    33 case class Id(n: Int, m: Int) extends Rec {
 
    25   override def eval(ns: List[Int]) = 
    34   override def eval(ns: List[Int]) = 
    26     if (ns.length == n && m < n) ns(m)
 
    35     if (ns.length == n && m < n) ns(m)
 
    27     else throw new IllegalArgumentException("Id args: " + ns + "," + n + "," + m)
 
    36     else throw new IllegalArgumentException("Id args: " + ns + "," + n + "," + m)
 
       
    37 
       
    38   override def arity = n
 
    28 }
 
    39 }
 
    29 
    40 
    30 case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {
 
    41 case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {
 
    31   override def eval(ns: List[Int]) = 
    42   override def eval(ns: List[Int]) = 
    32     if (ns.length == n) f.eval(gs.map(_.eval(ns)))
 
    43     if (ns.length == n && gs.forall(_.arity == n) && f.arity == gs.length) f.eval(gs.map(_.eval(ns)))
 
    33     else throw new IllegalArgumentException("Cn: args")
 
    44     else throw new IllegalArgumentException("Cn args: " + ns + "," + n)
 
       
    45 
       
    46   override def arity = n
 
       
    47 }
 
       
    48 
       
    49 // syntactic convenience
 
       
    50 object Cn {
 
       
    51   def apply(n: Int, f: Rec, g: Rec) : Rec = new Cn(n, f, List(g))
 
    34 }
 
    52 }
 
    35 
    53 
    36 case class Pr(n: Int, f: Rec, g: Rec) extends Rec {
 
    54 case class Pr(n: Int, f: Rec, g: Rec) extends Rec {
 
    37   override def eval(ns: List[Int]) = 
    55   override def eval(ns: List[Int]) = 
    38     if (ns.length == n + 1) {
 
    56     if (ns.length == n + 1) {
 
    41         val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))
 
    59         val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))
 
    42         g.eval(ns.init ::: List(ns.last - 1, r))
 
    60         g.eval(ns.init ::: List(ns.last - 1, r))
 
    43       }
 
    61       }
 
    44     }
 
    62     }
 
    45     else throw new IllegalArgumentException("Pr: args")
 
    63     else throw new IllegalArgumentException("Pr: args")
 
       
    64 
       
    65   override def arity = n + 1
 
       
    66 }
 
       
    67 
       
    68 // syntactic convenience
 
       
    69 object Pr {
 
       
    70   def apply(r: Rec, f: Rec) : Rec = Pr(r.arity, r, f) 
    46 }
 
    71 }
 
    47 
    72 
    48 case class Mn(n: Int, f: Rec) extends Rec {
 
    73 case class Mn(n: Int, f: Rec) extends Rec {
 
    49   def evaln(ns: List[Int], n: Int) : Int = 
    74   def evaln(ns: List[Int], n: Int) : Int = 
    50     if (f.eval(ns ::: List(n)) == 0) n else evaln(ns, n + 1)
 
    75     if (f.eval(ns ::: List(n)) == 0) n else evaln(ns, n + 1)
 
    51 
    76 
    52   override def eval(ns: List[Int]) = 
    77   override def eval(ns: List[Int]) = 
    53     if (ns.length == n) evaln(ns, 0) 
    78     if (ns.length == n) evaln(ns, 0) 
    54     else throw new IllegalArgumentException("Mn: args")
 
    79     else throw new IllegalArgumentException("Mn: args")
 
       
    80 
       
    81   override def arity = n
 
    55 }
 
    82 }
 
    56 
    83 
    57 
    84 
    58 
    85 
    59 // Recursive Function examples
 
    86 // Recursive Function examples
 
    60 def arity(f: Rec) = f match {
 
       
    61   case Z => 1
 
       
    62   case S => 1
 
       
    63   case Id(n, _) => n
 
       
    64   case Cn(n, _, _) => n
 
       
    65   case Pr(n, _, _) => n + 1
 
       
    66   case Mn(n, _) => n 
       
    67 }
 
       
    68 
       
    69 val Add = Pr(1, Id(1, 0), Cn(3, S, List(Id(3, 2))))
 
       
    70 val Mult = Pr(1, Z, Cn(3, Add, List(Id(3, 0), Id(3, 2))))
 
       
    71 val Twice = Cn(1, Mult, List(Id(1, 0), Const(2)))
 
       
    72 val Fourtimes = Cn(1, Mult, List(Id(1, 0), Const(4)))
 
       
    73 val Pred = Cn(1, Pr(1, Z, Id(3, 1)), List(Id(1, 0), Id(1, 0)))
 
       
    74 val Minus = Pr(1, Id(1, 0), Cn(3, Pred, List(Id(3, 2))))
 
       
    75 def Const(n: Int) : Rec = n match {
 
    87 def Const(n: Int) : Rec = n match {
 
    76   case 0 => Z
 
    88   case 0 => Z
 
    77   case n => Cn(1, S, List(Const(n - 1)))
 
    89   case n => S o Const(n - 1)
 
    78 }
 
    90 }
 
    79 
    91 
    80 val Power = Pr(1, Const(1), Cn(3, Mult, List(Id(3, 0), Id(3, 2))))
 
    92 val Add = Pr(Id(1, 0), S o Id(3, 2))
 
    81 val Sign = Cn(1, Minus, List(Const(1), Cn(1, Minus, List(Const(1), Id(1, 0)))))
 
    93 val Mult = Pr(Z, Add o (Id(3, 0), Id(3, 2)))
 
    82 val Less = Cn(2, Sign, List(Cn(2, Minus, List(Id(2, 1), Id(2, 0)))))
 
    94 val Twice = Mult o (Id(1, 0), Const(2))
 
    83 val Not = Cn(1, Minus, List(Const(1), Id(1, 0)))
 
    95 val Fourtimes = Mult o (Id(1, 0), Const(4))
 
    84 val Eq = Cn(2, Minus, List(Cn(2, Const(1), List(Id(2, 0))), 
    96 val Pred = Pr(Z, Id(3, 1)) o (Id(1, 0), Id(1, 0))
 
    85            Cn(2, Add, List(Cn(2, Minus, List(Id(2, 0), Id(2, 1))), 
    97 val Minus = Pr(Id(1, 0), Pred o Id(3, 2))
 
    86              Cn(2, Minus, List(Id(2, 1), Id(2, 0)))))))
 
    98 val Power = Pr(Const(1), Mult o (Id(3, 0), Id(3, 2)))
 
    87 val Noteq = Cn(2, Not, List(Cn(2, Eq, List(Id(2, 0), Id(2, 1))))) 
    99 val Fact = Pr(Const(1), Mult o (Id(3, 2), S o Id(3, 1))) o (Id(1, 0), Id(1, 0))
 
    88 val Conj = Cn(2, Sign, List(Cn(2, Mult, List(Id(2, 0), Id(2, 1)))))
 
   100 
    89 val Disj = Cn(2, Sign, List(Cn(2, Add, List(Id(2, 0), Id(2, 1)))))
 
   101 val Sign = Minus o (Const(1), Minus o (Const(1), Id(1, 0)))
 
       
   102 val Less = Sign o (Minus o (Id(2, 1), Id(2, 0)))
 
       
   103 val Not = Minus o (Const(1), Id(1, 0))
 
       
   104 val Eq = Minus o (Const(1) o Id(2, 0), 
       
   105                   Add o (Minus o (Id(2, 0), Id(2, 1)), 
       
   106                          Minus o (Id(2, 1), Id(2, 0))))
 
       
   107 val Noteq = Not o (Eq o (Id(2, 0), Id(2, 1)))
 
       
   108 val Conj = Sign o (Mult o (Id(2, 0), Id(2, 1)))
 
       
   109 val Disj = Sign o (Add o (Id(2, 0), Id(2, 1)))
 
    90 
   110 
    91 def Nargs(n: Int, m: Int) : List[Rec] = m match {
 
   111 def Nargs(n: Int, m: Int) : List[Rec] = m match {
 
    92   case 0 => Nil
 
   112   case 0 => Nil
 
    93   case m => Nargs(n, m - 1) ::: List(Id(n, m - 1))
 
   113   case m => Nargs(n, m - 1) ::: List(Id(n, m - 1))
 
    94 }
 
   114 }
 
    95 
   115 
    96 def Sigma(f: Rec) = {
 
   116 def Sigma(f: Rec) = {
 
    97   val ar = arity(f)  
   117   val ar = f.arity
 
    98   Pr(ar - 1, Cn(ar - 1, f, Nargs(ar - 1, ar - 1) :::
 
   118   Pr(Cn(ar - 1, f, Nargs(ar - 1, ar - 1) ::: List(Const(0) o Id(ar - 1, 0))), 
    99                     List(Cn(ar - 1, Const(0), List(Id(ar - 1, 0))))), 
   119      Add o (Id(ar + 1, ar), 
   100              Cn(ar + 1, Add, List(Id(ar + 1, ar), 
   120             Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: List(S o (Id(ar + 1, ar - 1))))))
 
   101                     Cn(ar + 1, f, Nargs(ar + 1, ar - 1) :::
 
       
   102                         List(Cn(ar + 1, S, List(Id(ar + 1, ar - 1))))))))
 
       
   103 }
 
   121 }
 
   104 
   122 
   105 def Accum(f: Rec) = {
 
   123 def Accum(f: Rec) = {
 
   106   val ar = arity(f)  
   124   val ar = f.arity
 
   107   Pr(ar - 1, Cn(ar - 1, f, Nargs(ar - 1, ar - 1) :::
 
   125   Pr(Cn(ar - 1, f, Nargs(ar - 1, ar - 1) ::: List(Const(0) o Id(ar - 1, 0))), 
   108                     List(Cn(ar - 1, Const(0), List(Id(ar - 1, 0))))), 
   126      Mult o (Id(ar + 1, ar), 
   109              Cn(ar + 1, Mult, List(Id(ar + 1, ar), 
   127              Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: List(S o Id(ar + 1, ar - 1)))))
 
   110                     Cn(ar + 1, f, Nargs(ar + 1, ar - 1) :::
 
       
   111                         List(Cn(ar + 1, S, List(Id(ar + 1, ar - 1))))))))
 
       
   112 }
 
   128 }
 
   113 
   129 
   114 def All(t: Rec, f: Rec) = {
 
   130 def All(t: Rec, f: Rec) = {
 
   115   val ar = arity(f)
 
   131   val ar = f.arity
 
   116   Cn(ar - 1, Sign, List(Cn(ar - 1, Accum(f), Nargs(ar - 1, ar - 1) ::: List(t))))
 
   132   Sign o (Cn(ar - 1, Accum(f), Nargs(ar - 1, ar - 1) ::: List(t)))
 
   117 }
 
   133 }
 
   118 
   134 
   119 def Ex(t: Rec, f: Rec) = {
 
   135 def Ex(t: Rec, f: Rec) = {
 
   120   val ar = arity(f)
 
   136   val ar = f.arity
 
   121   Cn(ar - 1, Sign, List(Cn(ar - 1, Sigma(f), Nargs(ar - 1, ar - 1) ::: List(t))))
 
   137   Sign o (Cn(ar - 1, Sigma(f), Nargs(ar - 1, ar - 1) ::: List(t)))
 
   122 }
 
   138 }
 
   123 
   139 
   124 //Definition on page 77 of Boolos's book.
 
   140 //Definition on page 77 of Boolos's book.
 
   125 def Minr(f: Rec) = {
 
   141 def Minr(f: Rec) = {
 
   126   val ar = arity(f)
 
   142   val ar = f.arity
 
   127   val rq = All(Id(ar, ar - 1), 
   143   Sigma(All(Id(ar, ar - 1), Not o (Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: List(Id(ar + 1, ar))))))
 
   128     Cn(ar + 1, Not, List(Cn(ar + 1, f, Nargs(ar + 1, ar - 1) ::: List(Id(ar + 1, ar)))))) 
       
   129   Sigma(rq)
 
       
   130 }
 
   144 }
 
   131 
   145 
   132 //Definition on page 77 of Boolos's book.
 
   146 //Definition on page 77 of Boolos's book.
 
   133 def Maxr(f: Rec) = {
 
   147 def Maxr(f: Rec) = {
 
   134   val ar  = arity(f) 
   148   val ar  = f.arity
 
   135   val rt  = Id(ar + 1, ar - 1) 
   149   val rt  = Id(ar + 1, ar - 1) 
   136   val rf1 = Cn(ar + 2, Less, List(Id(ar + 2, ar + 1), Id(ar + 2, ar))) 
   150   val rf1 = Less o (Id(ar + 2, ar + 1), Id(ar + 2, ar)) 
   137   val rf2 = Cn(ar + 2, Not, List(Cn (ar + 2, f, Nargs(ar + 2, ar - 1) ::: List(Id(ar + 2, ar + 1))))) 
   151   val rf2 = Not o (Cn (ar + 2, f, Nargs(ar + 2, ar - 1) ::: List(Id(ar + 2, ar + 1)))) 
   138   val rf  = Cn(ar + 2, Disj, List(rf1, rf2)) 
   152   val Qf  = Not o All(rt, Disj o (rf1, rf2)) 
   139   val rq  = All(rt, rf) 
       
   140   val Qf  = Cn(ar + 1, Not, List(rq))
 
       
   141   Cn(ar, Sigma(Qf), Nargs(ar, ar) ::: List(Id(ar, ar - 1)))
 
   153   Cn(ar, Sigma(Qf), Nargs(ar, ar) ::: List(Id(ar, ar - 1)))
 
   142 }
 
   154 }
 
       
   155 
       
   156 
       
   157 //Prime test
 
       
   158 val Prime = Conj o (Less o (Const(1), Id(1, 0)),
 
       
   159                     All(Minus o (Id(1, 0), Const(1)), 
       
   160                         All(Minus o (Id(2, 0), Const(1) o Id(2, 0)), 
       
   161                             Noteq o (Mult o (Id(3, 1), Id(3, 2)), Id(3, 0)))))
 
       
   162 
       
   163 //Returns the first prime number after n (very slow for n > 4)
 
       
   164 val NextPrime = {
 
       
   165   val R = Conj o (Less o (Id(2, 0), Id(2, 1)), Prime o Id(2, 1))
 
       
   166   Minr(R) o (Id(1, 0), S o Fact)
 
       
   167 }
 
       
   168 
       
   169 val NthPrime = Pr(Const(2), NextPrime o Id(3, 2)) o (Id(1, 0), Id(1, 0))
 
       
   170 
       
   171 def Listsum(k: Int, m: Int) : Rec = m match {
 
       
   172   case 0 => Z o Id(k, 0)
 
       
   173   case n => Add o (Listsum(k, n - 1), Id(k, n - 1))
 
       
   174 }
 
       
   175 
       
   176 //strt-function on page 90 of Boolos, but our definition generalises 
       
   177 //the original one in order to deal with multiple input-arguments
 
       
   178 
       
   179 def Strt(n: Int) = {
 
       
   180   
       
   181   def Strt_aux(l: Int, k: Int) : Rec = k match {
 
       
   182     case 0 => Z o Id(l, 0)
 
       
   183     case n => {
 
       
   184       val rec_dbound = Add o (Listsum(l, n - 1), Const(n - 1) o Id(l, 0))
 
       
   185       Add o (Strt_aux(l, n - 1), 
       
   186              Minus o (Power o (Const(2) o Id(l, 0), Add o (Id(l, n - 1), rec_dbound)), 
       
   187                       Power o (Const(2) o Id(l, 0), rec_dbound)))
 
       
   188     }
 
       
   189   }
 
       
   190 
       
   191   def Rmap(f: Rec, k: Int) = (0 until k).map{i => f o Id(k, i)}.toList
 
       
   192  
       
   193   Cn(n, Strt_aux(n, n), Rmap(S, n))
 
       
   194 }
 
       
   195 
   143 
   196 
   144 //Mutli-way branching statement on page 79 of Boolos's book
 
   197 //Mutli-way branching statement on page 79 of Boolos's book
 
   145 def Branch(rs: List[(Rec, Rec)]) = {
 
   198 def Branch(rs: List[(Rec, Rec)]) = {
 
   146   val ar = arity(rs.head._1)
 
   199 
   147   
       
   148   def Branch_aux(rs: List[(Rec, Rec)], l: Int) : Rec = rs match {
 
   200   def Branch_aux(rs: List[(Rec, Rec)], l: Int) : Rec = rs match {
 
   149     case Nil => Cn(l, Z, List(Id(l, l - 1)))
 
   201     case Nil => Z o Id(l, l - 1)
 
   150     case (rg, rc)::recs => Cn(l, Add, List(Cn(l, Mult, List(rg, rc)), Branch_aux(recs, l)))
 
   202     case (rg, rc)::recs => Add o (Mult o (rg, rc), Branch_aux(recs, l))
 
   151   }
 
   203   }
 
   152 
   204 
   153   Branch_aux(rs, ar)
 
   205   Branch_aux(rs, rs.head._1.arity)
 
   154 }
 
   206 }
 
   155 
   207 
   156 //Factorial
 
   208 }
 
   157 val Fact = {
 
       
   158   val Fact_aux = Pr(1, Const(1), Cn(3, Mult, List(Id(3, 2), Cn(3, S, List(Id(3, 1))))))
 
       
   159   Cn(1, Fact_aux, List(Id(1, 0), Id(1, 0)))
 
       
   160 }
 
       
   161 
       
   162 //Prime test
 
       
   163 val Prime = Cn(1, Conj, List(Cn(1, Less, List(Const(1), Id(1, 0))),
 
       
   164                              All(Cn(1, Minus, List(Id(1, 0), Const(1))), 
       
   165                                  All(Cn(2, Minus, List(Id(2, 0), Cn(2, Const(1), List(Id(2, 0))))), 
       
   166                                      Cn(3, Noteq, List(Cn(3, Mult, List(Id(3, 1), Id(3, 2))), Id(3, 0)))))))
 
       
   167 
       
   168 //Returns the first prime number after n
 
       
   169 val NextPrime = {
 
       
   170   val R = Cn(2, Conj, List(Cn(2, Less, List(Id(2, 0), Id(2, 1))), 
       
   171                            Cn(2, Prime, List(Id(2, 1)))))
 
       
   172   Cn(1, Minr(R), List(Id(1, 0), Cn(1, S, List(Fact))))
 
       
   173 }
 
       
   174 
       
   175 val NthPrime = {
 
       
   176   val NthPrime_aux = Pr(1, Const(2), Cn(3, NextPrime, List(Id(3, 2))))
 
       
   177   Cn(1, NthPrime_aux, List(Id(1, 0), Id(1, 0)))
 
       
   178 }
 
       
   179 
       
   180 def Listsum(k: Int, m: Int) : Rec = m match {
 
       
   181   case 0 => Cn(k, Z, List(Id(k, 0)))
 
       
   182   case n => Cn(k, Add, List(Listsum(k, n - 1), Id(k, n - 1)))
 
       
   183 }
 
       
   184 
       
   185 //strt-function on page 90 of Boolos, but our definition generalises 
       
   186 //the original one in order to deal with multiple input-arguments
 
       
   187 
       
   188 def Strt(n: Int) = {
 
       
   189   def Strt_aux(l: Int, k: Int) : Rec = k match {
 
       
   190     case 0 => Cn(l, Z, List(Id(l, 0)))
 
       
   191     case n => {
 
       
   192       val rec_dbound = Cn(l, Add, List(Listsum(l, n - 1), Cn(l, Const(n - 1), List(Id(l, 0)))))
 
       
   193       Cn(l, Add, List(Strt_aux(l, n - 1), 
       
   194                       Cn(l, Minus, List(Cn(l, Power, List(Cn(l, Const(2), List(Id(l, 0))), 
       
   195                                                           Cn(l, Add, List(Id(l, n - 1), rec_dbound)))), 
       
   196                                         Cn(l, Power, List(Cn(l, Const(2), List(Id(l, 0))), rec_dbound))))))
 
       
   197     }
 
       
   198   }
 
       
   199 
       
   200   def Rmap(f: Rec, k: Int) = (0 until k).map{i => Cn(k, f, List(Id(k, i)))}.toList
 
       
   201  
       
   202   Cn(n, Strt_aux(n, n), Rmap(S, n))
 
       
   203 }
 
       
   204 
       
   205 }
tm