निरंतरता को कैसे कार्यान्वित करें?

मैं सी में लिखे गए स्कीम दुभाषिया पर काम कर रहा हूं। वर्तमान में यह सी रनटाइम स्टैक का उपयोग अपने स्वयं के ढेर के रूप में करता है, जो निरंतर कार्यान्वयन के साथ मामूली समस्या पेश कर रहा है। मेरा वर्तमान समाधान ढेर में सी स्टैक की मैन्युअल प्रतिलिपि है, फिर आवश्यक होने पर इसे वापस कॉपी करना। मानक सी नहीं होने के अलावा, यह समाधान शायद ही आदर्श है।

सी में योजना के लिए निरंतरता को लागू करने का सबसे आसान तरीका क्या है?

0
ro fr bn

12 उत्तर

मुझे एक लेख पढ़ना याद है जो आपकी मदद कर सकता है: एमटीए पर चेनी </ए> :-)

योजना के कुछ कार्यान्वयन जिन्हें मैं जानता हूं, जैसे एसआईएससी , ढेर पर उनके कॉल फ्रेम आवंटित करते हैं।

@ollie: यदि आपके सभी कॉल फ्रेम ढेर पर हैं तो आपको उछालने की आवश्यकता नहीं है। प्रदर्शन में एक व्यापार है, ज़ाहिर है: उछालने का समय, ढेर पर सभी फ्रेम आवंटित करने के लिए ओवरहेड बनाम। शायद यह दुभाषिया में एक ट्यूनेबल रनटाइम पैरामीटर होना चाहिए। :-P

0
जोड़ा

इसके बजाए एक स्पष्ट ढेर का प्रयोग करें।

0
जोड़ा
-1: एक स्पष्ट ढेर क्या है? एक ढेर-आवंटित डेटा संरचना एक ढेर मॉडलिंग? एक ढेर आवंटित डेटा संरचना ढेर उपयोग के इतिहास मॉडलिंग? सवाल के लिए प्रासंगिकता?
जोड़ा लेखक Charles Stewart, स्रोत

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

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

0
जोड़ा
लेकिन, बंद करने का समर्थन करने के लिए, क्या आप सिर्फ लैम्ब्डा उठाना नहीं कर सकते?
जोड़ा लेखक apg, स्रोत

निरंतरता में संदर्भ स्विच के बिंदु पर मूल रूप से स्टैक और सीपीयू रजिस्टरों की सहेजी गई स्थिति शामिल होती है। स्विचिंग करते समय कम से कम आपको पूरे ढेर को ढेर में कॉपी करने की ज़रूरत नहीं है, आप केवल स्टैक पॉइंटर को रीडायरेक्ट कर सकते हैं।

निरंतर फाइबर का उपयोग करके कार्यान्वित किया जाता है। http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 । सावधान encapsulation की आवश्यकता केवल एक चीजें पैरामीटर गुजरने और मूल्य वापस कर रहे हैं।

विंडोज फाइबर में कॉल के CreateFiber / SwitchToFiber परिवार का उपयोग करके किया जाता है। Posix-compliant सिस्टम में इसे makecontext / swapcontext के साथ किया जा सकता है।

boost :: coroutine में C ++ के लिए कोरआउट का एक कार्यान्वयन कार्यान्वयन है जो कार्यान्वयन के लिए संदर्भ बिंदु के रूप में कार्य कर सकता है।

0
जोड़ा
trivially कार्यान्वित ... सावधान encapsulation की जरूरत है - इस अनुच्छेद में एक निश्चित मात्रा में तनाव है। यह उत्तर कुछ कोड के लिंक के साथ सुधार किया जाएगा।
जोड़ा लेखक Charles Stewart, स्रोत

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

स्टेक पर स्कीमेटी स्टेक मैपिंग के लिए सबसे अच्छा वर्तमान दृष्टिकोण ट्रैम्पोलिन का उपयोग कर रहा है: गैर-सी-जैसे कॉल को संभालने के लिए अनिवार्य रूप से अतिरिक्त आधारभूत संरचना और प्रक्रियाओं से बाहर निकलना। Trampolined Style (ps) देखें।

इन दोनों विचारों को चित्रित करने वाले कुछ कोड हैं।

0
जोड़ा

ऐसा लगता है कि अब तक डिबविग की थीसिस अनियमित है। यह पढ़ने में खुशी है। ढेर आधारित मॉडल लागू करने के लिए सबसे आसान है, लेकिन ढेर आधारित है अधिक कुशल है। स्ट्रिंग आधारित मॉडल को अनदेखा करें।

R. Kent Dybvig. "Three Implementation Models for Scheme". http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Also check out the implementation papers on ReadScheme.org. http://library.readscheme.org/page8.html

