Structures de données en langage de programmation avec types linéaires

Supposons que nous ayons affaire à un langage de programmation prenant en charge les types linéaires (les termes de type linéaire peuvent être utilisés au maximum une fois, pour ainsi dire). Cela permet de traiter certains effets de calcul (comme la mutation, voire de changer le type de l'opérande) d'une manière problématique pour les langages dont les systèmes de types ne fonctionnent que sur des "vérités éternelles".

De nombreuses structures de données peuvent être caractérisées par des types inductifs (les listes et les arbres sont des exemples canoniques). Si nous ajoutons des types inductifs linéaires au mélange, nous pouvons également gérer des structures de données mutables.

Cependant, il n'est pas clair pour moi comment représenter les structures de données qui présentent le partage et les références cycliques dans un langage de programmation avec des types linéaires (des exemples de telles structures de données sont les DAG et autres graphiques, représentés par des listes d'adjacence ou autre chose, des listes cycliques). pouvons-nous faire cela? Si ce n'est pas possible, de quelle manière devrions-nous étendre le langage afin d'accueillir de telles structures de données?

L'exemple le plus impliqué que j'ai trouvé jusqu'à présent est une liste doublement liée. Y a-t-il d'autres exemples?

La linéarité n'est pas une contrainte suffisante pour définir une représentation avec état unique, et donc la réponse à votre question dépend de la façon dont vous interprétez la logique linéaire en termes d'état. Cela se reflétera généralement dans la façon dont vous devez interpréter le $!A$ modalité.

Si la sémantique voulue des références indique que tous les pointeurs sont des valeurs uniques (c'est-à-dire qu'il n'y a au plus qu'une seule référence à un objet), les dags et les structures de graphe ne sont pas exprimables, pour le type de raison tautologique qu'un dag peut contenir plusieurs références à le même objet. Dans ce cas doit être un calcul qui crée une nouvelle valeur de type A , puisque vous voulez des cartes Et .$!A$$A$ε A : ! A ⊸ $\delta_A : !A \multimap !A \otimes !A$$\epsilon_A : !A \multimap A$

Cependant, supposons que vous voulez pour représenter le partage . Ensuite, les objets peuvent être récupérés avec le comptage des références, avec les cartes et peuvent être réalisées comme des opérations qui ne font que bousculer les comptages de références. Dans ce cas, vous ne pouvez pas utiliser la linéarité pour supposer qu'il est toujours sûr de muter les valeurs, car il y a partage. Mais vous pouvez vous assurer que toute l'allocation de mémoire est explicite dans votre programme et qu'il n'y a pas de cycles dans le tas.δ A : ! Un ⊸ ! Un ⊗ ! A ε A : ! A ⊸ $!A$$\delta_A : !A \multimap !A \otimes !A$$\epsilon_A : !A \multimap A$

La plupart des implémentations pratiques de types linéaires n'utilisent aucune de ces deux interprétations. Au lieu de cela, les références sont considérées comme des entités librement reproductibles, et ce que nous suivons de manière linéaire sont en fait des capacités . Les capacités ne sont pas des valeurs d'exécution; ce sont des entités purement conceptuelles qui sont censées représenter l'autorisation d'accéder à une référence. L'idée est que vous programmez dans un style de passage d'autorisations, et donc même s'il existe de nombreuses références au même objet, une lecture ou une modification d'un élément d'état ne peut se produire que si vous avez également la possibilité d'y accéder. Et puisque la capacité est linéaire, vous savez que vous seul pouvez la changer.

$$\array{ \mathsf{new} & : & \forall \alpha. \;\alpha \multimap \exists c : \iota. \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{get} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \multimap \alpha \otimes \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{set} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \otimes \alpha \multimap \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{copy} & : & \forall \alpha, c:\iota.\; \mathsf{ref}(\alpha,c) \multimap \mathsf{ref}(\alpha,c) \otimes \mathsf{ref}(\alpha,c) }$$

Dans l'API esquissée ci-dessus, s'étend sur , certains domaines d'indices au moment de la compilation et étend sur les types. Nous avons un type qui est une capacité indexée par , et un type , qui est un type de références à accessible par une capacité . L'appel de et sur une référence nécessite la capacité , et l'appel de crée une nouvelle référence et une nouvelle capacité partageant un index commun. Cependant,ι α c a p ( c ) c r e f ( α , c ) α c g e t s e t c n e w c o p $c$$\iota$$\alpha$$\mathsf{cap}(c)$$c$$\mathsf{ref}(\alpha, c)$$\alpha$$c$$\mathsf{get}$$\mathsf{set}$$c$$\mathsf{new}$$\mathsf{copy}$-une référence ne nécessite aucun accès à aucune capacité, donc n'importe qui peut copier une référence tant qu'il n'y regarde pas.