प्रोग्रामेटिक गैर पूंछ प्रत्यावर्तन उन्मूलन

Question

मैं जावास्क्रिप्ट में एक खिलौना लिस्प दुभाषिया बना रहा हूं। जे एस कोई पूंछ प्रत्यावर्तन उन्मूलन (TRE) है, इसलिए मैं का उपयोग कर TRE लागू किया, जबकि जे एस (स्यूडोकोड) में पाश:

function eval (exp, env) 
    while true 
    if exp is self evaluating 
     return exp 
    else if ... 
     ... 
    else if exp is a function call 
     procedure = eval(car(exp), env) 
     arguments = eval_operands(cdr(exp), env) 
     exp = procedure.body 
     env = extend_env(procedure.env, env) 
     continue # tail call 

तो मैं खुश हूँ, और निम्न में से एक की तरह पूंछ पुनरावर्ती कार्यों ढेर के समाप्त न हो :

(define + 
    (lambda (n m) 
    (cond ((zero? n) m) 
      (else (+ (sub1 n) (add1 m)))))) 

(+ 10000 1) ;=> 10001 

हालांकि, कार्यों कि पूंछ पुनरावर्ती नहीं हैं, (eval_operands पर क्योंकि जे एस कोड फिर से होता है बहुत ज्यादा) जे एस ढेर से बाहर चलाने:

(define + 
    (lambda (n m) 
    (cond ((zero? n) m) 
      (else (add1 (+ (sub1 n) m))))) ; not proper tail-recursive 

(+ 10000 1) ;=> JS: Maximum call stack size exceeded 

मैं कैसे गैर ताई के साथ सौदा करना एल-रिकर्सिव फ़ंक्शन? विकल्प क्या हैं? अच्छे संसाधन क्या हैं? मैं ट्रैम्पोलाइनिंग, ढेर externalizing और निरंतरता-गुजर शैली के बारे में थोड़ा पढ़ा है, लेकिन सभी मैं मिल सकता है कि कैसे उन शैलियों में कोड लिखने के लिए, कैसे नहीं दुभाषिया लिखने के लिए उन तकनीकों का प्रयोग है।

Answer 1

आप हमेशा कूद सकते हैं यदि आप कॉल फ्रेम जानकारी कहीं और पकड़ने में सक्षम हैं। यही है कि "स्टैक बाहरीकरण" का अर्थ है।

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

ढेर अंतरिक्ष के लिए सभी से करता है, जाहिर है, है व्यापार ढेर अंतरिक्ष। अंत में, आप इस तरह से किसी भी स्मृति को वास्तव में सहेजते नहीं हैं। :-)