Calculul pi

$\pi$ -calcul în informatica teoretică - calculul proceselor , dezvoltat inițial de Robin Milner , Joachim Parrow și David Walker, ca o continuare a lucrărilor privind calculul sistemelor comunicante . Scopul calculului este de a putea descrie calculul paralel , a cărui configurație se poate schimba în timpul unui calcul. $\pi$

Definiție informală

$\pi$ -calculul aparține familiei calculilor de proces . De fapt , -calcul ca λ-calcul este atât de minim încât nu conține primitive, cum ar fi numere , expresii booleene , structuri de date , variabile , funcții sau instrucțiuni de control al fluxului (de exemplu, if-then-else, while). $\pi$

$\pi$ -calcul definește procese paralele care interacționează dinamic între ele. Fiecare proces poate consta dintr-una sau mai multe activități , aranjate secvenţial sau în paralel, și alternativ sau recursiv. O acțiune poate fi trimiterea sau primirea de date pe un canal. Un mesaj de la un proces la altul include un nume de canal care poate fi folosit pentru a răspunde. Numele este o variabilă [1] .

Se mai poate spune că -calculul este o teorie deschisă care depinde de o anumită teorie a numelor. De exemplu, din punct de vedere operațional, π-calculul poate fi reprezentat ca o procedură care, pentru o anumită teorie a numelor, dă o teorie a proceselor asupra acestor nume . $\pi$

Construcții de proces

În centrul calculului este conceptul de nume. Simplitatea calculului constă în rolul dublu al numelor, care acționează atât ca canale de comunicare , cât și ca variabile. Următoarele construcții de proces sunt disponibile în calcul (definițiile exacte sunt date în următoarele secțiuni): $\pi$

competiție , notatcu , undeși sunt două procese sau fire care rulează simultan. $P\mid Q$ $P$ $Q$
conexiune unde
- prefixul de intrare este un proces care așteaptă un mesaj trimis prin canalul de comunicare înainte de a continua ca , legând numele primit de numele . De obicei, aceasta modelează procesul de așteptare a comunicării din rețea sau o etichetă care poate fi utilizată cu operațiunea . $c\left(x\right).P$ $c$ $P$ $X$ cgoto c
- prefixul de ieșire descrie faptul că numele este trecut prin conductă înainte de a continua ca . De obicei, aceasta modelează trimiterea unui mesaj printr-o rețea sau o operațiune . $\overline {c}\langle y\rangle .P$ $y$ $c$ $P$ goto c
replicare , notatcu , care poate fi considerat ca un proces care poate crea întotdeauna o nouă copie a. De regulă, aceste modele sunt fie un serviciu de rețea, fie o etichetăcare așteaptă orice numărde operațiuni. $!\,P$ $P$ cgoto c
crearea unui nume nou , este notat cu , care poate fi gândit ca un proces care plasează o nouă constantă în interior . Constantele de calcul sunt definite numai prin numele lor și sunt întotdeauna canale de comunicare. $\left(\nux\right)P$ $X$ $P$ $\pi$
Procesul zero, notat cu 0 , este procesul a cărui execuție s-a încheiat și s-a oprit.

Minimalismul lui -calcul nu vă permite să scrieți programe în sensul obișnuit al cuvântului, dar calculul poate fi ușor extins. În special, este ușor să definiți structurile de control (cum ar fi recursiunea , buclele și compoziția secvențială) și tipurile de date (cum ar fi funcțiile de ordinul întâi, valorile de adevăr , listele și numerele întregi ). În plus, au fost propuse extensii ale -calculului la criptografia cu cheie publică . Calculul π aplicat , dezvoltat de Abadi și Fournet, oferă acestor diverse extensii ale calculului π o bază formală prin tipuri de date arbitrare . $\pi$ $\pi$

Un mic exemplu

Mai jos este un exemplu de proces cu trei componente paralele. Canalul este cunoscut doar în primele două componente. $X$

{\begin{aliniat}&{\begin{aliniat}(\nu x)\;&(\;\overline {x}\langle z\rangle .\;0\\&|\;x(y).\ ;\overline {y}\langle x\rangle .\;x(y).\;0\;)\end{aligned}}\\|\;&z(v).\;\overline {v}\langle v\rangle .0\end{aliniat}}

