Akkumulatoren in Haskell

Question

In Haskell, wenn ich

fac n = facRec n 1 
    where facRec 0 acc = acc 
     facRec n acc = facRec (n-1) (acc*n) 

und kompilieren Sie es mit GHC schreiben, wird das Ergebnis anders sein, als wenn ich verwendet

fac 0 = 1 
fac n = n * fac (n-1) 

ich leicht fac n = product [1..n] tun könnte und vermeiden die Ganze Sache, aber ich interessiere mich dafür, wie ein Versuch der Tail-Rekursion in einer faulen Sprache ausgeht. Ich bekomme, dass ich immer noch einen Stack-Overflow bekomme, weil sich Thunks aufbauen, aber passiert tatsächlich etwas anders (in Bezug auf das resultierende kompilierte Programm), wenn ich einen Akkumulator verwende, als wenn ich gerade die naive Rekursion feststelle? Gibt es einen Vorteil, die Tail-Rekursion außer einer besseren Lesbarkeit zu vernachlässigen? Ändert sich die Antwort überhaupt, wenn ich runhaskell verwende, um die Berechnung auszuführen, anstatt sie zuerst zu kompilieren?

Answer 1

Tail Rekursion macht Sinn in (GHC) Haskell, wenn Ihr Akku ist streng. Um das Problem zu zeigen, ist hier eine „Spur“ von der Schwanz-rekursive Definition von fac:

fac 4 
~> facRec 4 1 
~> facRec 3 (1*4) 
~> facRec 2 ((1*4)*3) 
~> facRec 1 (((1*4)*3)*2) 
~> facRec 0 ((((1*4)*3)*2)*1) 
~> (((1*4)*3)*2) * 1 
    ~> ((1*4)*3) * 2 
    ~> (1*4) * 3 
     ~> 1*4 
    ~> 4 * 3 
    ~> 12 * 2 
~> 24 * 1 
~> 24 

Die Einrückungsebene entspricht (grob) Ebene zu stapeln. Beachten Sie, dass der Akkumulator nur am Ende ausgewertet wird, was einen Stapelüberlauf verursachen kann. Der Trick besteht natürlich darin, den Akkumulator strikt zu machen. Es ist theoretisch möglich, zu zeigen, dass facRec streng ist, wenn es in einem strikten Kontext aufgerufen wird, aber ich kenne keinen Compiler, der das tut, ATM. GHC tut tun Schwanz Anrufoptimierung, obwohl, so verwenden die facRec Aufrufe konstanten Stapelspeicherplatz.

Aus dem gleichen Grund wird foldl' in der Regel über foldl bevorzugt, da ersteres im Akkumulator streng ist.

In Bezug auf Ihren zweiten Teil ist runhaskell/runghc nur ein Wrapper über GHCi. Wenn GHCi kompilierten Code findet, wird es das verwenden, andernfalls wird es den Bytecode-Interpreter verwenden, der wenige Optimierungen durchführt, also erwarten Sie keine ausgefallenen Optimierungen.

Answer 2

Ihre Frage ist nicht vollständig. Ich nehme an, Sie meinen GHC, und zumindest ohne Optimierungen ist die Antwort "ja", weil die Worker-Funktion (facRec in der ersten oder fac in der zweiten) eine Arity 2 im Vergleich zu einer hat und die Baugruppe dies widerspiegelt. Bei Optimierungen oder bei JHC lautet die Antwort wahrscheinlich "Nein".

Answer 3

In Haskell hilft es nur, Ihr Programm auf eine tail-rekursive Weise zu schreiben, wenn Ihr Akku streng ist und Sie das ganze Ergebnis benötigen.

Mit ghc runHaskell wird das Programm nicht optimiert, so dass es keine Striktitätsanalyse geben wird, so dass Sie Überlauf stapeln können; Wenn Sie jedoch mit Optimierungen kompilieren, erkennt der Compiler möglicherweise, dass der Akkumulator strikt sein muss, und optimiert ihn entsprechend.

Um zu sehen, wie die Dinge anders ablaufen (oder nicht), ist es am besten, die generierte Kernsprache zu prüfen, a good blog post from Don Stewart explains things. Viele seiner Blogposts sind interessant, wenn Sie sich übrigens für Performance interessieren.