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.
turing.scala
changeset 191 98370b96c1c5
parent 189 5974111de158
child 192 3c1107984b41
equal deleted inserted replaced
190:f1ecb4a68a54 191:98370b96c1c5 
       
     1 import scala.annotation.tailrec
 
     1 
     2 
     2 //some list functions
 
     3 //some list functions
 
     3 def tl[A](xs: List[A]) : List[A] = xs match {
 
     4 def tl[A](xs: List[A]) : List[A] = xs match {
 
     4   case Nil => Nil
 
     5   case Nil => Nil
 
     5   case x::xs => xs
 
     6   case x::xs => xs
 
   101   def steps(cf: Config, n: Int) : Config = n match {
 
   102   def steps(cf: Config, n: Int) : Config = n match {
 
   102     case 0 => cf
 
   103     case 0 => cf
 
   103     case n => steps(step(cf), n - 1)
 
   104     case n => steps(step(cf), n - 1)
 
   104   } 
   105   } 
   105 
   106 
   106   def run(cf: Config) : Config = {
 
   107   @tailrec
 
       
   108   final def run(cf: Config) : Config = {
 
   107     if (cf.is_final) cf else run(step(cf))
 
   109     if (cf.is_final) cf else run(step(cf))
 
   108   }
 
   110   }
 
   109  
   111  
   110   def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 
   112   def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 
   111 }
 
   113 }
 
   134                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
 
   136                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
 
   135 
   137 
   136   TMMopup1(n) ++ TMMopup2.shift(2 * n)
 
   138   TMMopup1(n) ++ TMMopup2.shift(2 * n)
 
   137 }
 
   139 }
 
   138 
   140 
   139 
       
   140 println("TMCopy:    " + (TMCopy.run(new STape(3))))
 
   141 println("TMCopy:    " + (TMCopy.run(new STape(3))))
 
   141 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
 
   142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
 
   142 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
   143 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
   143 
   144 
   144 
   145 
   146 abstract class AInst 
   147 abstract class AInst 
   147 case class Inc(n: Int) extends AInst
 
   148 case class Inc(n: Int) extends AInst
 
   148 case class Dec(n: Int, l: Int) extends AInst
 
   149 case class Dec(n: Int, l: Int) extends AInst
 
   149 case class Goto(l: Int) extends AInst
 
   150 case class Goto(l: Int) extends AInst
 
   150 
   151 
   151 // shifting and adjusting labels
 
       
   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 
   166 type AProg = List[AInst]
 
   153 type AProg = List[AInst]
 
   167 type Regs = Map[Int, Int]
 
   154 type Regs = Map[Int, Int]
 
   168 
   155 
   169 case class AConfig(s: Int, regs: Regs)  
   156 case class AConfig(s: Int, regs: Regs)  
   170 
   157 
   171 case class Abacus(p: AProg) {
 
   158 case class Abacus(p: AProg) {
 
   172 
   159 
   173    def ++ (that: Abacus) = Abacus(this.p ::: that.p)
 
   160   def ++ (that: Abacus) = Abacus(this.p ::: that.p)
 
   174 
   161 
   175   def shift(offset: Int, jump: Int) = Abacus(p.map(ashift(_, offset, jump)))
 
   162   def shift(offset: Int, jump: Int) = Abacus(p.map(_ match {
 
   176   def adjust(old_jump: Int, jump: Int) = Abacus(p.map(aadjust(_, old_jump, jump)))
 
   163     case Inc(n) => Inc(n)
 
       
   164     case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset)
 
       
   165     case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset)
 
       
   166   }))
 
       
   167       
       
   168   def adjust(old_jump: Int, jump: Int) = Abacus(p.map(_ match {
 
       
   169     case Inc(n) => Inc(n)
 
       
   170     case Dec(n, l) => if (l == old_jump) Dec(n, jump) else Dec(n, l)
 
       
   171     case Goto(l) => if (l == old_jump) Goto(jump) else Goto(l)
 
       
   172   }))
 
   177 
   173 
   178   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
 
   174   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
 
   179     case (None, _) => cf
 
   175     case (None, _) => cf
 
   180     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
 
   176     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
 
   181     case (Some(Dec(n, l)), s) => {
 
   177     case (Some(Dec(n, l)), s) => {
 
   183       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
 
   179       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
 
   184     }
 
   180     }
 
   185     case (Some(Goto(l)), _) => AConfig(l, cf.regs)
 
   181     case (Some(Goto(l)), _) => AConfig(l, cf.regs)
 
   186   }  
   182   }  
   187 
   183 
       
   184   
   188   def steps(cf: AConfig, n: Int) : AConfig = n match {
 
   185   def steps(cf: AConfig, n: Int) : AConfig = n match {
 
   189     case 0 => cf
 
   186     case 0 => cf
 
   190     case n => steps(step(cf), n - 1)
 
   187     case n => steps(step(cf), n - 1)
 
   191   } 
   188   } 
   192 
   189 
   213   Abacus(List(Inc(out), Dec(in1, jump))) ++ 
   210   Abacus(List(Inc(out), Dec(in1, jump))) ++ 
   214   Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++
 
   211   Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++
 
   215   Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
 
   212   Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
 
   216 }
 
   213 }
 
   217 
   214 
   218 
   215 println("Copy: 3     " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
 
   219 println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
 
       
   220 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
 
   216 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
 
   221 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
 
   217 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
 
   222 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
   218 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
   223 
   219 
   224 
   220 
       
   221 
   225 // Abacus to TM translation
 
   222 // Abacus to TM translation
 
       
   223 type Layout = List[Int]
 
       
   224 
       
   225 def layout(p: AProg) = p.map(_ match {
 
       
   226   case Inc(n) => 2 * n + 9 
       
   227   case Dec(n, _) => 2 * n + 16 
       
   228   case Goto(n) => 1
 
       
   229 })
 
       
   230 
       
   231 def start(ly: Layout, n: Int) = ly.take(n).sum + 1
 
       
   232 
   226 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
   233 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
   227                     (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
 
   234                     (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
 
   228                     (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
 
   235                     (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
 
   229 
   236 
   230 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
   237 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
   232                     (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
 
   239                     (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
 
   233                     (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
 
   240                     (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
 
   234                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
   241                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
   235                     (R, 0), (WBk, 16)))
 
   242                     (R, 0), (WBk, 16)))
 
   236 
   243 
   237 def TMINC(s: Int, n: Int, e: Int) = (TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n)).shift(s - 1).adjust(e)
 
   244 def TMINC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
 
   238 
   245 
   239 def TMDEC(s: Int, n: Int, e: Int) = (TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n)).shift(s - 1).adjust(e)
 
   246 def TMDEC(s: Int, n: Int, e: Int) = TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
 
   240 
   247 
   241 //def toTM()
 
   248 def TMGOTO(n: Int) = TM(List((Nop, n), (Nop, n)))
 
       
   249 
       
   250 def compile(ly: Layout, s: Int, i: AInst) = i match {
 
       
   251   case Inc(n) => TMINC(s, n)
 
       
   252   case Dec(n, e) => TMDEC(s, n, start(ly, e))
 
       
   253   case Goto(e) => TMGOTO(start(ly, e))
 
       
   254 }
 
       
   255 
       
   256 def tms(p: AProg) = {
 
       
   257   val ss = (0 until p.length).map (start(layout(p),_))
 
       
   258   (ss zip p).map{case (n, i) => compile(layout(p), n, i)}
 
       
   259 }
 
       
   260 
       
   261 def toTM(p: AProg) = tms(p).reduceLeft(_ ++ _)
 
       
   262 
       
   263 //examples
 
       
   264 println("Copy 3:     " + toTM(Copy(0, 1, Int.MaxValue).p).run(new STape(3,0,0)))
 
       
   265 println("Plus 3 + 4: " + toTM(Plus(0, 1, 2, Int.MaxValue).p).run(new STape(3,4,0,0)))
 
       
   266 println("Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(new STape(3,5,0,0)))
 
       
   267 println("Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(new STape(3,4,0,0,0)))
 
   242 
   268 
   243 
   269 
   244 //Recursive Functions
 
   270 //Recursive Functions
 
   245 abstract class Rec {
 
   271 abstract class Rec {
 
   246   def eval(ns: List[Int]) : Int
 
   272   def eval(ns: List[Int]) : Int
tm