Was sind Superkombinatoren und konstante Anwendungsformen?

Question

Ich kämpfe mit was Superkombinatoren sind:

Ein Supercombinator ist entweder eine Konstante oder ein Kombinator, der nur Supercombinatoren als Subtexpressionen enthält.

Und auch mit was Konstante Anwendungsformen sind:

Jeder Super -Kombinator, der keine Lambda -Abstraktion ist. Dies umfasst wirklich konstante Ausdrücke wie 12, ((+) 1 2), [1,2,3] sowie teilweise angewandte Funktionen wie ((+) 4). Beachten Sie, dass dieses letzte Beispiel unter ETA -Abstraktion zu x -> (+) 4 x äquivalent ist, was kein CAF ist.

Das macht mir einfach keinen Sinn! Nicht ((+) 4) Genauso "wirklich konstant" wie 12? CAFs klingen nach Werten für meinen einfachen Verstand.

Answer 1

Diese Haskell -Wiki -Seiten, auf die Sie verweisen, sind alt, und ich denke leider geschrieben. Besonders unglücklich ist, dass sie CAFs und Supercombinatoren durcheinander bringen. Supercombinatoren sind interessant, aber nicht mit GHC zusammen. CAFs sind immer noch ein Teil von GHC und können ohne Bezug auf Supercombinatoren verstanden werden.

---

Also beginnen wir mit Supercombinators. Kombinatoren stammen aus Kombinationslogik, und bestehen in der Verwendung hier aus Funktionen, die nur die Werte anwenden, die in der einen oder anderen Form einander übergeben wurden - dh sie kombinieren ihre Argumente. Die berühmtesten Kombinators sind S, k und ich, die zusammengenommen wurden, sind abgeschlossen. Supercombinatoren sind in diesem Zusammenhang Funktionen, die nur von Werten, Kombinators und anderen Supercombinatoren erstellt wurden. Daher kann jeder Supercombinator durch Substitution in einen einfachen alten Kombinator erweitert werden.

Einige Compiler für funktionale Sprachen (nicht GHC!) Verwenden Kombinatoren und Supercombinatoren als Zwischenschritte in der Zusammenstellung. Wie bei jeder ähnlichen Compiler -Technologie ist der Grund dafür, eine Optimierungsanalyse zuzugeben, die in einer so vereinfachten, minimalen Sprache leichter durchgeführt wird. Eine solche Kernsprache auf Supercombinators ist Edwin Brady's Epos.

---

Konstante Anwendungsformen sind etwas anderes ganz. Sie sind ein bisschen subtiler und haben ein paar Gotchas. Die Art und Weise, sie zu sehen, ist ein Aspekt der Compiler -Implementierung ohne separate semantische Bedeutung, jedoch mit einem potenziell tiefgreifenden Einfluss auf die Laufzeitleistung. Das Folgende ist möglicherweise keine perfekte Beschreibung eines CAF, aber es wird versuchen, meine Intuition dessen zu vermitteln, was man ist, da ich keine gesehen habe Ja wirklich Gute Beschreibung irgendwo anders für mich, von denen ich kribte. Das saubere "maßgebliche" Beschreibung im GHC -Kommentar Wiki liest wie folgt:

Konstante Anwendungsformen oder kurze CAFs sind in einem Programm definierte Werte auf höchster Ebene. Im Wesentlichen sind sie Objekte, die zur Laufzeit nicht dynamisch zugewiesen werden, sondern sind Teil der statischen Daten des Programms.

Das ist ein guter Anfang. Reine, funktionale, faule Sprachen können in gewissem Sinne als Graph -Reduktionsmaschine betrachtet werden. Das erste Mal, dass Sie den Wert eines Knotens verlangen, der seine Bewertung erzwingt, die wiederum die Werte von Subnoden usw. verlangen kann, wird ein Knoten bewertet, der resultierende Wert bleibt herum (obwohl dies nicht der Fall ist haben Um zu bleiben - da es sich um eine reine Sprache handelt, konnten wir die Subnoden immer leben und ohne semantische Wirkung neu berechnen). Ein CAF ist in der Tat nur ein Wert. Aber im Zusammenhang hat eine besondere Art von Wert - eine, die der Compiler bestimmen kann, eine Bedeutung, die völlig von seinen Unternoten abhängt. Das heißt:

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

Warum kümmern wir uns also darum, ob es CAFs sind? Grundsätzlich, weil wir manchmal wirklich wirklich etwas neu berechnen wollen (zum Beispiel ein memotierbares!) Und also sicherstellen möchten, dass es richtig geteilt wird. Andere Male wir wirklich tun Ich möchte etwas neu berechnen (z. B. eine riesige, leicht zu erzeugende Liste - wie die Natur wie das, über die wir nur übergehen) und sie nicht für immer in Erinnerung bleiben. Eine Kombination aus Benennung von Dingen und Binden von Los oder Schreiben inline usw. lässt uns diese Art von Dingen typischerweise auf natürliche, intuitive Weise angeben. Gelegentlich ist der Compiler jedoch intelligenter oder dümmer als wir erwarten, und etwas, von dem wir glauben, dass er nur einmal berechnet werden sollte, wird immer neu berechnet oder etwas, an das wir nicht hängen wollen, um als CAF herauszuheben. Dann müssen wir Dinge genauer durchdenken. Sehen Sie sich diese Diskussion an, um eine Vorstellung von einigen der Schwärmen zu bekommen: Ein guter Weg, um "Teilen" zu vermeiden?

Übrigens, ich fühle mich nicht dem vor, aber jeder, der gerne so viel von dieser Antwort entgegennimmt, wie er versuchen möchte, sie in die vorhandenen Haskell -Wiki -Seiten zu integrieren und sie zu verbessern/zu verbessern.

Answer 2

Matt hat Recht, als die Definition verwirrend ist. Es ist sogar widersprüchlich. Ein CAF ist definiert als:

Jeder Super -Kombinator, der keine Lambda -Abstraktion ist. Dies beinhaltet wirklich ständige Ausdrücke wie z. 12, ((+) 1 2), [1,2,3] sowie teilweise angewandte Funktionen wie z. ((+) 4).

Somit, ((+) 4) wird als CAF angesehen. Aber im nächsten Satz ist uns gesagt, dass es etwas entspricht, das kein CAF ist:

Dieses letzte Beispiel entspricht der ETA -Abstraktion zu \ x -> (+) 4 x Das ist kein CAF.

Es wäre sauberer, teilweise angewandte Funktionen auszuschließen, weil sie Lambda -Abstraktionen entsprechen.