सामान्यीकृत बीजीय डेटा प्रकार

From Vigyanwiki
Revision as of 09:55, 15 July 2023 by alpha>Nileshj

कार्यात्मक प्रोग्रामिंग में, एक सामान्यीकृत बीजगणितीय डेटा प्रकार (जीएडीटी, प्रथम श्रेणी फैंटम प्रकार,[1] संरक्षित पुनरावर्ती डेटाटाइप,[2] या समानता-योग्य प्रकार [3]) पैरामीट्रिक बीजगणितीय डेटा प्रकारों का एक सामान्यीकरण है।

सिंहावलोकन

जीएडीटी में, उत्पाद कंस्ट्रक्टर (हास्केल में डेटा कंस्ट्रक्टर कहा जाता है) अपने रिटर्न वैल्यू (प्रतिफल मान) के प्रकार इंस्टेंशियेशन (दृष्टांतिकरण) के रूप में एडीटी का एक स्पष्ट इंस्टेंशियेशन प्रदान कर सकते हैं। यह कार्यों को अधिक उन्नत प्रकार के व्यवहार के साथ परिभाषित करने की अनुमति देता है। हास्केल 2010 के डेटा कंस्ट्रक्टर के लिए, रिटर्न वैल्यू में कंस्ट्रक्टर के एप्लिकेशन पर एडीटी पैरामीटर्स के इंस्टेंशियशन द्वारा निहित प्रकार इंस्टेंशियशन होता है।

-- A parametric ADT that is not a GADT
data List a = Nil | Cons a (List a)

integers = Cons 12 (Cons 107 Nil)       -- the type of integers is List Int
strings = Cons "boat" (Cons "dock" Nil) -- the type of strings is List String

-- A GADT
data Expr a where
    EBool  :: Bool     -> Expr Bool
    EInt   :: Int      -> Expr Int
    EEqual :: Expr Int -> Expr Int  -> Expr Bool

eval :: Expr a -> a

eval e = case e of
    EBool a    -> a
    EInt a     -> a
    EEqual a b -> (eval a) == (eval b)

expr1 = EEqual (EInt 2) (EInt 3)        -- the type of expr1 is Expr Bool
ret = eval expr1                        -- ret is False

वे वर्तमान में जीएचसी कंपाइलर में एक गैर-मानक एक्सटेंशन के रूप में कार्यान्वित किए जाते हैं, जिनका उपयोग अन्य लोगों के अलावा, पग्स और डार्क्स द्वारा किया जाता है। ओकैमल संस्करण 4.00 से मूल रूप से जीएडीटी का समर्थन करता है।[4]

जीएचसी कार्यान्वयन अस्तित्वगत मात्रात्मक प्रकार के मापदंडों और स्थानीय बाधाओं के लिए समर्थन प्रदान करता है।

इतिहास

सामान्यीकृत बीजगणितीय डेटा प्रकारों के प्रारंभिक संस्करण का वर्णन किसके द्वारा किया गया था? Augustsson & Petersson (1994) और ALF (प्रमेय कहावत) में पैटर्न मिलान (कार्यात्मक प्रोग्रामिंग) पर आधारित है।

सामान्यीकृत बीजगणितीय डेटा प्रकार स्वतंत्र रूप से पेश किए गए थे Cheney & Hinze (2003) और इससे पहले Xi, Chen & Chen (2003) एमएल (प्रोग्रामिंग भाषा) और हास्केल (प्रोग्रामिंग भाषा) के बीजगणितीय डेटा प्रकारों के विस्तार के रूप में।[5] दोनों मूलतः एक दूसरे के समकक्ष हैं। वे कोक के आगमनात्मक निर्माणों की गणना और अन्य आश्रित रूप से टाइप की गई भाषाओं में पाए जाने वाले बीजगणितीय डेटा प्रकार (या आगमनात्मक डेटाटाइप) के समान हैं, आश्रित प्रकारों को मॉड्यूलो करते हैं और सिवाय इसके कि बाद वाले में एक अतिरिक्त सकारात्मकता प्रतिबंध होता है जो जीएडीटी में लागू नहीं होता है।[6]

