Pi-Kalkül

Beschreibungssprache für Systeme mit gleichzeitig ablaufenden und untereinander kommunizierenden Prozessen

Der Pi-Kalkül (π-Kalkül) ist ein Prozesskalkül, der von Robin Milner, Joachim Parrow und David Walker in den 1990er Jahren[1] als Nachfolger des Calculus of Communicating Systems (CCS) entwickelt wurde. Mit dem Pi-Kalkül können nebenläufige Systeme, die sich während der Laufzeit ändern, beschrieben werden. Trotz seiner einfachen Syntax ist er sehr expressiv. Es lassen sich funktionale Programmierungen darin ausdrücken. Erweiterungen wie der spi-Kalkül und „applied π“ wurden erfolgreich zur Brechung von Verschlüsselungsprotokollen eingesetzt.

Ein Anwendungszweck dieser Art von Verfahren ist die Simulation von Nebenläufigkeiten wie zum Beispiel Threads oder Prozessen auf Mehrkernprozessoren, weil bei der Programmierung von Software, welche diese Funktionalität nutzt, komplexe Randbedingungen ins Spiel kommen, die mittels einer solchen Simulation leichter in den Griff zu bekommen sind. Weitere Anwendungszwecke haben sich in der Molekularbiologie und zur Geschäftsprozessmodellierung ergeben.

Konstrukte

Bearbeiten

Die Prozessalgebra des Pi-Kalküls[2] ist stark mit Namen verknüpft. Durch die doppelte Rolle von Namen als Kommunikationskanal und Variable ist eine einfache Anwendung sichergestellt.

Konstrukt Syntax Beschreibung
Nebenläufigkeit     und   können gleichzeitig ausgeführt werden.
Eingabepräfix   Der Prozess   wartet auf Input  , der über den Kommunikationskanal   gesendet wird. Der Name   ist gebunden.
Ausgabepräfix   Der Name   wird über den Kanal   gesendet, bevor der Prozess   beginnt.
Silent Prefix  
Replikation   Der Prozess   kann eine Kopie von   erstellen.
Neuer Name     kann eine neue Konstante   innerhalb von   erstellen. Dies ist ein neuer Kommunikationskanal.
Null-Prozess 0 Der Prozess ist vollständig abgearbeitet und angehalten.

Diese minimale Definition des Pi-Kalküls verhindert einerseits Programme im üblichen Sinn. Anderseits ist es einfach, die fehlenden Kontrollstrukturen und Verzweigungen zu ergänzen.

Formale Definition

Bearbeiten

Seien X eine Menge von Namen und x und y Elemente dieser Menge![2] Die folgende Formale Grammatik in Backus-Naur-Form beschreibt die Formale Sprache des Pi-Kalküls:

 

In Worte übersetzt heißt das:

  • Empfange auf dem Kanal  , binde das Resultat an   und starte  
  • sende den Wert von   über den Kanal   und starte  
  • starte   und   gleichzeitig
  • erzeuge einen neuen Kanal   und starte  
  • erzeuge eine Kopie von  
  • beende den Prozess.

Beispiel

Bearbeiten

Ein Beispiel zeigt drei nebenläufige Prozesse, wobei der Name   nur den ersten beiden Komponenten bekannt ist.

 

Die ersten zwei Komponenten können über den Kanal   kommunizieren, der Name   wird an   gebunden.

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Nebenläufige Programmierung: Praxis und Semantik. 2011, abgerufen am 8. Oktober 2018.
  2. a b PI-Kalkül Prozessalgebra. Abgerufen am 8. Oktober 2018.