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

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

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

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

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

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

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

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

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

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

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

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

$\begin{array}{cc}& \begin{array}{cc}(\nu x)& (\bar{x}⟨z⟩.0\\ & |x(y).\bar{y}⟨x⟩.x(y).0)\end{array}\\ |& z(v).\bar{v}⟨v⟩.0\end{array}$

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

$\begin{array}{cc}& \begin{array}{cc}(\nu x)(& 0\\ |& \bar{z}⟨x⟩.x(y).0)\end{array}\\ |& z(v).\bar{v}⟨v⟩.0\end{array}$

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

$\begin{array}{cc}(\nu x)(& 0\\ |& x(y).0\\ |& \bar{x}⟨x⟩.0)\end{array}$

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

$\begin{array}{cc}(\nu x)(& 0\\ |& 0\\ |& 0)\end{array}$

Применение

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

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

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

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

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

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

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

заказ(клиент).Шаблон:Overline<заказГотов,заказНеГотов>

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

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

заказГотов(блюдо).Шаблон:Overline<блюдо>

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

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

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

Ресторан=

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

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

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

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

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

Литература

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Книга