टोटल फंक्शनल प्रोग्रामिंग: 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> | ||
==रेस्ट्रिक्शन्स== | ==रेस्ट्रिक्शन्स== | ||
इस प्रकार से निम्नलिखित प्रतिबंधों द्वारा समाप्ति का प्रमाण दिया गया है: | इस प्रकार से निम्नलिखित प्रतिबंधों द्वारा समाप्ति का प्रमाण दिया गया है: | ||
| Line 7: | Line 7: | ||
#* सामान्यतः उपयोग किए जाने वाले [[आंशिक कार्य|पार्शियल फ़ंक्शन]] को विस्तारित करने के अनेक संभावित विधि हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए इच्छानुसार परिणाम चुनना है, और जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) <math>\forall x \in \mathbb{N}. x \div 0 = 0</math> विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए और लाॅजिक जोड़ना; या [[शोधन प्रकार|रेफीनेमेंट टाइप्स]] जैसे एक प्रकार के सिस्टम सुविधाओं का उपयोग करके उन्हें बाहर करना है।<ref name="TFP"/> | #* सामान्यतः उपयोग किए जाने वाले [[आंशिक कार्य|पार्शियल फ़ंक्शन]] को विस्तारित करने के अनेक संभावित विधि हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए इच्छानुसार परिणाम चुनना है, और जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) <math>\forall x \in \mathbb{N}. x \div 0 = 0</math> विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए और लाॅजिक जोड़ना; या [[शोधन प्रकार|रेफीनेमेंट टाइप्स]] जैसे एक प्रकार के सिस्टम सुविधाओं का उपयोग करके उन्हें बाहर करना है।<ref name="TFP"/> | ||
इस प्रकार से प्रतिबंधों का अर्थ है कि | इस प्रकार से प्रतिबंधों का अर्थ है कि टोटल फंक्शनल प्रोग्रामिंग [[ट्यूरिंग-पूर्ण]] नहीं है। चूंकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी अधिक उच्च है। अतः उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए [[ऊपरी सीमा|असिम्पटोटिक अपर बाउंड]] की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त लाॅजिक के रूप में ऊपरी सीमा का उपयोग करके सिद्ध-समाप्ति फ़ंक्शन में परिवर्तित किया जा सकता है। | ||
अतः उदाहरण के लिए, [[जल्दी से सुलझाएं|क्विकशोर्ट]] को नगण्य रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, किन्तु यह केवल सदिश की लंबाई की अधिकतम गहराई (अधिक व्यर्थ स्थिति में समय सम्मिश्र [[ बिग ओ अंकन |O(''n''<sup>2</sup>))]] तक ही पुनरावृत्ति करता है )). हास्केल (प्रोग्रामिंग लैंग्वेज ) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा): | अतः उदाहरण के लिए, [[जल्दी से सुलझाएं|क्विकशोर्ट]] को नगण्य रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, किन्तु यह केवल सदिश की लंबाई की अधिकतम गहराई (अधिक व्यर्थ स्थिति में समय सम्मिश्र [[ बिग ओ अंकन |O(''n''<sup>2</sup>))]] तक ही पुनरावृत्ति करता है )). हास्केल (प्रोग्रामिंग लैंग्वेज ) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा): | ||
| Line 35: | Line 35: | ||
चूंकि एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, किन्तु व्यावहारिक ऊपरी सीमा होती है (उदाहरण के लिए, कुछ अनुमान-आधारित एल्गोरिदम को इतने सारे रिकर्सन के पश्चात छोड़ने के लिए प्रोग्राम किया जा सकता है, जो समाप्ति भी सुनिश्चित करता है)। | चूंकि एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, किन्तु व्यावहारिक ऊपरी सीमा होती है (उदाहरण के लिए, कुछ अनुमान-आधारित एल्गोरिदम को इतने सारे रिकर्सन के पश्चात छोड़ने के लिए प्रोग्राम किया जा सकता है, जो समाप्ति भी सुनिश्चित करता है)। | ||
अतः | अतः टोटल फंक्शनल प्रोग्रामिंग का परिणाम यह है कि [[सख्त मूल्यांकन|स्ट्रिक्ट इवैल्यूएशन]] और [[आलसी मूल्यांकन|लेजी]] [[सख्त मूल्यांकन|इवैल्यूएशन]] दोनों का सिद्धांत रूप से ही व्यवहार करती है; चूंकि , प्रदर्शन कारणों से या द्वतीय अभी भी उत्तम (या आवश्यक भी) हो सकता है।<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 12:49, 7 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
