Datenstrukturen in Programmiersprache mit linearen Typen

Angenommen, wir haben es mit einer Programmiersprache zu tun, die lineare Typen unterstützt (Begriffe von linearem Typ können sozusagen höchstens einmal verwendet werden). Dies ermöglicht es, einige rechnerische Effekte (wie Mutation, sogar Änderung des Operandentyps) auf eine Weise zu behandeln, die für Sprachen problematisch ist, deren Typensysteme nur auf "ewigen Wahrheiten" beruhen.

Viele Datenstrukturen können mit induktiven Typen charakterisiert werden (Listen und Bäume sind kanonische Beispiele). Wenn wir der Mischung lineare induktive Typen hinzufügen, können wir auch veränderbare Datenstrukturen verarbeiten.

Es ist mir jedoch nicht klar, wie Datenstrukturen mit gemeinsamen und zyklischen Referenzen in einer Programmiersprache mit linearen Typen dargestellt werden sollen (Beispiele für solche Datenstrukturen sind DAGs und andere Diagramme, die durch Adjazenzlisten oder andere zyklische Listen dargestellt werden). Können wir das tun? Wenn es nicht möglich ist, wie sollten wir die Sprache erweitern, um solche Datenstrukturen aufzunehmen?

Das umfangreichste Beispiel, das ich bisher gefunden habe, ist eine doppelt verknüpfte Liste. Gibt es noch andere Beispiele?

Linearität ist keine ausreichende Einschränkung, um eine eindeutige zustandsbezogene Darstellung festzulegen. Die Antwort auf Ihre Frage hängt daher davon ab, wie Sie die lineare Logik als Zustand interpretieren. Dies wird sich in der Regel darin widerspiegeln, wie Sie das interpretieren müssen Modalität.$!A$

Wenn Ihre beabsichtigte Semantik von Referenzen besagt, dass alle Zeiger eindeutige Werte sind (dh es gibt höchstens eine einzige Referenz auf ein Objekt), sind Tags und Diagrammstrukturen aus dem tautologischen Grund, auf den ein Tag möglicherweise mehrere Referenzen enthält, nicht ausdrückbar das gleiche Objekt. In diesem Fall muss eine sein , die Berechnung , die einen neuen Wert vom Typ erstellt A , da Sie Karten möchten δ A : ! Ein ⊸ ! Ein ⊗ ! A und .$!A$$A$$\delta_A : !A \multimap !A \otimes !A$$\epsilon_A : !A \multimap A$

Nehmen Sie jedoch an, dass Sie möchten, dass das Teilen darstellt . Dann können Objekte mit Referenzzählung mit den Maps und als Operationen realisiert werden, die nur die Referenzzählung erhöhen. In diesem Fall können Sie mit der Linearität nicht davon ausgehen, dass das Mutieren von Werten immer sicher ist, da es gemeinsame Nutzung gibt. Sie können jedoch sicherstellen, dass die gesamte Speicherzuordnung in Ihrem Programm explizit angegeben ist und dass sich keine Zyklen im Heap befinden.δ A : ! Ein ⊸ ! Ein ⊗ ! A ε A : ! A ⊸ $!A$$\delta_A : !A \multimap !A \otimes !A$$\epsilon_A : !A \multimap A$

Die meisten praktischen Implementierungen linearer Typen verwenden keine dieser beiden Interpretationen. Stattdessen werden Referenzen als frei duplizierbare Entitäten betrachtet, und was wir linear verfolgen, sind tatsächlich Funktionen . Funktionen sind keine Laufzeitwerte. Es handelt sich um rein konzeptionelle Einheiten, die die Erlaubnis zum Zugriff auf eine Referenz darstellen sollen. Die Idee ist, dass Sie in einem Stil programmieren, bei dem Berechtigungen weitergegeben werden. Selbst wenn viele Verweise auf dasselbe Objekt vorhanden sind, kann ein Status nur dann gelesen oder geändert werden, wenn Sie auch die Möglichkeit haben, darauf zuzugreifen. Und da die Fähigkeit linear ist, wissen Sie, dass nur Sie sie ändern können.

$$\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) }$$

In der oben skizzierten API liegt über , einem Bereich von Indizes zur Kompilierungszeit, und liegt über Typen. Wir haben einen Typ der eine durch indizierte Fähigkeit ist , und einen Typ , der eine Art von Verweisen auf auf die eine Fähigkeit . Das Aufrufen von und für eine Referenz erfordert die Funktion , und das Aufrufen von erstellt eine neue Referenz und eine neue Funktion, die einen gemeinsamen Index verwendet. Allerdingsι α 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}$-um eine Referenz zu erstellen, ist kein Zugriff auf eine Funktion erforderlich, sodass jeder eine Referenz kopieren kann, solange er nicht in sie hineinschaut.