Pi kalkulus

$\pi$ -számítás az elméleti számítástechnikában - a folyamatok számítása , amelyet eredetileg Robin Milner , Joachim Parrow és David Walker fejlesztett ki a kommunikáló rendszerek kalkulusával kapcsolatos munka folytatásaként . A -calculus célja olyan párhuzamos számítások leírása , amelyek konfigurációja a számítás során változhat. $\pi$

Informális meghatározás

$\pi$ A -calculus a folyamatkalculusok családjába tartozik . Valójában a -kalkulus λ-számításként olyan minimális, hogy nem tartalmaz olyan primitíveket, mint a számok , logikai kifejezések , adatszerkezetek , változók , függvények vagy folyamvezérlő utasítások (például if-then-else, while). $\pi$

$\pi$ A -calculus egymással dinamikusan kölcsönható párhuzamos folyamatokat határoz meg. Minden folyamat egy vagy több tevékenységből állhat , amelyek egymás után vagy párhuzamosan, illetve alternatív vagy rekurzív módon vannak elrendezve. Egy művelet lehet adatok küldése vagy fogadása egy csatornán keresztül. Az egyik folyamattól a másiknak küldött üzenet tartalmaz egy csatornanevet, amely a válaszadásra használható. A név egy változó [1] .

Azt is mondhatjuk, hogy a -calculus egy nyitott elmélet, amely valamilyen névelmélettől függ. Például működési szempontból a π-kalkulust olyan eljárásként ábrázolhatjuk, amely adott névelméletre ad egy folyamatelméletet ezeken a neveken . $\pi$

Folyamat konstrukciók

A -calculus központi eleme a név fogalma. A kalkulus egyszerűsége a nevek kettős szerepében rejlik, amelyek kommunikációs csatornaként és változóként is működnek. A következő folyamatkonstrukciók érhetők el a kalkulusban (a pontos definíciókat a következő szakaszokban adjuk meg): $\pi$

verseny , jelölése, aholés két folyamat vagy szál fut párhuzamosan. $P\mid Q$ $P$ $K$
kapcsolat hol
- A bemeneti előtag egy olyan folyamat, amely megvárja a kommunikációs csatornán keresztül elküldött üzenetet, mielőtt a következővel folytatná, és a kapott nevet a névhez kötné . Ez általában azt a folyamatot modellezi, amely a hálózatról érkező kommunikációra vagy a művelethez használható címkére vár . $c\left(x\jobbra).P$ $c$ $P$ $x$ cgoto c
- a kimeneti előtag azt írja le, hogy a név átkerül a csövön , mielőtt a következővel folytatná . Ez általában az üzenet hálózaton vagy műveleten keresztül történő elküldését modellezi . $\overline {c}\langle y\rangle .P$ $y$ $c$ $P$ goto c
replikáció , jelölése, amely egy olyan folyamatnak tekinthető, amely mindig képes új másolatot készíteni a -ból. Általában ezek a modellek vagy hálózati szolgáltatások, vagyműveletreváró $!\,P$ $P$ cgoto c
egy új név létrehozását jelöli , ami egy új állandót behelyező folyamatnak tekinthető . A számítási állandókat csak a nevük határozza meg, és mindig kommunikációs csatornák. $\left(\nux\right)P$ $x$ $P$ $\pi$
a nulla folyamat, amelyet 0 -val jelölünk , az a folyamat, amelynek végrehajtása megszakadt és leállt.

A -calculus minimalizmusa nem teszi lehetővé, hogy a szó szokásos értelmében programokat írjunk, de a kalkulus könnyen bővíthető. Különösen könnyű meghatározni a vezérlőstruktúrákat (például rekurzió , hurkok és szekvenciális összetétel) és adattípusokat (például elsőrendű függvények, igazságértékek , listák és egész számok ). Ezenkívül javasolták a -calculus kiterjesztését a nyilvános kulcsú kriptográfiára . Az Abadi és Fournet által kifejlesztett alkalmazott π-számítás formális alapot ad a π-számítás e különféle kiterjesztéseihez tetszőleges adattípusokon keresztül . $\pi$ $\pi$

