डेटा संरचना विकसित करना

Question

मैं हास्केल में सी-जैसी भाषा के लिए एक कंपाइलर लिखने की कोशिश कर रहा हूं। एक एएसटी बदलने से संकलक प्रगति करता है। पहला पास एएसटी बनाने के लिए इनपुट को पार करता है, प्रतीक तालिका के साथ गाँठ लगाकर प्रतीकों को आगे संदर्भों की आवश्यकता के बिना परिभाषित किए जाने से पहले स्थित होने की अनुमति देता है।

एएसटी में प्रकार और अभिव्यक्तियों के बारे में जानकारी है, और उनके बीच कनेक्शन हो सकते हैं; जैसे sizeof(T) एक अभिव्यक्ति है जो T पर निर्भर करती है, और T[e] एक सरणी प्रकार है जो निरंतर अभिव्यक्ति e पर निर्भर करता है।

प्रकार और भाव इतने तरह हास्केल डेटा प्रकार का प्रतिनिधित्व कर रहे:

data Type = TypeInt Id 
      | TypePointer Id Type -- target type 
      | TypeArray Id Type Expr -- elt type, elt count 
      | TypeStruct Id [(String, Type)] -- [(field name, field type)] 
      | TypeOf Id Expr 
      | TypeDef Id Type 

data Expr = ExprInt Int -- literal int 
      | ExprVar Var -- variable 
      | ExprSizeof Type 
      | ExprUnop Unop Expr 
      | ExprBinop Binop Expr Expr 
      | ExprField Bool Expr String -- Bool gives true=>s.field, false=>p->field 

कहाँ Unop (&) पता-की तरह ऑपरेटर, और भिन्नता (*) भी शामिल है, और Binop तरह प्लस ऑपरेटरों भी शामिल है (+) , और समय (*), आदि ...

ध्यान दें कि प्रत्येक प्रकार को एक अद्वितीय Id असाइन किया गया है। इसका उपयोग उन चक्रों का पता लगाने के लिए एक प्रकार निर्भरता ग्राफ बनाने के लिए किया जाता है जो अनंत प्रकार तक पहुंचते हैं। एक बार जब हम सुनिश्चित हों कि टाइप ग्राफ़ में कोई चक्र नहीं है, तो अनंत लूप में आने के बिना उन पर रिकर्सिव फ़ंक्शन लागू करना सुरक्षित है।

अगला चरण प्रत्येक प्रकार के आकार को निर्धारित करना है, संरचना क्षेत्रों में ऑफसेट असाइन करना है, और पॉइंटर अंकगणितीय के साथ ExprField एस को प्रतिस्थापित करना है। ऐसा करने में, हम भाव के प्रकार का निर्धारण कर सकते हैं, और इसलिए हमारे प्रकार और भाव विकसित किया है, ExprSizeof रों, ExprField रों, TypeDef है, और प्रकार ग्राफ से TypeOf रों को खत्म करने, और अब और अधिक इस तरह दिखेगा:

