Pi beregning

$\pi$ -calculus i teoretisk datalogi - calculus of processer , oprindeligt udviklet af Robin Milner , Joachim Parrow og David Walker som en fortsættelse af arbejdet med calculus af kommunikerende systemer . Formålet med -calculus er at kunne beskrive parallel computing , hvis konfiguration kan ændre sig i løbet af en beregning. $\pi$

Uformel definition

$\pi$ -calculus tilhører familien af procesregninger . Faktisk er -calculus som en λ-calculus så minimal, at den ikke indeholder primitiver såsom tal , booleske udtryk , datastrukturer , variabler , funktioner eller flowkontroludsagn (f.eks. if-then-else, while). $\pi$

$\pi$ -calculus definerer parallelle processer, der dynamisk interagerer med hinanden. Hver proces kan bestå af en eller flere aktiviteter , arrangeret sekventielt eller parallelt, og alternativt eller rekursivt. En handling kan være at sende eller modtage data over en kanal. En besked fra én proces til en anden indeholder et kanalnavn, der kan bruges til at svare. Navnet er en variabel [1] .

Man kan også sige, at -calculus er en åben teori, der afhænger af en eller anden teori om navne. For eksempel fra et operationelt synspunkt kan π-regningen repræsenteres som en procedure, der for en given teori om navne giver en teori om processer over disse navne . $\pi$

Proceskonstruktioner

Centralt for -calculus er begrebet et navn. Enkeltheden i beregningen ligger i navnenes dobbelte rolle, som både fungerer som kommunikationskanaler og som variable. Følgende proceskonstruktioner er tilgængelige i kalkulationen (nøjagtige definitioner er givet i de følgende afsnit): $\pi$

konkurrence , betegnetmed , hvorog er to processer eller tråde, der kører samtidigt. $P\midt Q$ $P$ $Q$
forbindelse hvor
- inputpræfiks er en proces , der venter på en besked sendt over kommunikationskanalen, før den fortsætter som , binder det modtagne navn til navnet . Dette modellerer typisk processen med at vente på kommunikation fra netværket eller en etiket , der kan bruges sammen med operationen . $c\venstre(x\højre).P$ $c$ $P$ $x$ cgoto c
- output- præfikset beskriver, at navnet føres gennem røret, før det fortsætter som . Dette modellerer typisk afsendelsen af en besked gennem et netværk eller en operation . $\overline {c}\langle y\rangle .P$ $y$ $c$ $P$ goto c
replikering , betegnetmed , som kan opfattes som en proces, der altid kan skabe en ny kopi af. Som regel er disse modeller enten en netværkstjeneste eller en etiket, derventer på et vilkårligt antaloperationer. $!\,P$ $P$ cgoto c
skabelsen af et nyt navn , er betegnet med, hvilket kan opfattes som en proces, der placerer en ny konstant indeni . Kalkuluskonstanter er kun defineret ved deres navn og er altid kommunikationskanaler. $\venstre(\nux\højre)P$ $x$ $P$ $\pi$
nul-proces, angivet med 0 , er den proces, hvis udførelse er afsluttet og stoppet.

Minimalismen ved -calculus giver dig ikke mulighed for at skrive programmer i ordets sædvanlige betydning, men calculus kan nemt udvides. Det er især nemt at definere kontrolstrukturer (såsom rekursion , loops og sekventiel sammensætning) og datatyper (såsom førsteordensfunktioner, sandhedsværdier , lister og heltal ). Derudover er der foreslået udvidelser af -calculus til public-key kryptografi . Anvendt π-calculus , udviklet af Abadi og Fournet, giver disse forskellige udvidelser af π-calculus et formelt grundlag gennem vilkårlige datatyper . $\pi$ $\pi$

Et lille eksempel

Nedenfor er et eksempel på en proces med tre parallelle komponenter. Kanalen er kun kendt i de to første komponenter. $x$

{\begin{aligned}&{\begin{aligned}(\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{aligned}}

De to første komponenter er i stand til at kommunikere gennem kanalen og binder sig til . Næste trin i processen: $x$ $y$ $z$

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

I dette eksempel er det ikke påvirket, da det er defineret i det indre omfang af . Nu kan den anden og tredje parallelle komponent kommunikere gennem kanalen , mens den kommunikerer med . Næste trin i processen: $y$ $z$ $v$ $x$

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

Bemærk, at siden det lokale navn er blevet udledt, er omfanget blevet udvidet til også at omfatte den tredje komponent. Endelig kan en kanal bruges til at sende et navn . Derefter stoppes alle processer. $x$ $x$ $x$ $x$

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

Formel definition

Ansøgning

$\pi$ -calculus er en af de mest populære formalismer i BPM-fællesskabet (Business Process Management) . For eksempel hævder populærlitteraturen (og kritiseres [3] [1] ), at XLANG , WSCI , BPML , BPEL og WS-CDL er baseret på denne beregning. I det mindste kan egenskaberne ved -calculus - rækkefølgen af beregning, beskedbaseret kommunikation, mobilitet - tjene som grundlag for BPM-sprog [1] . $\pi$

En anden uventet brug af -calculus er modellering af biomolekylære systemer [4] . $\pi$

Eksempel på forretningsproces

Følgende eksempel kan give en idé om at beskrive en forretningsproces ved hjælp af pi-calculus (omskrevet fra [1] ):

Kunde(ordre, kunde)= bestil <kunde>.kunde(fad) Tjeneren tager ordre(Ordre,OrderReady,OrderNotReady,Køkken)= ordre (kunde). køkken <ordreReady,orderNotReady> .Tjeneren bringer mad (ordre klar, ordre ikke klar, kunde) Tjeneren bringer mad (ordre klar, ordre ikke klar, kunde)= bestil Klar (fad). klient <parabol> + ordre ikke klar (beklager). klient <beklager> Køkken(køkken,ordreKlar,bestillingIkkeKlar)= køkken(ordreReady,orderNotReady). ordreklar <"borscht"> Restaurant= (ν zkz, klnt, klar, ikke klar, køkken) Klient(ccz,clnt) | Tjeneren tager imod ordren | Køkken (køkken, klar, ikke klar)

For dette eksempel er beregningen blevet udvidet med valgoperatoren (P + Q).

Noter

↑ 1 2 3 4 Havey, 2005 .
↑ WMP van der Aalst. Pi calculus versus Petrinets: Lad os spise "humblepie" i stedet for at puste "Pi-hypen" yderligere op . Hentet 2. april 2021. Arkiveret fra originalen 17. maj 2021. (ubestemt)
↑ 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.

Litteratur

Milner, Robin. Kommunikations- og mobile systemer: π-regningen . - Cambridge, Storbritannien: Cambridge University Press, 1999. - ISBN 0-521-65869-1 .
Milner, Robin. Den polyadiske π-Calculus: A Tutorial // Logik og algebra af specifikation / FL Hamer; W. Brauer; H. Schwichtenberg. — Springer-Verlag, 1993.
Sangiorgi, Davide. π-calculus: A Theory of Mobile Processes / Davide Sangiorgi, David Walker . - Cambridge, Storbritannien: Cambridge University Press, 2001. - ISBN 0-521-78177-9 .
Michael Havey. 3.2. Pi-Calculus // Essential Business Process Modeling . - O'Reilly Media, Inc., 2005. - ISBN 9780596008437 .