2012-10-24 39 views
5

यहां एक डिजाइन समस्या है जिसे मैंने बार-बार सामना किया है। मान लीजिए कि आप एक कंपाइलर बना रहे हैं, आप पेड़ों में प्रकार कैसे स्टोर करते हैं?अपरिवर्तनीय, टाइप करने योग्य, पेड़ का डिजाइन

एक सरल 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 
// ... 

आगे मान लें कि मैं जब मैं अभिव्यक्ति पेड़ का निर्माण पहचानकर्ता के प्रकार पता नहीं है, और इसलिए निर्माण के द्वारा प्रकार पता नहीं कर सकते हैं। अब एक ठेठ typechecking समारोह ऐसा दिखाई दे सकता:

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 रों परिवर्तनशील हैं। कोई भी उत्परिवर्तन पसंद नहीं करता है।
  • टाइप किए गए और untyped अभिव्यक्तियों को प्रतिष्ठित नहीं किया जा सकता है। मैं एक ऐसा फ़ंक्शन नहीं लिख सकता जिसका हस्ताक्षर निर्दिष्ट करता है कि उसका तर्क एक टाइप की गई अभिव्यक्ति होनी चाहिए।

तो मेरा प्रश्न निम्न है। एक अच्छा तरीका है (मैं कहता हूँ की हिम्मत नहीं डिजाइन पैटर्न) संभवतः untyped पेड़ों को परिभाषित करने के क्या है ऐसा है कि:

  1. मैं केवल एक बार Expr पदानुक्रम परिभाषित करने की जरूरत।
  2. टाइप किए गए और untyped पेड़ों के अलग प्रकार हैं और मैं उन्हें असंगत बनाने के लिए चुन सकते हैं।

संपादित करें: एक और आवश्यकता है कि यह प्रकार के एक असीम और अप्रत्याशित संख्या के साथ प्रकार सिस्टम के लिए काम करना चाहिए है (लगता है: उदाहरण के लिए, case class ClassType(classID : String) extends Type)।

उत्तर

6

यह प्रकार-स्तर प्रोग्रामिंग के लिए एक आदर्श उपयोग-मामला है! ,

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

अगला:

सबसे पहले, हम इतना है कि हम प्रकार स्तरीय None के मामले में untyped पेड़ प्रतिनिधित्व करते हैं और प्रकार स्तरीय Some[X] के मामले में प्रकार X के पेड़ टाइप किया जा सकता है एक प्रकार स्तरीय Option की जरूरत अब

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 
} 
+2

एक उपयोग उदाहरण बहुत अच्छा होगा। आप अपने सिस्टम में 'टाइप चेक' कैसे लिखेंगे? –

+1

ऐसा लगता है कि यह वही हो सकता है जो मैं ढूंढ रहा था। जैसा कि यूजीन सुझाव देता है, क्या आप शायद दिखा सकते हैं कि आप अपने 'टाइप चेक' फ़ंक्शन को अपनी परिभाषाओं में कैसे अनुकूलित करेंगे? – Philippe

+1

मुझे लगता है कि आपने गलती से भ्रमित नहीं किया है और कुछ भी नहीं। इसके अलावा, कुछ भी नहीं। टाइप, मुझे लगता है कि आपका मतलब कोई नहीं है। – nnythm

1

यह सिर्फ एक विचार है।

सबसे पहले अगर आप अपरिवर्तनीय जाना चाहते हैं, तो स्पष्ट रूप से आपको चर tpe से छुटकारा पाना होगा।

विशिष्ट अभिव्यक्ति प्रकार

, बस दो पदानुक्रम, TypedExpression <: Expression के साथ एक और UntypedExpression <: Expression के साथ एक बनाते हैं। इस दृष्टिकोण के परिणामस्वरूप लगभग दो समान वर्ग पदानुक्रमों का परिणाम होगा।

एक प्रकार पैरामीटर सिग्नल Typedness

दो पदानुक्रम के ऊपरी को निकालने के लिए (और कुछ प्रकार बॉयलरप्लेट मिल), आप एक ही पदानुक्रम बना सकता है और 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]] 
} 

मुझे वास्तव में पता नहीं है कि यदि आप ऐसा करते हैं तो आप कितनी हजार समस्याएं चलाएंगे। लेकिन यह वही है जो मैं कोशिश करूंगा।

3

इसे अपरिवर्तनीय बनाने के लिए, आप इसकी सामग्री को बदलने के बजाय एक नया एक्सप्रप्रो बना सकते हैं। केस क्लास में 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

जवाब के लिए धन्यवाद। यह पहली आवश्यकता को पूरा करता है (सबकुछ अपरिवर्तनीय है), लेकिन दूसरा नहीं (टाइप और अनियोजित पेड़ समान हैं - स्काला - यहां टाइप करें)। – Philippe

+1

आह, ठीक है, मैं इस चिंता से निपट रहा था कि इसका मिलान किया जा सकता है, न कि उनके पास अलग-अलग प्रकार हैं। अलग-अलग प्रकार के लिए, आप किसी ऑब्जेक्ट के बजाय टाइप की गई विशेषता बनाना चाहते हैं। मैं उस समाधान से पुनः सबमिट करूंगा जो उस आवश्यकता को पूरा करता है। संपादित करें: असल में, मुझे एहसास हुआ कि मेरे पास अभी भी गुणों में मिश्रण के साथ प्रतिलिपि बनाने का एक अच्छा तरीका नहीं है। मैं इसके बारे में सोचूंगा। – nnythm

+1

दरअसल, मेरे समाधान में पैरामीटर जोड़ना जैसे @ पाथरीन के ज्वाला के समाधान में मिश्रणों से बेहतर काम करता है, मुझे लगता है। – nnythm