Пі-числення

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

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

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

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

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

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

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

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

  • конкурентність, позначається , де та є два процеси або потоки, що виконуються конкурентно (одночасно)
  • комунікація, де
    • префікс введення означає процес, що очікує повідомлення, яке було відіслане через канал зв'язку перед тим, як продовжити як , прив'язуючи отримане ім'я до імені . Як правило, це моделює або процес, що очікує на повідомлення з мережі, або мітку c яку можна використати лише один раз в операції goto c.
    • префікс виведення означає що ім'я передається через канал перед тим як продовжити як . Зазвичай, це описує або відправку повідомлення в мережу, або операцію goto c.
  • реплікація, позначається , яка може розглядатись як процес, який завжди може створити нову копію . Зазвичай, це описує або мережеву службу, або мітку c що очікує на декілька операцій goto c.
  • створення нового імені, записується , яка може розглядатись як розміщення процесом нової констатнти в . На відміну від операції let x=... in... в функціональному програмуванні, константи в π-численні визначаються лише іменем і завжди є каналами зв'язку.
  • нульовий процес, який записується як 0, є процесом, виконання якого завершено і він перебуває стані зупинки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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