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

Question

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

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

Answer 1

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

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

Это не похоже на Схему, где Спецификация языка требует , чтобы все Реализации должны выполнять TCO. Но это также непохоже на Python, где Гвидо ван Россум неоднократно (последний раз всего пару дней назад) очень ясно давал понять, что реализации 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, а это означает, что каждый раз, когда вы хотите вызвать Java или вызвать из Java в Ruby, вы должны выполнить какое-то конверсия, которая медленная. Итак, XRuby и JRuby предпочли идти в ногу со скоростью и интеграцией Java, а не с TCO и продолжениями (которые в основном имеют ту же проблему).

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

Answer 2

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

Обновление: Возможно, вы также захотите проверить tco_method gem: 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" не является "tail" вызова».

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

Answer 3

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

https://bugs.ruby -lang.org / вопросы / 1256

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

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

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