不変の型指定可能なツリーの設計

Question

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

はシンプル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. 
} 

これを書くのはかなり簡単ですが、2つの大きな問題が付属しています：

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

私の質問は次のとおりです。

1. 私はExpr階層を1回しか定義する必要はありません。
2. タイプされたツリーとタイプのないツリーには異なるタイプがあり、それらを互換性のないものにすることができます。

編集：（：例えば、case class ClassType(classID : String) extends Type思う）もう一つの要件は、それは種類の無制限かつ予測不可能な数字で型システムのために働くべきであるということです。

Answer 1

これは、タイプレベルプログラミングのための完全な使用例です。

まず、我々はタイプレベルNoneの面で型なしの木を表し、タイプレベルSome[X]の観点タイプXの木々を入力できるように、我々はタイプレベルOptionが必要になります。

// 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 

：我々は、我々の型システムの階層をレイアウト210

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] 

---

EDIT：

シンプルだが、完全な型チェック機能：答えを

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 
} 

Answer 2

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

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

異なる発現型

単純に2つの階層、TypedExpression <: Expressionと1とUntypedExpression <: Expressionのものを作ります。このアプローチはおそらく2つのほぼ同一のクラス階層をもたらすでしょう。

タイプパラメータ信号Typedness 2つの階層のオーバーヘッドを除去するために

を作る（およびいくつかの種類の定型文を取得する）、あなたは、単一の階層を作ることができるとa bool typeのための型のparamaterを追加します。

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

私が実際に何千もの問題を抱えているかどうかはわかりません。しかし、これは私が試みるものです。

Answer 3

不変にするには、内容を変更する代わりに、新しいExprを作成することができます。ケースクラスにはcopy methodがあり、これだけでも使用できます。

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とのマッチングによって、型付けされているかどうかを調べることで問題を解決できます。彼らはまた、異なるタイプを持っており、そのタイプは、コピーと共に変化すると変化します。