Ich bin mit der Idee der grundlegenden Beseitigung der Schwanzrekursion vertraut , bei der Funktionen, die das direkte Ergebnis eines Aufrufs an sich selbst zurückgeben, als iterative Schleifen umgeschrieben werden können.
foo(...):
# ...
return foo(...)
Ich verstehe auch, dass die Funktion als Sonderfall immer noch umgeschrieben werden kann, wenn der rekursive Aufruf in einen Aufruf an eingeschlossen wird cons
.
foo(...):
# ...
return (..., foo(...))
Welche Eigenschaft cons
erlaubt dies? Welche anderen Funktionen cons
können einen rekursiven Tail-Aufruf umbrechen, ohne unsere Fähigkeit zu beeinträchtigen, ihn iterativ umzuschreiben?
GCC (aber nicht Clang) ist in der Lage, dieses Beispiel der "Tail Recursion Modulo Multiplication " zu optimieren , aber es ist unklar, mit welchem Mechanismus es dies entdeckt oder wie es seine Transformationen durchführt.
pow(x, n):
if n == 0: return 1
else if n == 1: return x
else: return x * pow(x, n-1)
if(n==0) return 0;
(nicht 1 wie in Ihrer Frage).x^0 = 1
Das ist also ein Fehler. Nicht, dass es für den Rest der Frage von Bedeutung wäre; Der iterative ASM sucht zuerst nach diesem Sonderfall. Aber seltsamerweise führt die iterative Implementierung ein Vielfaches dessen ein1 * x
, was in der Quelle nicht vorhanden war, selbst wenn wir einefloat
Version erstellen. gcc.godbolt.org/z/eqwine (und gcc gelingt nur mit-ffast-math
.)return 0
wurde behoben. Die Multiplikation mit 1 ist interessant. Ich bin mir nicht sicher, was ich davon halten soll.float
ohne-ffast-math
, auch wenn es der gleiche Wert jedes Mal multipliziert wird. (Mit Ausnahme der 1.0f, die der Knackpunkt sein könnte?)Antworten:
Während GCC wahrscheinlich Ad-hoc-Regeln verwendet, können Sie diese auf folgende Weise ableiten. Ich werde es
pow
zur Veranschaulichung verwenden, da dufoo
so vage definiert bist . Dies kannfoo
auch am besten als eine Instanz der Last-Call-Optimierung in Bezug auf Einzelzuweisungsvariablen verstanden werden, wie sie die Sprache Oz hat und wie sie in Konzepte, Techniken und Modelle der Computerprogrammierung erörtert wird . Der Vorteil der Verwendung von Variablen mit einfacher Zuweisung besteht darin, dass ein deklaratives Programmierparadigma beibehalten werden kann. Grundsätzlich kann jedes Feld der Strukturrückgabefoo
durch Variablen mit einfacher Zuweisung dargestellt werden, die dannfoo
als zusätzliche Argumente übergeben werden.foo
dann wird ein Schwanz rekursivvoid
Rückgabefunktion. Hierfür ist keine besondere Klugheit erforderlich.Kehren wir
pow
zunächst zu dem Stil der Weitergabe zurück .pow
wird:Alle Anrufe sind jetzt Tail Calls. Der Kontrollstapel wurde jedoch in die erfassten Umgebungen in den Verschlüssen verschoben, die die Fortsetzungen darstellen.
Als nächstes defunktionalisieren Sie die Fortsetzungen. Da es nur einen rekursiven Aufruf gibt, ist die resultierende Datenstruktur, die die defunktionalisierten Fortsetzungen darstellt, eine Liste. Wir bekommen:
Was
applyPow(k, acc)
tut, ist eine Liste, dh freie Monoide, zu nehmenk=Cons(x, Cons(x, Cons(x, Nil)))
und daraus zu machenx*(x*(x*acc))
. Aber da*
es assoziativ ist und im Allgemeinen ein Monoid mit der Einheit bildet1
, können wir dies wieder in die Produktion einordnen((x*x)*x)*acc
und der Einfachheit halber1
beginnen(((1*x)*x)*x)*acc
. Der Schlüssel ist, dass wir das Ergebnis tatsächlich teilweise berechnen können, noch bevor wir es habenacc
. Das heißt, anstattk
als Liste herumzulaufen, die im Wesentlichen eine unvollständige "Syntax" ist, die wir am Ende "interpretieren", können wir sie "interpretieren", während wir gehen. Das Ergebnis ist, dass wir in diesem Fall durchNil
die Einheit des Monoids1
undCons
durch die Operation des Monoids ersetzen können*
und nunk
das "laufende Produkt" darstellen.applyPow(k, acc)
Dann wird genau das,k*acc
was wir wieder einbindenpow2
und das Produzieren vereinfachen können:Eine rekursive Version des Originals im Akkumulator-Passing-Stil
pow
.Natürlich sage ich nicht, dass GCC all diese Überlegungen zur Kompilierungszeit ausführt. Ich weiß nicht, welche Logik GCC verwendet. Mein Punkt ist einfach, diese Überlegung einmal gemacht zu haben, es ist relativ einfach, das Muster zu erkennen und den ursprünglichen Quellcode sofort in diese endgültige Form zu übersetzen. Die CPS-Transformation und die Defunktionalisierungstransformation sind jedoch vollständig allgemein und mechanisch. Von dort aus könnten Fusions-, Entwaldungs- oder Superkompilierungstechniken verwendet werden, um zu versuchen, die wiedervereinigten Fortsetzungen zu beseitigen. Die spekulativen Transformationen könnten verworfen werden, wenn es nicht möglich ist, die gesamte Zuordnung der wiedervereinigten Fortsetzungen aufzuheben. Ich vermute jedoch, dass dies zu teuer wäre, um es die ganze Zeit über zu tun, und daher mehr Ad-hoc-Ansätze.
Wenn Sie sich lächerlich machen möchten, können Sie die Papierrecycling- Fortsetzungen durchlesen, die ebenfalls CPS und Darstellungen von Fortsetzungen als Daten verwenden, jedoch etwas Ähnliches tun, das sich von den Schwanzrekursions-Modulo-Kons unterscheidet. Hier wird beschrieben, wie Sie durch Transformation Pointer-Reversing-Algorithmen erzeugen können.
Dieses Muster der CPS-Transformation und -Defunktionalisierung ist ein ziemlich mächtiges Werkzeug zum Verständnis und wird in einer Reihe von Arbeiten, die ich hier aufführe, effektiv eingesetzt .
quelle
Ich werde eine Weile um den heißen Brei herumreden, aber es gibt einen Grund.
Halbgruppen
Die Antwort ist die assoziative Eigenschaft der binären Reduktionsoperation .
Das ist ziemlich abstrakt, aber Multiplikation ist ein gutes Beispiel. Wenn x , y und z natürliche Zahlen (oder ganze Zahlen oder rationale Zahlen oder reelle Zahlen oder komplexe Zahlen oder N × N Matrizen oder eine ganze Reihe weiterer Dinge) sind, dann ist x × y dieselbe Art der Zahl als x und y . Wir haben mit zwei Zahlen begonnen, es ist also eine binäre Operation, und wir haben eine bekommen, also haben wir die Anzahl der Zahlen, die wir hatten, um eins reduziert, was dies zu einer Reduktionsoperation macht. Und ( x × y ) × z ist immer dasselbe wie x × ( y ×z ), welches die assoziative Eigenschaft ist.
(Wenn Sie dies alles bereits wissen, können Sie mit dem nächsten Abschnitt fortfahren.)
Noch ein paar Dinge, die Sie in der Informatik häufig sehen und die auf dieselbe Weise funktionieren:
"a"+"b"+"c"
ist,"abc"
ob Sie mit"ab"+"c"
oder beginnen"a"+"bc"
)[a]++[b]++[c]
ist ähnlich[a,b,c]
entweder von hinten nach vorne oder von vorne nach hinten.cons
Auf Kopf und Schwanz, wenn Sie sich den Kopf als Singleton-Liste vorstellen. Das verkettet nur zwei Listen.&
,|
und^
Einige Dinge, die dies nicht tun:
int print2(int x, int y) { return printf( "%d %d\n", x, y ); }
, asprint2( print2(x,y), z );
undprint2( x, print2(y,z) );
haben unterschiedliche Ausgabe.Es ist ein ausreichend nützliches Konzept, das wir es genannt haben. Eine Menge mit einer Operation, die diese Eigenschaften aufweist, ist eine Halbgruppe . Die reellen Zahlen unter Multiplikation sind also eine Halbgruppe. Und Ihre Frage erweist sich als eine der Möglichkeiten, wie diese Art der Abstraktion in der realen Welt nützlich wird. Der Betrieb von Halbgruppen kann nach Ihren Wünschen optimiert werden.
Versuchen Sie dies zu Hause
Soweit ich weiß, wurde diese Technik 1974 erstmals in Daniel Friedmans und David Wises Aufsatz "Folding Stylized Recursions into Iterations" beschrieben , obwohl sie ein paar Eigenschaften mehr annahmen, als es sich als notwendig herausstellte.
Haskell ist eine großartige Sprache, um dies zu veranschaulichen, da die
Semigroup
Typenklasse in der Standardbibliothek enthalten ist. Es nennt die Bedienung eines GenerikumsSemigroup
den Operator<>
. Da Listen und Zeichenfolgen Instanzen von sindSemigroup
, definieren ihre Instanzen<>
beispielsweise den Verkettungsoperator++
. Und mit dem richtigen Import,[a] <> [b]
ist ein Alias für[a] ++ [b]
, was ist[a,b]
.Aber was ist mit Zahlen? Wir haben gerade gesehen, dass numerische Typen Halbgruppen sind, die entweder addiert oder multipliziert werden! Also was darf man
<>
für ein seinDouble
? Na ja, einer von beiden! Haskell definiert die ArtenProduct Double
,where (<>) = (*)
(dass die tatsächliche Definition in Haskell ist), und auchSum Double
,where (<>) = (+)
.Eine Falte ist, dass Sie die Tatsache verwendet haben, dass 1 die multiplikative Identität ist. Eine Halbgruppe mit einer Identität wird als Monoid bezeichnet und im Haskell-Paket definiert
Data.Monoid
, das das generische Identitätselement einer Typenklasse aufruftmempty
.Sum
,Product
und list haben jeweils ein Identitätselement (0, 1[]
bzw.), sie sind also Instanzen vonMonoid
sowieSemigroup
. (Nicht zu verwechseln mit einer Monade , also vergiss einfach, dass ich diese sogar angesprochen habe.)Das sind genug Informationen, um Ihren Algorithmus mit Hilfe von Monoiden in eine Haskell-Funktion zu übersetzen:
Es ist wichtig zu beachten, dass dies eine Modulo-Halbgruppe mit Endrekursion ist: Jeder Fall ist entweder ein Wert, ein Endrekursionsaufruf oder das Halbgruppenprodukt von beiden. Auch dieses Beispiel wurde
mempty
für einen der Fälle verwendet, aber wenn wir das nicht gebraucht hätten, hätten wir es mit der allgemeineren Typenklasse machen könnenSemigroup
.Laden wir dieses Programm in GHCI und sehen, wie es funktioniert:
Erinnern Sie sich, wie wir
pow
für ein Generikum deklariert habenMonoid
, dessen Typ wir genannt habena
? Wir gaben GHCI genug Informationen abzuleiten , dass der Typa
hier istProduct Integer
, die eine istinstance
vonMonoid
deren<>
Betrieb Integer - Multiplikation ist. Sopow 2 4
dehnt sich rekursiv auf2<>2<>2<>2
, was ist2*2*2*2
oder16
. So weit, ist es gut.Unsere Funktion verwendet jedoch nur generische Monoid-Operationen. Zuvor habe ich gesagt, dass es eine andere Instanz von
Monoid
called gibtSum
, deren<>
Operation ist+
. Können wir das versuchen?Die gleiche Erweiterung gibt uns jetzt
2+2+2+2
statt2*2*2*2
. Multiplikation ist Addition, Exponentiation ist Multiplikation!Aber ich habe ein anderes Beispiel für ein Haskell-Monoid gegeben: Listen, deren Operation Verkettung ist.
Das Schreiben
[2]
teilt dem Compiler mit, dass dies eine Liste ist,<>
auf Listen ist++
, so[2]++[2]++[2]++[2]
ist es[2,2,2,2]
.Schließlich ein Algorithmus (zwei, in der Tat)
Durch einfaches Ersetzen
x
durch[x]
konvertieren Sie den generischen Algorithmus, der das Rekursionsmodul einer Halbgruppe verwendet, in einen Algorithmus, der eine Liste erstellt. Welche Liste? Die Liste der Elemente, auf die der Algorithmus angewendet wird<>
. Da wir nur Halbgruppenoperationen verwendet haben, die auch Listen enthalten, ist die resultierende Liste isomorph zur ursprünglichen Berechnung. Und da die ursprüngliche Operation assoziativ war, können wir die Elemente genauso gut von hinten nach vorne oder von vorne nach hinten bewerten.Wenn Ihr Algorithmus jemals einen Basisfall erreicht und endet, ist die Liste nicht leer. Da der Terminal-Fall etwas zurückgegeben hat, ist dies das letzte Element der Liste, sodass mindestens ein Element enthalten ist.
Wie wendet man eine binäre Reduktionsoperation auf jedes Element einer Liste in der angegebenen Reihenfolge an? Das ist richtig, eine Falte. So können Sie ersetzen können ,
[x]
fürx
, zu reduzieren , indem eine Liste von Elementen erhalten<>
, und dann entweder mit dem rechten oder linken fach-fach der Liste:Die Version mit
foldr1
existiert tatsächlich in der Standardbibliothek, wiesconcat
fürSemigroup
undmconcat
fürMonoid
. Es macht eine faule rechte Falte auf der Liste. Das heißt, es erweitert sich[Product 2,Product 2,Product 2,Product 2]
zu2<>(2<>(2<>(2)))
.Dies ist in diesem Fall nicht effizient, da Sie mit den einzelnen Begriffen erst dann etwas anfangen können, wenn Sie alle generieren. (Irgendwann hatte ich hier eine Diskussion darüber, wann man rechte und wann man strenge linke Falten verwendet, aber es ging zu weit.)
Die Version mit
foldl1'
ist eine streng bewertete Linksfalte. Das heißt, eine schwanzrekursive Funktion mit einem strengen Akkumulator. Dies(((2)<>2)<>2)<>2
wird sofort berechnet und nicht später, wenn es benötigt wird. (Zumindest gibt es keine Verzögerungen innerhalb der Falte selbst: Die Liste, die gefaltet wird, wird hier von einer anderen Funktion generiert, die möglicherweise eine verzögerte Auswertung enthält.) Die Falte berechnet(4<>2)<>2
dann sofort und berechnet8<>2
dann16
. Aus diesem Grund musste die Operation assoziativ sein: Wir haben nur die Gruppierung der Klammern geändert!Die strikte linke Falte entspricht dem, was GCC tut. Die am weitesten links stehende Zahl im vorherigen Beispiel ist der Akku, in diesem Fall ein laufendes Produkt. Bei jedem Schritt wird es mit der nächsten Zahl in der Liste multipliziert. Eine andere Möglichkeit, dies auszudrücken, besteht darin, dass Sie über die zu multiplizierenden Werte iterieren, das laufende Produkt in einem Akkumulator halten und bei jeder Iteration den Akkumulator mit dem nächsten Wert multiplizieren. Das heißt, es ist eine
while
Verkleidungsschleife.Es kann manchmal genauso effizient gemacht werden. Der Compiler ist möglicherweise in der Lage, die Listendatenstruktur im Speicher zu optimieren. Theoretisch verfügt es zur Kompilierungszeit über genügend Informationen, um herauszufinden, wie dies hier
[x]
geschehen sollte: Ist ein Singleton,[x]<>xs
ist also dasselbe wiecons x xs
. Bei jeder Iteration der Funktion kann möglicherweise derselbe Stack-Frame wiederverwendet und die Parameter aktualisiert werden.Entweder eine rechte oder eine strenge linke Falte ist in bestimmten Fällen besser geeignet. Wissen Sie also, welche Sie möchten. Es gibt auch einige Dinge, die nur eine richtige Falte tun kann (z. B. interaktive Ausgabe generieren, ohne auf die gesamte Eingabe zu warten, und eine unendliche Liste bearbeiten). Hier reduzieren wir jedoch eine Abfolge von Operationen auf einen einfachen Wert, sodass wir eine strenge linke Falte wünschen.
Wie Sie sehen, ist es also möglich, das Modulo der Schwanzrekursion für jede Halbgruppe (ein Beispiel hierfür ist einer der üblichen numerischen Typen unter Multiplikation) automatisch in eine träge Rechtsfalte oder eine strenge Linksfalte in einer Zeile von zu optimieren Haskell.
Weitere Verallgemeinerungen
Die beiden Argumente der Binäroperation müssen nicht vom selben Typ sein, solange der Anfangswert vom selben Typ ist wie Ihr Ergebnis. (Sie können die Argumente natürlich immer umdrehen, um sie an die Reihenfolge der Falzarten anzupassen, die Sie ausführen (links oder rechts).) Sie können einer Datei also wiederholt Patches hinzufügen, um eine aktualisierte Datei zu erhalten, oder mit dem Anfangswert von beginnen 1,0, durch ganze Zahlen dividieren, um ein Gleitkommaergebnis zu erhalten. Oder stellen Sie der leeren Liste Elemente voran, um eine Liste zu erhalten.
Eine andere Art der Verallgemeinerung besteht darin, die Falten nicht auf Listen, sondern auf andere
Foldable
Datenstrukturen anzuwenden . Häufig entspricht eine unveränderliche lineare verknüpfte Liste nicht der Datenstruktur, die Sie für einen bestimmten Algorithmus wünschen. Ein Problem, auf das ich oben nicht eingegangen bin, ist, dass das Hinzufügen von Elementen an der Vorderseite einer Liste viel effizienter ist als an der Rückseite. Wenn die Operation nicht kommutativ ist, gilt dies nichtx
für die linke und rechte Seite der Operation das Gleiche. Sie müssten also eine andere Struktur verwenden, z. B. ein Listenpaar oder einen Binärbaum, um einen Algorithmus darzustellen,x
der sowohl rechts<>
als auch links angewendet werden kann.Beachten Sie auch, dass Sie mit der assoziativen Eigenschaft die Operationen auf andere nützliche Arten neu gruppieren können, z. B. durch Teilen und Erobern:
Oder automatische Parallelität, bei der jeder Thread einen Unterbereich auf einen Wert reduziert, der dann mit den anderen kombiniert wird.
quelle
pow(float x, unsigned n)
Version gcc.godbolt.org/z/eqwine optimiert nur mit-ffast-math
(was impliziert-fassociative-math
. Strenge Gleitkomma ist natürlich nicht assoziativ , weil verschiedene Provisorien = andere Rundung). Das führt ein1.0f * x
, das in der abstrakten C-Maschine nicht vorhanden war (aber immer ein identisches Ergebnis liefert). Dann sind n-1-Multiplikationen wiedo{res*=x;}while(--n!=1)
die rekursiven, so dass dies eine fehlende Optimierung ist.