Sind in Frege Tail Calls optimiert? Ich weiß, dass es TCO weder in Java noch in Sprachen gibt, die wie Clojure und Scala zu JVM-Bytecode kompilieren. Was ist mit Frege?Führt Frege die Tail Call Optimierung durch?
Frege optimiert die Tail Recursion-Optimierung, indem einfach While-Schleifen erzeugt werden.
Allgemeine Schwanz Anrufe werden "nebenbei" durch Faulheit behandelt. Wenn der Compiler einen Tail-Aufruf an eine verdächtige Funktion erkennt, von der bekannt ist, dass sie (indirekt) rekursiv ist, wird ein Lazy-Ergebnis (ein Thunk) zurückgegeben. Somit liegt die tatsächliche Last beim Aufruf dieser Funktion beim Anrufer. Auf diese Weise werden Stapel vermieden, deren Tiefe von den Daten abhängt.
Damit ist die statische Stapeltiefe von Natur aus tiefer in einer funktionalen Sprache als in Java. Daher müssen einige Programme einen größeren Stapel erhalten (d. H. Mit -Xss1m).
Es gibt pathologische Fälle, in denen große Thunks erstellt werden und wenn sie ausgewertet werden, wird ein Stapelüberlauf passieren. Ein berüchtigtes Beispiel ist die Faltfunktion (dasselbe Problem wie in Haskell). Daher ist die Standard-Linksfaltung in Frege eine Falte, die im Akkumulator tendierend und strikt rekursiv ist und somit im konstanten Stapelraum arbeitet (wie Haskells faltl ').
Das folgende Programm sollte nicht Stack-Überlauf, aber print "false" nach 2 oder 3-Fettsäuren:
module Test
-- inline (odd)
where
even 0 = true
even 1 = false
even n = odd (pred n)
odd n = even (pred n)
main args = println (even 123_456_789)
Dies funktioniert wie folgt: println muss einen Wert zu drucken, hat so versucht (auch n zu bewerten). Aber alles, was es bekommt, ist ein Thunk zu (Odd (pred n)). Daher versucht es, diesen Thunk auszuwerten, der einen weiteren Thunk erhält (gerade (pred (pred n))). sogar muss evaluieren (pred (pred n)), um zu sehen, ob das Argument 0 oder 1 war, bevor ein weiteres Thunk (odd (pred (n-2)) zurückgegeben wird, wobei n-2 bereits ausgewertet wird. auf JVM-Ebene) wird innerhalb von println getan. Zu keinem Zeitpunkt wird sogar ungerade oder umgekehrt aufgerufen.
Wenn man die Inline-Direktive auskommentiert, erhält man eine tail rekursive Version von even, und das Ergebnis wird zehnmal erhalten . schneller
Unnötig diese ungeschickte Algorithmus nur zu sagen, für die Demonstration ist -. normalerweise würde man mit einem Bit-Betrieb für even-ness überprüfen
Hier ist eine andere Version ist, ist, dass pathologische und stapelt overflo w:
even 0 = true
even 1 = false
even n = not . odd $ n
odd = even . pred
Das Problem hier ist, dass not die Endrekursion ist, und es ist streng in ihrem Argument (das heißt, zu negieren etwas, müssen Sie sich zuerst, dass etwas haben). Wenn also even n berechnet wird, muss not vollständig auswerten, was wiederum even (pred n) auswerten muss und somit 2 * n Stack-Frames benötigen.
Leider wird sich das nicht ändern, auch wenn die JVM eines Tages einen richtigen Tail Call haben sollte. Der Grund ist die Rekursion im Argument einer strikten Funktion.
Erstaunliche Antwort, vielen Dank! Übrigens gibt es Strenge Annotationen in Frege? – haskelline
Ja. Bang Muster. – Ingo
@Landei TCO wird in Scala nicht vollständig unterstützt ... versuchen Sie es.
def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() }
Hinweis, ich habe nicht genug Ruf, um direkt zu kommentieren. Kommentar finden Ich antworte auf die Kommentare der ursprünglichen Frage.
Der Titel Ihrer Frage ist das erste, was die Leute sehen, und "TCO" ist nur eine weitere TLA. –
Es sollte erwähnt werden, dass Scala TCO hat, und dass einige JVMs (wie IBMs) es auch implementieren. – Landei
@Landei ist das ein neues Feature in Scala? TCO wurde lange nicht in Scala unterstützt! – haskelline