lambda - कॉल/सीसी क्या है?




scheme continuations (7)

FScheme के लिए कॉल / सीसी के विवरण और कार्यान्वयन पर नज़र डालें: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx

मैंने continuations और call/cc की अवधारणा को समझने के लिए कई बार कोशिश की है। हर एक प्रयास विफलता थी। क्या कोई मुझे इन अवधारणाओं को समझा सकता है, आदर्श रूप से विकिपीडिया या अन्य एसओ पदों पर इनके मुकाबले अधिक यथार्थवादी उदाहरणों के साथ।

मेरे पास वेब प्रोग्रामिंग और ओओपी में पृष्ठभूमि है। मैं 6502 असेंबली को भी समझता हूं और एरलांग के साथ एक मामूली रैंडेज-वास था। हालांकि, मैं अपने सिर को कॉल / सीसी के आसपास लपेट नहीं सकता।


इसे सी से तुलना करने के लिए, वर्तमान निरंतरता स्टैक की वर्तमान स्थिति की तरह है। वर्तमान कार्य के परिणामस्वरूप समाप्त होने के लिए सभी फ़ंक्शन प्रतीक्षा कर रहे हैं ताकि वे निष्पादन फिर से शुरू कर सकें। वर्तमान निरंतरता के रूप में कब्जा कर लिया गया चर एक फ़ंक्शन की तरह उपयोग किया जाता है, सिवाय इसके कि यह प्रदत्त मान लेता है और इसे प्रतीक्षा स्टैक पर लौटाता है। यह व्यवहार सी फ़ंक्शन longjmp समान है जहां आप तुरंत स्टैक के निचले भाग पर वापस जा सकते हैं।

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

सी स्टैक और निरंतरता के बीच एक महत्वपूर्ण अंतर यह है कि कार्यक्रम में किसी भी बिंदु पर निरंतरता का उपयोग किया जा सकता है, भले ही ढेर की स्थिति बदल गई हो। इसका मतलब यह है कि आप अनिवार्य रूप से स्टैक के पुराने संस्करणों को पुनर्स्थापित कर सकते हैं और उन्हें दोबारा उपयोग कर सकते हैं, जिससे कुछ अनूठे कार्यक्रम प्रवाह होते हैं।

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

किसी प्रोग्राम की स्थिति को सहेजने और पुनर्स्थापित करने की क्षमता मल्टीथ्रेडिंग के साथ बहुत आम है। वास्तव में, आप निरंतरता का उपयोग करके अपने स्वयं के थ्रेड शेड्यूलर को कार्यान्वित कर सकते हैं, क्योंकि मैंने here वर्णन करने का प्रयास किया here


कल्पना करें कि आपकी स्क्रिप्ट एक वीडियो गेम मंच है। कॉल / सीसी बोनस चरण की तरह है।

जैसे ही आप इसे स्पर्श करते हैं, आपको बोनस चरण में स्थानांतरित किया जाता है (यानी कॉल / सीसी [इस मामले में एफ] के लिए तर्क के रूप में पारित समारोह की परिभाषा)।

बोनस चरण सामान्य चरणों से अलग होते हैं क्योंकि आमतौर पर उनके पास एक तत्व होता है (यानी कॉल / सीसी को पारित समारोह का तर्क) कि यदि आप इसे स्पर्श करते हैं तो आप हार जाते हैं और सामान्य चरण में वापस ले जाते हैं।

इसलिए इससे कोई फर्क नहीं पड़ता कि कई args , जब आप उनमें से एक तक पहुंच जाते हैं। तो हमारा निष्पादन पहुंचता है (arg 42) और इसे योग (+ 42 10) लौटाता है।

