Höherrangiger Polymorphismus gegenüber Typen ohne Box

10

Ich habe eine Sprache, in der Typen standardmäßig deaktiviert sind, wobei die Typinferenz auf Hindley-Milner basiert. Ich möchte einen höherrangigen Polymorphismus hinzufügen, hauptsächlich für die Arbeit mit existenziellen Typen.

Ich glaube, ich verstehe, wie man diese Typen überprüft , bin mir aber nicht sicher, was ich beim Kompilieren tun soll. Derzeit kompiliere ich polymorphe Definitionen, indem ich Spezialisierungen generiere, ähnlich wie C ++ - Vorlagen, damit sie mit Werten ohne Box arbeiten können. f<T>Wenn bei einer Definition von beispielsweise , wenn das Programm nur f<Int32>und aufruft f<Char>, nur diese Spezialisierungen im kompilierten Programm angezeigt werden. (Ich gehe vorerst von einer Zusammenstellung des gesamten Programms aus.)

Wenn ich jedoch eine polymorphe Funktion als Argument übergebe, sehe ich nicht, wie ich die richtige Spezialisierung statisch generieren kann, da die Funktion zur Laufzeit ausgewählt werden könnte. Habe ich keine andere Wahl, als eine Boxdarstellung zu verwenden? Oder gibt es einen Weg, um das Problem zu umgehen?

Mein erster Gedanke war, Rang- n- Polymorphismus irgendwie als Rang 1 zu kodieren , aber ich glaube nicht, dass dies im Allgemeinen möglich ist, da eine Formel in der konstruktiven Logik nicht unbedingt eine Prenex-Normalform hat.

Jon Purdy
quelle
Eine Alternative besteht darin, die Menge an Boxen zu reduzieren, die durch Speichern von Bitmaps benötigt wird, für die Argumente einer Funktion und Wörter im Speicher Zeiger sind. Dann ist eine polymorphe Funktion / Struktur über einen Zeiger oder ein beliebiges Datenwort tatsächlich polymorph , und Strukturen können ihr letztes Feld (auch wenn es polymorph ist) inline speichern. Diese Bitmaps können auch vom GC verwendet werden, um die Notwendigkeit von Tagwords für Nicht-Summen-Typen zu vermeiden.
fread2281
@ fread2281: Ich habe so etwas in einer älteren Version der Sprache gemacht. Ich generiere derzeit keine Tags für Nicht-Summen-Typen und es gibt keine GC. Ich denke, das ist auch mit dem Ansatz von Neel K vereinbar.
Jon Purdy

Antworten:

6

Ich habe ein bisschen darüber nachgedacht. Das Hauptproblem ist, dass wir im Allgemeinen nicht wissen, wie groß der Wert des polymorphen Typs ist. Wenn Sie diese Informationen nicht haben, müssen Sie sie irgendwie bekommen. Die Monomorphisierung erhält diese Informationen für Sie, indem sie sich auf den Polymorphismus spezialisiert. Boxing erhält diese Informationen für Sie, indem es alles in eine Darstellung bekannter Größe bringt.

Eine dritte Alternative besteht darin, diese Informationen in den Arten zu verfolgen. Grundsätzlich können Sie für jede Datengröße eine andere Art einführen, und dann können polymorphe Funktionen für alle Typen einer bestimmten Größe definiert werden. Ich werde ein solches System unten skizzieren.

Kindsκ::=nType constructorsA::=a:κ.A|α|A×B|A+B|AB|refA|Pad(k)|μα:κ.A

Hier besteht die übergeordnete Idee darin, dass die Art eines Typs angibt, wie viele Wörter erforderlich sind, um ein Objekt im Speicher auszulegen. Für jede gegebene Größe ist es einfach, über alle Arten dieser bestimmten Größe polymorph zu sein. Da jeder Typ - auch polymorphe - immer noch eine bekannte Größe hat, ist die Kompilierung nicht schwieriger als bei C.

α:nΓΓα:nΓ,α:nA:mΓα:n.A:m
ΓA:nΓB:mΓA×B:n+mΓA:nΓB:nΓA+B:n+1
ΓA:mΓB:nΓAB:1ΓA:nΓrefA:1
ΓPad(k):kΓ,α:nA:nΓμα:n.A:n

A×BAB

