1 import scala.annotation.tailrec

     2 

     3 //some list functions

     4 def tl[A](xs: List[A]) : List[A] = xs match {

     5   case Nil => Nil

     6   case x::xs => xs

     7 }

     8 

     9 def hd[A](xs: List[A]) : A = xs.head

    10 

    11 def nth_of[A](xs: List[A], n: Int) = 

    12   if (n <= xs.length) Some(xs(n)) else None 

    13 

    14 

    15 //some map functions

    16 def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)

    17 

    18 

    19 //some string functions

    20 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)

    21 

    22 

    23 

    24 sealed abstract class Cell {

    25   def * (n: Int) : List[Cell] = n match {

    26     case 0 => Nil

    27     case n => this :: this * (n - 1)

    28   }

    29 }

    30 case object Bk extends Cell { override def toString = "0" }

    31 case object Oc extends Cell { override def toString = "1" }

    32 

    33 sealed abstract class Action

    34 case object WBk extends Action

    35 case object WOc extends Action

    36 case object R extends Action

    37 case object L extends Action

    38 case object Nop extends Action

    39 

    40 type State = Int

    41 type Inst = (Action, State)

    42 type Prog = List[Inst]

    43 

    44 //tapes

    45 case class Tape(l: List[Cell], r: List[Cell]) {

    46   def update(a: Action) = a match {

    47     case WBk => Tape(l, Bk::tl(r))

    48     case WOc => Tape(l, Oc::tl(r))

    49     case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)

    50     case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))

    51     case Nop => Tape(l, r)

    52   }

    53 

    54   def read = r match {

    55     case Nil => Bk

    56     case x::_ => x

    57   }

    58 

    59   override def toString = join(l.reverse) + ">" + join(r)

    60 }

    61 

    62 // standard tapes

    63 class STape(ns: Int*) extends 

    64   Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))

    65   

    66 

    67 // configurations

    68 case class Config(s: State, tp: Tape) {

    69   def is_final = s == 0

    70 

    71   override def toString = tp.toString

    72 }

    73 

    74 

    75 // Turing machines

    76 case class TM(p: Prog) {

    77 

    78   def ++ (that: TM) = TM(this.p ::: that.p)

    79 

    80   def shift(n: Int) =

    81     TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})

    82   def adjust(n: Int) : TM =

    83     TM(p.map{case (a, s) => (a, if (s == 0) n else s)})

    84   def adjust : TM = adjust(p.length / 2 + 1)

    85   

    86   def fetch(s: State, a: Cell) = (s, a) match {

    87     case (0, _) => (Nop, 0)

    88     case (s, Bk) => nth_of(p, 2 * (s - 1)) match {

    89       case None => (Nop, 0)

    90       case Some(i) => i

    91     }

    92     case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {

    93       case None => (Nop, 0)

    94       case Some(i) => i

    95     }

    96   } 

    97 

    98   def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {

    99     case (a, s_next) => Config(s_next, cf.tp.update(a))

   100   }

   101 

   102   def steps(cf: Config, n: Int) : Config = n match {

   103     case 0 => cf

   104     case n => steps(step(cf), n - 1)

   105   } 

   106 

   107   @tailrec

   108   final def run(cf: Config) : Config = {

   109     if (cf.is_final) cf else run(step(cf))

   110   }

   111  

   112   def run(tp: Tape) : Tape = run(Config(1, tp)).tp

   113 }

   114 

   115 

   116 // Turing machine examples

   117 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 

   118                      (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 

   119                      (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 

   120                      (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 

   121                      (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 

   122                      (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))

   123 

   124 def TMFindnth(n: Int) : TM = n match {

   125   case 0 => TM(Nil)

   126   case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))

   127 }

   128 

   129 def TMMopup(n: Int) = {

   130   def TMMopup1(n: Int) : TM = n match {

   131     case 0 => TM(Nil)

   132     case n => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))

   133   }

   134 

   135   val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),

   136                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))

   137 

   138   TMMopup1(n) ++ TMMopup2.shift(2 * n)

   139 }

   140 

   141 println("TMCopy:    " + (TMCopy.run(new STape(3))))

   142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))

   143 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))

   144 

   145 

   146 // Abacus machines

   147 sealed abstract class AInst 

   148 case class Inc(n: Int) extends AInst

   149 case class Dec(n: Int, l: Int) extends AInst

   150 case class Goto(l: Int) extends AInst

   151 

   152 

   153 type AProg = List[AInst]

   154 type Regs = Map[Int, Int]

   155 

   156 case class AConfig(s: Int, regs: Regs)  

   157 

   158 case class Abacus(p: AProg) {

   159 

   160   def ++ (that: Abacus) = Abacus(this.p ::: that.p)

   161 

   162   def shift(offset: Int, jump: Int) = Abacus(p.map(_ match {

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

   173 

   174   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {

   175     case (None, _) => cf

   176     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))

   177     case (Some(Dec(n, l)), s) => {

   178       if (dget(cf.regs, n) == 0) AConfig(l, cf.regs)

   179       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))

   180     }

   181     case (Some(Goto(l)), _) => AConfig(l, cf.regs)

   182   }  

   183 

   184   def steps(cf: AConfig, n: Int) : AConfig = n match {

   185     case 0 => cf

   186     case n => steps(step(cf), n - 1)

   187   } 

   188 

   189   def steps(regs: Regs, n: Int) : AConfig = steps(AConfig(0, regs), n)

   190 

   191   def run(cf: AConfig) : AConfig = {

   192     if (cf.s >= p.length || cf.s < 0) cf else run(step(cf))

   193   }

   194  

   195   def run(regs: Regs): Regs = run(AConfig(0, regs)).regs

   196 }

   197 

   198 // Abacus examples

   199 def Copy(in: Int, out: Int, jump: Int) = 

   200   Abacus(List(Dec(in, jump), Inc(out), Goto(0))) 

   201 

   202 def Plus(m: Int, n: Int, tmp: Int, jump: Int) =

   203   Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) 

   204 

   205 def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = 

   206   Abacus(List(Dec(in1, jump))) ++ Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0)

   207 

   208 def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = {

   209   Abacus(List(Inc(out), Dec(in1, jump))) ++ 

   210   Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) ++

   211   Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)

   212 }

   213 

   214 println("Copy: 3     " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))

   215 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))

   216 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))

   217 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))

   218 

   219 

   220 

   221 // Abacus to TM translation

   222 def layout(p: AProg) = p.map(_ match {

   223   case Inc(n) => 2 * n + 9 

   224   case Dec(n, _) => 2 * n + 16 

   225   case Goto(n) => 1

   226 })

   227 

   228 def start(p: AProg, n: Int) = layout(p).take(n).sum + 1

   229 

   230 def compile_Inc(s: Int, n: Int) = {

   231   val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 

   232                       (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),

   233                       (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))

   234   TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)

   235 }

   236 

   237 def compile_Dec(s: Int, n: Int, e: Int) = {

   238   val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),

   239                       (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),

   240                       (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),

   241                       (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),

   242                       (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),

   243                       (R, 0), (WBk, 16)))

   244   TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)

   245 }

   246 

   247 def compile_Goto(s: Int) = {

   248   val TMGoto = TM(List((Nop, 1), (Nop, 1)))

   249   TMGoto.shift(s - 1)

   250 }

   251 

   252 def compile(p: AProg, s: Int, i: AInst) = i match {

   253   case Inc(n) => compile_Inc(s, n)

   254   case Dec(n, e) => compile_Dec(s, n, start(p, e))

   255   case Goto(e) => compile_Goto(start(p, e))

   256 }

   257 

   258 def tms(p: AProg) = {

   259   val ss = (0 until p.length).map (start(p,_))

   260   (ss zip p).map{case (n, i) => compile(p, n, i)}

   261 }

   262 

   263 def toTM(p: AProg) = tms(p).reduceLeft(_ ++ _)

   264 

   265 //examples

   266 println("Copy 3:     " + toTM(Copy(0, 1, Int.MaxValue).p).run(new STape(3,0,0)))

   267 println("Plus 3 + 4: " + toTM(Plus(0, 1, 2, Int.MaxValue).p).run(new STape(3,4,0,0)))

   268 println("Mult 3 * 5: " + toTM(Mult(0, 1, 2, 3, Int.MaxValue).p).run(new STape(3,5,0,0)))

   269 println("Expo 3 ^ 4: " + toTM(Expo(0, 1, 2, 3, 4, 10000).p).run(new STape(3,4,0,0,0)))

   270 

   271 

   272 //Recursive Functions

   273 abstract class Rec {

   274   def eval(ns: List[Int]) : Int

   275 }

   276 case object Z extends Rec {

   277   override def eval(ns: List[Int]) = ns match {

   278     case n::Nil => 0

   279     case _ => throw new IllegalArgumentException("Z: args")

   280   }

   281 } 

   282 case object S extends Rec {

   283   override def eval(ns: List[Int]) = ns match {

   284     case n::Nil => n + 1

   285     case _ => throw new IllegalArgumentException("S: args")

   286   }

   287 } 

   288 case class Id(n: Int, m: Int) extends Rec {

   289   override def eval(ns: List[Int]) = 

   290     if (ns.length == n && m < n) ns(m)

   291     else throw new IllegalArgumentException("Id: args")

   292 }

   293 case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {

   294   override def eval(ns: List[Int]) = 

   295     if (ns.length == n) f.eval(gs.map(_.eval(ns)))

   296     else throw new IllegalArgumentException("Cn: args")

   297 }

   298 case class Pr(n: Int, f: Rec, g: Rec) extends Rec {

   299   override def eval(ns: List[Int]) = 

   300     if (ns.length == n - 1) {

   301       if (ns.last == 0) f.eval(ns.init)

   302       else {

   303         val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))

   304         g.eval(ns.init ::: List(ns.last - 1, r))

   305       }

   306     }

   307     else throw new IllegalArgumentException("Cn: args")

   308 }

   309 case class Mn(n: Int, f: Rec) extends Rec {

   310   override def eval(ns: List[Int]) = 0

   311     

   312 }

   313