scala – 不可变的,可打字的树的设计

发布时间：2020-12-16 18:40:36 所属栏目：安全来源：网络整理

导读：这是我一再遇到的设计问题.假设您正在构建编译器,如何在树中存储类型？考虑一个简单的Expr和Type层次结构,并假设Plus和Equals是多态的(例如,仅加上||中的布尔值). trait Typecase object BoolType extends Typecase object IntType extends Typecase object

这是我一再遇到的设计问题.假设您正在构建编译器,如何在树中存储类型？

考虑一个简单的Expr和Type层次结构,并假设Plus和Equals是多态的(例如,仅加上||中的布尔值).

trait Type
case object BoolType extends Type
case object IntType extends Type
case object Untyped extends Type

trait Expr { var tpe : Type = Untyped }

case class Var(id : String) extends Expr
case class Plus(l : Expr,r : Expr) extends Expr
case class Equals(l : Expr,r : Expr) extends Expr
// ...

进一步假设我在构造表达式树时不知道标识符的类型,因此无法通过构造知道类型.
现在典型的类型检查功能可能如下所示：

def typeCheck(env : Map[String,Type])(expr : Expr) : Expr = expr match {
  case Var(id) =>
    expr.tpe = env(id)
    expr

  case Plus(l,r) =>
    val tl = typeCheck(env)(l)
    val tr = typeCheck(env)(r)
    assert(tl == tr)
    expr.tpe = tl
    expr

  // etc.
}

这写起来相当简单,但有两个主要问题：

> Exprs是可变的.没人喜欢变异.
>无法区分键入和无类型表达式.我不能编写一个函数,其签名指定其参数必须是一个类型化的表达式.

所以我的问题如下.什么是好方法(我不敢说设计模式)来定义可能无类型的树,这样：

>我只需要定义一次Expr层次结构.
>键入的和非类型化的树具有不同的类型,我可以选择使它们不兼容.

编辑：还有一个要求是它应该适用于具有无限且不可预测的类型数量的类型系统(例如：案例类ClassType(classID：String)扩展Type).

解决方法

这是类型级编程的完美用例！

首先,我们需要一个类型级别的选项,以便我们可以根据类型级别来表示非类型化树,并且在类型级别的某些[X]中表示类型为X的类型树：

// We are restricting our type-level option to
// only (potentially) hold subtypes of `Type`.
sealed trait IsTyped
sealed trait Untyped extends IsTyped
sealed trait Typed[T <: Type] extends IsTyped

接下来,我们布置我们的类型系统层次结构：

sealed trait Type

// We can create complicated subhierarchies if we want.
sealed trait SimpleType extends Type
sealed trait CompoundType extends Type

sealed trait PrimitiveType extends Type
sealed trait UserType extends Type

// Declaring our types.
case object IntType extends SimpleType with PrimitiveType

case object BoolType extends SimpleType with PrimitiveType

// A type with unbounded attributes.
case class ClassType(classId: String) extends CompoundType with UserType

// A type that depends statically on another type.
case class ArrayType(elemType: Type) extends CompoundType with PrimitiveType

现在,剩下的就是声明我们的表达式树：

sealed trait Expr[IT <: IsTyped] { val getType: Option[Type] }

// Our actual expression types.
case class Var[IT <: IsTyped](id: String,override val getType: Option[Type] = None) extends Expr[IT]

case class Plus[IT <: IsTyped](l: Expr[IT],r: Expr[IT],override val getType: Option[Type] = None) extends Expr[IT]

case class Equals[IT <: IsTyped](l: Expr[IT],override val getType: Option[Type] = None) extends Expr[IT]

case class ArrayLiteral[IT](elems: List[Expr[_ :< IsTyped]],override val getType: Option[Type] = None) extends Expr[IT]

编辑：

一个简单但完整的类型检查功能：

def typeCheck(expr: Expr[Untyped],env: Map[String,Type]): Option[Expr[Typed[_ :< Type]]] = expr match {
  case Var(id,None) if env isDefinedAt id => Var[Typed[_ <: Type]](id,Some(env(id)))
  case Plus(r,l,None) => for {
      lt <- typeCheck(l,env)
      IntType <- lt.getType
      rt <- typeCheck(r,env)
      IntType <- rt.getType
    } yield Plus[Typed[IntType]](lt,rt,Some(IntType))
  case Equals(r,env)
      lType <- lt.getType
      rt <- typeCheck(r,env)
      rType <- rt.getType
      if rType == lType
    } yield Equals[Typed[BoolType]](lt,Some(BoolType))
  case ArrayLiteral(elems,None) => {
    val elemst: List[Option[Expr[Typed[_ <: Type]]]] =
      elems map { typeCheck(_,env) }
    val elemType: Option[Type] = if (elemst.isEmpty) None else elemst map { elem =>
      elem map { _.getType }
    } reduce { (elemType1,elemType2) =>
      for {
        et1 <- elemType1
        et2 <- elemType2
        if et1 == et2
      } yield et1
    }
    if (elemst forall { _.isDefined }) elemType map { et =>
      ArrayLiteral[Typed[ArrayType]](elemst map { _.get },ArrayType(et))
    } else None
  }
  case _ => None
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!