Polymorphisme de rang supérieur sur les types sans boîte

10

J'ai une langue dans laquelle les types sont déballés par défaut, avec l'inférence de type basée sur Hindley – Milner. Je voudrais ajouter un polymorphisme de rang supérieur, principalement pour travailler avec des types existentiels.

Je pense que je comprends comment vérifier ces types, mais je ne sais pas quoi faire lors de la compilation. Actuellement, je compile des définitions polymorphes en générant des spécialisations, un peu comme les modèles C ++, afin qu'elles puissent fonctionner avec des valeurs non encadrées. Par exemple, étant donné une définition de f<T>, si le programme invoque uniquement f<Int32>et f<Char>, alors seules ces spécialisations apparaissent dans le programme compilé. (Je suppose que la compilation du programme entier pour l'instant.)

Mais lorsque je passe une fonction polymorphe en argument, je ne vois pas comment générer statiquement la bonne spécialisation, car la fonction pourrait être sélectionnée au moment de l'exécution. Dois-je pas d'autre choix que d'utiliser une représentation encadrée? Ou existe-t-il un moyen de contourner le problème?

Ma première pensée a été de coder en quelque sorte le polymorphisme de rang n en rang 1, mais je ne crois pas que ce soit possible en général parce qu'une formule en logique constructive n'a pas nécessairement une forme normale prénex.

Jon Purdy
la source
Une alternative consiste à réduire la quantité de boxe nécessaire en stockant les bitmaps pour lesquels les arguments d'une fonction et les mots en mémoire sont des pointeurs. Ensuite, une fonction / structure polymorphe est en fait polymorphe sur un pointeur ou un mot de données arbitraire, et les structures peuvent stocker leur dernier champ (même s'il est polymorphe) en ligne. Ces bitmaps peuvent également être utilisés par le GC pour éviter d'avoir à utiliser des mots-clés pour les types sans somme.
fread2281
@ fread2281: J'avais l'habitude de faire quelque chose comme ça dans une ancienne version de la langue. Je ne génère pas actuellement de balises pour les types sans somme, et il n'y a pas de GC. Je pense que c'est également compatible avec l'approche de Neel K.
Jon Purdy

Réponses:

6

J'y ai réfléchi un peu. Le problème principal est qu'en général, nous ne savons pas quelle est la valeur d'une valeur de type polymorphe. Si vous ne disposez pas de ces informations, vous devez les obtenir d'une manière ou d'une autre. La monomorphisation obtient ces informations pour vous en spécialisant le polymorphisme. La boxe obtient ces informations pour vous en mettant tout dans une représentation de taille connue.

Une troisième alternative est de garder une trace de ces informations dans les types. Fondamentalement, ce que vous pouvez faire est d'introduire un type différent pour chaque taille de données, puis des fonctions polymorphes peuvent être définies sur tous les types d'une taille particulière. Je vais esquisser un tel système ci-dessous.

Sortesκ:: =nConstructeurs de typesUNE:: =une:κ.UNE|α|UNE×B|UNE+B|UNEB|reFUNE|Pune(k)|μα:κ.UNE

Ici, l'idée de haut niveau est que le type d'un type vous indique le nombre de mots nécessaires pour disposer un objet en mémoire. Pour une taille donnée, il est facile d'être polymorphe sur tous les types de cette taille particulière. Étant donné que chaque type, même polymorphe, a toujours une taille connue, la compilation n'est pas plus difficile que pour C.

α:nΓΓα:nΓ,α:nUNE:mΓα:n.UNE:m
ΓUNE:nΓB:mΓUNE×B:n+mΓUNE:nΓB:nΓUNE+B:n+1
ΓUNE:mΓB:nΓUNEB:1ΓUNE:nΓreFUNE:1
ΓPune(k):kΓ,α:nUNE:nΓμα:n.UNE:n

UNE×BUNEB

