सीमांकित निरंतरता

प्रोग्रामिंग लैंग्वेजेज में, एक सीमांकित निरंतरता, रचना योग्य निरंतरता या आंशिक निरंतरता, एक स्टैक फ़्रेम का एक टुकड़ा है जिसे एक फ़ंक्शन में पुन: एकीकृत किया गया है। नियमित निरंतरता के विपरीत, सीमांकित निरंतरता एक मान लौटाती है, और इस प्रकार इसका पुन: उपयोग और रचना की जा सकती है। नियंत्रण सीमांकक, सीमांकित निरंतरता का आधार, 1988 में मैथ्यू फेलिसेन द्वारा पेश किया गया था हालाँकि रचना योग्य और सीमांकित निरंतरता के प्रारंभिक संकेत कैरोलिन टैल्कॉट के स्टैनफोर्ड 1984 शोध प्रबंध, फेलिसेन और अन्य में पाए जा सकते हैं। फेलिसेन का 1987 का शोध प्रबंध, और कार्यात्मक बैक ट्रैकिंग के लिए एल्गोरिदम, उदाहरण के लिए, पैटर्न मिलान के लिए, पार्सिंग के लिए, बीजगणितीय तर्क कार्यात्मक प्रोग्रामिंग लैंग्वेज में, और प्रोलॉग की कार्यात्मक कार्यान्वयन में जहां विफलता निरंतरता को अक्सर अंतर्निहित रखा जाता है और सफलता निरंतरता के लिए होने का कारण है कि यह रचना योग्य है।

इतिहास

सीमांकित निरंतरताएँ पहली बार 1988 में फेलिसेन द्वारा प्रस्तुत की गईंएक ऑपरेटर के साथ बुलाया गया ${\mathcal {F}}$, पहली बार 1987 में एक तकनीकी रिपोर्ट में पेश किया गया था,शीघ्र निर्माण के साथ $\#$. ऑपरेटर को नियंत्रण ऑपरेटरों के सामान्यीकरण के रूप में डिज़ाइन किया गया था जिसका वर्णन साहित्य में किया गया था call/cc स्कीम (प्रोग्रामिंग भाषा) से, ISWIM के जे ऑपरेटर, जॉन सी. रेनॉल्ड्स' escape ऑपरेटर, और अन्य। इसके बाद, प्रोग्रामिंग भाषाओं के अनुसंधान समुदाय द्वारा कई प्रतिस्पर्धी सीमांकित नियंत्रण ऑपरेटरों का आविष्कार किया गया prompt और control, shift और reset,cupto, fcontrol, और दूसरे।

उदाहरण

शोध साहित्य में सीमांकित निरंतरता के लिए विभिन्न ऑपरेटरों का प्रस्ताव किया गया है।

एक स्वतंत्र प्रस्तावनिरंतरता-पासिंग शैली (सीपीएस) पर आधारित है - अर्थात, निरंतरता फ़्रेम पर नहीं - और दो नियंत्रण ऑपरेटर प्रदान करता है, shift और reset, जो गतिशील सीमांकित निरंतरताओं के बजाय स्थैतिक को जन्म देता है।

reset e> ऑपरेटर निरंतरता के लिए सीमा निर्धारित करता है जबकि shift ऑपरेटर वर्तमान निरंतरता को अंतरतम परिक्षेत्र तक पकड़ता है या उसका पुनरीक्षण करता है reset. उदाहरण के लिए, स्कीम (प्रोग्रामिंग भाषा) में निम्नलिखित स्निपेट पर विचार करें:  

(* 2 (reset (+ 1 (shift k (k 5)))))

reset e> उस निरंतरता का परिसीमन करता है shift कैप्चर (नाम से) k इस उदाहरण में)। जब यह स्निपेट निष्पादित किया जाता है, तो इसका उपयोग होता है shift बांध देंगे k निरंतरता के लिए (+ 1 []) कहाँ [] गणना के उस भाग का प्रतिनिधित्व करता है जिसे किसी मान से भरा जाना है। यह निरंतरता सीधे उस कोड से मेल खाती है जो इसके चारों ओर है shift तक reset. क्योंकि शिफ्ट का शरीर (यानी, (k 5)) तुरंत निरंतरता का आह्वान करता है, यह कोड निम्नलिखित के बराबर है:  

(* 2 (+ 1 5))

सामान्य तौर पर, ये ऑपरेटर, उदाहरण के लिए, कैप्चर की गई निरंतरता को वापस करके अधिक दिलचस्प व्यवहार को एनकोड कर सकते हैं k एक मूल्य या आह्वान के रूप में k कई बार। shift ई> ऑपरेटर कैप्चर की गई निरंतरता को पास करता है k इसके मुख्य भाग में कोड के लिए, जो या तो इसे लागू कर सकता है, इसके परिणामस्वरूप इसे उत्पन्न कर सकता है, या इसे पूरी तरह से अनदेखा कर सकता है। चाहे उसका परिणाम कुछ भी हो shift उत्पादन अंतरतम को प्रदान किया जाता है reset, बीच में निरंतरता को त्यागना reset और shift. हालाँकि, यदि निरंतरता लागू की जाती है, तो यह प्रभावी रूप से वापस लौटने के बाद निरंतरता को पुनः स्थापित करता है reset. जब सारा हिसाब भीतर reset पूरा हो गया है, परिणाम सीमांकित निरंतरता द्वारा लौटाया जाता है। उदाहरण के लिए, इस योजना (प्रोग्रामिंग भाषा) कोड में:

 (reset (* 2 (shift k CODE)))

