निरंतर-अग्रगामी शैली (सीपीएस)

फंक्शनल प्रोग्रामिंग में, निरंतरता-पासिंग शैली (सीपीएस) प्रोग्रामिंग की एक शैली है जिसमें नियंत्रण प्रवाह को निरंतरता के रूप में स्पष्ट रूप से पास्ड किया जाता है। इसकी तुलना प्रत्यक्ष शैली से की जाती है, जो की प्रोग्रामिंग की उसुअल शैली है। अतः गेराल्ड जे सुसमैन और गाइ एल. स्टील, जूनियर ने एआई मेमो 349 (1975) में वाक्यांश गढ़ा, जो स्कीम (प्रोग्रामिंग लैंग्वेज ) प्रोग्रामिंग लैंग्वेज का प्रथम वर्शन निर्धारित करता है। इस प्रकार से जॉन सी. रेनॉल्ड्स निरंतरता की अनेक खोजों का विस्तृत अकाउंट देते हैं।

निरंतरता-पासिंग शैली में लिखा गया एक फ़ंक्शन एक्सप्लिसिट लॉजिक लेता है: एक स्पष्ट "निरंतरता"; अर्थात , एक लॉजिक का एक कार्य: और स्पष्ट निरंतरता; अर्थात लॉजिक का कार्य है। जब सीपीएस फ़ंक्शन ने अपने परिणाम मान की गणना की है, तो यह लॉजिक के रूप में इस मान के साथ निरंतरता फ़ंक्शन को कॉल करके इसे वापस कर देता है। इसका अर्थ यह है कि सीपीएस फ़ंक्शन को प्रयुक्त करते समय, कॉलिंग फ़ंक्शन को सबरूटीन के रिटर्न वैल्यू के साथ प्रयुक्त करने के लिए प्रोसीजर प्रदान करने की आवश्यकता होती है। अतः कोड को इस रूप में व्यक्त करने से अनेक वस्तु स्पष्ट हो जाती हैं जो की प्रत्यक्ष शैली में अंतर्निहित होती हैं। इनमें सम्मिलित हैं: इस प्रकार से प्रोसीजर रिटर्न, जो निरंतरता के लिए कॉल के रूप में स्पष्ट हो जाते हैं; इंटरमीडिएट मान, जो सभी दिए गए नाम हैं; लॉजिक इवैल्यूएशन का क्रम, जिसे स्पष्ट किया गया है; और टेल कॉल , जो बस उसी निरंतरता के साथ प्रोसीजर को कॉल करते हैं, जो उनमोडीफ़िएड, कॉलर को दी गई थी।

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

उदाहरण

इस प्रकार से सीपीएस में, प्रत्येक प्रोसीजर एक्स्ट्रा लॉजिक प्राप्त करती है जो यह दर्शाती है कि फ़ंक्शन द्वारा गणना किए जा रहे परिणाम के साथ क्या किया जाना चाहिए। यह, सामान्यतः उपलब्ध विभिन्न प्रकार के निर्माणों को प्रतिबंधित करने वाली रेस्ट्रिक्टिव शैली के साथ, प्रोग्राम के शब्दार्थ को उजागर करने के लिए उपयोग किया जाता है, जिससे उनका विश्लेषण करना सरल हो जाता है। यह शैली असामान्य नियंत्रण स्ट्रूकचर को जैसे कैच/थ्रो या नियंत्रण के अन्य नॉन-लोकल ट्रांस्फर्स व्यक्त करना भी सरल बनाती है।

अतः सीपीएस की कुंजी यह याद रखना है कि (a) प्रत्येक फ़ंक्शन एक्स्ट्रा लॉजिक लेता है जिसे इसकी निरंतरता के रूप में जाना जाता है, और (b) फ़ंक्शन कॉल में प्रत्येक लॉजिक या तो चर या लैम्ब्डा (प्रोग्रामिंग) होना चाहिए (अधिक सम्मिश्र अभिव्यक्ति नहीं)। इसमें अभिव्यक्ति को इनसाइड-आउट करने का प्रभाव होता है क्योंकि अभिव्यक्ति के सबसे इनरमोस्ट पार्ट्स का इवैल्यूएशन पहले किया जाना चाहिए, चूंकि इस प्रकार सीपीएस इवैल्यूएशन के क्रम के साथ-साथ नियंत्रण प्रवाह को भी स्पष्ट करता है। प्रत्यक्ष शैली में कोड और संबंधित सीपीएस के कुछ उदाहरण नीचे दिखाई देते हैं। ये उदाहरण योजना (प्रोग्रामिंग लैंग्वेज) में लिखे गए हैं; प्रिमिटीव्स के अनुसार निरंतरता फ़ंक्शन k: को नामित पैरामीटर के रूप में दर्शाया जाता है

