पैरामीट्रिक बहुरूपता

प्रोग्रामिंग भाषाओं और प्रकार के सिद्धांत में, पैरामीट्रिक बहुरूपता कोड के एक टुकड़े को वास्तविक प्रकार के स्थान पर चर का उपयोग करके "जेनेरिक" प्रकार देने की अनुमति देता है, और फिर आवश्यकतानुसार विशेष प्रकार के साथ तत्काल किया जाता है।^[1]^: 340 पैरामीट्रिक रूप से बहुरूपी कार्यों और डेटा प्रकारों को कभी-कभी क्रमशः सामान्य कार्य और सामान्य डेटा प्रकार कहा जाता है, और वे सामान्य प्रोग्रामिंग का आधार बनाते हैं।

पैरामीट्रिक बहुरूपता की तुलना तदर्थ बहुरूपता से की जा सकती है। पैरामीट्रिक रूप से बहुरूपी परिभाषाएँ 'एकसमान' हैं: वे जिस प्रकार के वर्तमान में हैं, उसकी परवाह किए बिना समान रूप से व्यवहार करते हैं।^[1]^: 340^[2]^: 37 इसके विपरीत, तदर्थ बहुरूपी परिभाषाओं को प्रत्येक प्रकार के लिए अलग परिभाषा दी जाती है। इस प्रकार, तदर्थ बहुरूपता सामान्यतः केवल सीमित संख्या में ऐसे विशिष्ट प्रकारों का समर्थन कर सकता है, क्योंकि प्रत्येक प्रकार के लिए अलग कार्यान्वयन प्रदान किया जाना है।

मूल परिभाषा

उन कार्यों को लिखना संभव है जो उनके तर्कों के प्रकारों पर निर्भर नहीं होते हैं। उदाहरण के लिए, पहचान फलन ${\mathsf {id}}(x)=x$ बस अपना तर्क अपरिवर्तित लौटाता है। यह स्वाभाविक रूप से संभावित प्रकार के परिवार को जन्म देता है, जैसे ${\mathsf {Int}}\to {\mathsf {Int}}$ , ${\mathsf {Bool}}\to {\mathsf {Bool}}$ , ${\mathsf {String}}\to {\mathsf {String}}$ , और इसी प्रकार होता है। पैरामीट्रिक बहुरूपता ${\mathsf {id}}$ को सार्वभौमिक रूप से परिमाणित प्रकार चर प्रस्तुत करके एकल, सबसे सामान्य प्रकार देने की अनुमति देता है:

{\mathsf {id}}:\forall \alpha .\alpha \to \alpha

बहुरूपी परिभाषा को $\alpha$ के लिए किसी भी ठोस प्रकार को प्रतिस्थापित करके तत्काल किया जा सकता है, जिससे संभावित प्रकारों का पूरा परिवार प्राप्त होता है।^[3]

पहचान कार्य विशेष रूप से चरम उदाहरण है, किन्तु कई अन्य कार्य भी पैरामीट्रिक बहुरूपता से लाभान्वित होते हैं। उदाहरण के लिए, ${\mathsf {append}}$ फलन जो दो सूचियों को जोड़ता है, केवल सूची संरचना में ही सूची के तत्वों का निरीक्षण नहीं करता है। इसलिए, ${\mathsf {append}}$ प्रकार का समान परिवार दिया जा सकता है, जैसे $(([{\mathsf {Int}}],[{\mathsf {Int}}])\to [{\mathsf {Int}}])$ , $(([{\mathsf {Bool}}],[{\mathsf {Bool}}])\to [{\mathsf {Bool}}])$ , और इसी प्रकार, जहाँ $[T]$ प्रकार के तत्वों की सूची को $T$ दर्शाता है. इसलिए सबसे सामान्य प्रकार है

{\mathsf {append}}:\forall \alpha .([\alpha ],[\alpha ])\to [\alpha ]

जिसे परिवार में किसी भी प्रकार से तत्काल किया जा सकता है।

