Entwurf von unveränderlichen, typisierbaren Bäumen

Question

Hier ist ein Designproblem, das ich wiederholt hatte. Angenommen, Sie erstellen einen Compiler, wie speichern Sie die Typen in den Bäumen?

eine einfache Expr und Type Hierarchie betrachten und davon ausgeht, dass Plus und Equals polymorph sind (plus auf booleans in nur ||, zum Beispiel).

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

Nehmen wir weiter an, dass ich die Art von Identifikatoren weiß nicht, wann ich die Ausdrucksbäume konstruieren und damit die Art von Konstruktion nicht wissen kann. nun eine typische Typprüfung Funktion könnte wie folgt aussehen:

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

Diese recht einfach ist, zu schreiben, aber kommt mit zwei großen Problemen:

• Expr s wandelbar sind. Niemand mag Mutation.
• Typisierte und nicht typisierte Ausdrücke können nicht unterschieden werden. Ich kann keine Funktion schreiben, deren Signatur angibt, dass ihr Argument ein typisierter Ausdruck sein muss.

Also meine Frage ist die folgende. Was ist ein guter Weg (ich nicht Entwurfsmuster sagen wagen) möglicherweise nicht typisierten Bäume zu definieren, so dass:

1. ich nur einmal die Expr Hierarchie definieren muß.
2. Getippte und untypisierte Bäume haben unterschiedliche Typen und ich kann wählen, sie inkompatibel zu machen.

Edit: Eine weitere Voraussetzung ist, dass es für Typ-Systeme mit unbeschränkter und unberechenbar Anzahl von Typen funktionieren soll (man denkt: case class ClassType(classID : String) extends Type, zum Beispiel).

Answer 1

Dies ist ein perfekter Anwendungsfall für die Typenprogrammierung!

Zuerst müssen wir einen Typ-Ebene Option, so dass wir nicht typisierten Bäume in Art-Ebene None und tippte Bäume vom Typ X in Bezug auf die Art-Ebene Some[X] darstellen kann:

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

Als nächstes wir legen unsere Art Systemhierarchie aus:

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 

Nun, alles, was übrig bleibt, ist unser Ausdrucksbaum zu erklären:

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:

Eine einfache, aber vollständige Typprüfung Funktion:

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

Dies ist nur eine Idee.

Zuerst, wenn Sie unveränderlich gehen wollen, müssen Sie natürlich die Variable tpe loswerden.

Distinct Expression Typen

einfach zwei Hierarchien, ein mit TypedExpression <: Expression und einem mit UntypedExpression <: Expression. Dieser Ansatz führt wahrscheinlich zu zwei nahezu identischen Klassenhierarchien.

Sie einen Typ Parameter Signal Typedness

Um den Aufwand der beiden Hierarchien zu entfernen (und irgendeine Art Textvorschlag erhalten), können Sie eine einzelne Hierarchie machen könnte und eine Art Paramater für a bool type hinzufügen:

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

Ich weiß nicht wirklich, wie viele tausend Probleme Sie ausführen, wenn Sie dies tun. Aber das würde ich versuchen.

Answer 3

Um es unveränderlich zu machen, können Sie einen neuen Ausdruck erstellen, anstatt seinen Inhalt zu ändern. Fallklassen haben eine copy method, die Sie für genau dies verwenden können.

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) 

Jetzt bist du frei, alle Arten von netten Dingen wie:

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

Allerdings ist es jetzt unveränderlich ist. Sie können Ihr Problem lösen, indem Sie herausfinden, ob es getippt ist oder nicht, indem Sie es mit tpe abgleichen, jetzt da es eines der Argumente für Var, Plus und Equals ist. Sie haben auch verschiedene Typen, und ihr Typ wird sich ändern, wenn sich tpe mit der Kopie ändert.