Direct style	Continuation passing style
(define (pyth x y) (sqrt (+ (* x x) (* y y))))	(define (pyth& x y k) (*& x x (lambda (x2) (*& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k))))))))
(define (factorial n) (if (= n 0) 1 ; NOT tail-recursive (* n (factorial (- n 1)))))	(define (factorial& n k) (=& n 0 (lambda (b) (if b ; growing continuation (k 1) ; in the recursive call (-& n 1 (lambda (nm1) (factorial& nm1 (lambda (f) (*& n f k)))))))))
(define (factorial n) (f-aux n 1)) (define (f-aux n a) (if (= n 0) a ; tail-recursive (f-aux (- n 1) (* n a))))	(define (factorial& n k) (f-aux& n 1 k)) (define (f-aux& n a k) (=& n 0 (lambda (b) (if b ; unmodified continuation (k a) ; in the recursive call (-& n 1 (lambda (nm1) (*& n a (lambda (nta) (f-aux& nm1 nta k)))))))))

ध्यान दें कि सीपीएस वर्शन में, प्रिमिटीव्स का उपयोग किया जाता है, जैसे +& और *& स्वयं सीपीएस हैं, प्रत्यक्ष शैली नहीं है, इसलिए उपरोक्त उदाहरणों को स्कीम सिस्टम में कार्य करने के लिए हमें प्रिमिटीव्स के इन सीपीएस वर्शन को लिखने की आवश्यकता होती है, उदाहरण के लिए *& द्वारा परिभाषित:

(define (*& x y k)
 (k (* x y)))

सामान्य रूप से ऐसा करने के लिए, हम कन्वर्शन रूटीन लिख सकते हैं:

