${\displaystyle \pi }$ -исчисление в теоретической информатике  — исчисление процессов , изначально разработанное Робином Милнером , и Дэвидом Уокером как продолжение работы над исчислением общающихся систем . Целью ${\displaystyle \pi }$ -исчисления является возможность описать параллельные вычисления , конфигурация которых может меняться на протяжении вычисления.

Неформальное определение

${\displaystyle \pi }$ -исчисление принадлежит к семейству исчислений процессов . Фактически ${\displaystyle \pi }$ -исчисление как λ-исчисление настолько минимально, что не содержит примитивов, таких как числа , булевы выражения , структуры данных , переменные , функции или операторы управления потоком (например, if-then-else, while).

${\displaystyle \pi }$ -исчисление определяет динамически взаимодействующие друг с другом параллельные процессы. Каждый процесс может состоять из одного или нескольких действий , расположенных последовательно или параллельно, а также альтернативно или рекурсивно. Действием может быть отправка или получение данных по каналу. Сообщение от одного процесса другому включает имя канала, который может быть использован для ответа. Имя является переменной .

Можно также сказать, что ${\displaystyle \pi }$ -исчисление — это открытая теория, которая зависит от некоторой теории имен. Например, с операционной точки зрения π-исчислении можно представить как процедуру, которая для данной теории имен даёт теорию процессов над этими именами .

Конструкции процесса

Центральным для ${\displaystyle \pi }$ -исчисления является понятие имени. Простота исчисления заключается в двойной роли имён, которые выступают и как каналы связи и как переменные. В исчислении доступны следующие конструкции процесса (точные определения даны в следующих секциях):

• конкуренция , обозначается ${\displaystyle P\mid Q}$ , где ${\displaystyle P}$ и ${\displaystyle Q}$ — два процесса или потока, выполняемых конкурентно.
• связь , где
  • префикс ввода ${\displaystyle c\left(x\right).P}$ — процесс, ожидающий сообщение, отправленное по каналу связи ${\displaystyle c}$ , перед тем как продолжаться как ${\displaystyle P}$ , привязывающий полученное имя к имени ${\displaystyle x}$ . Как правило, это моделирует процесс ожидания связи из сети , или метку c , которую можно использовать с помощью операции goto c .
  • префикс вывода ${\displaystyle {\overline {c}}\langle y\rangle .P}$ описывает, что имя ${\displaystyle y}$ передаётся через канал ${\displaystyle c}$ , перед тем как продолжаться как ${\displaystyle P}$ . Как правило, это моделирует отправку сообщения через сеть или операцию goto c .
• репликация , обозначается ${\displaystyle !\,P}$ , которая может быть рассмотрена как процесс, который может всегда создавать новую копию ${\displaystyle P}$ . Как правило, эти модели или сетевой сервис или метка c , ожидающая любое число goto c операций.
• создание нового имени , обозначается ${\displaystyle \left(\nu x\right)P}$ , которое может быть рассмотрено как процесс, размещающий новую константу ${\displaystyle x}$ внутри ${\displaystyle P}$ . Константы ${\displaystyle \pi }$ -исчисления определяются только через своё имя и всегда являются каналами связи.
• ноль процесс, обозначается 0 , процесс, выполнение которого завершено и остановлено.

Минимализм ${\displaystyle \pi }$ -исчисления не позволяет писать программы в обычном смысле этого слова, но исчисление можно легко расширить. В частности, просто определить структуры управления (такие как рекурсия , циклы и последовательная композиция) и типы данных (такие как функции первого порядка, значения истинности , списки и целые числа ). Кроме того, были предложены расширения ${\displaystyle \pi }$ -исчисления для криптографии с публичным ключом . Прикладное π-исчисление , разработанное Абади и Фурне, даёт этим различным расширениям π-исчисления формальную основу с помощью произвольных типов данных .

Небольшой пример

Ниже приведён пример процесса из трёх параллельных компонент. Канал ${\displaystyle x}$ известен только в двух первых компонентах.