Parametrically बहुरूपी कार्य जैसे ${\mathsf {id}}$ और ${\mathsf {append}}$ कहा जाता है कि मनमानी प्रकार $\alpha$ पर पैरामिट्रीकृत किया जाता है.^[4] दोनों ${\mathsf {id}}$ और ${\mathsf {append}}$ ही प्रकार पर परिचालित किया जाता है, किन्तुकार्यों को इच्छानुसार कई प्रकारों पर परिचालित किया जा सकता है। उदाहरण के लिए, ${\mathsf {fst}}$ और ${\mathsf {snd}}$ उत्पाद प्रकार के पहले और दूसरे तत्वों को क्रमशः लौटाने वाले कार्यों को निम्न प्रकार दिया जा सकता है:

{\begin{aligned}{\mathsf {fst}}&:\forall \alpha .\forall \beta .(\alpha ,\beta )\to \alpha \\{\mathsf {snd}}&:\forall \alpha .\forall \beta .(\alpha ,\beta )\to \beta \end{aligned}}

अभिव्यक्ति में ${\mathsf {fst}}((3,{\mathsf {true}}))$ , $\alpha$ पर ${\mathsf {Int}}$ और $\beta$ प्रवर्तित किया जाता है और ${\mathsf {Bool}}$ को ${\mathsf {fst}}$ कॉल में प्रवर्तित किया जाता है, तो इसलिये समग्र अभिव्यक्ति का प्रकार ${\mathsf {Int}}$ है.

पैरामीट्रिक बहुरूपता को प्रस्तुत करने के लिए प्रयुक्त सिंटैक्स (प्रोग्रामिंग भाषाएं) प्रोग्रामिंग भाषाओं के बीच महत्वपूर्ण रूप से भिन्न होता है। उदाहरण के लिए, कुछ प्रोग्रामिंग भाषाओं में, जैसे हास्केल, $\forall \alpha$ परिमाणक (तर्क)तर्क) अंतर्निहित है और इसे छोड़ा जा सकता है।^[5] अन्य भाषाओं को कुछ या सभी पैरामीट्रिक पॉलीमॉर्फिक फलन की कॉल साइटो पर स्पष्ट रूप से तत्काल होने की आवश्यकता होती है।

इतिहास