सार इस प्रकार है:

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

     

ढेर-आधारित मॉडल ए में कई महत्वपूर्ण डेटा संरचनाओं को आवंटित करता है   ढेर, वास्तविक पैरामीटर सूचियों, बाध्यकारी वातावरण, और कॉल सहित   फ्रेम।

     

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

     

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

     

स्टैक-आधारित मॉडल तत्काल व्यावहारिक सिद्धांत का है; यह है   मॉडल के चेज़ स्कीम सिस्टम द्वारा उपयोग किया जाने वाला मॉडल, एक उच्च प्रदर्शन   योजना का कार्यान्वयन स्ट्रिंग-आधारित मॉडल के लिए उपयोगी होगा   एफएफपी मशीन पर एफएफपी के उच्च स्तरीय विकल्प के रूप में योजना प्रदान करना   एक बार मशीन को एहसास हो जाता है।

0
जोड़ा

यदि आप खरोंच से शुरू कर रहे हैं, तो आपको वास्तव में निरंतर पासिंग स्टाइल (सीपीएस) परिवर्तन में देखना चाहिए।

अच्छे स्रोतों में "छोटे टुकड़ों में LISP" और 90 मिनट की प्रस्तुति में मार्क फीले की योजना

0
जोड़ा
क्विनेक की पुस्तक लिस्प इन इन छोटे टुकड़े है उपलब्ध है (कम से कम अपने फ्रेंच संस्करण पैराकाम्पस से)
जोड़ा लेखक Basile Starynkevitch, स्रोत

As soegaard pointed out, the main reference remains this one

विचार यह है कि, एक निरंतरता एक बंद है जो इसके मूल्यांकन नियंत्रण ढेर रखती है। call / cc का उपयोग करके निरंतरता बनाए जाने के पल से evalution जारी रखने के लिए नियंत्रण ढेर की आवश्यकता है।

अक्सर निरंतरता का आह्वान करने से निष्पादन का लंबा समय लगता है और स्मृति को डुप्लिकेट किए गए ढेर के साथ भर देता है। मैंने साबित करने के लिए यह बेवकूफ कोड लिखा है कि, मिट-स्कीम में यह योजना को दुर्घटनाग्रस्त कर देता है,

कोड पहले 1000 नंबर <�कोड> 1 + 2 + 3 + ... + 1000 को प्रस्तुत करता है।

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

यदि आप 1000 से 100 000 तक स्विच करते हैं तो कोड 2 सेकंड व्यतीत करेगा, और यदि आप इनपुट नंबर बढ़ाते हैं तो यह क्रैश हो जाएगा।

0
जोड़ा

परंपरागत तरीका setjmp और longjmp का उपयोग करना है, हालांकि चेतावनी हैं।

Here's a reasonably good explanation

0
जोड़ा

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

स्टैक कॉपी करना जटिल नहीं है और प्रदर्शन में सुधार के लिए कई अच्छी तरह से समझी जाने वाली तकनीकें उपलब्ध हैं। ढेर-आवंटित फ्रेम का उपयोग करना काफी सरल है, लेकिन आप "सामान्य" स्थिति के लिए ओवरहेड बनाने का एक व्यापारिक तरीका बनाते हैं जहां आप स्पष्ट निरंतरता का उपयोग नहीं कर रहे हैं।

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

0
जोड़ा

जिन उदाहरणों पर आप देख सकते हैं वे हैं: चिकन (एक योजना कार्यान्वयन, सी में लिखा गया है निरंतर समर्थन); पॉल ग्राहम के लिस्प पर - जहां वह आम लिस्प में निरंतरता के सबसेट को लागू करने के लिए एक सीपीएस ट्रांसफार्मर बनाता है; और वेबलॉक्स - एक निरंतर आधारित वेब ढांचा, जो निरंतरता के सीमित रूप को भी लागू करता है सामान्य लिस्प।

0
जोड़ा

आपके द्वारा अब तक के अच्छे उत्तरों के अलावा, मैं एंड्रयू एपेल के निरंतरता के साथ संकलन की अनुशंसा करता हूं । यह बहुत अच्छी तरह लिखा गया है और सी के साथ सीधे व्यवहार नहीं करते हैं, यह संकलक लेखकों के लिए वास्तव में अच्छे विचारों का स्रोत है।

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

0
जोड़ा
मुझे एपेल की किताब बहुत पसंद है। एक बोनस यह है कि आप एसएमएल / एनजे कंपाइलर के स्रोत कोड का उल्लेख कर सकते हैं, जो कि इस प्रक्रिया में एपेल का वर्णन करने वाली प्रक्रिया का एक बहुत अच्छा उदाहरण है।
जोड़ा लेखक Nate C-K, स्रोत