data Type' = TypeInt Id 
      | TypePointer Id Type' 
      | TypeArray Id Type' Int -- constant expression has been eval'd 
      | TypeStruct Id [(String, Int, Type')] -- field offset has been determined 

data Expr' = ExprInt Type' Int 
      | ExprVar Type' Var 
      | ExprUnop Type' Unop Expr' 
      | ExprBinop Type' Binop Expr' Expr' 

ध्यान दें कि हमने कुछ डेटा रचनाकारों को हटा दिया है, और कुछ अन्य लोगों को थोड़ा बदल दिया है। विशेष रूप से, Type' में अब कोई Expr' नहीं है, और प्रत्येक Expr' ने Type' निर्धारित किया है।

तो आखिरकार, प्रश्न: क्या डेटा प्रकारों के दो लगभग समान सेट बनाना बेहतर है, या उन्हें एक डेटा प्रकार में एकीकृत करने का प्रयास करना बेहतर है?

दो अलग-अलग डेटा प्रकारों को रखने से यह स्पष्ट हो जाता है कि कुछ रचनाकार अब प्रकट नहीं हो सकते हैं। हालांकि, जो समारोह निरंतर भाव का मूल्यांकन करने के प्रकार होगा निरंतर तह करती है:

foldConstants :: Expr -> Either String Expr' 

लेकिन इसका मतलब है कि हम Expr' रों (कुछ पास है कि एक Expr' manipulates, और गुना करना चाहता है की कल्पना के साथ बाद में निरंतर तह प्रदर्शन नहीं कर सकते कोई उभरा निरंतर अभिव्यक्ति)। हम एक और कार्यान्वयन की आवश्यकता होगी:

foldConstants' :: Expr' -> Either String Expr' 

दूसरी ओर, लगातार तह समस्या का समाधान होगा एक ही प्रकार के ध्यान में रखते हुए, लेकिन स्थिर अपरिवर्तनशीलताओं को लागू करने से प्रकार चेकर रोका जा सके।

इसके अलावा, हम पहले पास के दौरान अज्ञात फ़ील्ड (जैसे फील्ड ऑफ़सेट, सरणी आकार और अभिव्यक्ति प्रकार) में क्या डालते हैं? हम undefined, या error "*hole*" के साथ छेद प्लग कर सकते हैं, लेकिन ऐसा लगता है कि ऐसा होने वाली आपदा की तरह (जैसे NULL पॉइंटर्स जिन्हें आप चेक भी नहीं कर सकते)।हम अज्ञात फ़ील्ड को Maybe एस में बदल सकते हैं, और Nothing (पॉइंटर्स जैसे चेक) के साथ छेद प्लग कर सकते हैं, लेकिन Maybe एस से हमेशा मूल्यों को खींचने के लिए इसे बाद में गुजरना होगा जो हमेशा चल रहे हैं Just एस होने के लिए।

Answer 1

उम्मीद है कि अधिक अनुभव के साथ किसी के लिए एक अधिक पॉलिश, लड़ाई-परीक्षण किया और तैयार जवाब होगा, लेकिन यहाँ यह मेरी शॉट है।

आप अपने पाई है और GADTs साथ अपेक्षाकृत कम कीमत पर भी इसका हिस्सा खा सकते हैं: बातें हम बदल दिया है यहाँ

{-# LANGUAGE GADTs #-} 

data P0 -- phase zero 
data P1 -- phase one 

data Type p where 
    TypeInt  :: Id -> Type p 
    TypePointer :: Id -> Type p -> Type p    -- target type 
    TypeArray :: Id -> Type p -> Expr p -> Type p -- elt type, elt count 
    TypeStruct :: Id -> [(String, Type p)] -> Type p -- [(field name, field type)] 
    TypeOf  :: Id -> Expr P0 -> Type P0 
    TypeDef  :: Id -> Type P0 -> Type P0 

data Expr p where 
    ExprInt  :: Int -> Expr p      -- literal int 
    ExprVar  :: Var -> Expr p      -- variable 
    ExprSizeof :: Type P0 -> Expr P0 
    ExprUnop :: Unop -> Expr p -> Expr p 
    ExprBinop :: Binop -> Expr p -> Expr p -> Expr p 
    ExprField :: Bool -> Expr P0 -> String -> Expr P0 -- Bool gives true=>s.field, false=>p->field 

हैं:

• डेटाटाइप्स अब GADT का उपयोग वाक्य - विन्यास। इसका मतलब है कि रचनाकारों को उनके प्रकार के हस्ताक्षरों का उपयोग करके घोषित किया जाता है। data Foo = Bar Int Chardata Foo where Bar :: Int -> Char -> Foo बन जाता है (वाक्यविन्यास से अलग, दोनों पूरी तरह से समकक्ष हैं)।

• हमने Type और Expr दोनों में एक प्रकार चर जोड़ा है। यह एक तथाकथित प्रेत प्रकार चर है: p प्रकार का कोई वास्तविक डेटा संग्रहित नहीं है, इसका उपयोग केवल प्रकार सिस्टम में इनवेरिएंट को लागू करने के लिए किया जाता है। चरण शून्य और चरण एक:

• हम पहले और परिवर्तन के बाद के चरणों का प्रतिनिधित्व करने के डमी प्रकार घोषित कर दिया है। (कई चरणों के साथ एक और विस्तृत प्रणाली में हम उन्हें इंगित करने के लिए संभावित रूप से टाइप-स्तरीय संख्याओं का उपयोग कर सकते हैं।)

• जीएडीटी हमें डेटा संरचना में टाइप-स्तरीय इनवेरिएंट स्टोर करने देते हैं। यहां हमारे पास दो हैं। पहला यह है कि पुनरावर्ती पदों को उसी चरण का होना चाहिए, जिसमें संरचना शामिल है। उदाहरण के लिए, TypePointer :: Id -> Type p -> Type p पर, आप TypePointer कन्स्ट्रक्टर को पास करते हैं और परिणामस्वरूप Type p प्राप्त करते हैं, और p एस एक ही प्रकार का होना चाहिए। (अगर हम विभिन्न प्रकार की अनुमति के लिए चाहते थे, हम p और q इस्तेमाल कर सकते हैं।)

• पीछे नहीं है कि हम इस तथ्य है कि कुछ निर्माताओं के केवल पहले चरण में इस्तेमाल किया जा सकता लागू। अधिकांश रचनाकार प्रेत प्रकार परिवर्तनीय p में पॉलिमॉर्फिक हैं, लेकिन उनमें से कुछ की आवश्यकता है कि यह P0 हो। इसका मतलब है कि उन रचनाकारों का उपयोग केवल Type P0 या Expr P0 के मानों के निर्माण के लिए किया जा सकता है, किसी भी अन्य चरण में नहीं।

जीएडीटी दो दिशाओं में काम करते हैं। पहला यह है कि यदि आपके पास कोई ऐसा फ़ंक्शन है जो Type P1 देता है, और इसे बनाने के लिए Type P0 लौटने वाले रचनाकारों में से एक का उपयोग करने का प्रयास करें, तो आपको एक प्रकार की त्रुटि मिल जाएगी। इसे "निर्माण द्वारा सही" कहा जाता है: यह अमान्य संरचना बनाने के लिए स्थिर रूप से असंभव है (बशर्ते आप टाइप सिस्टम में सभी प्रासंगिक आविष्कारों को एन्कोड कर सकें)। इसका फ्लिप पक्ष यह है कि यदि आपके पास Type P1 का मान है, तो आप सुनिश्चित कर सकते हैं कि यह सही ढंग से बनाया गया था: TypeOf और TypeDef रचनाकारों का उपयोग नहीं किया जा सकता है (वास्तव में, यदि आप पैटर्न मिलान करने का प्रयास करते हैं तो संकलक शिकायत करेगा उन पर), और किसी भी रिकर्सिव पदों को चरण P1 का होना चाहिए। अनिवार्य रूप से, जब आप एक जीएडीटी बनाते हैं तो आप सबूत जमा करते हैं कि प्रकार की बाधाएं संतुष्ट होती हैं, और जब आप पैटर्न पर मेल खाते हैं तो आप उस सबूत को पुनः प्राप्त करते हैं और इसका लाभ उठा सकते हैं।

यह आसान हिस्सा था। दुर्भाग्यवश, हमारे पास दो प्रकार के बीच कुछ मतभेद हैं जो कि रचनाकारों की अनुमति है: कुछ कन्स्ट्रक्टर तर्क चरणों के बीच अलग हैं, और कुछ केवल परिवर्तन-परिवर्तन चरण में मौजूद हैं। हम फिर से एन्कोड करने के लिए जीएडीटी का उपयोग कर सकते हैं, लेकिन यह कम लागत और सुरुचिपूर्ण नहीं है। एक समाधान उन सभी रचनाकारों को डुप्लिकेट करना होगा जो अलग-अलग हैं, और P0 और P1 के लिए प्रत्येक एक है। लेकिन नकल अच्छा नहीं है। हम ऐसा करने के लिए कोशिश कर सकते हैं यह अधिक परिष्कृत:

-- a couple of helper types 
-- here I take advantage of the fact that of the things only present in one phase, 
-- they're always present in P1 and not P0, and not vice versa 
data MaybeP p a where 
    NothingP :: MaybeP P0 a 
    JustP :: a -> MaybeP P1 a 

data EitherP p a b where 
    LeftP :: a -> EitherP P0 a b 
    RightP :: b -> EitherP P1 a b 

data Type p where 
    TypeInt  :: Id -> Type p 
    TypePointer :: Id -> Type p -> Type p 
    TypeArray :: Id -> Type p -> EitherP p (Expr p) Int -> Type p 
    TypeStruct :: Id -> [(String, MaybeP p Int, Type p)] -> Type p 
    TypeOf  :: Id -> Expr P0 -> Type P0 
    TypeDef  :: Id -> Type P0 -> Type P0 

-- for brevity 
type MaybeType p = MaybeP p (Type p) 

data Expr p where 
    ExprInt  :: MaybeType p -> Int -> Expr p 
    ExprVar  :: MaybeType p -> Var -> Expr p 
    ExprSizeof :: Type P0 -> Expr P0 
    ExprUnop :: MaybeType p -> Unop -> Expr p -> Expr p 
    ExprBinop :: MaybeType p -> Binop -> Expr p -> Expr p -> Expr p 
    ExprField :: Bool -> Expr P0 -> String -> Expr P0 

यहाँ कुछ सहायक प्रकार हम तथ्य यह है कि कुछ निर्माता तर्क केवल चरण एक ( MaybeP) में मौजूद हो सकता है लागू किया गया है के साथ

और कुछ दोनों के बीच अलग हैं चरण (EitherP)। हालांकि यह हमें पूरी तरह से टाइप-सुरक्षित बनाता है, यह थोड़ा सा विज्ञापन लगता है और हमें अभी भी MaybeP एस और EitherP एस के अंदर और बाहर चीज़ों को लपेटना होगा। मुझे नहीं पता कि उस सम्मान में एक बेहतर समाधान है या नहीं। पूर्ण प्रकार की सुरक्षा कुछ है, हालांकि: हम fromJustP :: MaybeP P1 a -> a लिख सकते हैं और यह सुनिश्चित कर लें कि यह पूरी तरह से और पूरी तरह से सुरक्षित है।

अद्यतन: एक वैकल्पिक उपयोग करने के लिए है TypeFamilies:

data Proxy a = Proxy 

class Phase p where 
    type MaybeP p a 
    type EitherP p a b 
    maybeP :: Proxy p -> MaybeP p a -> Maybe a 
    eitherP :: Proxy p -> EitherP p a b -> Either a b 
    phase :: Proxy p 
    phase = Proxy 

instance Phase P0 where 
    type MaybeP P0 a =() 
    type EitherP P0 a b = a 
    maybeP _ _ = Nothing 
    eitherP _ a = Left a 

instance Phase P1 where 
    type MaybeP P1 a = a 
    type EitherP P1 a b = b 
    maybeP _ a = Just a 
    eitherP _ a = Right a 

Expr और Type रिश्तेदार पिछले संस्करण है कि निर्माताओं, उदा एक अतिरिक्त Phase p बाधा की आवश्यकता है के लिए एक ही परिवर्तन ExprInt :: Phase p => MaybeType p -> Int -> Expr p।

यहाँ अगर एक Type या Expr में p के प्रकार में जाना जाता है, आप स्थिर पता कर सकते हैं MaybeP रों () हो जाएगा कि क्या है या दिए गए प्रकार और प्रकार EitherP रों हैं जो, और उन्हें लगता है कि के रूप में सीधे उपयोग कर सकते हैं स्पष्ट unwrapping के बिना टाइप करें। जब p अज्ञात है तो आप Phase कक्षा से maybeP और eitherP का उपयोग करके पता लगा सकते हैं कि वे क्या हैं। (Proxy तर्क आवश्यक हैं, अन्यथा संकलक के पास आपको कौन सा चरण बताए जाने का कोई तरीका नहीं होगा।) यह GADT संस्करण के समान है, यदि p ज्ञात है, तो आप सुनिश्चित कर सकते हैं कि MaybeP और EitherP में, जबकि अन्यथा आपको पैटर्न दोनों संभावनाओं से मेल खाना पड़ेगा। यह समाधान या तो सम्मान में सही नहीं है कि 'लापता' तर्क पूरी तरह से गायब होने की बजाय () बन जाते हैं।

निर्माण Expr और Type रों भी मोटे तौर पर दो संस्करणों के बीच समान लगता है: यदि मान आप का निर्माण कर रहे हैं कुछ भी चरण-विशिष्ट इसके बारे में है तो यह अपने प्रकार में है कि चरण निर्दिष्ट करना होगा। समस्या तब आती है जब आप p में फ़ंक्शन पॉलिमॉर्फिक लिखना चाहते हैं लेकिन फिर भी चरण-विशिष्ट भागों को संभालना चाहते हैं। GADTs के साथ इस स्पष्ट है:

asdf :: MaybeP p a -> MaybeP p a 
asdf NothingP = NothingP 
asdf (JustP a) = JustP a 

ध्यान दें कि अगर मैं केवल asdf _ = NothingP लिखा था संकलक, शिकायत की है जाएगा क्योंकि उत्पादन के प्रकार के इनपुट के रूप में ही होने की गारंटी नहीं दी जाएगी। पैटर्न मिलान से हम यह पता लगा सकते हैं कि इनपुट किस प्रकार का था और उसी प्रकार के परिणाम को वापस कर दिया।

TypeFamilies संस्करण के साथ, हालांकि, यह बहुत कठिन है। बस maybeP और परिणामी Maybe का उपयोग करके आप कंपाइलर को कुछ भी साबित नहीं कर सकते हैं। इसके बजाय आप maybeP और eitherP वापसी Maybe और Either होने के, वहाँ से जिस तरह का हिस्सा प्राप्त कर सकते हैं, उन्हें maybe और either की तरह कार्य करता है जो यह भी एक प्रकार समानता उपलब्ध बनाने Deconstructor बनाने:

maybeP :: Proxy p -> (p ~ P0 => r) -> (p ~ P1 => a -> r) -> MaybeP p a -> r 
eitherP :: Proxy p -> (p ~ P0 => a -> r) -> (p ~ P1 => b -> r) -> EitherP p a b -> r 

(ध्यान दें कि हम Rank2Types की जरूरत । इस, और टिप्पणी भी है कि इन अनिवार्य रूप से MaybeP और EitherP की GADT संस्करणों में से सीपीएस-बदल संस्करण हैं) के लिए

तो हम लिख सकते हैं:

asdf :: Phase p => MaybeP p a -> MaybeP p a 
asdf a = maybeP phase() id a 

लेकिन वह पर्याप्त नहीं अभी भी है, क्योंकि GHC का कहना है:

data.hs:116:29: 
Could not deduce (MaybeP p a ~ MaybeP p0 a0) 
from the context (Phase p) 
    bound by the type signature for 
       asdf :: Phase p => MaybeP p a -> MaybeP p a 
    at data.hs:116:1-29 
NB: `MaybeP' is a type function, and may not be injective 
In the fourth argument of `maybeP', namely `a' 
In the expression: maybeP phase() id a 
In an equation for `asdf': asdf a = maybeP phase() id a 

शायद तुम कहीं एक प्रकार हस्ताक्षर के साथ इस का समाधान कर सकता है, लेकिन उस बिंदु पर इस तरह की और परेशान तुलना में यह लायक है लगता है। इसलिए किसी और से आगे की जानकारी लंबित है, मैं थोड़ा सा वाक्य रचनात्मक शोर की कीमत पर, सरल और अधिक मजबूत होने के नाते, जीएडीटी संस्करण का उपयोग करने की सिफारिश करने जा रहा हूं। फिर

अद्यतन: समस्या यहाँ क्योंकि MaybeP p a एक प्रकार समारोह है और कोई अन्य जानकारी के अनुसार जाना है, GHC कोई रास्ता नहीं पता है कि p और a होना चाहिए है कि था। अगर मैं Proxy p में पास करता हूं और phase के बजाय इसका उपयोग करता हूं जो p हल करता है, लेकिन a अभी भी अज्ञात है।

Answer 2

वहाँ इस समस्या का कोई आदर्श समाधान है, के बाद से हर एक अलग पक्ष-विपक्ष है है।

मैं व्यक्तिगत रूप से एक भी डेटा प्रकार "पेड़" का उपयोग कर के साथ जाने के लिए और चीजों को अलग-अलग करने की आवश्यकता है के लिए अलग से डेटा कंस्ट्रक्टर्स जोड़ना होगा। अर्थात्:

data Type 
    = ... 
    | TypeArray Id Type Expr 
    | TypeResolvedArray Id Type Int 
    | ... 

यह लाभ यह है कि आप एक ही पेड़ पर एक ही चरण में कई बार चला सकते हैं, जैसा कि आप कहते हैं कि है, लेकिन तर्क है कि तुलना में गहरा हो जाता है: मान लीजिए कि आप एक वाक्य रचना तत्व यह है कि उत्पन्न करता है कार्यान्वित कर रहे हैं चलो अधिक एएसटी (include या एक सी ++ टेम्पलेट प्रकार की तरह कुछ, और यह आपके TypeArray जैसे निरंतर एक्सप्रप्रस पर निर्भर हो सकता है ताकि आप पहले पुनरावृत्ति में इसका मूल्यांकन नहीं कर सकें)। एकीकृत डेटा प्रकार दृष्टिकोण के साथ, आप अपने मौजूदा पेड़ में केवल नया एएसटी डाल सकते हैं, न केवल आप उसी पेड़ पर पहले से ही उसी चरण को चला सकते हैं, लेकिन आपको मुफ्त में कैशिंग मिल जाएगी, यानी यदि नया एएसटी संदर्भ देता है sizeof(typeof(myarr)) या कुछ का उपयोग करके सरणी, तुम क्योंकि इसके प्रकार अपने पिछले संकल्प चरण से पहले से ही एक TypeResolvedArray है, फिर myarr की लगातार आकार निर्धारित करने की जरूरत नहीं है।

आप एक अलग प्रतिनिधित्व इस्तेमाल कर सकते हैं जब आप अपने संकलन सभी चरणों अतीत हैं, और यह कोड (या कुछ और) व्याख्या करने के लिए समय है; तो आप इस तथ्य से निश्चित हैं कि अब तक कोई भी एएसटी परिवर्तन आवश्यक नहीं होगा, और एक अधिक सुव्यवस्थित प्रतिनिधित्व एक अच्छा विचार हो सकता है।

वैसे, आपको Data.Word.Word का उपयोग Data.Int.Int के बजाय सरणी आकारों के लिए करना चाहिए। इंडेक्सिंग एरे के लिए int एस का उपयोग करने के लिए सी में यह एक आम त्रुटि है, जबकि सी पॉइंटर्स वास्तव में हस्ताक्षरित हैं। कृपया इस गलती को अपनी भाषा में भी न बनाएं, जब तक आप वास्तव में नकारात्मक आकार वाले सरणी का समर्थन नहीं करना चाहते।