Les références sont intéressantes - les pointeurs sont toujours un mot, mais ils peuvent pointer vers des valeurs de n'importe quelle taille. Cela permet aux programmeurs d' implémenter le polymorphisme à des objets arbitraires par boxe, mais ne les oblige pas à le faire. Enfin, une fois que les tailles explicites sont en jeu, il est souvent utile d'introduire un type de remplissage, qui utilise de l'espace mais ne fait rien. (Donc, si vous voulez prendre l'union disjointe d'un int et d'une paire d'entiers, vous devrez ajouter un remplissage au premier int, afin que la disposition de l'objet soit uniforme.)

Les types récursifs ont la règle de formation standard, mais notez que les occurrences récursives doivent avoir la même taille, ce qui signifie que vous devez généralement les coller dans un pointeur pour que le tri fonctionne. Par exemple, le type de données de liste pourrait être représenté comme

μα:1.reF(Pune(2)+jent×α)

Donc, cela pointe vers une valeur de liste vide, ou une paire d'int et un pointeur vers une autre liste liée.

La vérification de type pour des systèmes comme celui-ci n'est pas non plus très difficile; l'algorithme de mon article ICFP avec Joshua Dunfield, Typechecking bidirectionnel complet et facile pour le polymorphisme de rang supérieur s'applique à ce cas avec presque aucun changement.

Neel Krishnaswami
la source
Cool, je pense que cela couvre parfaitement mon cas d'utilisation. J'étais conscient d'utiliser des types pour raisonner sur les représentations de valeur (comme GHC *vs #), mais je n'avais pas envisagé de le faire de cette façon. Il semble raisonnable de restreindre les quantificateurs de rang supérieur à des types de taille connue, et je pense que cela me permettrait également de générer des spécialisations par taille statiquement, sans avoir besoin de connaître le type réel. Maintenant, il est temps de relire ce document. :)
Jon Purdy
1

Cela semble être plus proche d'un problème de compilation que d'un problème "d'informatique théorique", il vaut donc mieux demander ailleurs.

Dans le cas général, en effet, je pense qu'il n'y a pas d'autre solution que d'utiliser une représentation encadrée. Mais je m'attends également à ce que, dans la pratique, il existe de nombreuses alternatives différentes, selon les spécificités de votre situation.

Par exemple, la représentation de bas niveau des arguments non encadrés peut généralement être classée en très peu d'alternatives, par exemple entier ou similaire, virgule flottante ou pointeur. Donc, pour une fonction f<T>, vous n'avez peut-être vraiment besoin que de générer 3 implémentations différentes non encadrées et vous pouvez représenter celle polymorphe comme un tuple de ces 3 fonctions, donc l'instanciation de T en Int32 ne fait que sélectionner le premier élément du tuple, ...

Stefan
la source
Merci de votre aide. Je ne savais pas vraiment où demander, car un compilateur s'étend de la théorie de haut niveau à l'ingénierie de bas niveau, mais je pensais que les gens d'ici auraient des idées. Il semble que la boxe soit en effet l'approche la plus flexible ici. Après avoir lu votre réponse et y avoir réfléchi davantage, la seule autre solution raisonnable que j'ai pu trouver est de renoncer à une certaine flexibilité et d'exiger que les arguments polymorphes soient connus statiquement, par exemple en les passant comme paramètres de type eux-mêmes. Ce sont des compromis tout le long. : P
Jon Purdy
4
La question de l'OP contient des problèmes TCS parfaitement valides, comme comment faire l'inférence de type lorsque Damas-Hindley-Milner est étendu avec des types de rang supérieur. En général, le polymorphisme de rang 2 a une inférence de type décidable, mais pour le rang k> l'inférence de type 2 est indécidable. Que la restriction Damas-Hindley-Milner change cela, je ne sais pas. Enfin, à peu près tout ce que font les compilateurs modernes devrait faire partie de TCS, mais ce n'est généralement pas parce que les implémenteurs du compilateur sont en avance sur les théoriciens.
Martin Berger