Ich habe Probleme mit dem Fixpunktkombinator in F #:
%Vor%(Dieser Code soll nur das Problem demonstrieren, er wurde speziell geschrieben, damit der generierte IL-Code leicht zu lesen ist.)
Dieser Code - wenn er mit optimierten Optimierungen und Rückrufen kompiliert wurde - verursacht StackOverflowException . Ich schaute auf den IL-Code und konnte das Problem auf das Lambda innerhalb des Aufrufs von fix :
(Ich habe den Code ein wenig modifiziert, damit er leichter zu lesen ist.)
Der Grund für die StackOverflowException ist, dass der Aufruf von body kein Tail-Aufruf ist (der Befehl callvirt am Ende). Der Grund dafür ist, dass der Compiler einen Aufruf an das Lambda erstellt hat, der Unit ! Zurückgibt.
Also in C # -Begriffen: Körper ist Func<Int32,Unit> , wenn es wirklich Action<Int32> sein sollte. Da der Anruf etwas zurückgibt, das verworfen werden muss, kann es sich nicht um einen Rückruf handeln. Beachten Sie auch, dass die Methode f@1 als void und nicht als Unit kompiliert wird, weshalb das Ergebnis des Aufrufs des Arguments verworfen werden muss.
Ist das tatsächlich beabsichtigt oder kann ich etwas dagegen tun? Die Art, wie der Compiler dieses Lambda behandelt, macht den Fixpunktkombinator für alle Zwecke unbrauchbar, die ich verwenden wollte.
Ich möchte nur hinzufügen, dass, solange Sie etwas als Ergebnis zurückgeben, es gut funktioniert. Nur Funktionen, die nichts zurückgeben, funktionieren nicht wie erwartet.
Das funktioniert:
%Vor%Und das ist jetzt der Code, der für das Lambda erzeugt wurde:
%Vor%Jetzt gibt es einen Rückruf. Und alles funktioniert gut.
Der IL-Code für fix (zur Diskussion in Kommentaren):
So scheint es mir, dass der (fix f) innerhalb der Definition von fix kein rekursiver Aufruf ist, der zu diesem Zeitpunkt stattfindet, sondern lediglich ein Verweis auf fix selbst, der - zusammen mit dem Argument f - erhalten wird in einem Closure namens Program/fix@11 gespeichert und wird als Argument an das Lambda übergeben, das dann über diesen Closure tatsächlich fix aufruft.
Andernfalls wäre dies von Anfang an eine unendliche Rekursion und fix wäre nutzlos.
Ich verwende F # Version 3.1.2, F # Interaktive Version 12.0.30815.0
Ich bin nicht an alternativen Lösungen interessiert. Ich will nur wissen, warum der Compiler eine Unit zurückgibt, die weggeworfen werden muss, wenn das Lambda kein Ergebnis liefert.
Sie haben Ihre eigene Frage bereits beantwortet. Zitieren des Kommentars aus dem Quellcode,
%Vor%ist die ausstehende Operation nach des Aufrufs, die verhindert, dass der Compiler hier einen Tail-Aufruf verwendet.
Es gibt einen großartigen Blogbeitrag von Keith Battocchi, "Tail calls in F #" (blättern Sie zum Abschnitt "Limits / Calling function values returning unit"), der viele Details erkennt.
In zwei Worten:
Normalerweise werden die F # -Funktionen … -> unit in .NET-Methoden kompiliert, die void zurückgeben.
Funktionen, die als Werte behandelt werden (z. B. als Argumente für Funktionen höherer Ordnung), werden in Objekten vom Typ ('a->'b) gespeichert, sodass sie tatsächlich Microsoft.FSharp.Core.Unit , nicht void .
Der Compiler muss den Dummy-Wert unit value vom Stapel löschen, bevor er zurückkehrt.
Daher ist eine ausstehende Operation nach der rekursiven Aufruf und daher kann der Compiler sie nicht für einen Tail-Aufruf optimieren.
Gute Nachrichten:
Beachten Sie, dass dieses Problem nur auftritt, wenn Sie erstklassige Funktionen als Werte verwenden. Beim Aufrufen normaler .NET-Methoden , die void zurückgeben , tritt dieses Problem nicht auf, da es keinen Rückgabewert gibt, der aus dem Stapel entfernt werden kann.
Um den Code zu optimieren, muss der Compiler den Endanruf optimieren fix . Mit der Funktion höherer Ordnung in Fix ist der Compiler verwirrt.
Wenn Sie ein tail-rekursives fix wollen, versuchen Sie es anders zu definieren:
Interessante Tatsache: Ihr fix würde keinen Überlauf in Haskell stapeln, da Haskell Ausdrücke auswertet: Haskell verwendet eine Graphenreduzierung, die sich von der Verwendung von Aufrufstapeln unterscheidet.
Wenn wir von Ihrem zweiten Beispiel sprechen, könnte .NET Just-in-Time in der Lage sein, Tail-Aufrufe zur Laufzeit zu optimieren. Da es sich um eine Optimierung handelt, hängt es davon ab, wie intelligent die Laufzeitumgebung ist: Wenn Sie einen Rückgabewert haben oder nicht, stürzt der JIT-Optimierer möglicherweise ab. Zum Beispiel hat Mono auf meinem Rechner das zweite Beispiel nicht optimiert.
Siehe auch: Tail-Call-Opcode generieren
Tags und Links f# tail-recursion tail-call-optimization f#-3.1