ध्यान देने योग्य कुछ टिप्पणियां भी हैं:

  • कॉल / सीसी के साथ सभी कार्यों का उपयोग नहीं किया जा सकता है। चूंकि यह एक निरंतरता (यह एक समारोह है) की अपेक्षा करता है, तो आपके पास इस तरह का एफ नहीं हो सकता है: (define f (lambda (k) (+ k 42)) , क्योंकि आप कोई फ़ंक्शन नहीं sum सकते हैं।
  • इसके अलावा आप नहीं कर सकते (define f (lambda (k) (f 42 10))) क्योंकि निरंतरता केवल एक तर्क की अपेक्षा करता है।
  • आप किसी भी निकास को touching बिना खत्म कर सकते हैं, इस मामले में फ़ंक्शन किसी सामान्य कार्य की तरह आगे बढ़ता है (उदाहरण के लिए (define f (lambda (k) 42) समाप्त होता है और 42 देता है)।

कॉल / सीसी समझने के लिए कई स्तर हैं। सबसे पहले आपको नियमों को समझने की आवश्यकता है और तंत्र कैसे काम करता है। फिर "वास्तविक जीवन" प्रोग्रामिंग में कॉल / सीसी का उपयोग कब और कब किया जाता है इसकी समझ की आवश्यकता है।

पहला स्तर सीपीएस का अध्ययन करके पहुंचा जा सकता है, लेकिन विकल्प हैं।

दूसरे स्तर के लिए मैं फ्राइडमैन द्वारा निम्नलिखित क्लासिक की सिफारिश करता हूं।

डैनियल पी। फ्राइडमैन। "निरंतरता के अनुप्रयोग: आमंत्रित ट्यूटोरियल"। 1 9 88 प्रोग्रामिंग भाषाओं के सिद्धांत (पीओपीएल 88)। जनवरी 1 9 88।


जिस चीज ने मेरी मदद की वह यह विचार है कि एक पारंपरिक भाषा में फ़ंक्शन कॉल के साथ आप किसी भी समय फ़ंक्शन कॉल करने पर निरंतर निरंतर पास करते हैं।

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

अन्य भाषाएं निरंतरता के इस विचार को सामान्यीकृत करती हैं जो आपको स्पष्ट रूप से निर्दिष्ट करने की इजाजत देती है कि फ़ंक्शन कॉल कहां से जारी रखने के बजाय, कोड निष्पादन जारी रखना है।

टिप्पणी के आधार पर संपादित करें:

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


देखो, मुझे इस विषय पर इस निरंतर पासिंग शैली का सर्वोत्तम विवरण मिला है।

यहां उस आलेख की विवरण प्रतिलिपि छीन ली गई है:

लेखक: मारिजन हावरबेके दिनांक: 24 जुलाई 2007

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

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);

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

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});

कल्पना कीजिए कि हमारे पास पूंजीकरण के लिए एक विशाल दस्तावेज़ है। बस एक बार में इसे घुमाने में पांच सेकंड लगते हैं, और ब्राउज़र को पांच सेकंड के लिए फ्रीज करना खराब शैली है। पूंजीगत पाठ के इस सरल संशोधन पर विचार करें (बदसूरत वैश्विक पर ध्यान न दें):

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}

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

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


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

आपकी असेंबली पृष्ठभूमि का जिक्र करते हुए, निरंतरता स्थिति सहेजने और बहाल करने के लिए निर्देश सूचक, पंजीयक, और ढेर संदर्भ (सूचक) के रूप में ऐसे विवरणों को कैप्चर करेगी।

निरंतरता का उपयोग करने का एक अन्य तरीका कई थ्रेड-जैसी इकाइयों के साथ विधि कॉल को प्रतिस्थापित करने के बारे में सोचना होगा जो कि 'क्लासिक' call प्रतिमान के बजाय निरंतर संदर्भों का उपयोग करके एक दूसरे को समानांतर (या तो चल रहा है या निलंबित) नियंत्रण में सह-अस्तित्व में है। वे पैरामीटर पर भरोसा करने के बजाय वैश्विक (साझा) डेटा पर काम करेंगे। इस अर्थ में call तुलना में यह कुछ हद तक लचीला है कि ढेर को नीचे हवा में नहीं जाना है ( calls घोंसला है ), लेकिन नियंत्रण मनमाने ढंग से पास हो सकता है।

इस अवधारणा को ऐसी भाषा में कल्पना करने का प्रयास करते हुए , एक switch(continuation_point) { case point1: ... } कथन के साथ एक बड़ा लूप रखने की कल्पना करें, जहां प्रत्येक case निरंतरता-बचत बिंदु से मेल खाता है, और जहां प्रत्येक के अंदर कोड case continuation_point के मान को बदल सकता है और switch से break करके और लूप में अगले पुनरावृत्ति को जोड़कर उस continuation_point नियंत्रण छोड़ सकता है।

आपके प्रश्न का संदर्भ क्या है? कोई विशेष परिदृश्य जिसमें आप रुचि रखते हैं? कोई विशेष प्रोग्रामिंग भाषा? धागा / फाइबर उदाहरण पर्याप्त से ऊपर है?







callcc