Sulzmann, Wazny & Stuckey (2006) विस्तारित बीजगणितीय डेटा प्रकार पेश किए गए जो जीएडीटी को अस्तित्वगत प्रकार और प्रकार वर्ग बाधाओं के साथ जोड़ते हैं। किसी भी प्रोग्रामर द्वारा प्रदत्त प्रकार के एनोटेशन की अनुपस्थिति में प्रकार का अनुमान अनिर्णीत समस्या है[7] और जीएडीटी पर परिभाषित फ़ंक्शन सामान्य रूप से प्रमुख प्रकारों को स्वीकार नहीं करते हैं।[8] प्रकार के पुनर्निर्माण के लिए कई डिज़ाइन ट्रेड-ऑफ़ की आवश्यकता होती है और यह सक्रिय अनुसंधान का क्षेत्र है (Peyton Jones, Washburn & Weirich 2004; Peyton Jones et al. 2006. वसंत 2021 में, स्काला 3.0 जारी किया गया है।[9] स्काला (प्रोग्रामिंग भाषा) का यह प्रमुख अद्यतन GADTs लिखने की संभावना प्रस्तुत करता है[10] बीजगणितीय डेटा प्रकार के समान वाक्यविन्यास के साथ, जो मार्टिन ओडर्सकी के अनुसार अन्य प्रोग्रामिंग भाषा में नहीं है।[11]


अनुप्रयोग

जीएडीटी के अनुप्रयोगों में सामान्य प्रोग्रामिंग, मॉडलिंग प्रोग्रामिंग भाषाएं (उच्च-क्रम अमूर्त वाक्यविन्यास), डेटा संरचनाओं में अपरिवर्तनीय (कंप्यूटर विज्ञान) को बनाए रखना, एम्बेडेड डोमेन-विशिष्ट भाषाओं में बाधाओं को व्यक्त करना और मॉडलिंग ऑब्जेक्ट शामिल हैं।[12]

उच्च-क्रम अमूर्त वाक्यविन्यास

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

data Lam :: * -> * where
  Lift :: a                     -> Lam a        -- ^ lifted value
  Pair :: Lam a -> Lam b        -> Lam (a, b)   -- ^ product
  Lam  :: (Lam a -> Lam b)      -> Lam (a -> b) -- ^ lambda abstraction
  App  :: Lam (a -> b) -> Lam a -> Lam b        -- ^ function application
  Fix  :: Lam (a -> a)          -> Lam a        -- ^ fixed point

और एक प्रकार का सुरक्षित मूल्यांकन फ़ंक्शन:

eval :: Lam t -> t
eval (Lift v)   = v
eval (Pair l r) = (eval l, eval r)
eval (Lam f)    = \x -> eval (f (Lift x))
eval (App f x)  = (eval f) (eval x)
eval (Fix f)    = (eval f) (eval (Fix f))

फैक्टोरियल फ़ंक्शन को अब इस प्रकार लिखा जा सकता है:

fact = Fix (Lam (\f -> Lam (\y -> Lift (if eval y == 0 then 1 else eval y * (eval f) (eval y - 1)))))
eval(fact)(10)

हमें नियमित बीजगणितीय डेटा प्रकारों का उपयोग करने में समस्याओं का सामना करना पड़ता। प्रकार पैरामीटर को छोड़ने से उठाए गए आधार प्रकार अस्तित्वगत रूप से परिमाणित हो जाते, जिससे मूल्यांकनकर्ता को लिखना असंभव हो जाता। एक प्रकार के पैरामीटर के साथ हम अभी भी एक आधार प्रकार तक ही सीमित रहेंगे। इसके अलावा, ख़राब अभिव्यक्तियाँ जैसे App (Lam (\x -> Lam (\y -> App x y))) (Lift True) निर्माण करना संभव होता, जबकि वे GADT का उपयोग करके गलत टाइप किए गए हैं। एक सुगठित एनालॉग है App (Lam (\x -> Lam (\y -> App x y))) (Lift (\z -> True)). ऐसा इसलिए है क्योंकि का प्रकार x है Lam (a -> b), के प्रकार से अनुमान लगाया गया है Lam डेटा कंस्ट्रक्टर.

यह भी देखें

  • प्रकार चर

टिप्पणियाँ

  1. Cheney & Hinze 2003.
  2. Xi, Chen & Chen 2003.
  3. Sheard & Pasalic 2004.
  4. "OCaml 4.00.1". ocaml.org.
  5. Cheney & Hinze 2003, p. 25.
  6. Cheney & Hinze 2003, pp. 25–26.
  7. Peyton Jones, Washburn & Weirich 2004, p. 7.
  8. Schrijvers et al. 2009, p. 1.
  9. Kmetiuk, Anatolii. "SCALA 3 IS HERE!🎉🎉🎉". scala-lang.org. École Polytechnique Fédérale Lausanne (EPFL) Lausanne, Switzerland. Retrieved 19 May 2021.
  10. "SCALA 3 — BOOK ALGEBRAIC DATA TYPES". scala-lang.org. École Polytechnique Fédérale Lausanne (EPFL) Lausanne, Switzerland. Retrieved 19 May 2021.
  11. Odersky, Martin. "A Tour of Scala 3 - Martin Odersky". youtube.com. Scala Days Conferences. Archived from the original on 2021-12-19. Retrieved 19 May 2021.
  12. Peyton Jones, Washburn & Weirich 2004, p. 3.


अग्रिम पठन

Applications
Semantics
Type reconstruction
Other


बाहरी संबंध