5

これは、私が繰り返し直面した設計上の問題です。コンパイラを構築しているとします。どのように型をツリーに格納しますか?

単純なExprand階層を考えて、 andがポリモーフィックTypeであると仮定します (たとえば、 just のブール値に加えて)。PlusEquals||

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

これはかなり簡単に記述できますが、次の 2 つの大きな問題があります。

  • Exprs は変更可能です。突然変異が好きな人はいません。
  • 型付きと型なしの式は区別できません。引数が型付き式でなければならないことを署名が指定している関数を書くことができません。

だから私の質問は次のとおりです。次のような型付けされていない可能性のあるツリーを定義するための良い方法は何ですか (私はあえてデザインパターンとは言いません):

  1. Expr階層を一度だけ定義する必要があります。
  2. 型付けされたツリーと型付けされていないツリーには異なる型があり、それらを非互換にすることを選択できます。

編集:もう1つの要件は、無制限で予測不可能な数の型を持つ型システムで機能する必要があることです(case class ClassType(classID : String) extends Typeたとえば、 を考えてください)。

4

3 に答える 3

6

これは、タイプレベルのプログラミングの完璧なユースケースです。

まず、型レベルの観点から型指定されていないツリーと型レベルの観点から型付けされたタイプOptionのツリーを表すことができるように、型レベルが必要です。NoneXSome[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], r: 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, l, None) => for {
      lt <- typeCheck(l, env)
      lType <- lt.getType
      rt <- typeCheck(r, env)
      rType <- rt.getType
      if rType == lType
    } yield Equals[Typed[BoolType]](lt, rt, 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
}
于 2012-10-24T20:32:17.940 に答える
3

不変にするために、その内容を変更する代わりに、新しい Expr を作成できます。ケース クラスには、まさにこれに使用できるcopy メソッドがあります。

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

class Expr[A <: Type](tpe : Type = Untyped)

case class Var[A <: Type](id : String, tpe : Type = Untyped) extends Expr[A](tpe)
case class Plus[A <: Type](l : Expr, tpe : Type = Untyped) extends Expr[A](tpe)
case class Equals[A <: Type](l : Expr, tpe : Type = Untyped) extends Expr[A](tpe)

これで、次のようなあらゆる種類の素晴らしいことを自由に行うことができます。

val x = Var("name")
val y = x.copy(tpe = IntType)

ただし、現在は不変です。Var、Plus、および Equals の引数の 1 つになったので、tpe と照合することで、型付けされているかどうかを判断することで問題を解決できます。それらにもさまざまなタイプがあり、コピーによって tpe が変化するとタイプが変わります。

于 2012-10-24T20:14:11.087 に答える
1

これは単なるアイデアです。

まず、不変にしたい場合は、明らかに変数を削除する必要がありますtpe。

異なる式のタイプ

1つはで、もう1つはで2つの階層を作成するだけTypedExpression <: ExpressionですUntypedExpression <: Expression。このアプローチでは、おそらく2つのほぼ同じクラス階層が作成されます。

タイプパラメータ信号のタイプを作成します

2つの階層のオーバーヘッドを取り除く（そしてある種の定型文を取得する）ために、単一の階層を作成し、bool型の型パラメーターを追加することができます。

sealed trait TBool
sealed trait TTrue extends TBool
sealed trait TFalse extends TBool

trait Expression[T <: TBool]{
  //ensure that this gets only called on typed expressions
  def getType(implicit e: T =:= TTrue): Type
  def typeMe(m: Map[String,Type]): Expression[TTrue] = this.asInstanceOf[Expression[TTrue]]
}

これを行うと、何千もの問題が発生するかどうかはわかりません。しかし、これは私が試みることです。

于 2012-10-24T19:52:01.370 に答える