Пі-числення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії комп'ютерних наук, π-числення є численням процесів, розроблене Робіном Мілнером (англ. Robin Milner), Ійохімом Перроу (англ. Joachim Parrow) та Девідом Волкером (англ. David Walker) в якості розширення та розвитку роботи над численням процесів CCS (англ. Calculus of Communicating Systems). На меті створення π-числення є надання можливості описання конкурентних процесів, конфігурація яких може змінюватись під час роботи.

Неформальне визначення[ред.ред. код]

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

Основні поняття[ред.ред. код]

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

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

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

  • конкурентність, позначається P \mid Q, де P та Q є два процеси або потоки, що виконуються конкурентно (одночасно)
  • комунікація, де
    • префікс введення c\left(x\right).P означає процес, що очікує повідомлення, яке було відіслане через канал зв'язку c перед тим, як продовжити як P, прив'язуючи отримане ім'я до імені x. Як правило, це моделює або процес, що очікує на повідомлення з мережі, або мітку c яку можна використати лише один раз в операції goto c.
    • префікс виведення \overline{c} \langle y \rangle.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)(\overline{x} \langle z \rangle.0  |  x(y).   \overline{y}\langle x \rangle . x(y).0 ) | z(v) . \overline{v}\langle v \rangle. 0

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

 (\nu x)(0|  \overline{z}\langle x \rangle . x(y). 0 ) | z(v). \overline{v}\langle v \rangle .0

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

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

 (\nu x)(0|  x(y). 0  | \overline{x}\langle x \rangle .0)

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

Особливості[ред.ред. код]

На відміну від попередніх формалізмів в галузі паралельних процесів, таких як Числення Взаємодіючих Систем (англ. Calculus of Communicating Systems) та Числення Послідовних Процесів (англ. Calculus of Sequential Processes), в π-числені передбачена можливість відправлення каналів зв'язку в якості даних через інші канали. Ця особливість надає можливість визначати мобільність процесів, що, в свою чергу, дає можливість відображати зміни в структурі процесів.[1]

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

Джерела інформації[ред.ред. код]

  1. а б в Jeannette M. Wing, «FAQ on π-Calculus», 27 грудня 2002

Див. також[ред.ред. код]

Реалізації[ред.ред. код]

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

Посилання[ред.ред. код]


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.