simple-sub1

simplesub1.scala

import scala.collection.mutable.{Set => MutSet}
object simplesub1 extends App {
  sealed trait Term
  final case class Lit(value: Int) extends Term                         // as in: 27
  final case class Var(name: String) extends Term                       // as in: x
  final case class Lam(name: String, rhs: Term) extends Term            // as in: λx . t
  final case class App(lhs: Term, rhs: Term) extends Term               // as in: s t
  final case class Rcd(fields: List[(String, Term)]) extends Term       // as in: { a : 0; b : true; ... }
  final case class Sel(receiver: Term, fieldName: String) extends Term  // as in: t .a

  assert(typeTerm(Lit(1))(Map.empty)==Primitive("int"))
  println(typeTerm(App(Lam("x",Var("x")),Lit(1)))(Map.empty))
  println(typeTerm(Lam("x",Var("x")))(Map.empty))

  class VariableState(var lowerBounds: List[SimpleType],
                      var upperBounds: List[SimpleType])
  sealed trait SimpleType
  final case class Variable(st: VariableState) extends SimpleType
  final case class Primitive(name: String) extends SimpleType
  final case class Function(lhs: SimpleType, rhs: SimpleType) extends SimpleType
  final case class Record(fields: List[(String, SimpleType)]) extends SimpleType
  type Ctx = Map[String, SimpleType]

  def typeTerm(term: Term)(implicit ctx: Ctx): SimpleType = term match {
      // 整数リテラル:
      case Lit(n) => Primitive("int")
      // 変数参照:
      case Var(name) => ctx.getOrElse(name, err("not found: " + name))
      // レコード生成:
      case Rcd(fs) => Record(fs.map { case (n, t) => (n, typeTerm(t)) })
      // ラムダ抽象:
      case Lam(name, body) =>
        val param = freshVar
        Function(param, typeTerm(body)(ctx + (name -> param)))
      // 関数適用:
      case App(f, a) =>
        val res = freshVar
        constrain(typeTerm(f), Function(typeTerm(a), res))(MutSet.empty)
        res
      // レコードフィールドの選択:
      case Sel(obj, name) =>
        val res = freshVar
        constrain(typeTerm(obj), Record((name -> res) :: Nil))(MutSet.empty)
        res
    }
    def freshVar: Variable =
      Variable(new VariableState(Nil, Nil))
    def err(msg: String): Nothing =
      throw new Exception("type error: " + msg)

    def constrain(lhs: SimpleType, rhs: SimpleType)
          (implicit cache: MutSet[(SimpleType, SimpleType)]): Unit = {
      if (cache.contains(lhs -> rhs)) return () else cache += lhs -> rhs
      (lhs, rhs) match {
        case (Primitive(n0), Primitive(n1)) if n0 == n1 =>
        case (Function(l0, r0), Function(l1, r1)) =>
          constrain(l1, l0); constrain(r0, r1)
        case (Record(fs0), Record(fs1)) =>
          fs1.foreach { case (n1, t1) =>
            fs0.find(_._1 == n1) match {
              case None => err("missing field: " + n1 + " in " + lhs)
              case Some((_, t0)) => constrain(t0, t1)
            }
          }
        case (Variable(lhs), rhs) =>
          lhs.upperBounds = rhs :: lhs.upperBounds
          lhs.lowerBounds.foreach(constrain(_, rhs))
        case (lhs, Variable(rhs)) =>
          rhs.lowerBounds = lhs :: rhs.lowerBounds
          rhs.upperBounds.foreach(constrain(lhs, _))
        case _ => err("cannot constrain " + lhs + " <: " + rhs)
      }
    }
}