Egy kis példa

Az alábbiakban egy három párhuzamos komponensből álló folyamat példája látható. A csatorna csak az első két komponensben ismert. $x$

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

Az első két komponens képes a csatornán keresztül kommunikálni , és a -hoz kötődik . A folyamat következő lépése: $x$ $y$ $z$

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

Ebben a példában ez nincs hatással, mivel a belső hatókörében van definiálva . Most a második és a harmadik párhuzamos komponens kommunikálhat a csatornán keresztül , miközben kommunikál a -val . A folyamat következő lépése: $y$ $z$ $v$ $x$

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

Vegye figyelembe, hogy mivel a helyi névre következtetett, a hatókör kibővült a harmadik összetevővel is. Végül egy csatorna használható név küldésére . Ezt követően minden folyamat leáll. $x$ $x$ $x$ $x$

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

Formális definíció

Alkalmazás

$\pi$ A -calculus az egyik legnépszerűbb formalizmus az üzleti folyamatmenedzsment (BPM) közösségben . Például a népszerű irodalom azt állítja (és kritizálják [3] [1] ), hogy az XLANG , WSCI , BPML , BPEL és WS-CDL ezen a számításon alapulnak. Legalább a -calculus tulajdonságai - számítási sorrend, üzenet alapú kommunikáció, mobilitás - alapul szolgálhatnak a BPM nyelvekhez [1] . $\pi$

A -calculus másik váratlan felhasználási módja a biomolekuláris rendszerek modellezése [4] . $\pi$

Példa üzleti folyamatra

A következő példa ötletet adhat egy üzleti folyamat leírásához pi-calculus segítségével (a [1] -ből átfogalmazva ):

Ügyfél(megrendelés, vevő)= rendelés <ügyfél>.vásárló(tál) Waiter TakesOrder(Rendelés,RendelésKész,OrderNotReady,Kitchen)= megrendelés (vevő). konyha <orderReady,orderNotReady> .Pincér ételt hoz (rendelés kész, rendelés nincs kész, ügyfél) Pincér ételt hoz (rendelés kész, rendelés nincs kész, ügyfél)= rendelésKész(étel). kliens <étel> + Rendelés Nincs kész (elnézést). ügyfél <elnézést> Kitchen(kitchen,orderReady,orderNotReady)= konyha (rendelkezésre kész, rendelésNem kész). rendelésKész <"borscht"> Étterem= (ν zkz, klnt, kész, nincs kész, konyha) Ügyfél (ccz,clnt) | A pincér felveszi a rendelést | Konyha (konyha, kész, nincs kész)

Ebben a példában a számítást kibővítettük a választási operátorral (P + Q).

Jegyzetek

↑ 1 2 3 4 Havey, 2005 .
↑ WMP van der Aalst. Pi kalkulus versus Petrinets: Inkább együnk „alázatost”, ahelyett, hogy tovább fújnánk a „Pi hype-ot” . Letöltve: 2021. április 2. Az eredetiből archiválva : 2021. május 17. (határozatlan)
↑ 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.

Irodalom

Milner, Robin. Kommunikációs és mobil rendszerek: A π-számítás . - Cambridge, Egyesült Királyság: Cambridge University Press, 1999. - ISBN 0-521-65869-1 .
Milner, Robin. A poliádikus π-kalkulus: oktatóanyag // Specifikáció logika és algebra / FL Hamer ; W. Brauer; H. Schwichtenberg. — Springer-Verlag, 1993.
Sangiorgi, Davide. The π-calculus: A Theory of Mobile Processes / Davide Sangiorgi, David Walker . - Cambridge, Egyesült Királyság: Cambridge University Press, 2001. - ISBN 0-521-78177-9 .
Michael Havey. 3.2. A Pi-kalkulus // Essential Business Process Modeling . - O'Reilly Media, Inc., 2005. - ISBN 9780596008437 .