टोटल फंक्शनल प्रोग्रामिंग: Difference between revisions
From Vigyanwiki
(Created page with "कुल कार्यात्मक प्रोग्रामिंग (जिसे मजबूत कार्यात्मक प्रोग्रामिंग...") |
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>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"/> | ||
इन प्रतिबंधों का मतलब है कि कुल कार्यात्मक प्रोग्रामिंग [[ट्यूरिंग-पूर्ण]] नहीं है। हालाँकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी बहुत बड़ा है। उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए [[ऊपरी सीमा]] की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त तर्क के रूप में ऊपरी सीमा का उपयोग करके | इन प्रतिबंधों का मतलब है कि कुल कार्यात्मक प्रोग्रामिंग [[ट्यूरिंग-पूर्ण]] नहीं है। हालाँकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी बहुत बड़ा है। उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए [[ऊपरी सीमा]] की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त तर्क के रूप में ऊपरी सीमा का उपयोग करके सिद्ध-समाप्ति फ़ंक्शन में परिवर्तित किया जा सकता है। | ||
उदाहरण के लिए, [[जल्दी से सुलझाएं]] को तुच्छ रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, लेकिन यह केवल वेक्टर की लंबाई की अधिकतम गहराई (सबसे खराब स्थिति में समय जटिलता [[ बिग ओ अंकन ]] (एन) तक ही पुनरावृत्ति करता है<sup>2</sup>)). हास्केल (प्रोग्रामिंग भाषा) का उपयोग करके सूचियों पर | उदाहरण के लिए, [[जल्दी से सुलझाएं]] को तुच्छ रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, लेकिन यह केवल वेक्टर की लंबाई की अधिकतम गहराई (सबसे खराब स्थिति में समय जटिलता [[ बिग ओ अंकन |बिग ओ अंकन]] (एन) तक ही पुनरावृत्ति करता है<sup>2</sup>)). हास्केल (प्रोग्रामिंग भाषा) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा): | ||
<syntaxhighlight lang="haskell"> | <syntaxhighlight lang="haskell"> | ||
import Data.List (partition) | import Data.List (partition) | ||
| Line 35: | 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:05, 4 August 2023
कुल कार्यात्मक प्रोग्रामिंग (जिसे मजबूत कार्यात्मक प्रोग्रामिंग के रूप में भी जाना जाता है,[1] सामान्य, या कमजोर कार्यात्मक प्रोग्रामिंग के साथ तुलना करने के लिए) कंप्यूटर प्रोग्रामिंग प्रतिमान है जो प्रोग्रामों की सीमा को उन मशीनों तक सीमित करता है जो हमेशा रुकती हैं।[2]
प्रतिबंध
निम्नलिखित प्रतिबंधों द्वारा समाप्ति की गारंटी दी जाती है:
- रिकर्सन का प्रतिबंधित रूप, जो केवल अपने तर्कों के 'कम' रूपों पर काम करता है, जैसे वाल्थर प्रत्यावर्तन, अवसंरचनात्मक प्रत्यावर्तन , या दृढ़ता से सामान्यीकरण, जैसा कि कोड की अमूर्त व्याख्या से सिद्ध होता है।[3]
- प्रत्येक फ़ंक्शन कुल (आंशिक फ़ंक्शन के विपरीत) फ़ंक्शन होना चाहिए। यानी, इसके डोमेन के अंदर हर चीज़ की परिभाषा होनी चाहिए।
- आमतौर पर उपयोग किए जाने वाले आंशिक कार्य को विस्तारित करने के कई संभावित तरीके हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए मनमाना परिणाम चुनना, जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए और तर्क जोड़ना; या शोधन प्रकार जैसी प्रकार प्रणाली सुविधाओं का उपयोग करके उन्हें बाहर करना।[2]
इन प्रतिबंधों का मतलब है कि कुल कार्यात्मक प्रोग्रामिंग ट्यूरिंग-पूर्ण नहीं है। हालाँकि, उपयोग किए जा सकने वाले एल्गोरिदम का सेट अभी भी बहुत बड़ा है। उदाहरण के लिए, कोई भी एल्गोरिदम जिसके लिए ऊपरी सीमा की गणना की जा सकती है (एक प्रोग्राम द्वारा जो स्वयं केवल वाल्थर रिकर्सन का उपयोग करता है) को प्रत्येक पुनरावृत्ति या रिकर्सन पर घटते अतिरिक्त तर्क के रूप में ऊपरी सीमा का उपयोग करके सिद्ध-समाप्ति फ़ंक्शन में परिवर्तित किया जा सकता है।
उदाहरण के लिए, जल्दी से सुलझाएं को तुच्छ रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, लेकिन यह केवल वेक्टर की लंबाई की अधिकतम गहराई (सबसे खराब स्थिति में समय जटिलता बिग ओ अंकन (एन) तक ही पुनरावृत्ति करता है2)). हास्केल (प्रोग्रामिंग भाषा) का उपयोग करके सूचियों पर त्वरित सॉर्ट कार्यान्वयन (जिसे सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा):
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 जैसे अनुप्रयोगों के लिए किया जाता है। कोडाटा का उपयोग करने में corecursion जैसे ऑपरेशनों का उपयोग शामिल होता है। हालाँकि, कुल कार्यात्मक प्रोग्रामिंग भाषा (आश्रित प्रकार के साथ) में कोडाटा के बिना भी 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
