मैं सी में लिखे गए स्कीम दुभाषिया पर काम कर रहा हूं। वर्तमान में यह सी रनटाइम स्टैक का उपयोग अपने स्वयं के ढेर के रूप में करता है, जो निरंतर कार्यान्वयन के साथ मामूली समस्या पेश कर रहा है। मेरा वर्तमान समाधान ढेर में सी स्टैक की मैन्युअल प्रतिलिपि है, फिर आवश्यक होने पर इसे वापस कॉपी करना। मानक सी नहीं होने के अलावा, यह समाधान शायद ही आदर्श है।निरंतरता को कैसे कार्यान्वित करें?
सी में योजना के लिए निरंतरता को लागू करने का सबसे आसान तरीका क्या है?
मैं एक लेख है कि आप के लिए सहायक हो सकता है पढ़ने याद है।
@ollie: यदि आपके सभी कॉल फ्रेम ढेर पर हैं तो आपको उछाल करने की आवश्यकता नहीं है। प्रदर्शन में एक व्यापार है, ज़ाहिर है: उछालने का समय, ढेर पर सभी फ्रेम आवंटित करने के लिए ओवरहेड बनाम। शायद यह दुभाषिया में एक ट्यूनेबल रनटाइम पैरामीटर होना चाहिए। :-P
इसके बजाय एक स्पष्ट ढेर का उपयोग करें। SISC रूप Cheney on the M.T.A. :-)
योजना के कुछ कार्यान्वयन मैं के बारे में पता है, इस तरह, ढेर पर उनके कॉल फ्रेम का आवंटन:
पैट्रिक सही है, एकमात्र तरीका यह है कि आप वास्तव में ऐसा कर सकते हैं कि आप अपने दुभाषिया में एक स्पष्ट ढेर का उपयोग करें, और जब आप निरंतरता में परिवर्तित करने की आवश्यकता हो तो ढेर में उचित ढेर को उछाल दें।
यह मूल रूप से वही है जो उन्हें समर्थन देने वाली भाषाओं में बंद करने का समर्थन करने के लिए आवश्यक है (बंद और निरंतरता कुछ हद तक संबंधित है)।
लेकिन, बंद करने का समर्थन करने के लिए, क्या आप सिर्फ लैम्ब्डा उठाना नहीं कर सकते? – apg
परंपरागत तरीका setjmp और longjmp का उपयोग करना है, हालांकि चेतावनी हैं।
यहाँ एक reasonably good explanation
एक अच्छा सारांश उपलब्ध है Implementation Strategies for First-Class Continuations में, Clinger, Hartheimer, और ओस्ट ने एक लेख है। मैं विशेष रूप से चेज़ योजना के कार्यान्वयन को देखने की सलाह देता हूं।
स्टैक कॉपीिंग जटिल नहीं है और प्रदर्शन में सुधार के लिए कई अच्छी तरह से समझी जाने वाली तकनीकें उपलब्ध हैं। ढेर-आवंटित फ्रेम का उपयोग करना काफी सरल है, लेकिन आप "सामान्य" स्थिति के लिए ओवरहेड बनाने का एक व्यापारिक तरीका बनाते हैं जहां आप स्पष्ट निरंतरता का उपयोग नहीं कर रहे हैं।
यदि आप इनपुट कोड को निरंतर पासिंग शैली (सीपीएस) में कनवर्ट करते हैं तो आप स्टैक को पूरी तरह खत्म कर सकते हैं। हालांकि, जबकि सीपीएस सुरुचिपूर्ण है, यह फ्रंट एंड में एक और प्रसंस्करण चरण जोड़ता है और कुछ प्रदर्शन प्रभावों को दूर करने के लिए अतिरिक्त अनुकूलन की आवश्यकता होती है।
उदाहरण जो आप देख सकते हैं वे हैं: Chicken (एक योजना कार्यान्वयन, जो समर्थन जारी रखने वाले सी में लिखा गया है); पॉल ग्राहम का On Lisp - जहां वह आम लिस्प में निरंतरता के सबसेट को लागू करने के लिए एक सीपीएस ट्रांसफॉर्मर बनाता है; और Weblocks - एक निरंतर आधारित वेब ढांचा, जो सामान्य लिस्प में निरंतरता के सीमित रूप को लागू करता है।
यदि आप खरोंच से शुरू कर रहे हैं, तो आपको वास्तव में निरंतर पासिंग स्टाइल (सीपीएस) परिवर्तन में देखना चाहिए।
अच्छे स्रोतों में "छोटे टुकड़ों में LISP" और Marc Feeley's Scheme in 90 minutes presentation शामिल हैं।
क्विनेक की पुस्तक लिस्प इन इन छोटे टुकड़े * उपलब्ध हैं (कम से कम पैराकाम्पस से फ्रेंच संस्करण में) –
निरंतरता समस्या नहीं है: आप सीपीएस का उपयोग करके नियमित उच्च-आदेश कार्यों वाले लोगों को लागू कर सकते हैं।बेवकूफ ढेर आवंटन के साथ मुद्दा यह है कि पूंछ कॉल कभी अनुकूलित नहीं होते हैं, जिसका अर्थ है कि आप योजना नहीं बना सकते हैं।
स्टैक्स पर योजना के स्पेगेटी स्टैक मैपिंग के लिए सबसे अच्छा वर्तमान दृष्टिकोण ट्रैम्पोलिन का उपयोग कर रहा है: अनिवार्य रूप से अतिरिक्त बुनियादी ढांचे गैर-सी जैसी कॉलों को संभालने और प्रक्रियाओं से बाहर निकलने के लिए। Trampolined Style (ps) देखें।
some code इन दोनों विचारों को चित्रित करता है।
निरंतरता मूल रूप से संदर्भ स्विच के बिंदु पर स्टैक और सीपीयू रजिस्टरों की सहेजी गई स्थिति से मिलती है। स्विचिंग करते समय कम से कम आपको पूरे ढेर को ढेर में कॉपी करने की ज़रूरत नहीं है, आप केवल स्टैक पॉइंटर को रीडायरेक्ट कर सकते हैं।
निरंतर फाइबर का उपयोग करके कार्यान्वित किया जाता है। http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 । सावधान encapsulation की आवश्यकता केवल एक चीजें पैरामीटर गुजरने और मूल्य वापस कर रहे हैं।
विंडोज फाइबर में कॉल के CreateFiber/SwitchToFiber परिवार का उपयोग करके किया जाता है। Posix-compliant सिस्टम में इसे makecontext/swapcontext के साथ किया जा सकता है।
बढ़ावा :: कोरआउट में सी ++ के लिए कोरआउट का एक कार्यान्वयन कार्यान्वयन है जो कार्यान्वयन के लिए संदर्भ बिंदु के रूप में कार्य कर सकता है।
* trivially कार्यान्वित ... सावधान encapsulation की जरूरत है * - इस अनुच्छेद में कुछ निश्चित तनाव है। यह उत्तर कुछ कोड के लिंक के साथ सुधार किया जाएगा। –
आपके द्वारा अब तक के अच्छे उत्तरों के अलावा, मैं एंड्रयू एपेल की Compiling with Continuations की सलाह देता हूं। यह बहुत अच्छी तरह लिखा गया है और सी के साथ सीधे व्यवहार नहीं करते हैं, यह संकलक लेखकों के लिए वास्तव में अच्छे विचारों का स्रोत है।
चिकन विकी में ऐसे पृष्ठ भी हैं जो आपको बहुत ही रोचक लगेगा, जैसे internal structure और compilation process (जहां सीपीएस को संकलन के वास्तविक उदाहरण के साथ समझाया गया है)।
मुझे एपेल की किताब बहुत पसंद है। एक बोनस यह है कि आप एसएमएल/एनजे कंपाइलर के स्रोत कोड का उल्लेख कर सकते हैं, जो कि एपेल पुस्तक में वर्णित प्रक्रिया का एक बहुत अच्छा उदाहरण है। –
ऐसा लगता है कि अब तक डिबविग की थीसिस अनियमित है। पढ़ने के लिए यह एक खुशी है। ढेर आधारित मॉडल लागू करने के लिए सबसे आसान है, लेकिन स्टैक आधारित अधिक कुशल है। स्ट्रिंग आधारित मॉडल को अनदेखा करें।
आर केंट डाइबविग। "योजना के लिए तीन कार्यान्वयन मॉडल"। http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
ReadScheme.org पर कार्यान्वयन पत्र भी देखें। http://library.readscheme.org/page8.html
सार इस प्रकार है:
यह शोध प्रबंध योजना प्रोग्राम मिंग भाषा के लिए तीन कार्यान्वयन मॉडल प्रस्तुत करता है। आरएसटी एक ढेर-आधारित मॉडल है जो आज के अधिकांश योजना कार्यान्वयन में रूप में उपयोग किया जाता है; दूसरा एक नया स्टैक-आधारित मॉडल है जो अधिकांश कार्यक्रमों को निष्पादित करने पर ढेर-आधारित मॉडल से काफी अधिक ईमानदार है; और तीसरा एक नया स्ट्रिंग-आधारित मॉडल है जो योजना के कार्यान्वयन के एकाधिक प्रोसेसर में उपयोग के लिए है।
ढेर-आधारित मॉडल ढेर में कई महत्वपूर्ण डेटा संरचनाओं को आवंटित करता है, जिसमें वास्तविक पैरामीटर सूचियां, बाध्यकारी वातावरण शामिल हैं, और फ्रेम पर कॉल करें।
स्टैक-आधारित मॉडल जब भी संभव हो तो स्टैक पर इन संरचनाओं को आवंटित करता है।इसके परिणामस्वरूप कम ढेर आवंटन, कम स्मृति संदर्भ, छोटे निर्देश अनुक्रम, कम कचरा संग्रह, और स्मृति का अधिक ईमानदार उपयोग होता है।
स्ट्रिंग-आधारित मॉडल इन संरचनाओं के संस्करणों को प्रोग्राम टेक्स्ट में आवंटित करता है, जिसे प्रतीकों की एक स्ट्रिंग के रूप में दर्शाया जाता है। स्ट्रिंग-आधारित मॉडल में, योजना कार्यक्रमों का अनुवाद योजना का समर्थन करने के लिए विशिष्ट रूप से डिज़ाइन की गई एक एफएफपी भाषा में किया गया है। इस भाषा में प्रोग्राम सीधे एफएफपी मशीन द्वारा निष्पादित किए जाते हैं, एकाधिक प्रोसेसर स्ट्रिंग-कमी कंप्यूटर।
स्टैक-आधारित मॉडल तत्काल व्यावहारिक सिद्धांत का है; यह लेखक है जो लेखक के चेज़ स्कीम सिस्टम द्वारा उपयोग किया जाता है, एक उच्च प्रदर्शन योजना के कार्यान्वयन। स्ट्रिंग-आधारित मॉडल के लिए उपयोगी होगा, जब मशीन को एहसास हो जाने के बाद एफएफपी मशीन पर एफएफपी के उच्च स्तरीय विकल्प के रूप में योजना प्रदान की जाएगी।
रूप soegaard ने कहा, मुख्य संदर्भ रहता 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 सेकंड खर्च करेगा, और यदि आप इनपुट नंबर बढ़ाते हैं तो यह क्रैश हो जाएगा।
-1: एक स्पष्ट ढेर क्या है? एक ढेर-आवंटित डेटा संरचना एक ढेर मॉडलिंग? एक ढेर आवंटित डेटा संरचना ढेर उपयोग के इतिहास मॉडलिंग? सवाल के लिए प्रासंगिकता? –