सीमांकित निरंतरता: Difference between revisions
No edit summary |
No edit summary |
||
Line 44: | Line 44: | ||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(reset (* 2 (shift k (k (k 4)))))</syntaxhighlight> | (reset (* 2 (shift k (k (k 4)))))</syntaxhighlight> | ||
पहले <code>(k 4)</code> को आमंत्रित करता है (जो 8 लौटाता है), और फिर <code>(k 8)</code> (जो 16 लौटाता है)। इस बिंदु पर, <code>शिफ्ट</code> अभिव्यक्ति समाप्त हो गई है, और शेष <code>रीसेट</code> अभिव्यक्ति को छोड़ दिया गया है। इसलिए, अंतिम परिणाम 16 है। | |||
<code>रीसेट</code> अभिव्यक्ति के बाहर जो कुछ भी होता है वह छिपा हुआ होता है, यानी नियंत्रण हस्तांतरण से प्रभावित नहीं होता है। उदाहरण के लिए, यह 17 लौटाता है: | |||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(+ 1 (reset (* 2 (shift k (k (k 4))))))</syntaxhighlight> | (+ 1 (reset (* 2 (shift k (k (k 4))))))</syntaxhighlight> | ||
सीमांकित निरंतरताओं का वर्णन सबसे पहले फ़ेलिसेन एट अल द्वारा स्वतंत्र रूप से किया गया था।<ref name="felleisen 87 tr"/>और जॉनसन | सीमांकित निरंतरताओं का वर्णन सबसे पहले फ़ेलिसेन एट अल द्वारा स्वतंत्र रूप से किया गया था।<ref name="felleisen 87 tr"/> और जॉनसन<ref name="johnson 87 siit">{{cite conference|author=Johnson, Gregory F.|title=GL: a denotational testbed with continuations and partial continuations|pages=218–225|date=June 1987|book-title=Proc. SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques}}</ref> तब से उनका उपयोग बड़ी संख्या में डोमेन में किया गया है, विशेष रूप से नए नियंत्रण प्रवाह को परिभाषित करने के लिए है।<ref name="queinnec survey">{{cite journal|last=Queinnec|first=Christian|publisher=[[École Polytechnique]] and [[INRIA]]-Rocquencourt|title=उच्च स्तरीय नियंत्रण ऑपरेटरों की एक लाइब्रेरी|journal=Lisp Pointers, ACM SIGPLAN Special Interest Publ. On Lisp|citeseerx = 10.1.1.29.4790|date=April 1994|volume=6|pages=11–26}}</ref> | ||
जटिल उदाहरण : | |||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(reset | (reset | ||
Line 57: | Line 57: | ||
(shift k (cons 1 (k (void)))) ;; (1) | (shift k (cons 1 (k (void)))) ;; (1) | ||
null))</syntaxhighlight> | null))</syntaxhighlight> | ||
<code>शिफ्ट</code> द्वारा कैप्चर किया गया संदर्भ<code>(begin [*] null)</code> है, जहां <code>[*]</code> वह छेद है जहाँ <code>k</code>का पैरामीटर इंजेक्ट किया जाएगा है। <code>shift</code> के अंदर <code>k</code> इस संदर्भ का मूल्यांकन करता है <code>(void)</code> = <code>#<void></code> छेद को प्रतिस्थापित करने के साथ मूल्यांकन करती है, इसलिए<code>(k (void))</code> का मान<code>(begin #<void> null)</code> = <code>null है।</code> <code>shift</code> का मुख्य भाग, अर्थात् <code>(cons 1 null)</code> = <code>(1)</code>, अंतिम परिणाम के रूप में <code>reset</code> अभिव्यक्ति का समग्र मूल्य बन जाता है। | |||
इस उदाहरण को और अधिक जटिल बनाते | जो इस उदाहरण को और अधिक जटिल बनाते है: | ||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(reset | (reset | ||
Line 66: | Line 66: | ||
(shift k (cons 2 (k (void)))) | (shift k (cons 2 (k (void)))) | ||
null))</syntaxhighlight> | null))</syntaxhighlight> | ||
यदि हम सबसे पहले टिप्पणी करें करते हैं, तो हम पहले से ही परिणाम जानते हैं, यह है <code>(2)</code>; इसलिए हम इस प्रकार अभिव्यक्ति को फिर से लिख सकते हैं: | |||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(reset | (reset | ||
Line 74: | Line 74: | ||
यह काफी परिचित है, और इसे इस रूप में फिर से लिखा जा सकता है <code>(cons 1 (list 2))</code>, वह है, <code>(list 1 2)</code>. | यह काफी परिचित है, और इसे इस रूप में फिर से लिखा जा सकता है <code>(cons 1 (list 2))</code>, वह है, <code>(list 1 2)</code>. | ||
हम | हम इस ट्रिक का उपयोग करके<code>yield</code> को परिभाषित कर सकते हैं: | ||
( | (define (yield x) (shift k (cons x (k (void))))) | ||
और सूचियों के निर्माण में इसका उपयोग करें: | और सूचियों के निर्माण में इसका उपयोग करें: | ||
Line 85: | Line 85: | ||
(yield 3) | (yield 3) | ||
null)) ;; (list 1 2 3)</syntaxhighlight> | null)) ;; (list 1 2 3)</syntaxhighlight> | ||
यदि हम | यदि हम <code>cons</code> को <code>stream-cons</code> से प्रतिस्थापित करते हैं, तो हम आलसी स्ट्रीम बना सकते हैं: | ||
<syntaxhighlight lang="scheme"> | <syntaxhighlight lang="scheme"> | ||
(define (stream-yield x) (shift k (stream-cons x (k (void))))) | (define (stream-yield x) (shift k (stream-cons x (k (void))))) | ||
Line 114: | Line 114: | ||
stream-null)))) | stream-null)))) | ||
</syntaxhighlight> | </syntaxhighlight> | ||
<code>reset</code> और <code>shift</code> के बीच के हिस्से में <code>lambda</code> और <code>for-each</code> के लिए नियंत्रण कार्य शामिल हैं; लैम्ब्डा का उपयोग करके इसे दोबारा लिखना असंभव है{{why?|date=August 2012}}. | |||
सीमांकित निरंतरताएँ | [[भाषाशास्त्र]] में सीमांकित निरंतरताएँ भी उपयोगी हैं: विवरण के लिए [[भाषाशास्त्र में निरंतरताएँ]] देखें। | ||
== संदर्भ == | == संदर्भ == |
Revision as of 13:33, 18 July 2023
प्रोग्रामिंग लैंग्वेजेज में, एक सीमांकित निरंतरता, रचना योग्य निरंतरता या आंशिक निरंतरता, एक स्टैक फ़्रेम का एक टुकड़ा है जिसे एक फ़ंक्शन में पुन: एकीकृत किया गया है। नियमित निरंतरता के विपरीत, सीमांकित निरंतरता एक मान लौटाती है, और इस प्रकार इसका पुन: उपयोग और रचना की जा सकती है। नियंत्रण सीमांकक, सीमांकित निरंतरता का आधार, 1988 में मैथ्यू फेलिसेन द्वारा पेश किया गया था[1] हालाँकि रचना योग्य और सीमांकित निरंतरता के प्रारंभिक संकेत कैरोलिन टैल्कॉट के स्टैनफोर्ड 1984 शोध प्रबंध, फेलिसेन और अन्य में पाए जा सकते हैं।[2] फेलिसेन का 1987 का शोध प्रबंध,[3] और कार्यात्मक बैक ट्रैकिंग के लिए एल्गोरिदम, उदाहरण के लिए, पैटर्न मिलान के लिए, पार्सिंग के लिए, बीजगणितीय तर्क कार्यात्मक प्रोग्रामिंग लैंग्वेज में, और प्रोलॉग की कार्यात्मक कार्यान्वयन में जहां विफलता निरंतरता को अक्सर अंतर्निहित रखा जाता है और सफलता निरंतरता के लिए होने का कारण है कि यह रचना योग्य है।
इतिहास
सीमांकित निरंतरताओं को पहली बार 1988 में फेलिसेन द्वारा एक ऑपरेटर के साथ प्रस्तुत किया गया था,[1] पहली बार 1987 में एक तकनीकी रिपोर्ट में पेश किया गया था,[2] एक त्वरित निर्माण के साथ ऑपरेटर को उन नियंत्रण ऑपरेटरों के सामान्यीकरण के लिए डिज़ाइन किया गया था जिनका वर्णन साहित्य में किया गया था जैसे स्कीम से call/cc
, ISWIM के J ऑपरेटर, जॉन सी. रेनॉल्ड्स' escape
ऑपरेटर, और अन्य है। इसके बाद, प्रोग्रामिंग भाषाओं के अनुसंधान समुदाय द्वारा कई प्रतिस्पर्धी सीमांकित नियंत्रण ऑपरेटरों का आविष्कार किया गया prompt
और control
,[4] shift
और reset
,[5][6]cupto
,[7] fcontrol
, और दूसरे अन्य है।
उदाहरण
शोध साहित्य में सीमांकित निरंतरता के लिए विभिन्न ऑपरेटरों का प्रस्ताव किया गया है।[8]
एक स्वतंत्र प्रस्ताव[5]निरंतरता-पासिंग शैली (सीपीएस) पर आधारित है - अर्थात, निरंतरता फ़्रेम पर नहीं - और दो नियंत्रण ऑपरेटर प्रदान करता है, shift
और reset
, जो गतिशील सीमांकित निरंतरताओं के बजाय स्थैतिक को जन्म देता है।[9]
रीसेट
ऑपरेटर निरंतरता के लिए सीमा निर्धारित करता है जबकिshift
ऑपरेटर वर्तमान निरंतरता को अंतरतम परिक्षेत्र तक पकड़ता है या उसका पुनरीक्षण करता हैreset
. उदाहरण के लिए, निम्नलिखित स्निपेट पर विचार करें:
(* 2 (reset (+ 1 (shift k (k 5)))))
रीसेट
उस निरंतरता का परिसीमन करता है जोशिफ्ट
कैप्चर करता है। जब यह स्निपेट निष्पादित किया जाता है, तो इसका उपयोग होता है तोशिफ्ट
का उपयोगk
को निरंतरता(+ 1 [])
से बांध देगा जहां[]
गणना के उस हिस्से का प्रतिनिधित्व करता है जिसे एक मूल्य से भरा जाना है। यह निरंतरता सीधे उस कोड से मेल खाती है जो रीसेट तक शिफ्ट को घेरता है। क्योंकि शिफ्ट का मुख्य भाग (यानी, (k 5)) तुरंत निरंतरता का आह्वान करता है, यह कोड निम्नलिखित के बराबर है:
(* 2 (+ 1 5))
सामान्य तौर पर, ये ऑपरेटर अधिक दिलचस्प व्यवहार को एनकोड कर सकते हैं, उदाहरण के लिए, कैप्चर की गई निरंतरता k
को एक मान के रूप में वापस करना या k
को कई बार लागू करना है। शिफ्ट ऑपरेटर कैप्चर की गई निरंतरता को पास करता है k
इसके मुख्य भाग में कोड के लिए, जो या तो इसे लागू कर सकता है, इसके परिणामस्वरूप इसे उत्पन्न कर सकता है, या इसे पूरी तरह से अनदेखा कर सकता है। जो भी परिणाम शिफ्ट उत्पन्न करता है वह रीसेट और शिफ्ट के बीच की निरंतरता को छोड़कर, अंतरतम रीसेट को प्रदान किया जाता है। हालाँकि, यदि निरंतरता लागू की जाती है, तो यह रीसेट पर लौटने के बाद निरंतरता को प्रभावी ढंग से पुनः स्थापित करता है। जब रीसेट के भीतर संपूर्ण गणना पूरी हो जाती है, तो परिणाम सीमांकित निरंतरता द्वारा लौटाया जाता है।[10]
(reset (* 2 (shift k CODE)))
जब कभी भी CODE
(k N) को आमंत्रित करता है,
* 2 N)
का मूल्यांकन किया जाता है और वापस कर दिया जाता है।
यह निम्नलिखित के बराबर है:
(let ((k (lambda (x) (* 2 x)))) CODE)
इसके अलावा, एक बार शिफ्ट के भीतर पूरी गणना पूरी हो जाने के बाद, निरंतरता को हटा दिया जाता है, और निष्पादन रीसेट पुनः आरंभ होता है।
(reset (* 2 (shift k (k (k 4)))))
पहले (k 4)
को आमंत्रित करता है (जो 8 लौटाता है), और फिर (k 8)
(जो 16 लौटाता है)। इस बिंदु पर, शिफ्ट
अभिव्यक्ति समाप्त हो गई है, और शेष रीसेट
अभिव्यक्ति को छोड़ दिया गया है। इसलिए, अंतिम परिणाम 16 है।
रीसेट
अभिव्यक्ति के बाहर जो कुछ भी होता है वह छिपा हुआ होता है, यानी नियंत्रण हस्तांतरण से प्रभावित नहीं होता है। उदाहरण के लिए, यह 17 लौटाता है:
(+ 1 (reset (* 2 (shift k (k (k 4))))))
सीमांकित निरंतरताओं का वर्णन सबसे पहले फ़ेलिसेन एट अल द्वारा स्वतंत्र रूप से किया गया था।[2] और जॉनसन[11] तब से उनका उपयोग बड़ी संख्या में डोमेन में किया गया है, विशेष रूप से नए नियंत्रण प्रवाह को परिभाषित करने के लिए है।[12]
जटिल उदाहरण :
(reset
(begin
(shift k (cons 1 (k (void)))) ;; (1)
null))
शिफ्ट
द्वारा कैप्चर किया गया संदर्भ(begin [*] null)
है, जहां [*]
वह छेद है जहाँ k
का पैरामीटर इंजेक्ट किया जाएगा है। shift
के अंदर k
इस संदर्भ का मूल्यांकन करता है (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))
यदि हम सबसे पहले टिप्पणी करें करते हैं, तो हम पहले से ही परिणाम जानते हैं, यह है (2)
; इसलिए हम इस प्रकार अभिव्यक्ति को फिर से लिख सकते हैं:
(reset
(begin
(shift k (cons 1 (k (void))))
(list 2)))
यह काफी परिचित है, और इसे इस रूप में फिर से लिखा जा सकता है (cons 1 (list 2))
, वह है, (list 1 2)
.
हम इस ट्रिक का उपयोग करकेyield
को परिभाषित कर सकते हैं:
(define (yield x) (shift 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
के लिए नियंत्रण कार्य शामिल हैं; लैम्ब्डा का उपयोग करके इसे दोबारा लिखना असंभव है[why?].
भाषाशास्त्र में सीमांकित निरंतरताएँ भी उपयोगी हैं: विवरण के लिए भाषाशास्त्र में निरंतरताएँ देखें।
संदर्भ
- ↑ 1.0 1.1 Felleisen, Matthias (1988). "प्रथम श्रेणी के संकेतों का सिद्धांत और व्यवहार". Principles of Programming Languages. pp. 180–190. doi:10.1145/73560.73576. ISBN 0-89791-252-7. S2CID 16705769.
- ↑ 2.0 2.1 2.2 Felleisen, Matthias; Friedman, Daniel P.; Duba, Bruce; Marrill, John (February 1987). निरंतरता से परे (PDF) (Technical report). Computer Science Department, Indiana University. 216.
- ↑ Felleisen, Matthias (1987). The Calculi of Lambda-v-CS Conversion: A Syntactic Theory of Control and State in Imperative Higher-Order Programming Languages (PDF) (Thesis).
- ↑ Sitaram, Dorai; Felleisen, Matthias (1990). "सीमांकक और उनके पदानुक्रम को नियंत्रित करें" (PDF). Lisp and Symbolic Computation. 3: 67–99. doi:10.1007/BF01806126. S2CID 31430221.
- ↑ 5.0 5.1 Danvy, Olivier; Filinski, Andrzej (1990). "सार नियंत्रण". LISP and Functional Programming. pp. 151–160. doi:10.1145/91556.91622. ISBN 0-89791-368-X. S2CID 6426191.
- ↑ Danvy, Olivier (2006). डेटा ऑब्जेक्ट के रूप में प्रोग्राम के लिए एक विश्लेषणात्मक दृष्टिकोण (Thesis). doi:10.7146/aul.214.152.
- ↑ Rémy, Didier; Gunter, Carl; Riecke, Jon G. (1995). "एमएल जैसी भाषाओं में अपवादों और नियंत्रण का सामान्यीकरण". Functional Programming Language and Computer Architecture.
- ↑ उदाहरण के लिए, द्वारा प्रस्तावित ऑपरेटरों को देखें
racket/control
रैकेट (प्रोग्रामिंग भाषा) लाइब्रेरी [1]; निम्नलिखित उदाहरणों का उपयोग करके रैकेट में चलाया जा सकता है(require racket/control)
- ↑ Biernacki, Dariusz; Danvy, Olivier; Shan, Chung-chieh (2006). "On the Static and Dynamic Extents of Delimited Continuations". Science of Computer Programming. 60 (3): 274–297.
- ↑ Gasbichler, Martin; Sperber, Michael (2002). International Conference on Functional Programming. CiteSeerX 10.1.1.11.3425.
- ↑ Johnson, Gregory F. (June 1987). "GL: a denotational testbed with continuations and partial continuations". Proc. SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques. pp. 218–225.
- ↑ Queinnec, Christian (April 1994). "उच्च स्तरीय नियंत्रण ऑपरेटरों की एक लाइब्रेरी". Lisp Pointers, ACM SIGPLAN Special Interest Publ. On Lisp. École Polytechnique and INRIA-Rocquencourt. 6: 11–26. CiteSeerX 10.1.1.29.4790.
बाहरी संबंध
- 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