जब कभी भी CODE का आह्वान (k N), (* 2 N) मूल्यांकन कर लौटाया जाता है।

यह निम्नलिखित के बराबर है:

  (let ((k (lambda (x) (* 2 x)))) CODE)

इसके अलावा, एक बार पूरी गणना भीतर shift पूरा हो गया है, निरंतरता को छोड़ दिया गया है, और निष्पादन बाहर पुनः आरंभ होता है reset. इसलिए,

 (reset (* 2 (shift k (k (k 4)))))

का आह्वान (k 4) पहले (जो 8 लौटाता है), और फिर (k 8) (जो 16 लौटाता है)। इस बिंदु पर, shift अभिव्यक्ति समाप्त हो गई है, और शेष reset अभिव्यक्ति को त्याग दिया गया है. इसलिए, अंतिम परिणाम 16 है।

वह सब कुछ जो बाहर घटित होता है reset अभिव्यक्ति छिपी हुई है, यानी नियंत्रण हस्तांतरण से प्रभावित नहीं है। उदाहरण के लिए, यह 17 लौटाता है:

 (+ 1 (reset (* 2 (shift k (k (k 4))))))

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

आइए एक अधिक जटिल उदाहरण पर नजर डालें। होने देना null खाली सूची बनें:

 (reset
   (begin
     (shift k (cons 1 (k (void)))) ;; (1)
     null))

संदर्भ द्वारा कब्जा कर लिया गया shift है (begin [*] null), कहाँ [*] वह छेद है जहाँ kका पैरामीटर इंजेक्ट किया जाएगा. की पहली कॉल k अंदर shift इस संदर्भ का मूल्यांकन करता है (void) = #<void> छेद को बदलना, तो का मूल्य (k (void)) है (begin #<void> null) = null. का शरीर shift, अर्थात् (cons 1 null) = (1), का समग्र मूल्य बन जाता है reset अंतिम परिणाम के रूप में अभिव्यक्ति.

इस उदाहरण को और अधिक जटिल बनाते हुए, एक पंक्ति जोड़ें:

 (reset
   (begin
     (shift k (cons 1 (k (void))))
     (shift k (cons 2 (k (void))))
     null))

अगर हम सबसे पहले टिप्पणी करें shift, हम पहले से ही परिणाम जानते हैं, यह है (2); इसलिए हम इस प्रकार अभिव्यक्ति को फिर से लिख सकते हैं:

 (reset
   (begin
     (shift k (cons 1 (k (void))))
     (list 2)))

यह काफी परिचित है, और इसे इस रूप में फिर से लिखा जा सकता है (cons 1 (list 2)), वह है, (list 1 2).

हम परिभाषित कर सकते हैं yield इस ट्रिक का उपयोग करें:

(परिभाषित करें (उपज x) (शिफ्ट k (cons x (k (void)))))

और सूचियों के निर्माण में इसका उपयोग करें:

 (reset (begin
          (yield 1)
          (yield 2)
          (yield 3)
          null))    ;; (list 1 2 3)

यदि हम प्रतिस्थापित करते हैं cons साथ stream-cons, हम आलसी स्ट्रीम बना सकते हैं:

  (define (stream-yield x) (shift k (stream-cons x (k (void)))))

  (define lazy-example
    (reset (begin
            (stream-yield 1)
            (stream-yield 2)
            (stream-yield 3)
            stream-null)))

हम इसे सामान्यीकृत कर सकते हैं और सूचियों को एक झटके में स्ट्रीम में परिवर्तित कर सकते हैं:

 (define (list->stream xs)
   (reset (begin
            (for-each stream-yield xs)
            stream-null)))

नीचे दिए गए अधिक जटिल उदाहरण में निरंतरता को लैम्ब्डा के शरीर में सुरक्षित रूप से लपेटा जा सकता है, और इस प्रकार उपयोग किया जा सकता है:

 (define (for-each->stream-maker for-each) 
   (lambda (collection) 
     (reset (begin 
              (for-each (lambda (element) 
                          (shift k 
                            (stream-cons element (k 'ignored)))) 
                        collection) 
              stream-null))))

के बीच का भाग reset और shift जैसे नियंत्रण कार्य शामिल हैं lambda और for-each; लैम्ब्डा का उपयोग करके इसे दोबारा लिखना असंभव है.

सीमांकित निरंतरताएँ भाषाविज्ञान में भी उपयोगी हैं: विवरण के लिए निरंतरता#भाषाविज्ञान देखें।

बाहरी संबंध

• Composable continuations tutorial at SchemeWiki
• Delimited continuations in operating systems, by Oleg Kiselyov and Chung-chieh Shan
• Native delimited continuations in (byte-code and native-code) OCaml
• Shift/reset для самых маленьких (in Russian)
• Some nice papers on delimited continuations and first-class macros