Пи-исчисление

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

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

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

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

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

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

• конкуренция, обозначается $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$. Константы $\pi$-исчисления определяются только через своё имя и всегда являются каналами связи.
• ноль процесс, обозначается 0, процесс, выполнение которого завершено и остановлено.

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

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

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

${\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}}$

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

${\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}}$

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

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

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

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

Применение

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

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

Литература

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