टोटल फंक्शनल प्रोग्रामिंग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
कुल | '''कुल फंक्शनल प्रोग्रामिंग''' (जिसे स्ट्रोंग फंक्शनल प्रोग्रामिंग के रूप में भी जाना जाता है,<ref>This term is due to: {{Cite conference|last1=Turner|first1=D.A.|author-link=David Turner (computer scientist)|title=Elementary Strong Functional Programming|conference=First International Symposium on Functional Programming Languages in Education|date=December 1995|series=Springer LNCS|volume=1022|pages=1–13}}.</ref> इस प्रकार से सामान्य, या वीक [[कार्यात्मक प्रोग्रामिंग|फंक्शनल प्रोग्रामिंग]] से अलग किया जा सकता है) जो [[कंप्यूटर प्रोग्रामिंग]] प्रतिमान है, जो की प्रोग्रामों की सीमा को उन लोगों तक सीमित करता है जो सिद्ध रूप से समाप्त हो रहे हैं।<ref name="TFP">{{Citation|last=Turner|first=D.A.|author-link=David Turner (computer scientist)|title=Total Functional Programming|journal=[[Journal of Universal Computer Science]]|volume=10|date=2004-07-28|pages=751–768|url=http://www.jucs.org/jucs_10_7/total_functional_programming|doi=10.3217/jucs-010-07-0751|issue=7}}</ref> | ||
==प्रतिबंध== | ==प्रतिबंध== | ||
निम्नलिखित प्रतिबंधों द्वारा समाप्ति | इस प्रकार से निम्नलिखित प्रतिबंधों द्वारा समाप्ति का प्रमाण दिया गया है: | ||
# रिकर्सन का प्रतिबंधित रूप, जो केवल अपने तर्कों के 'कम' रूपों पर | # रिकर्सन का प्रतिबंधित रूप, जो केवल अपने तर्कों के 'कम' रूपों पर कार्य करता है, जैसे वाल्थर [[प्रत्यावर्तन|रिकर्सन]], [[ अवसंरचनात्मक प्रत्यावर्तन |सबस्ट्रक्चरल रिकर्सन,]] या दृढ़ता से सामान्यीकरण, जैसा कि कोड की [[अमूर्त व्याख्या]] से सिद्ध होता है।<ref name="ETinESFP">{{Citation|last=Turner|first=D. A.|author-link=David Turner (computer scientist)|title=Ensuring Termination in ESFP|journal=Journal of Universal Computer Science|volume=6|date=2000-04-28|pages=474–488|url=http://www.jucs.org/jucs_6_4/ensuring_termination_in_esfp|doi=10.3217/jucs-006-04-0474|issue=4}}</ref> | ||
# प्रत्येक फ़ंक्शन कुल ( | # प्रत्येक फ़ंक्शन कुल (पार्शियल फ़ंक्शन के विपरीत) फ़ंक्शन होना चाहिए। अर्थात , इसके डोमेन के अंदर सभी वस्तु की परिभाषा होनी चाहिए। | ||
#* | #* सामान्यतः उपयोग किए जाने वाले [[आंशिक कार्य|पार्शियल फ़ंक्शन]] को विस्तारित करने के अनेक संभावित विधि हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए इच्छानुसार परिणाम चुनना है, और जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) <math>\forall x \in \mathbb{N}. x \div 0 = 0</math> विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए और तर्क जोड़ना; या [[शोधन प्रकार|रेफीनेमेंट टाइप्स]] जैसी प्रकार प्रणाली सुविधाओं का उपयोग करके उन्हें बाहर करना है।<ref name="TFP"/> | ||
इस प्रकार से प्रतिबंधों का अर्थ है कि कुल फंक्शनल प्रोग्रामिंग [[ट्यूरिंग-पूर्ण]] नहीं है। चूंकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी अधिक उच्च है। अतः उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए [[ऊपरी सीमा|असिम्पटोटिक अपर बाउंड]] की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त तर्क के रूप में ऊपरी सीमा का उपयोग करके सिद्ध-समाप्ति फ़ंक्शन में परिवर्तित किया जा सकता है। | |||
उदाहरण के लिए, [[जल्दी से सुलझाएं]] को | अतः उदाहरण के लिए, [[जल्दी से सुलझाएं|क्विकशोर्ट]] को नगण्य रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, किन्तु यह केवल सदिश की लंबाई की अधिकतम गहराई (अधिक व्यर्थ स्थिति में समय सम्मिश्र [[ बिग ओ अंकन |O(''n''<sup>2</sup>))]] तक ही पुनरावृत्ति करता है )). हास्केल (प्रोग्रामिंग लैंग्वेज ) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा): | ||
<syntaxhighlight lang="haskell"> | <syntaxhighlight lang="haskell"> | ||
import Data.List (partition) | import Data.List (partition) | ||
| Line 18: | Line 18: | ||
in qsort lesser ++ [a] ++ qsort greater | in qsort lesser ++ [a] ++ qsort greater | ||
</syntaxhighlight> | </syntaxhighlight> | ||
एक सीमा के रूप में | इस प्रकार से एक सीमा के रूप में सदिश की लंबाई का उपयोग करके इसे उप-संरचनात्मक पुनरावर्ती बनाने के लिए, हम यह कर सकते हैं: | ||
<syntaxhighlight lang="haskell"> | <syntaxhighlight lang="haskell"> | ||
import Data.List (partition) | import Data.List (partition) | ||
| Line 33: | Line 33: | ||
in qsortSub ls lesser ++ [a] ++ qsortSub ls greater | in qsortSub ls lesser ++ [a] ++ qsortSub ls greater | ||
</syntaxhighlight> | </syntaxhighlight> | ||
एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, | चूंकि एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, किन्तु व्यावहारिक ऊपरी सीमा होती है (उदाहरण के लिए, कुछ अनुमान-आधारित एल्गोरिदम को इतने सारे रिकर्सन के पश्चात छोड़ने के लिए प्रोग्राम किया जा सकता है, जो समाप्ति भी सुनिश्चित करता है)। | ||
कुल | अतः कुल फंक्शनल प्रोग्रामिंग का और परिणाम यह है कि [[सख्त मूल्यांकन|स्ट्रिक्ट इवैल्यूएशन]] और [[आलसी मूल्यांकन|लेजी]] [[सख्त मूल्यांकन|इवैल्यूएशन]] दोनों का सिद्धांत रूप से ही व्यवहार करती है; चूंकि , प्रदर्शन कारणों से या द्वतीय अभी भी उत्तम (या आवश्यक भी) हो सकता है।<ref>The differences between lazy and eager evaluation are discussed in: {{cite book|last=Granström|first=J. G.|title=Treatise on Intuitionistic Type Theory|series=Logic, Epistemology, and the Unity of Science|volume=7|year=2011|url=https://www.springer.com/philosophy/book/978-94-007-1735-0|isbn=978-94-007-1735-0}} See in particular pp. 86–91.</ref> | ||
कुल | इस प्रकार से कुल फंक्शनल प्रोग्रामिंग में, डेटा और[[ आंकड़े | कोडाटा]] (कंप्यूटर साइंस ) के मध्य अंतर किया जाता है - पूर्व [[वित्तीय]] है, जबकि बाद वाला संभावित रूप से अनंत है। ऐसी संभावित अनंत डेटा संरचनाओं का उपयोग I/O जैसे अनुप्रयोगों के लिए किया जाता है। तब कोडाटा का उपयोग करने में [[corecursion|कोरकर्शन]] जैसे ऑपरेशनों का उपयोग सम्मिलित होता है। चूंकि , कुल फंक्शनल प्रोग्रामिंग लैंग्वेज ([[आश्रित प्रकार|डेपेनडेंट टाइप्स]] के साथ) में कोडाटा के बिना भी I/O करना संभव है।<ref>{{Citation|last=Granström|first=J. G.|title=A New Paradigm for Component-based Development|date=May 2012|journal=Journal of Software|volume=7|issue=5|pages=1136–1148|doi=10.4304/jsw.7.5.1136-1148}}{{Dead link|date=October 2020}} [https://web.archive.org/web/20200709203859/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.369.3459&rep=rep1&type=pdf Archived copy]</ref> | ||
[[एपिग्राम (प्रोग्रामिंग भाषा)]] और [[चैरिटी (प्रोग्रामिंग भाषा)]] दोनों को कुल | किन्तु [[एपिग्राम (प्रोग्रामिंग भाषा)|एपिग्राम (प्रोग्रामिंग लैंग्वेज)]] और [[चैरिटी (प्रोग्रामिंग भाषा)|चैरिटी (प्रोग्रामिंग लैंग्वेज)]] दोनों को कुल फंक्शनल प्रोग्रामिंग लैंग्वेज माना जा सकता है, तथापि वे [[डेविड टर्नर (कंप्यूटर वैज्ञानिक)]] द्वारा अपने पेपर में निर्दिष्ट विधि से कार्य नहीं करते हैं। तब मार्टिन-लोफ प्रकार के सिद्धांत या निर्माण के कैलकुलस में प्लेन [[सिस्टम एफ]] में प्रोग्रामिंग की जा सकती है। | ||
== यह भी देखें == | == यह भी देखें == | ||
*[[समाप्ति विश्लेषण]] | *[[समाप्ति विश्लेषण|टेर्मीनेसन एनालिसिस]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 18:52, 4 August 2023
कुल फंक्शनल प्रोग्रामिंग (जिसे स्ट्रोंग फंक्शनल प्रोग्रामिंग के रूप में भी जाना जाता है,[1] इस प्रकार से सामान्य, या वीक फंक्शनल प्रोग्रामिंग से अलग किया जा सकता है) जो कंप्यूटर प्रोग्रामिंग प्रतिमान है, जो की प्रोग्रामों की सीमा को उन लोगों तक सीमित करता है जो सिद्ध रूप से समाप्त हो रहे हैं।[2]
प्रतिबंध
इस प्रकार से निम्नलिखित प्रतिबंधों द्वारा समाप्ति का प्रमाण दिया गया है:
- रिकर्सन का प्रतिबंधित रूप, जो केवल अपने तर्कों के 'कम' रूपों पर कार्य करता है, जैसे वाल्थर रिकर्सन, सबस्ट्रक्चरल रिकर्सन, या दृढ़ता से सामान्यीकरण, जैसा कि कोड की अमूर्त व्याख्या से सिद्ध होता है।[3]
- प्रत्येक फ़ंक्शन कुल (पार्शियल फ़ंक्शन के विपरीत) फ़ंक्शन होना चाहिए। अर्थात , इसके डोमेन के अंदर सभी वस्तु की परिभाषा होनी चाहिए।
- सामान्यतः उपयोग किए जाने वाले पार्शियल फ़ंक्शन को विस्तारित करने के अनेक संभावित विधि हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए इच्छानुसार परिणाम चुनना है, और जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए और तर्क जोड़ना; या रेफीनेमेंट टाइप्स जैसी प्रकार प्रणाली सुविधाओं का उपयोग करके उन्हें बाहर करना है।[2]
इस प्रकार से प्रतिबंधों का अर्थ है कि कुल फंक्शनल प्रोग्रामिंग ट्यूरिंग-पूर्ण नहीं है। चूंकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी अधिक उच्च है। अतः उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए असिम्पटोटिक अपर बाउंड की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त तर्क के रूप में ऊपरी सीमा का उपयोग करके सिद्ध-समाप्ति फ़ंक्शन में परिवर्तित किया जा सकता है।
अतः उदाहरण के लिए, क्विकशोर्ट को नगण्य रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, किन्तु यह केवल सदिश की लंबाई की अधिकतम गहराई (अधिक व्यर्थ स्थिति में समय सम्मिश्र O(n2)) तक ही पुनरावृत्ति करता है )). हास्केल (प्रोग्रामिंग लैंग्वेज ) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा):
import Data.List (partition)
qsort [] = []
qsort [a] = [a]
qsort (a:as) = let (lesser, greater) = partition (<a) as
in qsort lesser ++ [a] ++ qsort greater
इस प्रकार से एक सीमा के रूप में सदिश की लंबाई का उपयोग करके इसे उप-संरचनात्मक पुनरावर्ती बनाने के लिए, हम यह कर सकते हैं:
import Data.List (partition)
qsort x = qsortSub x x
-- minimum case
qsortSub [] as = as -- shows termination
-- standard qsort cases
qsortSub (l:ls) [] = [] -- nonrecursive, so accepted
qsortSub (l:ls) [a] = [a] -- nonrecursive, so accepted
qsortSub (l:ls) (a:as) = let (lesser, greater) = partition (<a) as
-- recursive, but recurs on ls, which is a substructure of
-- its first input.
in qsortSub ls lesser ++ [a] ++ qsortSub ls greater
चूंकि एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, किन्तु व्यावहारिक ऊपरी सीमा होती है (उदाहरण के लिए, कुछ अनुमान-आधारित एल्गोरिदम को इतने सारे रिकर्सन के पश्चात छोड़ने के लिए प्रोग्राम किया जा सकता है, जो समाप्ति भी सुनिश्चित करता है)।
अतः कुल फंक्शनल प्रोग्रामिंग का और परिणाम यह है कि स्ट्रिक्ट इवैल्यूएशन और लेजी इवैल्यूएशन दोनों का सिद्धांत रूप से ही व्यवहार करती है; चूंकि , प्रदर्शन कारणों से या द्वतीय अभी भी उत्तम (या आवश्यक भी) हो सकता है।[4]
इस प्रकार से कुल फंक्शनल प्रोग्रामिंग में, डेटा और कोडाटा (कंप्यूटर साइंस ) के मध्य अंतर किया जाता है - पूर्व वित्तीय है, जबकि बाद वाला संभावित रूप से अनंत है। ऐसी संभावित अनंत डेटा संरचनाओं का उपयोग I/O जैसे अनुप्रयोगों के लिए किया जाता है। तब कोडाटा का उपयोग करने में कोरकर्शन जैसे ऑपरेशनों का उपयोग सम्मिलित होता है। चूंकि , कुल फंक्शनल प्रोग्रामिंग लैंग्वेज (डेपेनडेंट टाइप्स के साथ) में कोडाटा के बिना भी I/O करना संभव है।[5]
किन्तु एपिग्राम (प्रोग्रामिंग लैंग्वेज) और चैरिटी (प्रोग्रामिंग लैंग्वेज) दोनों को कुल फंक्शनल प्रोग्रामिंग लैंग्वेज माना जा सकता है, तथापि वे डेविड टर्नर (कंप्यूटर वैज्ञानिक) द्वारा अपने पेपर में निर्दिष्ट विधि से कार्य नहीं करते हैं। तब मार्टिन-लोफ प्रकार के सिद्धांत या निर्माण के कैलकुलस में प्लेन सिस्टम एफ में प्रोग्रामिंग की जा सकती है।
यह भी देखें
संदर्भ
- ↑ This term is due to: Turner, D.A. (December 1995). Elementary Strong Functional Programming. First International Symposium on Functional Programming Languages in Education. Springer LNCS. Vol. 1022. pp. 1–13..
- ↑ 2.0 2.1 Turner, D.A. (2004-07-28), "Total Functional Programming", Journal of Universal Computer Science, 10 (7): 751–768, doi:10.3217/jucs-010-07-0751
- ↑ Turner, D. A. (2000-04-28), "Ensuring Termination in ESFP", Journal of Universal Computer Science, 6 (4): 474–488, doi:10.3217/jucs-006-04-0474
- ↑ The differences between lazy and eager evaluation are discussed in: Granström, J. G. (2011). Treatise on Intuitionistic Type Theory. Logic, Epistemology, and the Unity of Science. Vol. 7. ISBN 978-94-007-1735-0. See in particular pp. 86–91.
- ↑ Granström, J. G. (May 2012), "A New Paradigm for Component-based Development", Journal of Software, 7 (5): 1136–1148, doi:10.4304/jsw.7.5.1136-1148[dead link] Archived copy
