Führt Ruby eine Tail Call-Optimierung durch?

92

Funktionale Sprachen führen zur Verwendung von Rekursion, um viele Probleme zu lösen, und daher führen viele von ihnen eine Tail Call Optimization (TCO) durch. TCO bewirkt, dass Aufrufe einer Funktion von einer anderen Funktion (oder von sich selbst. In diesem Fall wird diese Funktion auch als Tail Recursion Elimination bezeichnet, eine Teilmenge der TCO) als letzter Schritt dieser Funktion keinen neuen Stapelrahmen benötigt. Dies verringert den Overhead und die Speichernutzung.

Ruby hat offensichtlich eine Reihe von Konzepten aus funktionalen Sprachen "ausgeliehen" (Lambdas, Funktionen wie Map usw.), was mich neugierig macht: Führt Ruby eine Tail-Call-Optimierung durch?

Charlie Flowers
quelle

Antworten:

127

Nein, Ruby führt keine Gesamtbetriebskosten durch. Es kann aber auch nicht nicht TCO führen.

Die Ruby-Sprachspezifikation sagt nichts über die Gesamtbetriebskosten aus. Es heißt nicht, dass Sie es tun müssen, aber es heißt auch nicht, dass Sie es nicht tun können. Darauf kann man sich einfach nicht verlassen .

Dies unterscheidet sich von Schema, bei dem die Sprachspezifikation erfordert, dass alle Implementierungen TCO ausführen müssen . Aber es ist auch anders als bei Python, wo Guido van Rossum mehrfach (das letzte Mal vor ein paar Tagen) sehr deutlich gemacht hat, dass Python-Implementierungen keine TCO durchführen sollten.

Yukihiro Matsumoto ist mit TCO einverstanden, er möchte einfach nicht alle Implementierungen dazu zwingen, dies zu unterstützen. Leider bedeutet dies, dass Sie sich nicht auf die Gesamtbetriebskosten verlassen können. Andernfalls ist Ihr Code nicht mehr auf andere Ruby-Implementierungen portierbar.

Einige Ruby-Implementierungen führen TCO durch, die meisten jedoch nicht. YARV unterstützt beispielsweise TCO, obwohl Sie (im Moment) eine Zeile im Quellcode explizit auskommentieren und die VM neu kompilieren müssen, um TCO zu aktivieren - in zukünftigen Versionen wird sie standardmäßig aktiviert, nachdem die Implementierung dies bewiesen hat stabil. Die Parrot Virtual Machine unterstützt TCO nativ, daher könnte Cardinal sie auch problemlos unterstützen. Die CLR unterstützt TCO, was bedeutet, dass IronRuby und Ruby.NET dies wahrscheinlich tun könnten. Rubinius könnte es wahrscheinlich auch tun.

JRuby und XRuby unterstützen TCO jedoch nicht und werden dies wahrscheinlich auch nicht tun, es sei denn, die JVM selbst erhält Unterstützung für TCO. Das Problem ist folgendes: Wenn Sie eine schnelle Implementierung und eine schnelle und nahtlose Integration in Java wünschen, sollten Sie stapelkompatibel mit Java sein und den Stapel der JVM so oft wie möglich verwenden. Sie können TCO ganz einfach mit Trampolinen oder einem expliziten Continuation-Passing-Stil implementieren, verwenden dann aber nicht mehr den JVM-Stack. Dies bedeutet, dass Sie jedes Mal, wenn Sie Java aufrufen oder von Java in Ruby aufrufen möchten, eine Art ausführen müssen Umwandlung, die langsam ist. Daher entschieden sich XRuby und JRuby für Geschwindigkeit und Java-Integration über TCO und Fortsetzungen (die im Grunde das gleiche Problem haben).

Dies gilt für alle Implementierungen von Ruby, die eng in eine Hostplattform integriert werden sollen, die TCO nicht nativ unterstützt. Ich denke zum Beispiel, dass MacRuby das gleiche Problem haben wird.