Primele două componente sunt capabile să comunice prin canal și se leagă de . Următorul pas al procesului: $X$ $y$ $z$

{\begin{aliniat}&{\begin{aliniat}(\nu x)\;(\;&0\\|\;&\overline {z}\langle x\rangle .\;x(y).\; 0\;)\end{aliniat}}\\|\;&z(v).\;\overline {v}\langle v\rangle .\;0\end{aliniat}}

În acest exemplu , nu este afectat, deoarece este definit în domeniul intern al . Acum a doua și a treia componentă paralelă pot comunica prin canal , în timp ce comunică cu . Următorul pas al procesului: $y$ $z$ $v$ $X$

{\begin{aligned}(\nu x)(\;&0\\|\;&x(y).\;0\\|\;&\overline {x}\langle x\rangle .\;0\; )\end{aliniat}}

Rețineți că, deoarece numele local a fost dedus, domeniul de aplicare a fost extins pentru a include și a treia componentă. În cele din urmă, un canal poate fi folosit pentru a trimite un nume . După aceea, toate procesele sunt oprite. $X$ $X$ $X$ $X$

{\begin{aliniat}(\nu x)(\;&0\\|\;&0\\|\;&0)\end {aliniat))

Definiție formală

Aplicație

$\pi$ -calculul este unul dintre cele mai populare formalisme în comunitatea managementului proceselor de afaceri (BPM) . De exemplu, literatura populară susține (și este criticată [3] [1] ) că XLANG , WSCI , BPML , BPEL și WS-CDL se bazează pe acest calcul. Cel puțin, proprietățile -calculului - ordinea de calcul, comunicațiile bazate pe mesaje, mobilitatea - pot servi ca bază pentru limbajele BPM [1] . $\pi$

O altă utilizare neașteptată a -calculului este modelarea sistemelor biomoleculare [4] . $\pi$

Exemplu de proces de afaceri

Următorul exemplu poate oferi o idee despre descrierea unui proces de afaceri folosind pi-calcul (parafrazat din [1] ):

Client(comandă, client)= comanda <client>.client(farcare) Chelnerul ia comandă (Comandă, Comandă gata, Comanda nu este gata, Bucătărie)= comanda (client). bucătărie <orderReady,orderNotReady> .Chelnerul aduce mâncare (comanda gata, comanda nu este gata, clientul) Chelnerul aduce mâncare (Comandă gata, Comanda nu este gata, Client)= comandă Gata (farfurie). client <dish> + comanda Nu este gata (ne pare rău). client <scuze> Bucătărie(bucătărie,comandăGata,comandăNuGata)= bucătărie (comandă gata, comandă nu este gata). orderReady <"borș"> Restaurant= (ν zkz, klnt, gata, nu gata, bucătărie) Client(ccz,clnt) | Chelnerul preia comanda | Bucătărie (bucătărie, gata, nu gata)

Pentru acest exemplu, calculul a fost extins cu operatorul de alegere (P + Q).

Note

↑ 1 2 3 4 Havey, 2005 .
↑ WMP van der Aalst. Calcul Pi versus Petrineți: Să mâncăm „humblepie” în loc să umflam și mai mult „Pi hype” . Preluat la 2 aprilie 2021. Arhivat din original la 17 mai 2021. (nedefinit)
↑ Regev A., Shapiro E. The π-calculus as an Abstraction for Biomolecular Systems // Modeling in Molecular Biology. Natural Computing Series / Ciobanu G., Rozenberg G.. - Berlin, Heidelberg: Springer, 2004.

Literatură

Milner, Robin. Sisteme de comunicare și mobile: calculul π . - Cambridge, Marea Britanie: Cambridge University Press, 1999. - ISBN 0-521-65869-1 .
Milner, Robin. The Polyadic π-Calculus: A Tutorial // Logic and Algebra of Specification / FL Hamer ; W. Brauer; H. Schwichtenberg. — Springer-Verlag, 1993.
Sangiorgi, Davide. Calculul π: o teorie a proceselor mobile / Davide Sangiorgi, David Walker . - Cambridge, Marea Britanie: Cambridge University Press, 2001. - ISBN 0-521-78177-9 .
Michael Havey. 3.2. The Pi-Calculus // Modelarea esențială a proceselor de afaceri . - O'Reilly Media, Inc., 2005. - ISBN 9780596008437 .