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

टोटल फंक्शनल प्रोग्रामिंग (जिसे स्ट्रोंग फंक्शनल प्रोग्रामिंग के रूप में भी जाना जाता है, इस प्रकार से सामान्य, या वीक फंक्शनल प्रोग्रामिंग से अलग किया जा सकता है) जो कंप्यूटर प्रोग्रामिंग प्रतिमान है, जो की प्रोग्रामों की सीमा को उन लोगों तक सीमित करता है जो सिद्ध रूप से समाप्त हो रहे हैं।

रेस्ट्रिक्शन्स

इस प्रकार से निम्नलिखित प्रतिबंधों द्वारा समाप्ति का प्रमाण दिया गया है:

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

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

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

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 जैसे अनुप्रयोगों के लिए किया जाता है। तब कोडाटा का उपयोग करने में कोरकर्शन जैसे ऑपरेशनों का उपयोग सम्मिलित होता है। चूंकि , टोटल फंक्शनल प्रोग्रामिंग लैंग्वेज (डेपेनडेंट टाइप्स के साथ) में कोडाटा के बिना भी I/O करना संभव है।

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

यह भी देखें

• टेर्मीनेसन एनालिसिस