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

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

Рубин, очевидно, "заимствовал" ряд понятий из функциональные языки (лямбды, функции, такие как карта и т. д. и т. д.), что вызывает у меня любопытство: выполняет ли Ruby оптимизацию хвостового вызова?

5 87
ruby-on-rails functional-programming tail-recursion

5 ответов:

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

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

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

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

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

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

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

121

обновление: вот хорошее объяснение TCO в Ruby:http://nithinbekal.com/posts/ruby-tco/

обновление: вы можете также проверить tco_method драгоценный камень:http://blog.tdg5.com/introducing-the-tco_method-gem/

в Ruby MRI (1.9, 2.0 и 2.1) вы можете включить TCO с помощью:

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

было предложение включить TCO по умолчанию в Ruby 2.0. Это также объясняет некоторые проблемы в связи с этим: оптимизация хвостового вызова: включить по умолчанию?.

короткая выдержка из ссылки:

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

следующий пример. вызов метода fact() в предложении "else" не является a "хвост призывать."

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

Если вы хотите использовать оптимизацию хвостового вызова по методу fact (), вам нужно для изменения действительности() метод следующим образом (продолжение прохождения стиле).

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

Он может иметь, но не гарантируется:

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

12

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
4

это основывается на ответах Йорга и Эрнеста. В основном это зависит от реализации.

Я не мог получить ответ Эрнеста, чтобы работать на МРТ, но это выполнимо. Я нашел это работает для МРТ 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
2