„Communicating Sequential Processes“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 30. November 2024, 23:30 Uhr

Communicating Sequential Processes (CSP) ist eine von Tony Hoare an der Universität Oxford entwickelte Prozessalgebra zur Beschreibung von Interaktion zwischen kommunizierenden Prozessen. Die Idee wurde als imperative Sprache 1978 von Tony Hoare vorgestellt, dann von ihm zu einer formalen Algebra ausgebaut und 1985 mit der Veröffentlichung des Buchs mit dem gleichnamigen Titel Communicating Sequential Processes berühmt. Dieses Buch war 2003 laut CiteSeer bereits das dritthäufigst zitierte Werk der Informatik.^[1]

Als Abgrenzung zur ursprünglichen imperativen Sprache CSP wird die Prozessalgebra teilweise auch als Theoretical Communicating Sequential Processes (TCSP) bezeichnet.

Anwendungen

Die Programmiersprachen Go^[2] und Occam beinhalten praktische Implementierungen der CSP.
JCSP (Communicating Sequential Processes for Java) ist die Verbindung von CSP- und Occam-Konzepten in einer Java-API.
Mit C++CSP2 ist eine entsprechende Implementierung für C++ verfügbar.
das Message Passing Interface
die Parallel Virtual Machine.

Auszug aus der Syntax und Semantik

CSP verwendet Großbuchstaben für Zustände des Automaten sowie Kleinbuchstaben für Ereignisse. Die durch Ereignisse ausgelösten Zustandsübergänge werden durch einen Pfeil (→) gekennzeichnet.
- (x → B) Auf das Ereignis x folgt der Zustand B
- (x → y → B) Auf die Ereignisfolge x und dann y folgt Zustand B

In CSP werden bedingte Ereignisse durch Angabe des Auswahloperators | definiert.
- (x → A | y → B) Wenn Ereignis x, dann Zustand A. Wenn Ereignis y, dann Zustand B

Die Menge der Zustände und Ereignisse, die ein über CSP definierter Automat akzeptiert, wird durch das Alphabet αP angegeben. Jeder Automat enthält einen zusätzlichen Zustand STOP in αP, aus dem ein weiterer Zustandsübergang per Definition nicht mehr erlaubt ist.

Sequentielle Komposition wird durch das Einführen von Zwischenzuständen ermöglicht.
- P = (x → A), A = (y → B) ist äquivalent zu
- P = (x → y → B)

Die Parallelschaltung von Prozessen, die dieser Prozessalgebra den Namen gab, wird durch die Angabe des Symbols || erreicht.
- P = (a → (b → P | x → b → P)) mit αP = {a, b, x}
- Q = (a → b → Q | y → b → Q) mit αQ = {a, b, y}
- P || Q akzeptiert alle Zeichenfolgen {ab, axb, yb} sowie beliebige sequentielle Kombinationen

Rekursionen sind möglich.
- P = (x → y → P) generiert die unendliche Abfolge der Ereignisse xyxyxy…

Weblinks

Einzelnachweise

↑ CiteSeer Statistik
↑ Google Go package csp. Abgerufen am 26. Juni 2019 (englisch).

[1] CiteSeer Statistik

[2] Google Go package csp. Abgerufen am 26. Juni 2019 (englisch).

[1]

[2]

