Procesų algebra

Informatikoje procesų algebra (arba procesų aritmetika) – plati metodų, skirtų modeliuoti vienalaikėms sistemoms, šeima. Procesų algebra leidžia tiksliai aprašyti procesų ar agentų sąveiką, komunikavimą ir sinchronizaciją. Taip pat taip pateikiami algebros dėsniai kurie leidžia transformuoti ir analizuoti procesų aprašymus, formaliai samprotauti apie procesų ekvivalentumą (pvz., naudojant būsenų neatskiriamumą. Pagrindiniai proceso skaičiavimo pavyzdžiai yra CSP, CCS, ACP ir LOTOS. Naujesni variantai yra π-calculus, ambient calculus, PEPA, fusion calculus and Behavioural Hybrid Process Calculus.

Esminės savybės

Kadangi egzistuoja labai daug įvairių procesų algebrų (įskaitant tikimybines, laiko, stochastines, hibridines ir molekulinių sąveikų procesų algebras), tarp jų egzistuoja kelios savybės, kurios sieja visas procesų algebras:

• Sąveika tarp procesų modeliuojama kaip komunikacija (pranešimo siuntimas), o ne bendrų kintamųjų keitimas.

• Procesai ir sistemos aprašomi naudojant nedidelį kiekį bazinių elementų (primityvų), bei naudojant operatorius jų kombinavimui.

• Algebriniai dėsniai ir operacinės semantikos taisyklės, leidžiančia manipuoliuoti procesais.

Procesų matematika

Kad būtų galima aprašyti proceso skaičiavimą, reikia pradėti nuo vardų (arba kanalų), kurių paskirtis yra išreikšti komunikacijos reikšmes. Per daugelį procesų kanalai pasižymi išvystyta vidine struktūra, kuri leidžia pagerinti efektyvumą, tačiau daugelyje teoriškai žinomų modelių šios funkcijos nėra. Greta vardų reikalingos reikšmės, kurių dėka būtų galima suformuluoti naujus procesus iš senų. Svarbiausi operatoriai, kurie turi vienokią ar kitokią formą, gali:

• Lygiagrečiai rinkti procesus
• Nustatyti, kuriuos kanalus naudoti, norint siųsti ir gauti duomenis
• Sukurti sąveikų seką
• Slėpti sąveikų taškus
• Atlikti kopijavimo rekursiją

Lygiagretus komponavimas

Lygiagretaus komponavimo metu yra atliekami du procesai ${\mathit {P}}$ ir ${\mathit {Q}}$, kurie paprastai užrašomi kaip $P\vert Q$, tai yra primityvus proceso skaičiavimų atskyrimas nuo nuoseklių apskaičiavimo modelių. Lygiagretus komponavimas leidžia atlikti skaičiavimus naudojant ${\mathit {P}}$ ir ${\mathit {Q}}$, kad būtų galima dirbti vienu metu ir atskirai. Bet tai taip pat leidžia sukurti sąveiką, kuri sukuria informacijos ir ${\mathit {P}}$ į ${\mathit {Q}}$ sinchronizaciją ir tekėjimą. O svarbiausia, priemonė arba procesas gali būti sujungtas su daugiua nei vienu kanalu vienu metu.

Kanalai gali būti sinchroniški arba nesinchroniški. Kai yra kalbama apie sinchroniškus kanalus, priemonė, kuri siunčia pranešimą, palaukia, kol kita priemonė gaus pranešimą. Nesinchroniškiems kanalams nereikia tokios sinchronizacijos. Atliekant kai kuriuos proceso skaičiavimus (π skaičiavimas), kanalai patys gali būti nusiunčiami pranešimų forma per (kitus) kanalus, tokiu būdu yra galima pakeisti proceso susijungimo topologiją. Kai kurie proceso skaičiavimai taip pat gali būti sukuriami apskaičiavimo metu.

Bendravimas

Sąveika gali būti (bet ne visada būna) nukreiptu informacijos srautu. Tai yra, įvestis ir išvestis gali būti atskiriamos, kaip dvigubi sąveikos baziniai elementai. Proceso skaičiavimas, kuris leidžia atlikti tokį atskyrimą, paprastai apibrėžia įvesties operatorių (pvz., x (v)) ir išvesties operatorių (pvz., x(y)), jie abu įvardina sąveikos tašką (čia x), kuris yra naudojamas norint atlikti sinchronizaciją, naudojant dvigubą sąveikos bazinį elementą. Jei norima pakeisti informaciją, ji tekės išvesties proceso metu, kuris pereina į įvesties procesą. Išvesties bazinis elementas patvirtins, kurie duomenys turi būti siunčiami. x(y) tokie duomenys žymimi y. Panašiai yra, jei įvestyje norima gauti duomenis, tada vienas arba daugiau kintamųjų veiks kaip laikikliai, kurie turi būti pakeičiami duomenimis, kai duomenys ateis. x(v) raidė v atlieką šią funkciją. Duomenų, kuriuos norima sukeisti sąveikoje, pasirinkimas yra viena iš esminių savybių, kurios išskiria skirtingus procesų skaičiavimus.

Eilių kompozicija

Kartais sąveikos turi būti laikinai atliekamos. Pvz., galima patvirtinti tokius algoritmus: pirmiausia reikia gauti dalį duomenų į x ir nusiųsti duomenis į y. Nuoseklus komponavimas gali būti naudojamas tokiu tikslu. Jis yra gerai žinomas iš kitų apskaičiavimo modelių. Atliekant proceso skaičiavimą išdėstymo nuosekliai operatorius yra paprastai integruojamas su įvestimi ir išvestimi, arba abiem. Pvz., procesas x(v) .P palauks įvesties x. Tik kai ši įvestis pasirodys, procesas P bus aktyvuotas, o gauti duomenys per x bus pakeisti į vardą v.

Mažinimo semantika

Esminė operacinė mažinimo taisyklė, kuri pagrindžia proceso skaičiavimo apskaičiuojančiąją esmę, gali būti išreikšta per lygiagretų komponavimą, nuoseklumo sukūrimą, įvestį ir išvestį. Tokio mažinimo detalės yra įvairios, kalbant apie skirtingus skaičiavimus, bet esmė išlieka tokia pati. Mažinimo taisyklė: x(y) . P I x(v) . Q → P I Q [y/v] Ši mažinimo taisyklė yra interpretuojama taip:

1. Procesas x(y) . P siunčia pranešimą, čia y, per kanalą x. Tuo pačiu metu procesas x(v) . Q gauna pranešimą per kanalą x.
2. Kai tik pranešimas yra išsiunčiamas, x(y) . P tampa procesu P, tuo tarpu procesas x(v) . Q tampa procesu Q [y/v], tai yra Q kartu su laikikliu v, kurį keičia y, o duomenys gaunami į x.

Grupė procesų, kuriuose P yra skirtas grupuoti duomenis, jis yra tarsi tąsa išvesties operacijos, jis iš esmės įtakoja skaičiavimo savybes.

Slėpimas

Procesai neriboja jungčių, kurias galima atlikti konkrečiame sąveikos taške, skaičiaus. Tačiau sąveikos taškai lemia tam tikrus trukdžius (pvz., sąveika). Kalbant apie kompaktiškumo sintezę, kai kalbama apie minimalias ir sudėtines sistemas, galimybė riboti trukdžius, yra labai svarbi. Slėpimo operacijos leidžia kontroliuoti jungtis, kurios padaromos tarp sąveikos taškų, kai sudedamosios priemonės yra naudojamos lygiagrečiai. Slėpimas gali būti žymimas įvairiais būdais. Pvz., π skaičiavime x slėpimas P gali būti išreikštas kaip (vx) P, kai CSP gali būti užrašomas kaip P\ {x}.

Rekursija ir dauginimasis

Operacijos, pristatytos ligi šiol, apibūdina tiktai baigtinę sąveiką ir yra todėl nepakankamos pilnam suskaičiuojamumui, kuris apima nesibaigiantį elgesį. Rekursija ir dauginimasis" yra operacijos, kurios leidžia baigtinį begalinio elgesio apibūdinimą. Recursija yra žinoma iš nuoseklaus pasaulio elgesio. Dauginimasis $!P$ gali būti suprastas kaip trumpinimas lygiagrečios sudėties begalinio skaičiaus ${\mathit {P}}$ procesų:

$!P=P\vert !P$

Negaliojantys (Null) procesai

Proceso skaičiavimai apskritai taip pat apima ir negaliojantį "null procesą" (įvairiai žymimas kaip ${\mathit {nil}}$, $0$, ${\mathit {STOP}}$, $\delta$, arba kokiu nors kitu atitinkamu simboliu), kuris neturi jokių sąveikos punktų. Jis yra absoliučiai neaktyvus ir jo vienintelė paskirtis yra veikti kaip indukcinis inkaras, virš kurio gali būti vykdomi daug įdomesni procesai.

Atskira ir nuolatinė proceso algebra

Proceso algebra buvo studijuota diskretiniam laikui ir nuolatinis laikas (realus laikas ar tankus laikas).

Istorija

Pirmojoje XX amžiaus pusėje buvo bandoma naudoti įvairius formalizmus, kad būtų galima žymėti neformalią sąvoką skaičiuojamoji funkcija, reiškiančią µ-grįžtamąsias funkcijas, Turingo mašinas ir lambda skaičiavimą, visa tai yra geriausiai žinomi pavyzdžiai šiandien. Stebėtinas faktas, kad šie pavyzdžiai iš esmės yra lygūs, nes jie gali būti įtraukiami vienas į kitą, jie palaiko Church-Turing tezę. Kita visiems bendra savybė yra rečiau aptariama: jie visi yra geriausiai suprantami kaip nuoseklaus apskaičiavimo modeliai, ypač tiksliai jie išreiškia konkurenciją ir komunikaciją. Konkuravimo modeliai, kaip tarkim proceso skaičiavimas, Petri-Nets 1962 m. ir Aktoriaus modelis 1973 m. buvo išvesti iš šio tipo informacijos. Tyrimai proceso skaičiavimo tema buvo pradėti Robin Milner pradiniame darbe Komunikacinių sistemų skaičiavimas (CCS) per laikotarpį tarp 1973 ir 1980 m. A. A. R. Hoare darbas Komunikaciniai nuoseklūs procesai (CSP) pirmą kartą pasirodė 1978 m. ir buvo toliau išplėtotas į pilną procesų skaičiavimą devintojo dešimtmečio pradžioje. Čia buvo matomas idėjų supliekimas tarp CCS ir CSP, kol jie buvo vystomi. 1982 m. Jan Bergstra ir Jan Willem Klop pradėjo dirbti prie to, kas tapo žinoma kaip Komunikacinių procesų algebra (ACP), ir iš čia kilo terminas proceso algebra, kuris išreiškė jų darbą. CCS, CSP ir ACP sudaro tris pagrindines proceso skaičiavimo šeimos šakas: didžioji dalis proceso skaičiavimo gali būti grindžiamas šiais trimis skaičiavimais.

Dabartiniai tyrimai

Įvairūs skirtingi proceso skaičiavimai buvo tiriami ir ne visi iš jų atitinka paradigmą, kuri pateikta čia. Geriausiai žinomas pavyzdys gali būti aplinkos skaičiavimas. Šis proceso skaičiavimas yra aktyviai tiriamas. Dabartinis proceso skaičiavimo tyrimas orientuotas į toliau įvardintas problemas.

• Naujų procesų skaičiavimų kūrimą, kad būtų galima geriau modeliuoti apskaičiavimo reiškinį.
• Rasti geresnį esamo proceso skaičiavimo pakaitalą. Tai yra svarbu todėl, kad (1) dauguma skaičiavimų yra prastai išplėtoti, turint galvoje, kad jie yra labiau bendriniai ir nelabai daug galima pasakyti apie sutartinius procesus; ir (2) apskaičiavimo atvejais retai kada yra panaudojamas visas skaičiavimas. Jų metu yra naudojami tik procesai, kurie yra labai riboti. Procesų ribojimas yra tiriamas, naudojant tipines sistemas.
• Procesų logika leidžia pagrįsti esmines sutartines procesų savybes, remiantis Hoare logika.
• Funkcionavimo teorija: ką reiškia, kai du procesai yra vienodi? Kaip mes galime nuspręsti, ar du procesai yra skirtingi ar ne? Ar mes galime rasti lygiagrečių procesų klasių pavyzdžius? Paprastai procesai yra vertinami kaip vienodi, jei nėra konteksto, t. y. tarp kitų procesų, kurie vyksta lygiagrečiai, gali būti pastebimi skirtumai. Deja, norint pagrįsti šį teiginį, dažnai susipainiojama ir lygybė lieka nepagrįsta (daugeliu atvejų tai turi būti apibrėžiama kaip esamos problemos esmė). Dvigubi modeliavimai yra techninė priemonė, kuri padeda pagrįsti proceso ekvivalentiškumus.
• Skaičiavimo išraiška. Programavimo ilgametė praktika rodo, kad tam tikros problemos yra lengviau išsprendžiamos vienose kalbose, nei kitose. Šis reiškinys rodo, kad turi būti tiksliau apibrėžta skaičiavimo modeliavimo apskaičiavimo išraiška, nei išreiškia Church-Turing tezė. Vienas iš būdų tai padaryti yra atsižvelgiant į šifrus tarp dviejų formalizmų ir nustatyti, kurias savybes šifrai gali apsaugoti. Kuo daugiau savybių galima apsaugoti, tuo didesnę išraišką turi šifruojamas objektas. Kai kalbama apie proceso skaičiavimą, gaunami rezultatai, kurie rodo, kad π-skaičiavimas yra kur kas išraiškingesnis, nei nesinchroniškas variantas, jis turi tą pačią išraiškos galią, kaip ir aukštesnio lygio π skaičiavimas, bet mažesnio lygio, nei aplinkos skaičiavimas.
• Naudojant proceso skaičiavimą, galima modeliuoti biologines sistemas. Manoma, kad procesinių-teorinių priemonių sudėtingumas gali padėti biologams formaliai organizuoti savo žinias.

Santykis su kitais panašiai modeliais

Istorinis monoidas yra laisvas objektas, kuris leidžia bendrai išreikšti atskirų komunikacinių procesų istorijas. Proceso skaičiavimas tada yra žinomas, kaip formali kalba, kuri buvo nuosekliai primesta istoriniam monoidui. Tai yra, istorinis monoidas gali fiksuoti įvykių seką, ją sinchronizuojant, bet negali pagrįsti galimos būsenos perdavimo. Taigi, proceso skaičiavimas yra istorinis monoidas, kurį formali kalba išreiškia kaip laisvą monoidą (formali kalba yra visų galimų riboto ilgio alfabeto stygų pogrupis, kurį sukūrė Kleene star). Komunikacijos kanalų naudojimas yra viena iš savybių, kuri atskiria proceso skaičiavimą nuo kitų konkuravimo modelių, kaip tarkim Petri nets ir Actor modelis (žiūrėkite Actor modelį ir proceso skaičiavimą). Viena iš esminių motyvacijų, kuri leidžia į procesą įtraukti kanalus, buvo galimybė panaudoti tam tikras algebros technikas, tokiu būdu suteikiant galimybę lengviau pagrįsti procesus iš algebros pusės.

Nuorodos

1. J. C. M. Baeten: A brief history of process algebra, Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004
2. Benjamin Pierce: „Foundational Calculi for Programming Languages“, The Computer Science and Engineering Handbook, pp. 2190-2207, CRC Press, ISBN 0-8493-2909-4.
3. Baeten, J.C.M.; M. Bravetti (August 2005). "A Generic Process Algebra". Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3). Bertinoro, Forl`ı, Italy: BRICS, Department of Computer Science, University of Aarhus. http://www.brics.dk/NS/05/3/. Nuoroda tikrinta 2007-12-29.
4. Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3-41, in The Book of Traces, V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 981-02-2058-8

Tolimesniam skaitymui

• Matthew Hennessy: Algebraic Theory of Processes, The MIT Press, ISBN 0-262-08171-7.

• C. A. R. Hoare: Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
  • Šią knygą atnaujino Jim Davies Oksfardo universitete. Šios knygos PDF versija yra pasiekiama per internetinį puslapį CSP.

• Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3.

• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.