(define (cps-prim f)
 (lambda args
  (let ((r (reverse args)))
   ((car r) (apply f
             (reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))

इस प्रकार से सीपीएस में लिखी गई प्रोसीजर को प्रत्यक्ष शैली में लिखी गई प्रोसीजर से कॉल करने के लिए, निरंतरता प्रदान करना आवश्यक है जो की सीपीएस प्रोसीजर द्वारा गणना किए गए परिणाम प्राप्त करती है। अतः उपरोक्त उदाहरण में (यह मानते हुए कि सीपीएस प्राइमेटिव्स प्रदान किए गए हैं), हम कॉल कर सकते हैं (factorial& 10 (lambda (x) (display x) (newline))).

अतः सीपीएस में प्रिमिटीव्स कार्य प्रदान करने के विधि में कंपाइलरों के मध्य कुछ विविधता है। ऊपर हमने सबसे सिम्प्लेस्ट कन्वेंशन का उपयोग किया है, चूंकि कभी-कभी बूलियन प्राइमेटिव प्रदान किए जाते हैं जो दो संभावित स्तिथियों में कॉल करने के लिए दो थंक (विलंबित गणना) लेते हैं, इसलिए (=& n 0 (lambda (b) (if b ...))) अंदर कॉल करें f-aux& उपरोक्त परिभाषा के स्थान पर इस प्रकार कॉन्टीनुएशन (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). लिखा जाएगा इसी तरह, कभी-कभी if प्रिमिटिव स्वयं सीपीएस में सम्मिलित नहीं है, किन्तु फ़ंक्शन if& है प्रदान किया जाता है जिसमें तीन लॉजिक होते हैं: बूलियन स्थिति और सशर्त की दो आर्म्स के अनुरूप दो थंक आदि।

ऊपर दिखाए गए अनुवाद दर्शाया गया हैं कि सीपीएस ग्लोबल परिवर्तन है। जैसी कि अपेक्षा की जा सकती है, प्रत्यक्ष शैली का फैक्टोरियल ही लॉजिक प्राप्त करता है; इस प्रकार से लॉजिक और निरंतरता सीपीएस फैक्टोरियल टू प्राप्त करता है: अतः सीपीएस-एड फ़ंक्शन को कॉल करने वाले किसी भी फ़ंक्शन को या तो नई निरंतरता प्रदान करनी होगी या अपना स्वयं का पास करना होगा; सीपीएस-एड फ़ंक्शन से नॉन-सीपीएस फ़ंक्शन में कोई भी कॉल अंतर्निहित निरंतरता का उपयोग करती है। इस प्रकार, फ़ंक्शन स्टैक की पूर्ण अनुपस्थिति सुनिश्चित करने के लिए, एंटीरे प्रोग्राम सीपीएस में होना चाहिए।

हास्केल में सीपीएस (प्रोग्रामिंग लैंग्वेज)

इस अनुभाग में हम फ़ंक्शन लिखेंगे pyth जो पाइथागोरस प्रमेय का उपयोग करके कर्ण की गणना करता है। और pyth ट्रेडिशनल इम्प्लीमेंटेशन फ़ंक्शन इस तरह दिखता है:

pow2 :: Float -> Float
pow2 x = x ** 2

add :: Float -> Float -> Float
add x y = x + y

pyth :: Float -> Float -> Float
pyth x y = sqrt (add (pow2 x) (pow2 y))

ट्रेडिशनल फ़ंक्शन को सीपीएस में परिवर्तन के लिए, हमें इसके सिग्नेचर को परिवर्तन की आवश्यकता है। फ़ंक्शन को फ़ंक्शन प्रकार का और लॉजिक प्राप्त होगा, और इसका रिटर्न प्रकार उस फ़ंक्शन पर निर्भर करता है:

pow2' :: Float -> (Float -> a) -> a
pow2' x cont = cont (x ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' x y cont = cont (x + y)

-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function
-- may be viewed as a higher order function
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' x = \cont -> cont (sqrt x)

pyth' :: Float -> Float -> (Float -> a) -> a
pyth' x y cont = pow2' x (\x2 -> pow2' y (\y2 -> add' x2 y2 (\anb -> sqrt' anb cont)))

सर्वप्रथम हम pyth' फ़ंक्शन में a के वर्ग की गणना करते हैं और एक लैम्ब्डा फ़ंक्शन को निरंतरता के रूप में पास करते हैं जो प्रथम लॉजिक के रूप में a के वर्ग को स्वीकार करेगा। और इसी तरह जब तक हम अपनी गणना के परिणाम तक नहीं पहुंच जाते, इस फ़ंक्शन का परिणाम प्राप्त करने के लिए हम id फ़ंक्शन को अंतिम लॉजिक के रूप में पास कर सकते हैं, जो उसे दिए गए मान pyth' 3 4 id == 5.0 को अपरिवर्तित रिटर्निंग करता है:

एमटीएल लाइब्रेरी, जिसे ग्लासगो हास्केल कंपाइलर के साथ भेजा जाता है, में Control.Monad.Cont. मॉड्यूल है यह मॉड्यूल कॉन्ट प्रकार प्रदान करता है, जो मोनाड और कुछ अन्य उपयोगी कार्यों को प्रयुक्त करता है। निम्नलिखित स्निपेट कंट का उपयोग करके pyth' ' फ़ंक्शन दिखाता है:

pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

इस प्रकार से न केवल सिंटैक्स क्लीनर है, किन्तु यह प्रकार हमें MonadCont m => ((a -> m b) -> m a) -> m a. प्रकार के साथ फ़ंक्शन callCC का उपयोग करने की अनुमति देता है। इस फ़ंक्शन में फ़ंक्शन प्रकार का एक लॉजिक होता है; वह फ़ंक्शन लॉजिक फ़ंक्शन को भी स्वीकार करता है, जो उसके कॉल के पश्चात होने वाली सभी गणनाओं को छोड़ देता है। उदाहरण के लिए, आइए pyth फ़ंक्शन के निष्पादन को तोड़ दें यदि इसका कम से कम एक लॉजिक ऋणात्मक है और शून्य रिटर्निंग कर रहा है:

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do -- $ sign helps to avoid parentheses: a $ b + c == a (b + c)
  when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

ऑब्जेक्टस के रूप में निरंतरता

See also: कॉलबैक (कंप्यूटर प्रोग्रामिंग)

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

function confirmName() {
    fields.name = name;
    framework.Show_dialog_box(fields, confirmNameContinuation);
}

function confirmNameContinuation(fields) {
    name = fields.name;
}

एक समान विचार का उपयोग तब किया जा सकता है जब फ़ंक्शन को किसी डिफरेंट थ्रेड में या किसी डिफरेंट प्रोसेसर पर चलाना होता है। फ्रेमवर्क वर्कर थ्रेड में कॉल किए गए फ़ंक्शन को निष्पादित कर सकता है, फिर वर्कर के परिणामों के साथ मूल थ्रेड में निरंतरता फ़ंक्शन को कॉल कर सकता है। यह जावा 8 (प्रोग्रामिंग लैंग्वेज) में स्विंग (जावा) यूआई फ्रेमवर्क का उपयोग कर रहा है:

void buttonHandler() {
    // This is executing in the Swing UI thread.
    // We can access UI widgets here to get query parameters.
    int parameter = getField();

    new Thread(() => {
        // This code runs in a separate thread.
        // We can do things like access a database or a 
        // blocking resource like the network to get data.
        int result = lookup(parameter);

        javax.swing.SwingUtilities.invokeLater(() => {
            // This code runs in the UI thread and can use
            // the fetched data to fill in UI widgets.
            setField(result);
        });
    }).start();
}

टेल कॉल

सीपीएस में प्रत्येक कॉल टेल कॉल है, और निरंतरता स्पष्ट रूप से पारित की जाती है। टेल कॉल अनुकूलन (टीसीओ) के बिना सीपीएस का उपयोग करने से रिकर्सन के समय न केवल निर्मित निरंतरता संभावित रूप से बढ़ेगी, किन्तु कॉल स्टैक भी बढ़ता है। यह सामान्यतः उन्देसिरबले है, किन्तु इसका उपयोग (योजना इम्प्लीमेंटेशन ) या चिकन स्कीम कंपाइलर अर्थात रोचक विधियों से किया गया है। चूंकि सीपीएस और टीसीओ अंतर्निहित फ़ंक्शन रिटर्न की अवधारणा को समाप्त करते हैं, उनका संयुक्त उपयोग रन-टाइम स्टैक की आवश्यकता को समाप्त कर सकता है। अतः फंक्शनल प्रोग्रामिंग लैंग्वेज के लिए अनेक कंपाइलर और इनटरप्रेटर्शिप नए विधियों से इस क्षमता का उपयोग करते हैं।

उपयोग और इम्प्लीमेंटेशन

निरंतरता पासिंग शैली का उपयोग फंक्शनल लैंग्वेज में निरंतरता को प्रयुक्त करने और प्रवाह ऑपरेटरों को नियंत्रित करने के लिए किया जा सकता है जिसमें प्रथम श्रेणी की निरंतरता की सुविधा नहीं है किन्तु प्रथम श्रेणी के फ़ंक्शन और टेल-कॉल अनुकूलन हैं। टेल-कॉल ऑप्टिमाइज़ेशन के बिना, ट्रैम्पोलिन (कंप्यूटर) जैसी तकनीकों का उपयोग किया जा सकता है, अर्थात लूप का उपयोग करना जो पुनरावृत्त रूप से थंक ( फंक्शनल प्रोग्रामिंग)-रिटर्निंग फ़ंक्शंस को आमंत्रित करता है; प्रथम श्रेणी के फ़ंक्शंस के बिना, ऐसे लूप में टेल कॉल को केवल गोटो में परिवर्तित करना भी संभव है।

इस प्रकार से सीपीएस में कोड लिखना, चूंकि असंभव नहीं है, प्रायः एरर-प्रोन होता है। विभिन्न अनुवाद हैं, जिन्हें सामान्यतः शुद्ध लैम्ब्डा कैलकुलस के या दो-पास रूपांतरण के रूप में परिभाषित किया जाता है, जो प्रत्यक्ष शैली अभिव्यक्तियों को सीपीएस अभिव्यक्तियों में परिवर्तित करता है। चूंकि , ट्रम्पोलिन्ड शैली में लिखना अत्यंत कठिन है; जब उपयोग किया जाता है, तो यह सामान्यतः किसी प्रकार के परिवर्तन का लक्ष्य होता है, जैसे कि कंपाइलर आदि।

एक से अधिक निरंतरता का उपयोग करने वाले कार्यों को विभिन्न नियंत्रण प्रवाह प्रतिमानों को कैप्चर के लिए परिभाषित किया जा सकता है, उदाहरण के लिए (स्कीम (प्रोग्रामिंग लैंग्वेज) में) है:

(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err (list "div by zero!" x y))
                (ok (/ x y))))))

यह ध्यान देने वाली तथ्य है कि सीपीएस परिवर्तन वैचारिक रूप से योनेडा एम्बेडिंग है। यह π-कैलकुलस में लैम्ब्डा कैलकुलस के एम्बेडिंग के समान है।

अन्य क्षेत्रों में उपयोग

कंप्यूटर साइंस के बाहर, सरल अभिव्यक्तियों को सम्मिश्र अभिव्यक्तियों में लिखने की ट्रेडिशनल पद्धति के विकल्प के रूप में सीपीएस अधिक सामान्य रुचि है। उदाहरण के लिए, लिंगविस्टिक शब्दार्थ के अंतर्गत, क्रिस बार्कर और उनके सहयोगियों ने सुझाव दिया है कि सीपीएस का उपयोग करके वाक्यों के अर्थ निर्दिष्ट करने से नेचुरल लैंग्वेज में कुछ घटनाओं की व्याख्या हो सकती है।

गणित में, कंप्यूटर प्रोग्राम और गणितीय प्रमाणों के मध्य करी-हावर्ड समरूपता, निरंतरता-पासिंग शैली अनुवाद को इंटीसनस्टिक लॉजिक में मौलिक लॉजिक के दोहरे-ऋणात्मक एम्बेडिंग की विविधता से संबंधित करती है इंटीसनस्टिक (रचनात्मक) लॉजिक। नियमित दोहरे-ऋणात्मक अनुवाद के विपरीत, जो परमाणु प्रस्तावों p को ((p → ⊥) → ⊥) में माप करता है, निरंतरता पासिंग शैली अंतिम अभिव्यक्ति के प्रकार से ⊥ को प्रतिस्थापित करती है। तदनुसार, उपरोक्त उदाहरण के अनुसार, सीपीएस अभिव्यक्ति की निरंतरता के रूप में पहचान फ़ंक्शन को पारित करके परिणाम प्राप्त किया जाता है।

शास्त्रीय लॉजिक स्वयं प्रोग्राम की निरंतरता में सीधे हेरफेर करने से संबंधित है, जैसा कि स्कीम के कॉल-विथ-वर्तमान-निरंतरता नियंत्रण ऑपरेटर में, टिम ग्रिफिन (निकट से संबंधित सी नियंत्रण ऑपरेटर का उपयोग करके) के कारण अवलोकन है।

यह भी देखें

• टेल प्रत्यावर्तन या ट्रैम्पोलिनिंग के माध्यम से

संदर्भ

• Continuation Passing C (CPC) - programming language for writing concurrent systems, designed and developed by Juliusz Chroboczek and Gabriel Kerneis. github repository
• The construction of a सीपीएस-based compiler for ML is described in: Appel, Andrew W. (1992). Compiling with Continuations. Cambridge University Press. ISBN 978-0-521-41695-5.
• Danvy, Olivier; Filinski, Andrzej (1992). "Representing Control, A Study of the CPS Transformation". Mathematical Structures in Computer Science. 2 (4): 361–391. CiteSeerX 10.1.1.46.84. doi:10.1017/S0960129500001535. S2CID 8790522.
• Chicken Scheme compiler, a Scheme to C compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the generational garbage collector
• Kelsey, Richard A. (March 1995). "A Correspondence between Continuation Passing Style and Static Single Assignment Form". ACM SIGPLAN Notices. 30 (3): 13–22. CiteSeerX 10.1.1.3.6773. doi:10.1145/202530.202532.
• Appel, Andrew W. (April 1998). "SSA is Functional Programming". ACM SIGPLAN Notices. 33 (4): 17–20. CiteSeerX 10.1.1.34.3282. doi:10.1145/278283.278285. S2CID 207227209.
• Danvy, Olivier; Millikin, Kevin; Nielsen, Lasse R. (2007). "On One-Pass CPS Transformations". BRICS Report Series: 24. ISSN 0909-0878. RS-07-6. Retrieved 26 October 2007.
• Dybvig, R. Kent (2003). The Scheme Programming Language. Prentice Hall. p. 64. Direct link: "Section 3.4. Continuation Passing Style".