Пі-числення

В теорії комп'ютерних наук, π-числення є численням процесів, розроблене Робіном Мілнером (Шаблон:Lang-en), Ійохімом Перроу (Шаблон:Lang-en) та Девідом Волкером (Шаблон:Lang-en) як розширення та розвиток роботи над численням процесів CCS (Шаблон:Lang-en). На меті створення π-числення є надання можливості описання конкурентних процесів, конфігурація яких може змінюватись під час роботи.

Неформальне визначення

π-числення належить до родини числення процесів, — математичних формалізмів для описання та аналізу властивостей конкурентних процесів. Насправді, π-числення, як і λ-числення настільки мінімальне, що воно не містить таких примітивів, як числа, булеві значення, структури, змінні, функції, або, навіть, звичайні конструкції керування (такі як if... then...else, while...).

Основні поняття

Процес є абстракцією незалежного потоку керування. Канал є абстракцією зв'язку передачі інформації між двома процесами. Процеси взаємодіють між собою шляхом відправлення та отримання повідомлень (обміну повідомленнями) через канали.

Ключову роль в π-численні відіграє поняття ім'я. Простота числення завдячує тому факту, що імена мають подвійну роль: каналів зв'язку та змінних.

В π-численні пропонуються такі конструкції для описання процесів:

• конкурентність, позначається $P\mid Q$, де $P$ та $Q$ є два процеси або потоки, що виконуються конкурентно (одночасно).
• комунікація, де
  • префікс введення $c\left(x\right).P$ означає процес, що очікує повідомлення, яке було відіслане через канал зв'язку $c$ перед тим, як продовжити як $P$, прив'язуючи отримане ім'я до імені $x$. Як правило, це моделює або процес, що очікує на повідомлення з мережі, або мітку c яку можна використати лише один раз в операції goto c.
  • префікс виведення $\bar{c}⟨y⟩.P$ означає, що ім'я $y$ передається через канал $c$ перед тим, як продовжити як $P$. Зазвичай, це описує або відправку повідомлення в мережу, або операцію goto c.
• реплікація, позначається $!P$, яка може розглядатись як процес, який завжди може створити нову копію $P$. Зазвичай, це описує або мережеву службу, або мітку c що очікує на декілька операцій goto c.
• створення нового імені, записується $\left(\nu x\right)P$, яка може розглядатись як розміщення процесом нової константи $x$ в $P$. На відміну від операції let x=... in... в функціональному програмуванні, константи в π-численні визначаються лише іменем і завжди є каналами зв'язку.
• нульовий процес, який записується як 0, є процесом, виконання якого завершено і він перебуває стані зупинки.

Не зважаючи на те, що мінімальність π-числення заважає написанню програм в звичайному розумінні цього поняття, числення може легко розширюватись.

Приклад

Нижче наведено приклад описання процесу, який складається із трьох паралельних компонент. Канал з іменем $x$ відомий лише першим двом компонентам.

$(\nu x)(\bar{x}⟨z⟩.0|x(y).\bar{y}⟨x⟩.x(y).0)|z(v).\bar{v}⟨v⟩.0$

Перші два компоненти можуть обмінюватись інформацією через канал $x$, а ім'я $z$ прив'язується до $y$. Продовження процесу, таким чином

$(\nu x)(0|\bar{z}⟨x⟩.x(y).0)|z(v).\bar{v}⟨v⟩.0$

Зверніть увагу на те, що $y$ не змінюється, оскільки воно визначено у внутрішній області імен.

Друга і третя компонента можуть обмінюватись інформацією через канал з іменем $z$, та $x$ прив'язується до $v$. Продовження процесу тепер

$(\nu x)(0|x(y).0|\bar{x}⟨x⟩.0)$

Зверніть увагу на те, що, оскільки локальне ім'я $x$ було виведено, область видимості $x$ розширюється для того, аби покривати і інші компоненти. Як наслідок, канал $x$ може бути використано для пересилки імені $x$.

Особливості

На відміну від попередніх формалізмів в галузі паралельних процесів, таких як Числення Взаємодіючих Систем (Шаблон:Lang-en) та Числення Послідовних Процесів (Шаблон:Lang-en), в π-численні передбачена можливість відправлення каналів зв'язку як даних через інші канали. Ця особливість надає можливість визначати мобільність процесів, що, в свою чергу, дає можливість відображати зміни в структурі процесів.

Прикладом застосування такої особливості можна назвати процес обміну даними між мобільним телефоном та базовими станціями стільникового зв'язку під час пересування від зони покриття однієї базової станції до іншої.

Джерела інформації

• Робін Мілнер: Communicating and Mobile Systems: the Pi-Calculus, Cambridge Univ. Press, 1999, ISBN 0-521-65869-1
• Робін Мілнер: 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, ISBN 0-521-78177-9

Див. також

• Процес — базове поняття багатопоточного програмування.
• Діаграма послідовності (UML) — один із методів графічного представлення взаємодії між процесами.
• Обмін повідомленнями.
• Мережа Петрі
• Формальні методи

Реалізації

Реалізаціями або π-числення, або його розширень є такі мови програмування:

• Acute
• BPML (Business Process Modeling Language)
• Kell machine
• Nomadic Pict
• Occam-Pi
• Pict
• JoCaml (основана на Джоін-численні різновиді π-числення)

Посилання

• PiCalculus на C2 wikiШаблон:Ref-en
• Calculi for Mobile ProcessesШаблон:Ref-en
• FAQ on Pi-Calculus by Jeannette M. WingШаблон:Ref-en
• C. A. R. Hoare, Communicating Sequential Processes чудова книжка на близьку до пі числення тему (Взаємодія послідовних процесів).Шаблон:Ref-en

Шаблон:Compu-stub