पूंछ कॉल उन्मूलन को लागू करने के कुछ अच्छे तरीके क्या हैं?

Question

मैंने सी/सी ++ के अपवित्र मिश्रण में एक छोटा सा योजना दुभाषिया लिखा है, लेकिन मैंने अभी तक proper tail calls को लागू नहीं किया है।

मुझे क्लासिक Cheney on the MTA algorithm से अवगत है, लेकिन क्या इसे लागू करने के अन्य अच्छे तरीके हैं? मुझे पता है कि मैं ढेर पर स्कीम स्टैक डाल सकता हूं, लेकिन यह अभी भी उचित उन्मूलन नहीं होगा, क्योंकि मानक कहता है कि किसी को सक्रिय पूंछ कॉल की असीमित संख्या का समर्थन करना चाहिए।

मैंने भी लांगजेम्प के साथ झुका हुआ है, लेकिन अब तक मुझे लगता है कि यह केवल गैर-पारस्परिक रिकर्सिव पूंछ कॉल के लिए अच्छा काम करेगा।

प्रमुख सी-आधारित योजनाएं उचित पूंछ रिकर्सन कैसे लागू करती हैं?

Answer 1

एक कंपाइलर लिखने से सरल और वीएम आपके दुभाषिया को पंजीकृत और ट्राम्पोलिन करना है। चूंकि आपके पास एक दुभाषिया है और संकलक नहीं है (मुझे लगता है), आपको पूंछ कॉल के लिए उचित समर्थन प्राप्त करने के लिए केवल कुछ सरल परिवर्तनों की आवश्यकता है।

आपको पहले निरंतरता-गुजरने वाली शैली में सब कुछ लिखना होगा, जो सी/सी ++ में सोचने और करने के लिए अजीब हो सकता है। दान फ्राइडमैन के ParentheC ट्यूटोरियल एक रूप है कि मशीन अनुवाद है सी

के अंत में में एक उच्च स्तरीय बदलने, पुनरावर्ती कार्यक्रम के माध्यम से आप कदम, आप अनिवार्य रूप से एक सरल वीएम लागू करेंगे के बजाय जहां नियमित रूप से समारोह का उपयोग कर eval, applyProc, आदि, आप तर्क वैश्विक चर की स्थापना से गुजरती हैं और फिर अगले तर्क करने के लिए एक goto कर (या एक उच्च-स्तरीय पाश और कार्यक्रम काउंटर का उपयोग करें) करने के लिए कहता है ...

return applyProc(rator, rand) 

हो जाता है

reg_rator = rator 
reg_rand = rand 
reg_pc = applyProc 
return 

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

for(;;) { 
    switch(reg_pc) { 
    case EVAL: 
     eval(); 
     break; 
    case APPLY_PROC: 
     applyProc(); 
     break; 
    ... 
    } 
} 

संपादित करें: मैं अपने शौक योजना दुभाषिया, जावास्क्रिप्ट में लिखा के लिए एक ही प्रक्रिया के माध्यम से चला गया। मैंने कई अज्ञात प्रक्रियाओं का लाभ उठाया, लेकिन यह एक ठोस संदर्भ के रूप में मदद कर सकता है। FoxScheme's commit history 2011-03-13 से शुरू (30707a0432563ce1632a) ऊपर 2011-03-15 के माध्यम से (5dd3b521dac582507086) को देखो।

संपादित करें^2: गैर-पूंछ पुनरावृत्ति अभी भी स्मृति का उपभोग करेगी, भले ही यह ढेर में न हो।

Answer 2

आपके पास जो कुछ भी है, उसे जानने के बिना, मैं यह कहूंगा कि स्कीम कंपाइलर और वीएम को योजना के लिए "तीन कार्यान्वयन मॉडल" योजना से लागू करना सबसे आसान (और सबसे प्रबुद्ध) तरीका है।
मैं इसे यहाँ जावास्क्रिप्ट में किया है (Dybvig की पीडीएफ की एक प्रति भी है): https://github.com/z5h/zb-lisp

जांच src/compiler.js: compileCons, और "सेशन कोड" के कार्यान्वयन src/vm.js में

Answer 3

यदि आप दुभाषियों की कार्यान्वयन तकनीकों में रुचि रखते हैं, तो ईसाई क्विननेक द्वारा "लीप - लिस्प इन छोटे टुकड़े" पुस्तक के आसपास कोई रास्ता नहीं है। यह पूर्ण कोड के साथ एक योजना प्रणाली को लागू करने के सभी पहलुओं को समझाता है। यह एक अद्भुत किताब है।

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

लेकिन भूल जाते हैं ReadScheme.org पर कागजात की जाँच करने के लिए नहीं है।

अनुभाग

संकलक प्रौद्योगिकी/कार्यान्वयन तकनीक और अनुकूलन http://library.readscheme.org/page8.html

पूंछ कॉल अनुकूलन पर काफी कुछ कागजात है।

दूसरों के अलावा आपको डिबविग की थीसिस (क्लासिक), का एक लिंक मिलेगा जो बहुत अच्छी तरह लिखा गया है। यह में सब कुछ स्पष्ट रूप से बताता है और प्रेरित करता है।