क्या रूबी टेल कॉल ऑप्टिमाइज़ेशन करता है?

Question

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

रूबी ने स्पष्ट रूप से कार्यात्मक भाषाओं (लैम्बडा, मानचित्र जैसे कार्यों और आगे आदि) से कई अवधारणाओं को "उधार" दिया है, जो मुझे उत्सुक बनाता है: क्या रुबी पूंछ कॉल अनुकूलन करता है?

Answer 1

नहीं, रूबी TCO प्रदर्शन नहीं करता। हालांकि, यह नहीं टीसीओ निष्पादित नहीं करता है।

रूबी भाषा विशिष्टता टीसीओ के बारे में कुछ भी नहीं कहती है। यह नहीं कहता कि आपको यह करना है, लेकिन यह भी नहीं कहता कि आप नहीं कर सकते हैं। आप पर पर भरोसा नहीं कर सकते हैं।

यह योजना है, जहां भाषा विशिष्टता कि सभी क्रियान्वयन TCO करनी होगी की आवश्यकता के विपरीत है। लेकिन यह पाइथन के विपरीत भी है, जहां गिडो वैन रॉसम ने कई मौकों पर यह स्पष्ट कर दिया है (पिछली बार कुछ दिन पहले) कि पाइथन कार्यान्वयन टीसीओ नहीं करना चाहिए।

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

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

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

यह रूबी के सभी कार्यान्वयन पर लागू होता है जो कुछ होस्ट प्लेटफॉर्म के साथ कड़ाई से एकीकृत करना चाहते हैं जो टीसीओ को मूल रूप से समर्थन नहीं देता है। उदाहरण के लिए, मुझे लगता है कि मैकरुबी को एक ही समस्या होगी।

Answer 2

यह हो सकता है, लेकिन करने के लिए गारंटी नहीं है:

https://bugs.ruby-lang.org/issues/1256

Answer 3

अद्यतन: http://nithinbekal.com/posts/ruby-tco/

अपडेट:: यहाँ रूबी में TCO का अच्छा व्याख्या दी गई है तुम भी चाहते हो सकता है tco_method मणि की जाँच: 1.9, 2,0 http://blog.tdg5.com/introducing-the-tco_method-gem/

रूबी एमआरआई (में और 2.1) आप टीसीओ को चालू कर सकते हैं:

RubyVM::InstructionSequence.compile_option = { 
    :tailcall_optimization => true, 
    :trace_instruction => false 
} 

बारी करने का प्रस्ताव था रूबी 2.0 में डिफ़ॉल्ट रूप से टीसीओ। Tail call optimization: enable by default?.

लिंक से कम अंश:: - "कॉल" "कूद" के लिए अनुवाद

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

अगला उदाहरण। तथ्य() "अन्यथा" खंड में विधि आमंत्रण "पूंछ कॉल" नहीं है।

def fact(n) 
    if n < 2 
    1 
else 
    n * fact(n-1) 
end 
end 

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

def fact(n, r) 
    if n < 2 
    r 
    else 
    fact(n-1, n*r) 
    end 
end 

Answer 4

TCO भी vm_opts.h में एक जोड़े को चर अदल-बदल करके में संकलित किया जा सकता संकलन से पहले: https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h 
#define OPT_TRACE_INSTRUCTION  0 // default 1 
#define OPT_TAILCALL_OPTIMIZATION 1 // default 0 

Answer 5

यह जोर्ग की और अर्नेस्ट के जवाब पर बनाता है। असल में यह कार्यान्वयन पर निर्भर करता है।

मुझे एमआरआई पर काम करने के लिए अर्नेस्ट का जवाब नहीं मिला, लेकिन यह करने योग्य है। मुझे this example मिला जो एमआरआई 1.9 से 2.1 के लिए काम करता है। यह एक बहुत बड़ी संख्या मुद्रित करना चाहिए। यदि आप टीसीओ विकल्प को सत्य पर सेट नहीं करते हैं, तो आपको "बहुत गहरी ढेर" त्रुटि मिलनी चाहिए।

source = <<-SOURCE 
def fact n, acc = 1 
    if n.zero? 
    acc 
    else 
    fact n - 1, acc * n 
    end 
end 

fact 10000 
SOURCE 

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil, 
    tailcall_optimization: true, trace_instruction: false 

#puts i_seq.disasm 

begin 
    value = i_seq.eval 

    p value 
rescue SystemStackError => e 
    p e 
end