Jörg W Mittag
quelle
2
Ich könnte mich irren (bitte klären Sie mich auf, wenn ja), aber ich bezweifle, dass TCO in echten OO-Sprachen sinnvoll ist, da der Tail-Aufruf den Aufrufer-Stack-Frame wiederverwenden muss. Da bei der späten Bindung zum Zeitpunkt der Kompilierung nicht bekannt ist, welche Methode von einem Nachrichtensend aufgerufen wird, scheint es schwierig zu sein, dies sicherzustellen (möglicherweise mit einer JIT mit Typrückmeldung oder indem alle Implementierer einer Nachricht gezwungen werden, Stapelrahmen zu verwenden gleicher Größe oder durch Beschränkung der Gesamtbetriebskosten auf Selbstsendungen derselben Nachricht…).
Damien Pollet
2
Das ist eine großartige Antwort. Diese Informationen sind über Google nicht leicht zu finden. Interessant, dass yarv es unterstützt.
Charlie Flowers
15
Damien, es stellt sich heraus, dass TCO tatsächlich für echte OO-Sprachen erforderlich ist: siehe projectfortress.sun.com/Projects/Community/blog/… . Machen Sie sich nicht zu viele Sorgen um das Stack-Frame-Material: Es ist durchaus möglich, Stack-Frames sinnvoll zu gestalten, damit sie gut mit TCO zusammenarbeiten.
Tony Garnock-Jones
2
tonyg rettete den von GLS referenzierten Beitrag vor dem Aussterben und spiegelte ihn hier wider
Frank Shearar
Ich mache eine Hausaufgabe , bei der ich eine Reihe verschachtelter Arrays beliebiger Tiefe zerlegen muss. Der offensichtliche Weg, dies zu tun, ist rekursiv, und ähnliche Online-Anwendungsfälle (die ich finden kann) verwenden die Rekursion. Es ist sehr unwahrscheinlich, dass mein spezielles Problem in die Luft geht, auch ohne Gesamtbetriebskosten, aber die Tatsache, dass ich keine vollständig allgemeine Lösung schreiben kann, ohne auf Iteration umzusteigen, stört mich.
Isaac Rabinovitch
42

Update: Hier ist eine nette Erklärung der Gesamtbetriebskosten in Ruby: http://nithinbekal.com/posts/ruby-tco/

Update: Vielleicht möchten Sie auch das Juwel tco_method überprüfen : http://blog.tdg5.com/introducing-the-tco_method-gem/

In der Ruby-MRT (1.9, 2.0 und 2.1) können Sie die Gesamtbetriebskosten aktivieren mit:

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

Es gab einen Vorschlag, die Gesamtbetriebskosten in Ruby 2.0 standardmäßig zu aktivieren. Außerdem werden einige damit verbundene Probleme erläutert: Tail Call-Optimierung: Standardmäßig aktivieren?.

Kurzer Auszug aus dem Link:

Im Allgemeinen umfasst die Endrekursionsoptimierung eine andere Optimierungstechnik - "Aufruf" zur "Sprung" -Übersetzung. Meiner Meinung nach ist es schwierig, diese Optimierung anzuwenden, da es in Rubys Welt schwierig ist, "Rekursion" zu erkennen.

Nächstes Beispiel. Der Aufruf der fact () -Methode in der "else" -Klausel ist kein "Tail-Aufruf".

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

Wenn Sie die Tail-Call-Optimierung für die fact () -Methode verwenden möchten, müssen Sie die fact () -Methode wie folgt ändern (Continuation-Passing-Stil).

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

Es kann haben, ist aber nicht garantiert:

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

Steve Jessop
quelle
Der Link ist ab sofort tot.
Karatedog
@ Karatedog: Danke, aktualisiert. Obwohl, um ehrlich zu sein, die Referenz wahrscheinlich veraltet ist, da der Fehler jetzt 5 Jahre alt ist und seitdem Aktivitäten zum gleichen Thema stattgefunden haben.
Steve Jessop
Ja :-) Ich habe gerade über das Thema gelesen und festgestellt, dass es in Ruby 2.0 über den Quellcode aktiviert werden kann (keine Änderung und Neukompilierung der C-Quelle mehr).
Karatedog
4

TCO kann auch kompiliert werden, indem vor dem Kompilieren einige Variablen in vm_opts.h angepasst werden: 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
quelle
2

Dies baut auf den Antworten von Jörg und Ernest auf. Grundsätzlich kommt es auf die Umsetzung an.

Ich konnte Ernests Antwort nicht dazu bringen, an der MRT zu arbeiten, aber es ist machbar. Ich habe dieses Beispiel gefunden , das für MRT 1.9 bis 2.1 funktioniert. Dies sollte eine sehr große Anzahl drucken. Wenn Sie die TCO-Option nicht auf true setzen, sollte der Fehler "Stapel zu tief" angezeigt werden.

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
quelle