Пі-числення

В теорії комп'ютерних наук, π-числення є численням процесів, розроблене Робіном Мілнером (англ. 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. Архів оригіналу за 9 вересня 2006. Процитовано 12 червня 2007.

Див. також

Реалізації

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

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

Посилання


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.