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

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

जॉन सी. रेनॉल्ड्स निरंतरता की अनेक खोजों का विस्तृत विवरण देते हैं।

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

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

उदाहरण

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

सीपीएस की कुंजी यह याद रखना है कि (ए) प्रत्येक फ़ंक्शन अतिरिक्त तर्क लेता है जिसे इसकी निरंतरता के रूप में जाना जाता है, और (बी) फ़ंक्शन कॉल में प्रत्येक तर्क या तो चर या लैम्ब्डा (प्रोग्रामिंग) होना चाहिए (अधिक जटिल अभिव्यक्ति नहीं)। इसमें अभिव्यक्ति को अंदर-बाहर करने का प्रभाव होता है क्योंकि अभिव्यक्ति के सबसे अंदरूनी हिस्सों का मूल्यांकन पहले किया जाना चाहिए, इस प्रकार सीपीएस मूल्यांकन के क्रम के साथ-साथ नियंत्रण प्रवाह को भी स्पष्ट करता है। प्रत्यक्ष शैली में कोड और संबंधित सीपीएस के कुछ उदाहरण नीचे दिखाई देते हैं। ये उदाहरण योजना (प्रोग्रामिंग भाषा) में लिखे गए हैं; परंपरा के अनुसार निरंतरता फ़ंक्शन को नामित पैरामीटर के रूप में दर्शाया जाता है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& प्रदान किया जाता है जिसमें तीन तर्क होते हैं: बूलियन स्थिति और सशर्त की दो भुजाओं के अनुरूप दो थंक।

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

हास्केल में सीपीएस (प्रोग्रामिंग भाषा)

इस अनुभाग में हम फ़ंक्शन लिखेंगे 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)))

सबसे पहले हम a के वर्ग की गणना करते हैं pyth' फ़ंक्शन और लैम्ब्डा फ़ंक्शन को निरंतरता के रूप में पास करें जो पहले तर्क के रूप में ए के वर्ग को स्वीकार करेगा। और इसी तरह जब तक हम अपनी गणना के नतीजे पर नहीं पहुंच जाते। इस फ़ंक्शन का परिणाम प्राप्त करने के लिए हम पास हो सकते हैं 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

न केवल सिंटैक्स साफ़ हो गया है, बल्कि यह प्रकार हमें फ़ंक्शन का उपयोग करने की अनुमति देता है callCC प्रकार के साथ MonadCont m => ((a -> m b) -> m a) -> m a. इस फ़ंक्शन में फ़ंक्शन प्रकार का तर्क होता है; वह फ़ंक्शन तर्क फ़ंक्शन को भी स्वीकार करता है, जो उसके कॉल के बाद होने वाली सभी गणनाओं को छोड़ देता है। उदाहरण के लिए, आइए इसके निष्पादन को तोड़ें 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: Callback (computer programming)

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

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 CPS-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".