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

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

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

87 голосов | спросил Charlie Flowers 5 Maypm09 2009, 16:03:12

5 ответов


0

Нет, 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 будет та же проблема.

ответил Jörg W Mittag 5 Maypm09 2009, 17:21:34
0

Обновление . Вот хорошее объяснение 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. В нем также объясняются некоторые проблемы, связанные с этим: Оптимизация вызовов в хвосте: включить по умолчанию? /сильный>

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

  

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

     

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

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
ответил Ernest 12 12012vEurope/Moscow11bEurope/MoscowMon, 12 Nov 2012 23:46:40 +0400 2012, 23:46:40
0

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

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

ответил Steve Jessop 5 Maypm09 2009, 16:09:19
0

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
ответил Christopher Kuttruff 13 MaramThu, 13 Mar 2014 00:26:14 +04002014-03-13T00:26:14+04:0012 2014, 00:26:14
0

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

Я не смог получить ответ Эрнеста на МРТ, но это выполнимо. Я нашел этот пример , который подходит для 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
ответил Kelvin 3 Mayam14 2014, 00:54:59

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132