這是我反覆面對的設計問題。假設你正在構建一個編譯器，你如何將這些類型存儲在樹中？不可改變的，可鍵入的樹木的設計

考慮一個簡單的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. 
}

這是相當直白地寫，但帶有兩個主要問題：

Expr s爲可變的。沒有人喜歡突變。
無法區分有類型和無類型的表達式。我不能寫一個函數，它的簽名指定它的參數必須是一個類型化的表達式。

所以我的問題是以下。什麼是一個好方法（我不敢說設計模式）來定義可能無類型的樹這樣的：

我需要定義只有一次Expr層次。
有類型和無類型的樹有不同的類型，我可以選擇使它們不兼容。

編輯：還有一個要求是它應類型的系統工作，無界和不可預知號碼類型（認爲：case class ClassType(classID : String) extends Type，例如）。

來源

2012-10-24 Philippe

這是一個完美的用例類型級編程！

首先，我們需要一個類型級Option，使我們可以在類型級None方面表示無類型的樹木和類型級Some[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], 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-24 20:32:17

用法示例很棒。你將如何在你的系統中重寫'typeCheck'？ –

這看起來可能是我正在尋找的東西。正如Eugene所建議的那樣，你能否展示一下如何使我的'typeCheck'函數適應你的定義？ – Philippe

我想你已經不小心混淆了None和Nothing。此外，而不是Nothing.type，我認爲你的意思是無。 – nnythm

這只是一個想法。

首先，如果你想變得不可變，顯然你必須擺脫變量tpe。

不同的表達類型

簡單地使兩個層次，一個與TypedExpression <: Expression和一個與UntypedExpression <: Expression。這種方法可能會導致兩個幾乎相同的類層次結構。

做一個類型參數信號Typedness

爲了消除這兩個層次的開銷（並得到一些類型的樣板），你可以做一個單一的層次結構，並添加一個類型paramater爲a bool type：

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-24 19:52:01 ziggystar

爲了使它不可變，你可以組成一個新的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)

然而，現在是不可改變的。你可以通過與tpe進行匹配來確定是否輸入了它，因爲它是Var，Plus和Equals的一個參數。他們也有不同的類型，他們的類型會隨着副本的變化而改變。

來源

2012-10-24 20:14:11 nnythm

感謝您的回答。這符合第一個要求（一切都是不可變的），但不是第二個要求（類型化和非類型化的樹有相同的--Scala--類型）。 – Philippe

啊，對，我正在處理可以與之匹配的擔憂，而不是他們有不同的類型。對於不同的類型，您可能希望使Typed成爲特性而不是對象。我將重新提交滿足該要求的解決方案。編輯：其實，剛剛意識到我沒有一個讓你仍然使用複製和混合特性的好方法。我會考慮一下。 – nnythm

實際上，像@Ptharien's Flame的解決方案一樣，在我的解決方案中添加一個參數比mixin更有效，我認爲。 – nnythm

不可改變的，可鍵入的樹木的設計

回答

不同的表達類型

做一個類型參數信號Typedness

相關問題