Was ist Fusion in Haskell?

Im Allgemeinen bezieht sich Fusion auf Transformationen, deren Zweck es ist, zwischenliegende Datenstrukturen loszuwerden. Sie fusionieren Funktionsaufrufe, die zu verschwenderischen Speicherzuweisungen führen, zu etwas effizienterem. Dies ist eigentlich IMO eine der größten Anwendungen von Haskell ist rein. Und Sie müssen so gut wie nichts tun, um es zu bekommen, es kommt kostenlos durch den GHC-Compiler.

Haskell ist rein

Da Haskell rein ist, bekommen wir diese referentielle Transparenz , die (aus dem Link) "Ausdruck immer" bedeutet bewertet in jedem Zusammenhang das gleiche Ergebnis " ¹ . Das bedeutet, dass ich sehr allgemeine Programmebenenmanipulationen durchführen kann, ohne zu ändern, was das Programm tatsächlich ausgibt. Zum Beispiel, auch ohne zu wissen, was x , y , z und w sind, weiß ich immer, dass

wird dasselbe wie

aber die zweite wird in der Praxis weniger Speicherzuweisungen enthalten (da x ++ y das gesamte Präfix der Ausgabeliste neu zuweisen muss).

Regeln neu schreiben

Tatsächlich gibt es eine ganze Menge solcher Optimierungen, und da Haskell rein ist, können wir im Grunde einfach ganze Ausdrücke bewegen (indem wir x , y , z oder w für aktuelle Listen oder Ausdrücke, die im obigen Beispiel zu Listen ausgewertet werden, ändert nichts). Dies wird ein ziemlich mechanischer Prozess.

Außerdem stellt sich heraus, dass Sie viele Äquivalenzen für Funktionen höherer Ordnung finden können ( Sätze kostenlos! ). Zum Beispiel

egal was f , g und xs sind (die beiden Seiten sind semantisch gleich). Während die beiden Seiten dieser Gleichung die gleiche Ausgabe erzeugen, ist die linke Seite immer schlechter in der Effizienz: Es wird schließlich Platz für eine Zwischenliste map g xs zugewiesen, die sofort weggeworfen wird. Wir möchten dem Compiler sagen, wenn er auf etwas wie map f (map g xs) stößt, ersetze es durch map (f . g) xs . Und das ist für GHC die Neuschreibungsregeln :

Die f , g und xs können mit allen Ausdrücken verglichen werden, nicht nur mit Variablen (also wird etwa map (+1) (map (*2) ([1,2] ++ [3,4])) in map ((+1) . (*2)) ([1,2] ++ [3,4]) umgewandelt. (Es scheint keine gute Möglichkeit zu sein, nach Umschreibregeln zu suchen , also habe ich ein Liste ). Dieses Dokument erläutert die Motivation und Funktionsweise der GHC-Neufassungsregeln.

So optimiert GHC map ?

Eigentlich nicht ganz. Das Ding oben ist Abkürzungsfusion . Der Name impliziert den Nachteil: Es skaliert nicht so gut und ist nervig zu debuggen. Sie müssen am Ende eine Menge Ad-hoc-Regeln für alle Vereinbarungen der gleichen gemeinsamen Funktionen schreiben. Dann hoffen Sie, dass die wiederholte Anwendung von Umschreibungsregeln Ihre Ausdrücke schön vereinfacht.

Es stellt sich heraus, dass wir in einigen Fällen sogar noch besser werden können, indem wir unsere Regeln für das Umschreiben so organisieren, dass wir ein mittleres normales Formular erstellen und dann Regeln für dieses Zwischenformular haben. Auf diese Weise beginnen wir, "heiße" Pfade von Rewrite-Regeln zu erhalten.

Das wahrscheinlich fortschrittlichste dieser Systeme ist stream Fusion , die auf koinduktive Sequenzen abzielt (im Grunde genommen faule Sequenzen wie Listen). Schauen Sie sich diese These und dieses Papier (das ist eigentlich so ziemlich das vector Paket ist implementiert). Zum Beispiel wird Ihr Code in vector zuerst in eine Zwischenform umgewandelt, die Stream s und Bundle s enthält, wird in dieser Form optimiert und dann in Vektoren zurücktransformiert.

Und ... Data.Text ?

Data.Text verwendet die Stream-Fusion, um die Anzahl der Speicherzuweisungen zu minimieren, die auftreten (ich denke, das ist besonders wichtig für die strikte Variante). Wenn Sie die Quelle aufrufen, werden Sie sehen Sie, dass die Funktionen, die der Fusion unterliegen, tatsächlich Stream s zum größten Teil (sie haben die allgemeine Form unstream . (stuff manipulating stream) . stream ) und es gibt eine Menge RULES Pragmas für die Umwandlung von Stream s. Am Ende jede Kombination von Diese Funktionen sollen fusioniert werden, so dass nur eine Zuweisung stattfinden muss.

Also, was muss ich für meine tägliche Programmierung mitnehmen?

Der einzige Weg, um zu wissen, wann Ihr Code einer Fusion unterliegt, ist ein gutes Verständnis der involvierten Rewrite-Regeln und Sie verstehen gut, wie GHC funktioniert. Das heißt, es gibt eine Sache, die Sie tun sollten: versuchen Sie, nicht-rekursive Funktionen höherer Ordnung zu verwenden, wenn dies möglich ist, da diese (zumindest jetzt, aber im Allgemeinen immer mehr) einfach sein können verschmolzen.