TAPL 3.5.17の演習問題

arith.scala

 Arith extends App {
  type Info = String

  sealed trait Term
  case class TmTrue(s: Info) extends Term
  case class TmFalse(s: Info) extends Term
  case class TmIf(s: Info, cond: Term, t: Term, f: Term) extends Term
  case class TmZero(s: Info) extends Term
  case class TmSucc(s: Info, t: Term) extends Term
  case class TmPred(s: Info, t: Term) extends Term
  case class TmIsZero(s: Info, t: Term) extends Term

  def isNumericVal(t: Term):Boolean = t match {
    case TmZero(_) => true
    case TmSucc(_, t1) => isNumericVal(t1)
    case _ => false
  }

  object NumericVal{
    def unapply(t: Term):Option[Term] = if(isNumericVal(t)) Some(t) else None
  }
  def isVal(t: Term) = t match {
    case TmTrue(_) | TmFalse(_) => true
    case NumericVal(_) => true
    case _ => false
  }

  val dummyInfo = "DUMMY"

  def eval1: Term => Term = {
    case TmIf(_, TmTrue(_), t2, _) => t2
    case TmIf(_, TmFalse(_), t2, t3) => t3
    case TmIf(fi, t1, t2, t3) => 
      val t1_ = eval1(t1)
      TmIf(fi, t1_, t2, t3)
    case TmSucc(fi, t1) => 
      val t1_ = eval1(t1)
      TmSucc(fi, t1_)
    case TmPred(_, TmZero(_)) => TmZero(dummyInfo)
    case TmPred(_, TmSucc(_, NumericVal(nv1))) => nv1
    case TmPred(fi, t1) => 
      val t1_ = eval1(t1)
      TmPred(fi, t1_)
    case TmIsZero(_, TmZero(_)) => TmTrue(dummyInfo)
    case TmIsZero(_, TmSucc(_, NumericVal(nv1))) => TmFalse(dummyInfo)
    case TmIsZero(fi, t1) =>
      val t1_ = eval1(t1)
      TmIsZero(fi, t1_)
    case _ => throw new Exception("No Rule Applies")
  }

  object Value{
    def unapply(t: Term) = if (isVal(t)) Some(t) else None
  }

  object ⇓ {
    import scala.util.control.Exception._
    def unapply(t: Term) = allCatch opt (eval(t))
  }

  // 未テスト & 効率悪い
  def eval: Term => Term = {
    case Value(v) => v
    case TmIf(_, ⇓(TmTrue(_)), ⇓(Value(v)), _) => v
    case TmIf(_, ⇓(TmFalse(_)), _, ⇓(Value(v))) => v
    case TmSucc(_, ⇓(t)) => TmSucc(dummyInfo, t)
    case TmPred(_, ⇓(TmZero(_))) => TmZero(dummyInfo)
    case TmPred(_, ⇓(TmSucc(_, t))) => t
    case TmIsZero(_, ⇓(TmZero(_))) => TmTrue(dummyInfo)
    case TmIsZero(_, ⇓(TmSucc(_, _))) => TmFalse(dummyInfo)
    case _ => throw new Exception("No Rule Applies")
  }

  println(eval1(TmIsZero("isZero", TmSucc("1", TmZero("0")))))
  val code = eval1(
    TmIf("if", 
      TmIsZero("isZero", TmSucc("1", TmZero("0"))),
      TmFalse("false"),
      TmSucc("w", TmZero("dummy"))))
  println(eval(code))
}