पैरामीट्रिक बहुरूपता को पहली बार 1975 में एमएल प्रोग्रामिंग भाषा में प्रोग्रामिंग भाषाओं के लिए प्रस्तुत किया गया था।^[6] आज यह मानक एमएल, ओकैमल,एफ शार्प (F#) (प्रोग्रामिंग लैंग्वेज), ऐडा (प्रोग्रामिंग लैंग्वेज), हास्केल (प्रोग्रामिंग भाषा), मरकरी (प्रोग्रामिंग लैंग्वेज), विजुअल प्रोलॉग, स्काला (प्रोग्रामिंग भाषा), जूलिया (प्रोग्रामिंग लैंग्वेज) पायथन (प्रोग्रामिंग भाषा), टाइपप्रति, सी ++ और अन्य में उपस्थित है। जावा (प्रोग्रामिंग भाषा), सी शार्प (प्रोग्रामिंग लैंग्वेज), विजुअल बेसिक डॉट नेट, और डेल्फ़ी में से प्रत्येक ने पैरामीट्रिक बहुरूपता के लिए जेनरिक प्रस्तुत किए हैं। प्रकार के बहुरूपता के कुछ कार्यान्वयन सतही रूप से पैरामीट्रिक बहुरूपता के समान हैं, चूंकि तदर्थ पहलुओं को भी प्रस्तुत करते हैं। उदाहरण C++ टेम्पलेट विशेषज्ञता है।

विधेयता, अभेद्यता, और उच्च-श्रेणी बहुरूपता

पंक्ति -1 (विधेयात्मक) बहुरूपता

विधेय प्रकार की प्रणाली में (जिसे प्रीनेक्स पॉलीमॉर्फिक पद्धतिके रूप में भी जाना जाता है) टाइप वेरिएबल्स को पॉलीमॉर्फिक प्रकारों के साथ तत्काल नहीं किया जा सकता है।^[1]^{: 359–360} इसमें प्रिडिक्टिव टाइप थ्योरी में इंट्यूशनिस्टिक टाइप थ्योरी मार्टिन-लोफ टाइप थ्योरी और एनयूपीआरएल सम्मिलित हैं। यह एमएल-शैली या लेट-पॉलीमॉर्फिज्म के समान है (तकनीकी रूप से एमएल के लेट-पॉलिमोर्फिज्म में कुछ अन्य वाक्य-विन्यास प्रतिबंध हैं)।

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

भविष्यवाणी का परिणाम यह है कि सभी प्रकारों को ऐसे रूप में लिखा जा सकता है जो सभी परिमाणकों को सबसे बाहरी (प्रेनेक्स) स्थिति में रखता है। उदाहरण के लिए ऊपर वर्णित, ${\mathsf {append}}$ फलन पर विचार करें, जिसमें निम्न प्रकार हैं:

{\mathsf {append}}:\forall \alpha .([\alpha ],[\alpha ])\to [\alpha ]

इस फलन को सूचियों की जोड़ी पर प्रयुक्त करने के लिए, ठोस प्रकार $T$ चर के लिए $\alpha$ प्रतिस्थापित किया जाना चाहिए जैसे कि परिणामी फलन प्रकार तर्कों के प्रकार के अनुरूप है। अप्रतिबंधित प्रणाली में, $T$ किसी भी प्रकार का हो सकता है, जिसमें प्रकार भी सम्मिलित है जो स्वयं बहुरूपी है; इस प्रकार ${\mathsf {append}}$ को किसी भी प्रकार के तत्वों के साथ सूचियों के जोड़े पर प्रयुक्त किया जा सकता है - यहां तक कि स्वयं ${\mathsf {append}}$ जैसे बहुरूपी कार्यों की सूचियों पर भी प्रयुक्त किया जा सकता है।

भाषा एमएल में बहुरूपता विधेय है।^{[citation needed]} ऐसा इसलिए है क्योंकि भविष्यवाणी, अन्य प्रतिबंधों के साथ, प्रकार प्रणाली को इतना सरल बनाती है कि पूर्ण प्रकार का अनुमान सदैव संभव होता है।

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

उच्च-रैंक बहुरूपता

कुछ प्रकार के पद्धति इम्प्रिडिकेटिव फंक्शन टाइप कंस्ट्रक्टर का समर्थन करते हैं, तथापि अन्य प्रकार के कंस्ट्रक्टर प्रेडिक्टिव रहते हैं। उदाहरण के लिए, $(\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T$ प्रकार ऐसी प्रणाली में अनुमति है जो उच्च-श्रेणी के बहुरूपता का समर्थन करती है, तथापि $[\forall \alpha .\alpha \rightarrow \alpha ]$ नहीं हो सकता हैं।^[7]

प्रकार को रैंक k का कहा जाता है (कुछ निश्चित पूर्णांक k के लिए) यदि इसकी जड़ से a तक कोई रास्ता नहीं है $\forall$ क्वांटिफायर k या अधिक तीरों के बाईं ओर जाता है, जब पेड़ के रूप में टाइप किया जाता है।^[1]^: 359 प्रकार की प्रणाली को रैंक-के बहुरूपता का समर्थन करने के लिए कहा जाता है यदि यह रैंक के साथ के से कम या उसके बराबर के प्रकारों को स्वीकार करता है। उदाहरण के लिए, प्रकार की प्रणाली जो रैंक -2 बहुरूपता का समर्थन करती है, कि $(\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T$ अनुमति देगी किन्तु $((\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T)\rightarrow T$ नहीं. प्रकार की प्रणाली जो मनमाना रैंक के प्रकारों को स्वीकार करती है, उसे रैंक-एन बहुरूपी कहा जाता है।

रैंक-2 बहुरूपता के लिए प्रकार अनुमान निर्णायक है, किन्तुरैंक-3 और उससे ऊपर के लिए, यह नहीं है।^[8]^[1]^: 359

प्रतिकूल बहुरूपता

इम्प्रिडिकेटिव पोलिमोर्फिज्म (जिसे प्रथम श्रेणी का पॉलीमॉर्फिज्म भी कहा जाता है) पैरामीट्रिक पॉलीमॉर्फिज्म का सबसे शक्तिशाली रूप है।^[1]^: 340 औपचारिक तर्क में, परिभाषा को अप्रतिबंधात्मकता कहा जाता है यदि यह स्व-संदर्भित है; टाइप थ्योरी में, यह प्रकार के क्वांटिफायर के डोमेन में होने की क्षमता को संदर्भित करता है। यह पॉलिमॉर्फिक प्रकारों सहित किसी भी प्रकार के चर के किसी भी प्रकार के इन्स्टेन्शियशन की अनुमति देता है। पूर्ण प्रतिबाधा का समर्थन करने वाली प्रणाली का उदाहरण पद्धति एफ है, जो किसी भी प्रकार पर $\forall \alpha .\alpha \to \alpha$ को तत्काल करने की अनुमति देता है, जिसमें स्वयं भी सम्मिलित है।

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

परिबद्ध पैरामीट्रिक बहुरूपता

1985 में, लुका कार्डेली और पीटर वेगनर ने प्रकार के मापदंडों पर सीमा की अनुमति देने के लाभों को पहचाना।^[9] कई परिचालनों के लिए डेटा प्रकारों के कुछ ज्ञान की आवश्यकता होती है, किन्तु अन्यथा पैरामीट्रिक रूप से कार्य कर सकते हैं। उदाहरण के लिए, यह जाँचने के लिए कि क्या कोई वस्तु किसी सूची में सम्मिलित है, हमें समानता के लिए वस्तुओं की तुलना करने की आवश्यकता है। मानक एमएल में, फॉर्म के टाइप पैरामीटर a प्रतिबंधित हैं जिससे समानता ऑपरेशन उपलब्ध हो, इस प्रकार फलन में a × a list → bool और a केवल समानता परिभाषित करने वाला एक प्रकार हो सकता है। हास्केल (प्रोग्रामिंग लैंग्वेज) में, वर्ग टाइप करें से संबंधित प्रकारों की आवश्यकता के द्वारा बाउंडिंग प्राप्त की जाती है; इस प्रकार ${\textstyle \mathrm {Eq} \,\alpha \,\Rightarrow \alpha \,\rightarrow \left[\alpha \right]\rightarrow \mathrm {Bool} }$ हास्केल में ही फलन का प्रकार होता है। पैरामीट्रिक बहुरूपता का समर्थन करने वाली अधिकांश वस्तु-उन्मुख प्रोग्रामिंग भाषाओं में, मापदंडों को किसी दिए गए प्रकार के उपप्रकारों के लिए विवश किया जा सकता है (उपप्रकार बहुरूपता और सामान्य प्रोग्रामिंग पर लेख देखें)।

यह भी देखें

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Benjamin C. Pierce; Benjamin C. (Professor Pierce, University of Pennsylvania) (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.
↑ Strachey, Christopher (1967), Fundamental Concepts in Programming Languages (Lecture notes), Copenhagen: International Summer School in Computer Programming. Republished in: Strachey, Christopher (1 April 2000). "Fundamental Concepts in Programming Languages". Higher-Order and Symbolic Computation. 13 (1): 11–49. doi:10.1023/A:1010000313106. ISSN 1573-0557. S2CID 14124601.
↑ Yorgey, Brent. "More polymorphism and type classes". www.seas.upenn.edu. Retrieved 1 October 2022.
↑ Wu, Brandon. "Parametric Polymorphism - SML Help". smlhelp.github.io. Retrieved 1 October 2022.
↑ "Haskell 2010 Language Report § 4.1.2 Syntax of Types". www.haskell.org. Retrieved 1 October 2022. With one exception (that of the distinguished type variable in a class declaration (Section 4.3.1)), the type variables in a Haskell type expression are all assumed to be universally quantified; there is no explicit syntax for universal quantification.
↑ Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", Proc. Conference on Proving and Improving Programs, Arc-et-Senans (1975)
↑ Kwang Yul Seo. "Kwang's Haskell Blog - Higher rank polymorphism". kseo.github.io. Retrieved 30 September 2022.
↑ Kfoury, A. J.; Wells, J. B. (1 January 1999). "Principality and decidable type inference for finite-rank intersection types". Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Association for Computing Machinery: 161–174. doi:10.1145/292540.292556. ISBN 1581130953. S2CID 14183560.
↑ Cardelli & Wegner 1985.

संदर्भ

Hindley, J. Roger (1969), "The principal type scheme of an object in combinatory logic", Transactions of the American Mathematical Society, 146: 29–60, doi:10.2307/1995158, JSTOR 1995158, MR 0253905.
Girard, Jean-Yves (1971). "Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types". Proceedings of the Second Scandinavian Logic Symposium. Studies in Logic and the Foundations of Mathematics (in français). Vol. 63. Amsterdam. pp. 63–92. doi:10.1016/S0049-237X(08)70843-7. ISBN 9780720422597.
Girard, Jean-Yves (1972), Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (Ph.D. thesis) (in français), Université Paris 7.
Reynolds, John C. (1974), "Towards a Theory of Type Structure", Colloque Sur la Programmation, Lecture Notes in Computer Science, Paris, 19: 408–425, doi:10.1007/3-540-06859-7_148, ISBN 978-3-540-06859-4.
Milner, Robin (1978). "A Theory of Type Polymorphism in Programming" (PDF). Journal of Computer and System Sciences. 17 (3): 348–375. doi:10.1016/0022-0000(78)90014-4. S2CID 388583.
Cardelli, Luca; Wegner, Peter (December 1985). "On Understanding Types, Data Abstraction, and Polymorphism" (PDF). ACM Computing Surveys. 17 (4): 471–523. CiteSeerX 10.1.1.117.695. doi:10.1145/6041.6042. ISSN 0360-0300. S2CID 2921816.
Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.

[TAPL-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Benjamin C. Pierce; Benjamin C. (Professor Pierce, University of Pennsylvania) (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.

[Strachey_1967-2] Strachey, Christopher (1967), Fundamental Concepts in Programming Languages (Lecture notes), Copenhagen: International Summer School in Computer Programming. Republished in: Strachey, Christopher (1 April 2000). "Fundamental Concepts in Programming Languages". Higher-Order and Symbolic Computation. 13 (1): 11–49. doi:10.1023/A:1010000313106. ISSN 1573-0557. S2CID 14124601.

[3] Yorgey, Brent. "More polymorphism and type classes". www.seas.upenn.edu. Retrieved 1 October 2022.

[4] Wu, Brandon. "Parametric Polymorphism - SML Help". smlhelp.github.io. Retrieved 1 October 2022.

[5] "Haskell 2010 Language Report § 4.1.2 Syntax of Types". www.haskell.org. Retrieved 1 October 2022. With one exception (that of the distinguished type variable in a class declaration (Section 4.3.1)), the type variables in a Haskell type expression are all assumed to be universally quantified; there is no explicit syntax for universal quantification.

[6] Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", Proc. Conference on Proving and Improving Programs, Arc-et-Senans (1975)

[7] Kwang Yul Seo. "Kwang's Haskell Blog - Higher rank polymorphism". kseo.github.io. Retrieved 30 September 2022.

[8] Kfoury, A. J.; Wells, J. B. (1 January 1999). "Principality and decidable type inference for finite-rank intersection types". Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Association for Computing Machinery: 161–174. doi:10.1145/292540.292556. ISBN 1581130953. S2CID 14183560.

[FOOTNOTECardelliWegner1985-9] Cardelli & Wegner 1985.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]