Alternativen zur Defunktionalisierung

Die Defunktionalisierung ist eine Transformation, die erstmals 1972 von John C. Reynolds beschrieben wurde, um Funktionen höherer Ordnung zu eliminieren. Gibt es alternative Transformationen (effizienter?), Um Funktionen höherer Ordnung zu eliminieren?

Es gibt drei Hauptansätze (die mir bekannt sind) zur Implementierung von Funktionen höherer Ordnung. Defunktionalisierung, Verschlussumwandlung / Lambda-Heben und Kombinatoren.

Schreiben wir für den Typ einer Funktion höherer Ordnung von bis und für die Art der C-style Funktionszeiger von bis . (Wenn wir dies formalisieren wollten, könnten wir sagen, dass die Abstraktion von Funktionszeigern nur in der leeren Umgebung zulässig ist.)$A \Rightarrow B$$A$$B$$A \to B$$A$$B$

Die Abschlusskonvertierung ist die Idee, dass wir die Darstellung wählen Das ist typischerweise das Tupel, das die Werte freier Variablen an der Stelle von Lambda enthält Abstraktion. Es könnte jedoch auch eine andere Darstellung sein.

$$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ $E$

Das Lambda-Heben verfolgt einen etwas anderen und globaleren Ansatz, bei dem eine Lambda-Abstraktion nach außen in Bereiche gezogen wird, in denen freie Variablen als Parameter hinzugefügt werden, bis sie den Bereich der obersten Ebene erreicht. Während dies die Blockstrukturierung betrifft, erfordert die tatsächliche Handhabung von Funktionen höherer Ordnung das Zulassen einer Teilanwendung. Sie können dann teilweise angewendete Funktionen weitergeben, dies ist jedoch im Grunde die gleiche Darstellung wie die Konvertierung von Schließungen.

Wenn Sie Funktionszeiger entfernen möchten, können Sie die Defunktionalisierung verwenden, die in diesem speziellen Fall einfach eine Aufzählung erzeugt. Es gibt jedoch wenig Grund, dies zu tun, da Funktionszeiger in den meisten Assemblersprachen natürliche Konstrukte sind.

Der nächste Ansatz ist die Verwendung von Kombinatoren. Dies ist im Grunde dasselbe wie das Anheben von Lambda und die Verwendung von Teilanwendungen, außer dass ein fester Satz von Funktionen der obersten Ebene verwendet wird und alle anderen Funktionen als Kombinationen davon ausgedrückt werden. (Wenn sie keinen vordefinierten festen Satz von Kombinatoren haben, ist dies normalerweise nur ein Lambda-Lifting-basierter Ansatz, wie ich oben beschrieben habe.) Eine Funktion höherer Ordnung würde dann effektiv durch einen Wert in einem Datentyp unter Verwendung der Haskell-Syntax dargestellt wie folgt (mit SKKombinatoren ):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

Eine Darstellung, die eher der Wirbelsäulenrechnung ähnelt, ist für die Effizienz wahrscheinlich sinnvoller. Oder Sie könnten etwas tun wie:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA  

Das Anwenden einer Funktion höherer Ordnung wird in zwei Fälle aufgeteilt: Entweder wurde ein Kombinator vollständig angewendet und sollte daher ausgeführt werden, oder wir geben einen neuen Wert zurück, der die (Teil-) Anwendung darstellt.

Ich habe noch keine umfassende Umfrage durchgeführt, bin aber ziemlich zuversichtlich, dass Variationen der Closure-Konvertierung bei weitem die häufigste Implementierungsstrategie für Funktionen höherer Ordnung sind (daher werden sie häufig als "Closures" bezeichnet). Es hat die schönen Eigenschaften, modular, einfach und auch in seiner naiven Form einigermaßen effizient zu sein. Es bedarf einer guten Auswahl an Basiskombinatoren und einiger Klugheit, um kombinatorbasierte Ansätze für eine gute Leistung zu erhalten. Die Defunktionalisierung ist meines Erachtens nicht weit verbreitet, aber es gibt wenig Grund , Funktionszeiger nicht zu nutzen. In dem Maße, in dem Sie z. B. anstelle einer umfangreichen Fallanalyse eine Tabelle mit Funktionszeigern haben, in die Sie indizieren, haben Sie die Abschlusskonvertierung im Grunde neu erstellt.

Es gibt einige andere Ansätze. Eine davon ist die Instanziierung von Vorlagen, bei der im Grunde genommen die Reduktion wörtlich genommen und Begriffe einfach buchstäblich durch andere Begriffe ersetzt werden. Normalerweise erfordert dies das Vorhandensein und Bearbeiten einer abstrakten syntaxbaumartigen Struktur. Funktionen höherer Ordnung werden dann durch ihre (syntaktischen) Lambda-Terme oder "Vorlagen" davon dargestellt, was die Durchführung der Substitutionen vereinfachen kann.$\beta$