Utilisation de types d'unicité pour implémenter un parallélisme sûr

19

Je m'intéresse aux types d'unicité comme alternative aux monades dans les langages fonctionnels purs depuis un certain temps; malheureusement, il s'agit en quelque sorte d'un domaine ésotérique de la recherche CS et les ressources en ligne sur la programmation avec des types d'unicité sont rares.

Il est évident que les types d'unicité peuvent être utilisés pour implémenter des structures de données avec état comme les références ("boîtes") et les tableaux, bien que cela m'échappe comment vous pouvez implémenter d'autres structures de données avec état communes avec eux.

Est-il possible d'implémenter, par exemple, un verrouillage avec des types uniques? Les types d'unicité peuvent-ils être utilisés pour partager des données mutables entre les threads? Est-il possible d'utiliser des types uniques pour créer des primitives de synchronisation (comme les mutex), ou le passage de messages est-il nécessaire?

Ricky Stewart
la source
Pouvez-vous rendre votre question un peu plus précise? Par exemple, que savez-vous déjà sur le verrouillage avec des types uniques et où vos connaissances sont-elles insuffisantes?
Robert Harvey
> Que savez-vous déjà, par exemple, du verrouillage avec des types uniques? Je ne sais rien du verrouillage avec des types uniques - je ne sais pas vraiment comment le parallélisme sécurisé fonctionne avec des types uniques et j'aimerais savoir s'il y a sont des ressources sur le sujet.
Ricky Stewart
2
@RickyStewart: Vous connaissez probablement déjà Clean ( wiki.clean.cs.ru.nl/Clean ). Je voulais juste ajouter le lien car vous ne l'avez pas mentionné.
Giorgio
Je pense que vous devriez examiner les types linéaires pour le parallélisme. Les types d'unicité IIRC sont construits sur des types linéaires. Frank Pfenning a des trucs intéressants sur le sujet
Daniel Gratzer

Réponses:

2

Est-il possible d'implémenter, par exemple, un verrouillage avec des types uniques?

J'ai suivi le lien fourni par Robert Harvey et j'ai fait une lecture rapide. Je ne peux pas dire que j'ai tout compris ou que j'ai un niveau élevé de confiance que j'ai vraiment compris ce que je pense avoir compris, mais il me semble que tout le point de l'unicité externe et de l'immuabilité de référence est de ne pas avoir besoin de verrouillage.

Les approches modernes du multithreading essaient d'éviter le verrouillage car seuls des programmeurs hautement expérimentés peuvent écrire du code qui utilise le verrouillage, et même leur code est très sujet aux bogues. Si vous ajoutez en plus le fait que le code de verrouillage est pratiquement non testable, il devrait être évident que c'est une façon hautement indésirable de faire les choses, et toute solution visant à nous libérer du verrouillage promet de dire le moins.

La façon dont nous avons évité le verrouillage consiste à transmettre des messages, ce qui nécessite que les messages soient immuables. En gros, (à première vue), l'immuabilité de référence semble être une technique qui peut nous aider à garantir l'immuabilité sans avoir à construire réellement des types immuables, et l'unicité externe semble être une technique qui peut nous aider à assouplir localement l'exigence stricte d'immuabilité.

Les types d'unicité peuvent-ils être utilisés pour partager des données mutables entre les threads?

Le document ne l'a pas clairement énoncé, mais d'après ce que je comprends, un cluster d'objets extérieurement unique est sûr pour les threads parce qu'en quelque sorte (vraiment, comment? ), Il est garanti qu'il n'existe qu'une seule référence extérieure dans ce cluster d'objets, ce qui signifie que un thread recevant une telle référence peut traiter les objets référencés comme mutables sans avoir à se soucier qu'un autre thread puisse également les muter, car aucun autre thread ne peut possiblement avoir une autre référence. Je serais curieux de savoir comment une telle construction théorique peut être mise en œuvre et appliquée.

Est-il possible d'utiliser des types uniques pour créer des primitives de synchronisation (comme les mutex), ou le passage de messages est-il nécessaire?

Encore une fois, d'après ce que je comprends, les types externes uniques et l'immuabilité de référence sont censés rendre inutiles les verrous, les mutex et autres. La transmission des messages semble être la voie à suivre, et c'est bien.

Mike Nakis
la source