${\displaystyle {\begin{aligned}&{\begin{aligned}(\nu x)\;&(\;{\overline {x}}\langle z\rangle .\;0\\&|\;x(y).\;{\overline {y}}\langle x\rangle .\;x(y).\;0\;)\end{aligned}}\\|\;&z(v).\;{\overline {v}}\langle v\rangle .0\end{aligned}}}$

Первые две компоненты способны связываться через канал ${\displaystyle x}$ , при этом ${\displaystyle y}$ связывается с ${\displaystyle z}$ . Следующий шаг процесса:

${\displaystyle {\begin{aligned}&{\begin{aligned}(\nu x)\;(\;&0\\|\;&{\overline {z}}\langle x\rangle .\;x(y).\;0\;)\end{aligned}}\\|\;&z(v).\;{\overline {v}}\langle v\rangle .\;0\end{aligned}}}$

В этом примере ${\displaystyle y}$ не затрагивается, так как он определён во внутренней области видимости . Теперь вторая и третья параллельные компоненты могут связаться через канал ${\displaystyle z}$ , при этом ${\displaystyle v}$ связывается с ${\displaystyle x}$ . Следующий шаг процесса:

${\displaystyle {\begin{aligned}(\nu x)(\;&0\\|\;&x(y).\;0\\|\;&{\overline {x}}\langle x\rangle .\;0\;)\end{aligned}}}$

Обратите внимание, что, поскольку локальное имя ${\displaystyle x}$ было выведено, область действия ${\displaystyle x}$ расширена, чтобы охватить также третью компоненту. Наконец, канал ${\displaystyle x}$ можно использовать для отправки имени ${\displaystyle x}$ . После чего все процессы останавливаются.

${\displaystyle {\begin{aligned}(\nu x)(\;&0\\|\;&0\\|\;&0)\end{aligned}}}$

Формальное определение

Применение

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

${\displaystyle \pi }$ -исчисление — один из наиболее популярных формализмов в сообществе управления бизнес-процессами (BPM) . Например, популярная литература утверждает (и подвергается критике ), что , , , BPEL и основаны на этом исчислении. По крайней мере, свойства ${\displaystyle \pi }$ -исчисления — порядок вычисления, связи на основе сообщений, мобильность ( англ. mobility ) — могут служить основой для языков BPM .

Другим неожиданным направлением использования ${\displaystyle \pi }$ -исчисления является моделирование биомолекулярных систем .

Пример бизнес-процесса

Следующий пример может дать представление об описании бизнес-процесса при помощи пи-исчисления (перефразирован из ):

Клиент(заказ,клиент)=

заказ <клиент>.клиент(блюдо)

ОфициантПринимаетЗаказ(заказ,заказГотов,заказНеГотов,кухня)=

заказ(клиент). кухня <заказГотов,заказНеГотов>

.ОфициантПриноситЕду(заказГотов,заказНеГотов,клиент)

ОфициантПриноситЕду(заказГотов,заказНеГотов,клиент)=

заказГотов(блюдо). клиент <блюдо>

+ заказНеГотов(извинения). клиент <извинения>

Кухня(кухня,заказГотов,заказНеГотов)=

кухня(заказГотов,заказНеГотов). заказГотов <"борщ">

Ресторан=

(ν зкз,клнт,готов,неГотов,кух)

Клиент(зкз,клнт)

| ОфициантПринимаетЗаказ(зкз,готов,неГотов,кух)

| Кухня(кух,готов,неГотов)

Для данного примера исчисление было расширено оператором выбора (P + Q).

Примечания

Литература

• . — Cambridge, UK : Cambridge University Press, 1999. — ISBN 0-521-65869-1 .
• The Polyadic π-Calculus: A Tutorial // Logic and Algebra of Specification / F. L. Hamer ; W. Brauer ; H. Schwichtenberg. — Springer-Verlag, 1993.
• The π-calculus: A Theory of Mobile Processes / Davide Sangiorgi, . — Cambridge, UK : Cambridge University Press, 2001. — ISBN 0-521-78177-9 .
• Michael Havey. 3.2. The Pi-Calculus // . — O'Reilly Media, Inc., 2005. — ISBN 9780596008437 .

Для улучшения этой статьи желательно : Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . Оформить статью по правилам . Проверить качество перевода с иностранного языка. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.