Projektowanie niezmiennych, dających się sortować, drzew

Question

Oto problem z projektowaniem, z którym miałem do czynienia wielokrotnie. Załóżmy, że budujesz kompilator, w jaki sposób przechowujesz typy w drzewach?

Rozważmy prosty Expr i Type hierarchię, i zakładamy, że Plus i Equals są polimorficzne (plus na logicznych w zaledwie ||, na przykład).

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

Załóżmy dalej, że nie wiem, rodzaj identyfikatorów kiedy skonstruowania wyrażenia drzew, a zatem nie może znać typ poprzez budowę. Teraz typowa funkcja typechecking mógłby wyglądać następująco:

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

Jest to dość proste do napisania, ale pochodzi z dwóch głównych problemów:

• Expr s są zmienne. Nikt nie lubi mutacji.
• Nie można rozróżniać wyrażeń typu i bez typów. Nie mogę napisać funkcji, której podpis wskazuje, że jej argument musi być wyrażeniem pisanym na maszynie.

Moje pytanie jest następujące. Co to jest dobrym sposobem (nie śmiem powiedzieć wzorca projektowego), aby określić możliwie bez typu drzew takie, że:

1. muszę zdefiniować hierarchię Expr tylko raz.
2. Wpisane i bez typu drzewa mają różne typy i mogę je zmienić na niezgodne.

Edit: Kolejny wymóg jest, że powinien pracować dla systemów typu z nieograniczonego i nieprzewidywalnej liczby typów (myśleć: case class ClassType(classID : String) extends Type, na przykład).

Answer 1

Jest to idealny przypadek użycia do programowania na poziomie typu!

Po pierwsze, musimy typu poziom Option tak, że możemy reprezentować bez typu drzew pod względem typu poziomie None i wpisane drzew typu X pod względem typu poziomie Some[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 

Następny, kładziemy naszą hierarchię systemu Typ:

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 

teraz wszystko, co pozostało jest zadeklarować nasze drzewa wyrażenie:

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:

Prosty, ale pełna funkcja sprawdzania typu:

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

To tylko pomysł.

Po pierwsze, jeśli chcesz pozostać niezmienny, oczywiście musisz pozbyć się zmiennej tpe.

odrębnych typów ekspresji

Wystarczy zrobić dwie hierarchie, jeden z TypedExpression <: Expression i jeden z UntypedExpression <: Expression. Takie podejście prawdopodobnie doprowadzi do dwóch prawie identycznych hierarchii klas.

Zrób typ parametru Sygnał Typedness

W celu usunięcia napowietrznej dwóch hierarchii (i trochę typu boilerplate), można wykonać jedną hierarchię i dodać typ paramater dla 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]] 
} 

Naprawdę nie wiem, ile tysięcy problemów zostanie uruchomionych, jeśli to zrobisz. Ale tego właśnie spróbuję.

Answer 3

Aby było niezmienne, można utworzyć nowy Expr zamiast zmieniać jego zawartość. Klasy przypadków mają wartość copy method, której można użyć do tego celu.

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) 

Teraz jesteś wolny, aby robić wszystkie rodzaje miłych rzeczy jak:

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

Jednak teraz jest niezmienna. Możesz rozwiązać swój problem, ustalając, czy jest on wpisany, czy nie, dopasowując do tpe, teraz jest to jeden z argumentów dla Var, Plus i Equals. Mają też różne typy, a ich typ zmienia się wraz z zmianą tpe z kopią.