@@ Zeile 1: / Zeile 1: @@
+'''Communicating Sequential Processes''' ('''CSP''') ist eine von [[Tony Hoare]] an der [[Universität Oxford]] entwickelte [[Prozessalgebra]] zur Beschreibung von [[Interaktion]] zwischen kommunizierenden [[Prozess (Computer)|Prozessen]]. Die Idee wurde als [[imperative Sprache]] 1978 von Tony Hoare vorgestellt, dann von ihm zu einer formalen Algebra ausgebaut und 1985 mit der Veröffentlichung des Buchs mit dem gleichnamigen Titel ''Communicating Sequential Processes'' berühmt. Dieses Buch war 2003 laut [[CiteSeer]] bereits das dritthäufigst zitierte Werk der [[Informatik]].<ref>[http://citeseer.ist.psu.edu/articles.html CiteSeer Statistik]</ref>
-[[en:Communicating sequential processes]]
-CSP ist eine von Prof. Sir [[Tony Hoare]] an der [[Universität Oxford]] entwickelte [[Prozessalgebra]] zur mathematischen Beschreibung kommunizierender Automaten. Die zentrale Idee ist eine Entwurfsmethodik, die es erlaubt, systematisch komplexe Systeme aus kleineren zu konstruieren.
+Als Abgrenzung zur ursprünglichen imperativen Sprache&nbsp;CSP wird die Prozessalgebra teilweise auch als '''Theoretical Communicating Sequential Processes'''&nbsp;('''TCSP''') bezeichnet.
+== Anwendungen ==
-Syntax und Semantik:
+* Die [[Programmiersprache]]n [[Go (Programmiersprache)|Go]]<ref>{{Internetquelle | url=https://godoc.org/github.com/thomas11/csp | titel=Google Go package csp | sprache=en | datum= | abruf=2019-06-26}}</ref> und [[Occam]] beinhalten praktische [[Implementierung]]en der&nbsp;CSP.
-* In CSP werden Zustände mit Großbuchstaben, Ereignisse mit Kleinbuchstaben ausgedrückt.
+* [[JCSP]] (Communicating Sequential Processes for Java) ist die Verbindung von&nbsp;CSP- und Occam-Konzepten in einer [[Java (Programmiersprache)|Java]]-[[Application Programming Interface|API]].
+* Mit C++CSP2 ist eine entsprechende [[Implementierung]] für&nbsp;[[C++]] verfügbar.
+* das [[Message Passing Interface]]
+* die [[Parallele Virtuelle Maschine|Parallel Virtual Machine]].
+== Auszug aus der Syntax und Semantik ==
-* [[Transition]]en werden durch einen Pfeil -> gekennzeichnet. So bedeutet (x -> B), gesprochen "x, dann B", dass der [[Automat]] nach dem [[Ereignis]] x im [[Zustand]] B ankommt. Gleichermaßen meint (x -> y -> B) den [[Übergang]] in den Zustand B, nachdem die Ereignisse x und dann y eingetreten sind.
+* CSP verwendet Großbuchstaben für [[Automat (Informatik)|Zustände des Automaten]] sowie Kleinbuchstaben für [[Ereignis]]se. Die durch Ereignisse ausgelösten [[Transitionssystem|Zustandsübergänge]] werden durch einen Pfeil&nbsp;(→) gekennzeichnet.
+** <code>(x → B)</code> &nbsp; Auf das Ereignis&nbsp;x folgt der Zustand&nbsp;B
+** <code>(x → y → B)</code> &nbsp; Auf die Ereignisfolge x und dann&nbsp;y folgt Zustand&nbsp;B
+* In CSP werden bedingte Ereignisse durch Angabe des Auswahloperators | definiert.
-* Einfache sequentielle [[Komposition]] ist durch das Einführen von Zwischenzuständen möglich: P = (x -> A), A = (y -> B) akzeptiert also die gleiche Ereignisfolge wie P = (x -> y -> B)
+** <code>(x → A | y → B)</code> &nbsp; Wenn Ereignis x, dann Zustand A. Wenn Ereignis y, dann Zustand B
+* Die Menge der Zustände und Ereignisse, die ein über CSP definierter Automat akzeptiert, wird durch das [[Alphabet]] αP angegeben. Jeder Automat enthält einen zusätzlichen Zustand STOP in αP, aus dem ein weiterer Zustandsübergang per Definition nicht mehr erlaubt ist.
-* Der Auswahloperator | erlaubt das Schalten in verschiedene Zustände, abhängig vom aufgetretenen Ereignis: P = (x -> A | y -> B) schaltet z.B. bei x in den Zustand A, bei y in den Zustand B.
+* Sequentielle [[Komposition (Mathematik)|Komposition]] wird durch das Einführen von Zwischenzuständen ermöglicht.
-* Auch [[Rekursion]]en sind möglich: P = (x -> y -> P) lässt z.B. eine unendliche Abfolge xyxyxy... von Ereignissen zu.
+** <code>P = (x → A), A = (y → B)</code> &nbsp; ist äquivalent zu
+** <code>P = (x → y → B)</code>
+* Die Parallelschaltung von Prozessen, die dieser Prozessalgebra den Namen gab, wird durch die Angabe des Symbols || erreicht.
-* Jedem [[Prozess]] P ist ein [[Alphabet]] αP zugeordnet, das angibt, auf welche [[Signal]]e der Prozess P reagiert.
+** <code>P = (a → (b → P | x →  b → P))</code> &nbsp; mit &nbsp; αP = {a, b, x}
+** <code>Q = (a → b → Q | y → b → Q)</code> &nbsp; mit &nbsp; αQ = {a, b, y}
+** <code>P || Q</code> &nbsp; akzeptiert alle Zeichenfolgen {ab, axb, yb} sowie beliebige sequentielle Kombinationen
+* [[Rekursion]]en sind möglich.
-* Ein Sonderzustand ist der Zustand STOP/αP, aus dem der Automat mit Alphabet αP nicht wieder herauswechseln kann.
+** <code>P = (x → y → P)</code> &nbsp; generiert die unendliche Abfolge der Ereignisse xyxyxy…
+== Weblinks ==
+* [http://www.usingcsp.com/ Elektronische Version des Originalbuchs zu CSP von Tony Hoare]
+* [http://www.cs.kent.ac.uk/projects/ofa/c++csp C++CSP2 der University of Kent]
+== Einzelnachweise ==
-Automaten können mittels des Zeichens || parallel geschaltet werden, wobei zu beachten ist, dass der Produktautomat nur dann auf Ereignisse aus dem gemeinsamen Alphabet reagieren kann, wenn sich beide Teilautomaten in einem Zustand befinden, aus dem dieses Ereignis führt.
+<references />
+[[Kategorie:Theoretische Informatik]]
-Ein Beispiel:
+[[Kategorie:Parallelverarbeitung]]
-* P = (a -> (b -> P | x -> P) | (b -> P)) mit αP = {a, b, x}
+[[Kategorie:Logikkalkül]]
-* Q = (a -> b -> Q | y -> b -> Q) mit αQ = {a, b, y}
-* Dann akzeptiert P || Q die Zeichenfolgen {ab, axb, yb} sowie alle Kombinationen (abab..., ababx...) daraus.
-{{unverständlich}}
-{{NurListe}}
-[[Kategorie:Informatik]]