В теорії комп'ютерних наук, π-числення є численням процесів, розроблене Робіном Мілнером (англ. Robin Milner), Ійохімом Перроу (англ. Joachim Parrow) та (англ. David Walker) як розширення та розвиток роботи над численням процесів CCS (англ. Calculus of Communicating Systems). На меті створення π-числення є надання можливості описання , конфігурація яких може змінюватись під час роботи.
Неформальне визначення
π-числення належить до родини , — математичних формалізмів для описання та аналізу властивостей конкурентних процесів. Насправді, π-числення, як і λ-числення настільки мінімальне, що воно не містить таких примітивів, як числа, булеві значення, структури, змінні, функції, або, навіть, звичайні конструкції керування (такі як if... then...else
, while...
).
Основні поняття
Процес є абстракцією незалежного потоку керування. Канал є абстракцією зв'язку передачі інформації між двома процесами. Процеси взаємодіють між собою шляхом відправлення та отримання повідомлень (обміну повідомленнями) через канали.
Ключову роль в π-численні відіграє поняття ім'я. Простота числення завдячує тому факту, що імена мають подвійну роль: каналів зв'язку та змінних.
В π-численні пропонуються такі конструкції для описання процесів:
- конкурентність, позначається , де та є два процеси або потоки, що виконуються конкурентно (одночасно).
- комунікація, де
- префікс введення означає процес, що очікує повідомлення, яке було відіслане через канал зв'язку перед тим, як продовжити як , прив'язуючи отримане ім'я до імені . Як правило, це моделює або процес, що очікує на повідомлення з мережі, або мітку
c
яку можна використати лише один раз в операціїgoto c
. - префікс виведення означає, що ім'я передається через канал перед тим, як продовжити як . Зазвичай, це описує або відправку повідомлення в мережу, або операцію
goto c
.
- префікс введення означає процес, що очікує повідомлення, яке було відіслане через канал зв'язку перед тим, як продовжити як , прив'язуючи отримане ім'я до імені . Як правило, це моделює або процес, що очікує на повідомлення з мережі, або мітку
- реплікація, позначається , яка може розглядатись як процес, який завжди може створити нову копію . Зазвичай, це описує або мережеву службу, або мітку
c
що очікує на декілька операційgoto c
. - створення нового імені, записується , яка може розглядатись як розміщення процесом нової константи в . На відміну від операції
let x=... in...
в функціональному програмуванні, константи в π-численні визначаються лише іменем і завжди є каналами зв'язку. - нульовий процес, який записується як 0, є процесом, виконання якого завершено і він перебуває стані зупинки.
Не зважаючи на те, що мінімальність π-числення заважає написанню програм в звичайному розумінні цього поняття, числення може легко розширюватись.
Приклад
Нижче наведено приклад описання процесу, який складається із трьох паралельних компонент. Канал з іменем відомий лише першим двом компонентам.
Перші два компоненти можуть обмінюватись інформацією через канал , а ім'я прив'язується до . Продовження процесу, таким чином
Зверніть увагу на те, що не змінюється, оскільки воно визначено у внутрішній області імен.
Друга і третя компонента можуть обмінюватись інформацією через канал з іменем , та прив'язується до . Продовження процесу тепер
Зверніть увагу на те, що, оскільки локальне ім'я було виведено, область видимості розширюється для того, аби покривати і інші компоненти. Як наслідок, канал може бути використано для пересилки імені .
Особливості
На відміну від попередніх формалізмів в галузі паралельних процесів, таких як (англ. Calculus of Communicating Systems) та (англ. Calculus of Sequential Processes), в π-численні передбачена можливість відправлення каналів зв'язку як даних через інші канали. Ця особливість надає можливість визначати мобільність процесів, що, в свою чергу, дає можливість відображати зміни в структурі процесів.
Прикладом застосування такої особливості можна назвати процес обміну даними між мобільним телефоном та базовими станціями стільникового зв'язку під час пересування від зони покриття однієї базової станції до іншої.
Джерела інформації
- (PDF). Архів оригіналу (PDF) за 9 вересня 2006. Процитовано 12 червня 2007.
- Робін Мілнер: Communicating and Mobile Systems: the Pi-Calculus, Cambridge Univ. Press, 1999,
- Робін Мілнер: The Polyadic π-Calculus: A Tutorial. Logic and Algebra of Specification, 1993.
- Davide Sangiorgi та David Walker: The Pi-calculus: A Theory of Mobile Processes, Cambridge University Press,
Див. також
- Процес — базове поняття багатопоточного програмування.
- Діаграма послідовності (UML) — один із методів графічного представлення взаємодії між процесами.
- Обмін повідомленнями.
- Мережа Петрі
- Формальні методи
Реалізації
Реалізаціями або π-числення, або його розширень є такі мови програмування:
- (Business Process Modeling Language)
- (основана на різновиді π-числення)
Посилання
- PiCalculus на C2 wiki(англ.)
- Calculi for Mobile Processes(англ.)
- by (англ.)
- C. A. R. Hoare, Communicating Sequential Processes чудова книжка на близьку до пі числення тему (Взаємодія послідовних процесів).(англ.)
Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi komp yuternih nauk p chislennya ye chislennyam procesiv rozroblene Robinom Milnerom angl Robin Milner Ijohimom Perrou angl Joachim Parrow ta angl David Walker yak rozshirennya ta rozvitok roboti nad chislennyam procesiv CCS angl Calculus of Communicating Systems Na meti stvorennya p chislennya ye nadannya mozhlivosti opisannya konfiguraciya yakih mozhe zminyuvatis pid chas roboti Neformalne viznachennyap chislennya nalezhit do rodini matematichnih formalizmiv dlya opisannya ta analizu vlastivostej konkurentnih procesiv Naspravdi p chislennya yak i l chislennya nastilki minimalne sho vono ne mistit takih primitiviv yak chisla bulevi znachennya strukturi zminni funkciyi abo navit zvichajni konstrukciyi keruvannya taki yak if then else while Osnovni ponyattya Proces ye abstrakciyeyu nezalezhnogo potoku keruvannya Kanal ye abstrakciyeyu zv yazku peredachi informaciyi mizh dvoma procesami Procesi vzayemodiyut mizh soboyu shlyahom vidpravlennya ta otrimannya povidomlen obminu povidomlennyami cherez kanali Klyuchovu rol v p chislenni vidigraye ponyattya im ya Prostota chislennya zavdyachuye tomu faktu sho imena mayut podvijnu rol kanaliv zv yazku ta zminnih V p chislenni proponuyutsya taki konstrukciyi dlya opisannya procesiv konkurentnist poznachayetsya P Q displaystyle P mid Q de P displaystyle P ta Q displaystyle Q ye dva procesi abo potoki sho vikonuyutsya konkurentno odnochasno komunikaciya de prefiks vvedennya c x P displaystyle c left x right P oznachaye proces sho ochikuye povidomlennya yake bulo vidislane cherez kanal zv yazku c displaystyle c pered tim yak prodovzhiti yak P displaystyle P priv yazuyuchi otrimane im ya do imeni x displaystyle x Yak pravilo ce modelyuye abo proces sho ochikuye na povidomlennya z merezhi abo mitku c yaku mozhna vikoristati lishe odin raz v operaciyi goto c prefiks vivedennya c y P displaystyle overline c langle y rangle P oznachaye sho im ya y displaystyle y peredayetsya cherez kanal c displaystyle c pered tim yak prodovzhiti yak P displaystyle P Zazvichaj ce opisuye abo vidpravku povidomlennya v merezhu abo operaciyu goto c replikaciya poznachayetsya P displaystyle P yaka mozhe rozglyadatis yak proces yakij zavzhdi mozhe stvoriti novu kopiyu P displaystyle P Zazvichaj ce opisuye abo merezhevu sluzhbu abo mitku c sho ochikuye na dekilka operacij goto c stvorennya novogo imeni zapisuyetsya nx P displaystyle left nu x right P yaka mozhe rozglyadatis yak rozmishennya procesom novoyi konstanti x displaystyle x v P displaystyle P Na vidminu vid operaciyi let x in v funkcionalnomu programuvanni konstanti v p chislenni viznachayutsya lishe imenem i zavzhdi ye kanalami zv yazku nulovij proces yakij zapisuyetsya yak 0 ye procesom vikonannya yakogo zaversheno i vin perebuvaye stani zupinki Ne zvazhayuchi na te sho minimalnist p chislennya zavazhaye napisannyu program v zvichajnomu rozuminni cogo ponyattya chislennya mozhe legko rozshiryuvatis PrikladNizhche navedeno priklad opisannya procesu yakij skladayetsya iz troh paralelnih komponent Kanal z imenem x displaystyle x vidomij lishe pershim dvom komponentam nx x z 0 x y y x x y 0 z v v v 0 displaystyle nu x overline x langle z rangle 0 x y overline y langle x rangle x y 0 z v overline v langle v rangle 0 Pershi dva komponenti mozhut obminyuvatis informaciyeyu cherez kanal x displaystyle x a im ya z displaystyle z priv yazuyetsya do y displaystyle y Prodovzhennya procesu takim chinom nx 0 z x x y 0 z v v v 0 displaystyle nu x 0 overline z langle x rangle x y 0 z v overline v langle v rangle 0 Zvernit uvagu na te sho y displaystyle y ne zminyuyetsya oskilki vono viznacheno u vnutrishnij oblasti imen Druga i tretya komponenta mozhut obminyuvatis informaciyeyu cherez kanal z imenem z displaystyle z ta x displaystyle x priv yazuyetsya do v displaystyle v Prodovzhennya procesu teper nx 0 x y 0 x x 0 displaystyle nu x 0 x y 0 overline x langle x rangle 0 Zvernit uvagu na te sho oskilki lokalne im ya x displaystyle x bulo vivedeno oblast vidimosti x displaystyle x rozshiryuyetsya dlya togo abi pokrivati i inshi komponenti Yak naslidok kanal x displaystyle x mozhe buti vikoristano dlya peresilki imeni x displaystyle x OsoblivostiNa vidminu vid poperednih formalizmiv v galuzi paralelnih procesiv takih yak angl Calculus of Communicating Systems ta angl Calculus of Sequential Processes v p chislenni peredbachena mozhlivist vidpravlennya kanaliv zv yazku yak danih cherez inshi kanali Cya osoblivist nadaye mozhlivist viznachati mobilnist procesiv sho v svoyu chergu daye mozhlivist vidobrazhati zmini v strukturi procesiv Prikladom zastosuvannya takoyi osoblivosti mozhna nazvati proces obminu danimi mizh mobilnim telefonom ta bazovimi stanciyami stilnikovogo zv yazku pid chas peresuvannya vid zoni pokrittya odniyeyi bazovoyi stanciyi do inshoyi Dzherela informaciyi PDF Arhiv originalu PDF za 9 veresnya 2006 Procitovano 12 chervnya 2007 Robin Milner Communicating and Mobile Systems the Pi Calculus Cambridge Univ Press 1999 ISBN 0 521 65869 1 Robin Milner The Polyadic p Calculus A Tutorial Logic and Algebra of Specification 1993 Davide Sangiorgi ta David Walker The Pi calculus A Theory of Mobile Processes Cambridge University Press ISBN 0 521 78177 9Div takozhProces bazove ponyattya bagatopotochnogo programuvannya Diagrama poslidovnosti UML odin iz metodiv grafichnogo predstavlennya vzayemodiyi mizh procesami Obmin povidomlennyami Merezha Petri Formalni metodiRealizaciyi Realizaciyami abo p chislennya abo jogo rozshiren ye taki movi programuvannya Business Process Modeling Language osnovana na riznovidi p chislennya Posilannya PiCalculus na C2 wiki angl Calculi for Mobile Processes angl by angl C A R Hoare Communicating Sequential Processes chudova knizhka na blizku do pi chislennya temu Vzayemodiya poslidovnih procesiv angl Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi