wake-up-neo.net

Hat Haskell eine schwanzrekursive Optimierung?

Ich habe den Befehl "time" heute in Unix entdeckt und dachte, ich würde ihn verwenden, um die Laufzeitunterschiede zwischen rekursiven und normalen rekursiven Funktionen in Haskell zu überprüfen.

Ich habe folgende Funktionen geschrieben:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

Diese sind gültig, wenn man bedenkt, dass sie nur für dieses Projekt bestimmt sind, also habe ich nicht nach Nullen oder negativen Zahlen gesucht.

Nachdem jedoch für jede Methode eine Hauptmethode geschrieben, kompiliert und mit dem Befehl "time" ausgeführt wurde, hatten beide ähnliche Laufzeiten mit der rekursiven Funktion normal, die den rekursiven Schwanz ausblendet. Dies steht im Widerspruch zu dem, was ich in Bezug auf die Schwanz-rekursive Optimierung in LISP gehört hatte. Was ist der Grund dafür?

82
haskell rascal

Haskell verwendet Lazy-Evaluation, um die Rekursion zu implementieren. Behandelt also alles als Versprechen, bei Bedarf einen Wert bereitzustellen (dies wird als Thunk bezeichnet). Die Thunks werden nur so weit wie nötig reduziert, um fortzufahren, nicht mehr. Dies ähnelt der Art und Weise, wie Sie einen Ausdruck mathematisch vereinfachen. Daher ist es hilfreich, ihn so zu betrachten. Die Tatsache, dass die Auswertungsreihenfolge nicht in Ihrem Code angegeben ist, ermöglicht es dem Compiler, viele noch cleverere Optimierungen vorzunehmen, als Sie es früher getan haben. Kompilieren Sie mit -O2, Wenn Sie eine Optimierung wünschen!

Mal sehen, wie wir facSlow 5 Als Fallstudie bewerten:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Genauso wie Sie sich Sorgen gemacht haben, haben wir einen Aufbau von Zahlen, bevor Berechnungen durchgeführt werden, aber im Gegensatz zu Sie haben sich Sorgen gemacht, dass es keinen Stapel von facSlow Funktionsaufrufen gibt, die darauf warten, beendet zu werden - Jede Reduktion wird angewendet und verschwindet, wobei ein Stapelrahmen im Kielwasser verbleibt (das liegt daran, dass (*) streng ist und die Auswertung des zweiten Arguments auslöst).

Haskells rekursive Funktionen werden nicht sehr rekursiv ausgewertet! Der einzige Stapel von Anrufen, der herumhängt, sind die Multiplikationen selbst. Wenn (*) Als strenger Datenkonstruktor angesehen wird, wird dies als geschützt Rekursion bezeichnet (obwohl dies normalerweise mit nicht Bezeichnet wird = -strikte Datenkonstruktoren, bei denen die Datenkonstruktoren übrig bleiben (wenn durch weiteren Zugriff erzwungen).

Schauen wir uns nun den rekursiven Schwanz an fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

So können Sie sehen, dass die Schwanzrekursion an sich weder Zeit noch Platz gespart hat. Insgesamt sind nicht nur mehr Schritte erforderlich als bei facSlow 5, Sondern es wird auch ein verschachtelter Thunk erstellt (hier als {...} Dargestellt), für den ein zusätzlicher Speicherplatz benötigt wird. Hier werden die zukünftigen Berechnungen und die durchzuführenden verschachtelten Multiplikationen beschrieben.

Dieser Thunk wird dann entwirrt, indem it nach unten bewegt wird und die Berechnung auf dem Stapel neu erstellt wird. Hier besteht auch die Gefahr eines Stapelüberlaufs bei sehr langen Berechnungen für beide Versionen.

Wenn wir dies von Hand optimieren möchten, müssen wir es nur streng machen. Sie können den strengen Anwendungsoperator $! Zum Definieren verwenden

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

Dies zwingt facS' In seinem zweiten Argument dazu, streng zu sein. (Es ist bereits in seinem ersten Argument streng, da dieses ausgewertet werden muss, um zu entscheiden, welche Definition von facS' Angewendet werden soll.)

Manchmal kann Strenge enorm helfen, manchmal ist es ein großer Fehler, weil Faulheit effizienter ist. Hier ist es eine gute Idee:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Welches ist, was Sie erreichen wollten, denke ich.

Zusammenfassung

  • Wenn Sie Ihren Code optimieren möchten, müssen Sie zunächst mit -O2 Kompilieren.
  • Die Schwanzrekursion ist nur dann gut, wenn sich kein Thunk bildet, und wenn es angebracht ist, kann dies durch Hinzufügen von Strenge in der Regel verhindert werden. Dies geschieht, wenn Sie ein Ergebnis erstellen, das später auf einmal benötigt wird.
  • Manchmal ist die Schwanzrekursion ein schlechter Plan und die geschützte Rekursion ist eine bessere Anpassung, d. H. Wenn das Ergebnis, das Sie erstellen, nach und nach in Teilen benötigt wird. Siehe diese Frage zum Beispiel zu foldr und foldl und teste sie gegeneinander.

Probieren Sie diese beiden:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1 Ist schwanzrekursiv, während foldr1 Eine geschützte Rekursion ausführt, sodass das erste Element sofort für die weitere Verarbeitung/den Zugriff angezeigt wird. (Die erste "Klammer" auf einmal links, (...((s+s)+s)+...)+s, Zwingt die Eingabeliste vollständig zum Ende und erzeugt einen großen Teil der zukünftigen Berechnung, viel früher als die vollständigen Ergebnisse benötigt werden; die zweite Klammer rechts.) schrittweise, s+(s+(...+(s+s)...)), verbraucht die Eingabeliste Stück für Stück, so dass das Ganze mit Optimierungen in der Lage ist, in einem konstanten Raum zu arbeiten.

Je nach verwendeter Hardware müssen Sie möglicherweise die Anzahl der Nullen anpassen.

153
AndrewC

Es sollte erwähnt werden, dass die Funktion fac kein guter Kandidat für eine geschützte Rekursion ist. Schwanzrekursion ist der Weg hierher. Aufgrund der Faulheit erhalten Sie in Ihrer fac' - Funktion keinen TCO-Effekt, da die Akkumulatorargumente immer wieder große Thunks bilden, die bei der Auswertung einen großen Stapel erfordern. Um dies zu verhindern und den gewünschten Effekt der Gesamtbetriebskosten zu erzielen, müssen Sie diese Akkumulatorargumente streng definieren.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Wenn Sie mit -O2 Kompilieren (oder nur mit -O), Wird GHC dies wahrscheinlich in der Strenge-Analyse Phase alleine tun.

15
is7s

Sie sollten den Wiki-Artikel über Schwanzrekursion in Haskell lesen. Insbesondere aufgrund der Auswertung von Ausdrücken ist die Art der gewünschten Rekursion eine geschützte Rekursion. Wenn Sie die Details herausfinden, was unter der Haube vor sich geht (in der abstrakten Maschine für Haskell), erhalten Sie dasselbe wie bei der Schwanzrekursion in strengen Sprachen. Gleichzeitig haben Sie eine einheitliche Syntax für Lazy-Funktionen (die Schwanzrekursion bindet Sie an eine strenge Bewertung, wohingegen die geschützte Rekursion natürlicher funktioniert).

(Und wenn man Haskell lernt, ist der Rest dieser Wiki-Seiten auch fantastisch!)

6

Wenn ich mich richtig erinnere, optimiert GHC rekursive Funktionen automatisch in rekursiv optimierte Funktionen.

0
Ncat