Referenzen sind interessant - Zeiger sind immer ein Wort, können aber auf Werte beliebiger Größe verweisen. Auf diese Weise können Programmierer implementieren Polymorphismus auf beliebige Objekte durch Boxen, aber nicht erforderlich , sie so zu tun. Sobald explizite Größen im Spiel sind, ist es oft nützlich, einen Polstertyp einzuführen, der Platz beansprucht, aber nichts tut. (Wenn Sie also die disjunkte Vereinigung eines int und eines Int-Paares verwenden möchten, müssen Sie das erste int auffüllen, damit das Objektlayout einheitlich ist.)

Rekursive Typen haben die Standardformationsregel. Beachten Sie jedoch, dass rekursive Vorkommen dieselbe Größe haben müssen. Dies bedeutet, dass Sie sie normalerweise in einen Zeiger stecken müssen, damit die Sortierung funktioniert. Beispielsweise könnte der Listendatentyp als dargestellt werden

μα:1.ref(Pad(2)+int×α)

Dies zeigt also auf einen leeren Listenwert oder ein Paar aus einem int und einem Zeiger auf eine andere verknüpfte Liste.

Die Typprüfung für solche Systeme ist ebenfalls nicht sehr schwierig. Der Algorithmus in meinem ICFP- Artikel mit Joshua Dunfield, Vollständige und einfache bidirektionale Typprüfung für höherrangigen Polymorphismus, gilt für diesen Fall nahezu unverändert .

Neel Krishnaswami
quelle
Cool, ich denke, das deckt meinen Anwendungsfall ordentlich ab. Ich war mir bewusst, dass ich Arten verwendete, um über Wertrepräsentationen zu *argumentieren (wie GHC's vs. #), hatte aber nicht darüber nachgedacht, dies so zu tun. Es erscheint vernünftig, höherrangige Quantifizierer auf Typen bekannter Größe zu beschränken, und ich denke, dies würde es mir auch ermöglichen, statisch Spezialisierungen pro Größe zu generieren, ohne den tatsächlichen Typ kennen zu müssen. Jetzt ist es Zeit, das Papier noch einmal zu lesen. :)
Jon Purdy
1

Dies scheint eher einem Kompilierungsproblem als einem "theoretischen Informatik" -Problem zu entsprechen, daher ist es wahrscheinlich besser, wenn Sie anderswo nachfragen.

Im allgemeinen Fall gibt es meiner Meinung nach keine andere Lösung als die Verwendung einer Boxed-Darstellung. Ich erwarte aber auch, dass es in der Praxis viele verschiedene alternative Optionen gibt, abhängig von den Besonderheiten Ihrer Situation.

Beispielsweise kann die Darstellung von Argumenten ohne Box auf niedriger Ebene normalerweise in sehr wenige Alternativen eingeteilt werden, z. B. Ganzzahl oder ähnlich, Gleitkomma oder Zeiger. Für eine Funktion f<T>müssen Sie möglicherweise nur drei verschiedene Implementierungen ohne Box generieren und können die polymorphe als Tupel dieser drei Funktionen darstellen. Wenn Sie also T zu Int32 instanziieren, wählen Sie einfach das erste Element des Tupels aus, ...

Stefan
quelle
Danke für Ihre Hilfe. Ich war mir nicht sicher, wo ich fragen sollte, da ein Compiler von der High-Level-Theorie bis zum Low-Level-Engineering reicht, aber ich dachte, die Leute hier hätten einige Ideen. Es sieht so aus, als wäre Boxen hier tatsächlich der flexibelste Ansatz. Nachdem ich Ihre Antwort gelesen und mehr darüber nachgedacht habe, besteht die einzige vernünftige Lösung, die ich finden konnte, darin, auf Flexibilität zu verzichten und zu verlangen, dass polymorphe Argumente statisch bekannt sind, z. B. indem sie selbst als Typparameter übergeben werden. Es sind Kompromisse bis ganz nach unten. : P
Jon Purdy
4
Die Frage des OP enthält vollkommen gültige TCS-Probleme, wie z. B. die Typinferenz, wenn Damas-Hindley-Milner um Typen mit höherem Rang erweitert wird. Im Allgemeinen hat der Rang-2-Polymorphismus eine entscheidbare Typinferenz, aber für Rang k> 2 ist die Typinferenz nicht entscheidbar. Ob die Damas-Hindley-Milner-Beschränkung dies ändert, weiß ich nicht. Schließlich sollte fast alles, was moderne Compiler tun, Teil von TCS sein, aber normalerweise nicht, weil die Compiler-Implementierer den Theoretikern voraus sind.
Martin Berger