Kompilierung der Tail-Call-Optimierung bei der gegenseitigen Rekursion in C und Haskell

Question

Ich experimentiere mit der Fremdfunktionsschnittstelle in Haskell. Ich wollte einen einfachen Test implementieren, um zu sehen, ob ich eine gegenseitige Rekursion durchführen kann. Also, habe ich den folgenden Haskell Code:

module MutualRecursion where 
import Data.Int 

foreign import ccall countdownC::Int32->IO() 
foreign export ccall countdownHaskell::Int32->IO() 

countdownHaskell::Int32->IO() 
countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return() 

Beachten Sie, dass die rekursive Fall ist ein Aufruf an countdownC, so sollte dies sein Schwanz-rekursiv.

In meinem C-Code, habe ich

#include <stdio.h> 

#include "MutualRecursionHaskell_stub.h" 

void countdownC(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownHaskell(count-1); 
} 

int main(int argc, char* argv[]) 
{ 
    hs_init(&argc, &argv); 

    countdownHaskell(10000); 

    hs_exit(); 
    return 0; 
} 

die ebenfalls Schwanz rekursiv ist. Also dann mache ich einen

MutualRecursion: MutualRecursionHaskell_stub 
    ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion 
MutualRecursionHaskell_stub: 
    ghc -O2 -c MutualRecursionHaskell.hs 

und kompilieren mit make MutualRecursion.

Und ... nach dem Drucken segfaults nach dem Drucken 8991. Nur als Test sicher gcc machen sich tco in gegenseitige Rekursion umgehen kann, habe ich

void countdownC2(int); 

void countdownC(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownC2(count-1); 
} 

void countdownC2(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownC(count-1); 
} 

und das funktionierte sehr gut. Es funktioniert auch im Einzel-Rekursions-Fall von nur in C und nur in Haskell.

Meine Frage ist also, gibt es eine Möglichkeit, GHC anzuzeigen, dass der Aufruf der externen C-Funktion Tail rekursiv ist? Ich gehe davon aus, dass der Stack-Frame vom Aufruf von Haskell nach C kommt und nicht umgekehrt, da der C-Code sehr deutlich eine Rückgabe eines Funktionsaufrufs ist.

Answer 1

Ich glaube, sprachübergreifende C-Haskell Tail Calls sind sehr, sehr schwer zu erreichen.

Ich kenne nicht die genauen Details, aber die C-Laufzeit und die Haskell-Laufzeit sind gewaltig unterschiedlich. Die wichtigsten Faktoren für diesen Unterschied, soweit ich sehen kann, sind:

• anderes Paradigma: rein funktional vs Imperativ
• Garbage Collection vs manuelle Speicherverwaltung
• faul Semantik vs streng ein

Die Arten von Optimierungen, die bei solchen Unterschieden wahrscheinlich über Sprachgrenzen hinweg bestehen, sind nahezu gleich null. Vielleicht könnte man theoretisch eine Ad-hoc-C-Laufzeit zusammen mit einer Haskell-Laufzeit erfinden, so dass einige Optimierungen möglich sind, aber GHC und GCC wurden nicht auf diese Weise entworfen.

nur ein Beispiel für die möglichen Unterschiede zu zeigen, übernehmen wir die folgenden Haskell-Code haben

p :: Int -> Bool 
p x = x==42 

main = if p 42 
     then putStrLn "A"  -- A 
     else putStrLn "B"  -- B 

Eine mögliche Implementierung des main die folgende sein:

• Push die Adresse A auf dem Stapel
• drücken Sie die Adresse B auf dem Stapel
• pus h 42 auf dem Stapel
• Sprung zu p
• A: print "A", springe zu beenden
• B: print "B", springt

zu beenden, während p implementiert ist wie folgt:

• p: pop x vom Stapel
• pop b aus Stapel
• pop a von Stapel
• Test x gegen 42
• wenn gleich, springt zum a
• Sprung zu b

Beachten Sie, wie p mit zwei Absenderadressen aufgerufen wird, eine für jedes mögliche Ergebnis. Dies unterscheidet sich von C, dessen Standardimplementierungen nur eine Rücksprungadresse verwenden. Beim Überschreiten von Grenzen muss der Compiler diese Differenz berücksichtigen und kompensieren.

Oben habe ich auch nicht für den Fall berücksichtigt, wenn das Argument ein Thunk ist, um es einfach zu halten. Der GHC-Zuordner kann auch eine Speicherbereinigung auslösen.

Beachten Sie, dass die obige fiktive Implementierung tatsächlich in der Vergangenheit von GHC (die sogenannte "push/enter" STG-Maschine) verwendet wurde. Auch wenn es jetzt nicht mehr verwendet wird, ist die STG-Maschine "eval/apply" der C-Laufzeit nur marginal näher. Ich bin mir nicht einmal sicher, ob GHC den regulären C-Stack nutzt: Ich denke, es ist nicht so, dass es einen eigenen verwendet.

Sie können die GHC developer wiki überprüfen, um die blutigen Details zu sehen.

Answer 2

Während ich kein Experte in Haskel-C Interop bin, kann ich mir nicht vorstellen, dass ein Aufruf von C nach Haskel eine direkte Funktionsaufruf sein kann - es muss höchstwahrscheinlich durch Vermittler Umgebung einrichten. Infolgedessen würde Ihr Aufruf zu Hasel tatsächlich aus Anruf zu diesem Vermittler bestehen. Dieser Anruf wurde wahrscheinlich von gcc optimiert. Aber der Aufruf vom Vermittler zur tatsächlichen Haskel-Routine wurde nicht unbedingt optimiert - ich nehme also an, dass Sie damit zu tun haben. Sie können die Baugruppenausgabe überprüfen, um sicherzustellen.