Выполняет ли Ruby оптимизацию звонков?

Question

Функциональные языки приводят к использованию рекурсии для решения множества проблем, поэтому многие из них выполняют оптимизацию Tail Call Optimization (TCO). TCO вызывает вызовы функции из другой функции (или самой себя, и в этом случае эта функция также известна как Tail Recursion Elimination, которая является подмножеством TCO), в качестве последнего шага этой функции, чтобы не требовать новый стек стека, что уменьшает использование служебных данных и памяти.

Ruby, очевидно, «заимствовал» ряд понятий от функциональных языков (lambdas, функции, такие как карта и т. Д. И т. Д.), Что заставляет меня любопытно: выполняет ли Ruby оптимизацию хвостовых вызовов?

Answer 1

Нет, Ruby не выполняет TCO. Однако он также не не выполняет TCO.

Спецификация языка Ruby не говорит ничего о TCO. Он не говорит, что вам нужно это делать, но он также не говорит вам, что не может сделать это. Вы просто не можете rely на нем.

Это в отличие от схемы, где Спецификация языка требует что все Реализации должны выполнять TCO. Но это также не похоже на Python, где Guido van Rossum очень много раз делал (в последний раз всего пару дней назад), что Python Implementations не должен выполнять TCO.

Yukihiro Matsumoto сочувствует TCO, он просто не хочет принуждать все Реализации для его поддержки. К сожалению, это означает, что вы не можете полагаться на TCO, или если вы это сделаете, ваш код больше не будет переносимым для других Ruby-реализаций.

Итак, некоторые Ruby Implementations выполняют TCO, но большинство из них этого не делают. Например, YARV поддерживает TCO, хотя (на данный момент) вы должны явно раскомментировать строку в исходном коде и перекомпилировать виртуальную машину, чтобы активировать TCO - в будущих версиях она будет включена по умолчанию, после того, как реализация докажет стабильный. Виртуальная машина Parrot поддерживает TCO изначально, поэтому кардинал тоже вполне мог ее поддержать. CLR поддерживает некоторую поддержку TCO, что означает, что IronRuby и Ruby.NET могли бы это сделать. Возможно, Рубиний тоже мог бы это сделать.

Но JRuby и XRuby не поддерживают TCO, и они, вероятно, не будут, если только JVM не получит поддержку TCO. Проблема заключается в следующем: если вы хотите иметь быструю реализацию и быструю и плавную интеграцию с Java, тогда вы должны быть совместимы с Java и использовать стек JVM как можно больше. Вы можете с легкостью реализовать TCO с батутами или явным стилем продолжения прохождения, но тогда вы больше не используете стек JVM, а это означает, что каждый раз, когда вы хотите позвонить в Java или вызвать Java в Ruby, вам нужно выполнить какой-то конверсия, которая медленная. Итак, XRuby и JRuby решили пойти со скоростью и интеграцией Java по TCO и продолжениям (которые в основном имеют ту же проблему).

Это относится ко всем реализациям Ruby, которые хотят тесно интегрироваться с некоторой платформой хоста, которая не поддерживает TCO изначально. Например, я предполагаю, что у MacRuby будет такая же проблема.

Answer 2

Это может быть, но не гарантировано:

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

Answer 3

Update: Вот хорошее объяснение ТСО в Ruby: http://nithinbekal.com/posts/ruby-tco/

Update: Вы можете также проверить tco_method перл: http://blog.tdg5.com/introducing-the-tco_method-gem/

В Руби МРТ (1.9, 2.0 и 2.1) вы можете включить TCO в:

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

Было предложение повернуть TCO по умолчанию в Ruby 2.0. Это также объясняет некоторые проблемы, которые приходят с этим: Tail call optimization: enable by default?.

Короткий отрывок из ссылки:

Как правило, хвост рекурсии оптимизации включает в себя еще один метод оптимизации - «вызов» «перепрыгнуть» перевод. На мой взгляд, сложно применить эту оптимизацию, потому что распознавание «рекурсия» трудна в мире Ruby.

Следующий пример. Вызов метода fact() в предложении «else» не является «хвостом» call ».

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, который работает для MRI 1.9 до 2.1. Это должно печатать очень большое число. Если вы не установите для параметра TCO значение true, вы должны получить ошибку «слишком сложная».

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