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

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

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

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

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

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

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

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

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

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

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

Обновление: вы можете также проверить гем tco_method : http://blog.tdg5.com/introduction-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. Здесь также объясняются некоторые проблемы, связанные с этим: Оптимизация хвостового вызова: включить по умолчанию ?.

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

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

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

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

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

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

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

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

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

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

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