Wie ist der aktuelle Status von parallelen oder gleichzeitigen Programmen im Curry-Howard-Isomorphismus?

9

In Girards Beweisen und Typen können wir lesen:

Aus algorithmischer Sicht weist der sequentielle Kalkül keinen Curry-Howard-Isomorphismus auf, da es eine Vielzahl von Möglichkeiten gibt, denselben Beweis zu schreiben. Dies hindert uns daran, es als typisierten Kalkül zu verwenden, obwohl wir eine tiefe Struktur dieser Art sehen, die wahrscheinlich mit Parallelität verbunden ist.λ

Beweise und Typen , JY Girard (Seite 28)

Aber wir können das auch lesen (über lineare Logik)

Aus Sicht der Informatik bietet es einen neuen Ansatz für Fragen der Faulheit, der Nebenwirkungen und der Speicherzuordnung [GirLaf, Laf87, Laf88] mit vielversprechenden Anwendungen für die Parallelität.

Beweise und Typen , JY Girard (Seite 149, geschrieben von Yves Lafont)

Wie sind parallele Programme mit dem Curry-Howard-Isomorphismus verbunden? Was sind die aktuellen Gedanken dazu?

reference-request logic parallel-computing Boris
quelle

Antworten:

7

Das Concurrent Logical Framework ist ein interessanter Bereich, einschließlich seiner Nachkommen wie Linear Meld und LolliMon . Dies basiert auf intuitionistischer linearer Logik.

Die klassische lineare Logik hat Verbindungen zur linearen chemischen abstrakten Maschine (CHAM), wie z. B. Ein Kalkül für Interaktionsnetze basierend auf der linearen chemischen abstrakten Maschine, der das Ergebnis explizit als Ergebnis vom Typ Curry-Howard beschreibt.

λμ

Auf jeden Fall ist dies alles immer noch ein lebhaftes Forschungsgebiet. Es gibt viele aktuelle Artikel zu diesem Thema. Das Obige erwähnt nicht einmal die noch strukturellere Seite der Trennungslogik und die entsprechende Hoare-Typ-Theorie, die sich auf imperative Programmiersprachen konzentriert. Zum Beispiel gibt es Towards typentheoretische Semantik für Transaktions-Parallelität, deren Referenzen Sie für frühere Arbeiten verfolgen können.

(Als pedantische Anmerkung konzentrieren sich die meisten auf Parallelität und nicht auf Parallelität an sich.)

Derek Elkins verließ SE
quelle
Okay. Ich habe meinen Fragentitel bearbeitet, um ihn etwas breiter zu gestalten. Ich wusste nicht, dass Parallelität einen Link zu Curry-Howard hat. Aber was ist mit Parallelität?
Boris
In einer funktionalen Programmieransicht von Curry-Howard würde jede (reine) Parallelität auf der Ebene der Proof-Rewrites auftreten, und es gibt normalerweise genügend davon (jedes Mal, wenn es mehrere Redexes gibt). Sie könnten Anmerkungen wie die von Haskell hinzufügen par, um dies zu steuern (dh , es könnte standardmäßig eine weniger parallele Reduktionsreihenfolge verwendet werden, die selektiv paralleler gestaltet werden könnte), aber sie hätten keine logische Bedeutung.
Derek Elkins verließ SE
4

Für die Parallelität im Allgemeinen gibt es eine sehr aktive Forschungslinie, die ich in dieser Antwort zusammenzufassen versuchte: /cs//a/102711/98901

Ich füge hier unten einen Kommentar zur Parallelität hinzu.

Avron [1996] führte den Begriff der Hypersequenzen ein , dh Sammlungen von Sequenzen in Urteilen.

GH.G|H.|P.Q.GH.P.|Q.P.Q.G|H.

Wir haben gerade angefangen, die Oberfläche der semantischen Interpretation zu kratzen, aber dass dies Parallelität ist, ist ziemlich offensichtlich: Die Semantik der parallelen Komposition ermöglicht es, simultane Aktionen aus beiden Prozessen zu sehen, und es gibt einen Satz in der Arbeit, der besagt, dass keiner von beiden Die beiden Prozesse müssen warten, bis der andere mindestens eine Aktion ausführt (der Bereitschaftssatz). Die Erweiterung auf mehr als zwei Aktionen gleichzeitig scheint unkompliziert. (Die Eingabe erlaubt es bereits, aber die Semantik in diesem Artikel nutzt es nicht vollständig aus.)

fmontesi
quelle