Hat jemand die polymorphe Defunktionalisierung von Pottier und Gauthier in einem modularen Compiler verwendet?

15

Die Defunktionalisierung ist eine Programmtransformation, die Programme höherer Ordnung in Programme erster Ordnung umwandelt. Die Idee ist, dass es bei einem gegebenen Programm nur endlich viele Lambda-Abstraktionen gibt, sodass Sie jedes Lambda durch eine ID und jede Funktionsanwendung durch einen Aufruf einer Apply-Prozedur ersetzen können, die auf diese ID verzweigt. Dies wird manchmal verwendet in Compiler für funktionale Sprachen, aber seine Anwendbarkeit ist dadurch begrenzt , dass Entfunktionalisierung ist ein Vollprogramm - Transformation (statisch alle Funktionen des Programms kennen müssen), und so nur ganz-Programm Compiler nutzen es.

Allerdings Pottier und Gauthier haben einen gegebenen eine polymorphe typisierten Entfunktionalisierung Algorithmus eine anspruchsvolleres Typisierung Einbeziehung GADTs verwenden. Aufgrund ihrer Kodierung ist es nun möglich, ihrem Lambda-Datentyp einen Sammelbegriff hinzuzufügen, der kein Tag ist, aber eine Funktion höherer Ordnung enthält. Dies bedeutet, dass es möglich sein sollte, ihre Codierung zu verwenden, um sie modulweise zu defunktionalisieren.

Hat jemand dies getan und mich auf einen Compiler hingewiesen, der diese Idee verwendet? (Toy Compiler sind in Ordnung und sogar bevorzugt.)

Neel Krishnaswami
quelle

Antworten:

6

Ein Ansatz wird von beschrieben

Georgios Fourtounis und Nikolaos S. Papaspyrou. 2013. Unterstützung der separaten Kompilierung in einem Compiler zur Defunktionalisierung. SLATE 2013.

Als @ gasche erwähnt:

Eine andere Herangehensweise an das Problem wäre, zu berücksichtigen, dass jedes Modul seinen eigenen Typ "defunktionalisierter Funktionen" und Dispatcher / Handler definieren kann.

Sie können diese Typen und Handler mit einem speziellen Linker "verknüpfen". Im Gegensatz zur Verwendung offener Datentypen verketten Sie die Liste der Konstruktoren und die case-Funktionen. Der Linker muss jedoch Fälle für Teilanwendungen hinzufügen: Ohne die Analyse des gesamten Programms können Sie nicht vorhersagen, welche Teilanwendungen für welche Funktion verwendet werden können. Sie fügen daher alle Fälle hinzu. Eine -ary-Funktion kann teilweise auf Argumente angewendet werden (mit ) und erzeugt eine Funktion der Arität , die teilweise erneut angewendet werden kann.nich0<ich<nn-ich

Blaisorblade
quelle
4

Aufgrund ihrer Kodierung ist es nun möglich, ihrem Lambda-Datentyp einen Sammelbegriff hinzuzufügen, der kein Tag ist, aber eine Funktion höherer Ordnung enthält. Dies bedeutet, dass es möglich sein sollte, ihre Codierung zu verwenden, um sie modulweise zu defunktionalisieren.

Könnten Sie etwas genauer erläutern, was Sie hier meinen? Ich verstehe nicht, wie das Hinzufügen eines Basisfalls (wäre das der Datentyp, der Mustervergleich der Dispatching-Funktion oder beides?) Die Modularität in der von Ihnen beschriebenen Weise unterstützt. übrigens, warum meinst du das genau mit "Modul für Modul"?

Ich kann mir einen "Basisfall" vorstellen, der innerhalb eines bestimmten Moduls / Programms zur selektiven Defunktionalisierung verwendet wird: Sie hätten einen zusätzlichen Konstruktor zu Ihrem reifizierten Funktionstyp, der kein Tag ist, sondern einfach alle 'a -> 'bFunktionen einbettet , so dass eine Funktion gepackt wird In diesem Konstruktor würde die Defunktionalisierung verhindert, anstatt ihm ein reified-Tag zuzuweisen.

Eine andere Herangehensweise an das Problem wäre, zu berücksichtigen, dass jedes Modul seinen eigenen Typ "defunktionalisierter Funktionen" und Dispatcher / Handler definieren kann. Funktionen aus dem Modul M1müssten typisiert M1.arrowund angewendet werden M1.apply, usw. Obwohl dies für die Verwendung der Funktionen erster Ordnung gut funktioniert, sehe ich nicht recht gut, wie Sie sie auf Funktionen höherer Ordnung erweitern könnten (was nicht erforderlich sein sollte wissen, woher ihr Funktionsargument kommt): Wenn Sie eine Funktion mit ihrem Dispatcher bündeln, betreten Sie das Reich der indirekten Funktionsaufrufe erneut.

Schließlich wird in dem von Ihnen zitierten Artikel kurz auf den Gesamtprogramm-Ansatz im Vergleich zum modularen Ansatz eingegangen, aber ich verstehe nicht, in welchem ​​Zusammenhang er mit Ihrem Vorschlag steht. Was sie beschreiben, wird in Form von "offenen Erweiterungen" sowohl von Funktionen als auch von Datentypen ausgedrückt (Funktionen und Typen, die über mehrere unabhängige Module hinweg definiert werden könnten). Dies ist hauptsächlich eine ML-Methode, um die Tatsache zu beschreiben, dass Sie die Kombination von Analyse / Transformation von unabhängigen Modulen zum Zeitpunkt der Verknüpfung verschieben können, um die Notwendigkeit einer Ganzprogrammtransformation zu lockern.

gasche
quelle