Verwendung von Eindeutigkeitstypen zur Implementierung einer sicheren Parallelität

19

Ich interessiere mich seit einiger Zeit für Einzigartigkeitstypen als Alternative zu Monaden in reinen funktionalen Sprachen. Leider ist dies eine Art esoterischer Bereich der CS-Forschung, und Online-Ressourcen zum Programmieren mit Eindeutigkeitstypen sind rar gesät.

Es ist offensichtlich, wie Eindeutigkeitstypen verwendet werden können, um statusbezogene Datenstrukturen wie Referenzen ("Boxen") und Arrays zu implementieren, obwohl es mir entgeht, wie Sie andere gängige statusbezogene Datenstrukturen mit ihnen implementieren können.

Ist es beispielsweise möglich, Sperren mit eindeutigen Typen zu implementieren? Können Eindeutigkeitstypen verwendet werden, um veränderbare Daten über Threads hinweg gemeinsam zu nutzen? Ist es möglich, eindeutige Typen zum Erstellen von Synchronisationsprimitiven (wie Mutexe) zu verwenden, oder ist eine Nachrichtenübermittlung erforderlich?

Ricky Stewart
quelle
Können Sie Ihre Frage etwas präzisieren? Was wissen Sie zum Beispiel bereits über das Sperren mit eindeutigen Typen und wo ist Ihr eigenes Wissen unzureichend?
Robert Harvey
> Was wissen Sie zum Beispiel bereits über das Sperren mit eindeutigen Typen? Ich weiß nichts über das Sperren mit eindeutigen Typen. Ich weiß nicht wirklich, wie sichere Parallelität mit eindeutigen Typen funktioniert, und ich möchte wissen, ob es solche gibt sind alle Ressourcen zum Thema.
Ricky Stewart
2
@ RickyStewart: Du kennst Clean ( wiki.clean.cs.ru.nl/Clean ) wahrscheinlich schon. Ich wollte den Link nur hinzufügen, weil Sie ihn nicht erwähnt haben.
Giorgio
Ich denke, Sie sollten nach linearen Typen für Parallelität suchen. IIRC-Eindeutigkeitstypen basieren auf linearen Typen. Frank Pfenning hat einige interessante Dinge zu diesem Thema
Daniel Gratzer

Antworten:

2

Ist es beispielsweise möglich, Sperren mit eindeutigen Typen zu implementieren?

Ich folgte dem Link, den Robert Harvey zur Verfügung stellte, und las kurz nach. Ich kann nicht sagen, dass ich alles verstanden habe oder dass ich ein hohes Maß an Vertrauen habe, dass ich wirklich verstanden habe, was ich habe glaube , aber es scheint mir, dass der springende Punkt der äußeren Eindeutigkeit und der Unveränderlichkeit von Referenzen darin besteht, keine Notwendigkeit für Sperren zu haben.

Moderne Ansätze für Multithreading versuchen, Sperren zu vermeiden, da nur erfahrene Programmierer Code schreiben können, der Sperren verwendet, und selbst ihr Code ist sehr anfällig für Fehler. Wenn Sie zusätzlich hinzufügen, dass der Sperrcode praktisch nicht testbar ist, sollte klar sein, dass dies eine höchst unerwünschte Vorgehensweise ist und dass jede Lösung, die uns vom Sperren befreien soll, gelinde gesagt vielversprechend ist.

Die Art und Weise, wie wir das Sperren vermieden haben, ist das Übergeben von Nachrichten, was erfordert, dass die Nachrichten unveränderlich sein müssen. Auf den ersten Blick scheint die Referenz-Unveränderlichkeit eine Technik zu sein, mit der wir die Unveränderlichkeit gewährleisten können, ohne tatsächlich unveränderliche Typen konstruieren zu müssen, und die externe Einzigartigkeit scheint eine Technik zu sein, mit der wir die strengen Anforderungen an die Unveränderlichkeit vor Ort lockern können.

Können Eindeutigkeitstypen verwendet werden, um veränderbare Daten über Threads hinweg gemeinsam zu nutzen?

Das Papier hat es nicht klar dargelegt, aber nach meinem Verständnis ist eine äußerlich eindeutige Ansammlung von Objekten threadsicher, weil irgendwie (wirklich, wie? ) Garantiert ist, dass nur Verweis in dieser Gruppe von Objekten vorhanden ist, was bedeutet, dass Ein Thread, der eine solche Referenz erhält, kann die referenzierten Objekte als veränderlich behandeln, ohne dass befürchtet werden muss, dass ein anderer Thread diese ebenfalls verändert, da kein anderer Thread möglicherweise eine andere Referenz haben kann. Ich wäre gespannt, wie ein solches theoretisches Konstrukt umgesetzt und durchgesetzt werden kann.

Ist es möglich, eindeutige Typen zum Erstellen von Synchronisationsprimitiven (wie Mutexe) zu verwenden, oder ist eine Nachrichtenübermittlung erforderlich?

Soweit ich weiß, sollen äußerlich eindeutige Typen und die Unveränderlichkeit von Verweisen Sperren, Mutexe und dergleichen überflüssig machen. Die Weitergabe von Nachrichten scheint der richtige Weg zu sein, und das ist gut so.

Mike Nakis
quelle