टोटल फंक्शनल प्रोग्रामिंग

कुल कार्यात्मक प्रोग्रामिंग (जिसे मजबूत कार्यात्मक प्रोग्रामिंग के रूप में भी जाना जाता है, सामान्य, या कमजोर कार्यात्मक प्रोग्रामिंग के साथ तुलना करने के लिए) एक कंप्यूटर प्रोग्रामिंग प्रतिमान है जो प्रोग्रामों की सीमा को उन मशीनों तक सीमित करता है जो हमेशा रुकती हैं।

प्रतिबंध

निम्नलिखित प्रतिबंधों द्वारा समाप्ति की गारंटी दी जाती है:

1. रिकर्सन का एक प्रतिबंधित रूप, जो केवल अपने तर्कों के 'कम' रूपों पर काम करता है, जैसे [[ वाल्थर प्रत्यावर्तन ]], अवसंरचनात्मक प्रत्यावर्तन , या दृढ़ता से सामान्यीकरण, जैसा कि कोड की अमूर्त व्याख्या से सिद्ध होता है।
2. प्रत्येक फ़ंक्शन कुल (आंशिक फ़ंक्शन के विपरीत) फ़ंक्शन होना चाहिए। यानी, इसके डोमेन के अंदर हर चीज़ की एक परिभाषा होनी चाहिए।
   • आमतौर पर उपयोग किए जाने वाले आंशिक कार्यों को विस्तारित करने के कई संभावित तरीके हैं जैसे कि विभाजन को कुल करना: इनपुट के लिए एक मनमाना परिणाम चुनना, जिस पर फ़ंक्शन सामान्य रूप से अपरिभाषित होता है (जैसे कि) $\forall x\in \mathbb {N} .x\div 0=0$ विभाजन के लिए); उन इनपुटों के परिणाम निर्दिष्ट करने के लिए एक और तर्क जोड़ना; या शोधन प्रकार जैसी प्रकार प्रणाली सुविधाओं का उपयोग करके उन्हें बाहर करना।

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

उदाहरण के लिए, जल्दी से सुलझाएं को तुच्छ रूप से सबस्ट्रक्चरल रिकर्सिव के रूप में नहीं दिखाया गया है, लेकिन यह केवल वेक्टर की लंबाई की अधिकतम गहराई (सबसे खराब स्थिति में समय जटिलता बिग ओ अंकन (एन) तक ही पुनरावृत्ति करता है²)). हास्केल (प्रोग्रामिंग भाषा) का उपयोग करके सूचियों पर एक त्वरित सॉर्ट कार्यान्वयन (जिसे एक सबस्ट्रक्चरल रिकर्सिव चेकर द्वारा अस्वीकार कर दिया जाएगा):

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

एल्गोरिदम के कुछ वर्गों में कोई सैद्धांतिक ऊपरी सीमा नहीं होती है, लेकिन एक व्यावहारिक ऊपरी सीमा होती है (उदाहरण के लिए, कुछ अनुमान-आधारित एल्गोरिदम को इतने सारे रिकर्सन के बाद छोड़ने के लिए प्रोग्राम किया जा सकता है, जो समाप्ति भी सुनिश्चित करता है)।

कुल कार्यात्मक प्रोग्रामिंग का एक और परिणाम यह है कि सख्त मूल्यांकन और आलसी मूल्यांकन दोनों का सिद्धांत रूप में एक ही व्यवहार होता है; हालाँकि, प्रदर्शन कारणों से एक या दूसरा अभी भी बेहतर (या आवश्यक भी) हो सकता है। कुल कार्यात्मक प्रोग्रामिंग में, डेटा और कोआंकड़े (कंप्यूटर विज्ञान) के बीच एक अंतर किया जाता है - पूर्व वित्तीय है, जबकि बाद वाला संभावित रूप से अनंत है। ऐसी संभावित अनंत डेटा संरचनाओं का उपयोग I/O जैसे अनुप्रयोगों के लिए किया जाता है। कोडाटा का उपयोग करने में corecursion जैसे ऑपरेशनों का उपयोग शामिल होता है। हालाँकि, कुल कार्यात्मक प्रोग्रामिंग भाषा (आश्रित प्रकारों के साथ) में कोडाटा के बिना भी I/O करना संभव है। एपिग्राम (प्रोग्रामिंग भाषा) और चैरिटी (प्रोग्रामिंग भाषा) दोनों को कुल कार्यात्मक प्रोग्रामिंग भाषा माना जा सकता है, भले ही वे डेविड टर्नर (कंप्यूटर वैज्ञानिक) द्वारा अपने पेपर में निर्दिष्ट तरीके से काम नहीं करते हैं। तो मार्टिन-लोफ प्रकार के सिद्धांत या निर्माण के कैलकुलस में सीधे सादे सिस्टम एफ में प्रोग्रामिंग की जा सकती है।

यह भी देखें

• समाप्ति विश्लेषण