Пи-исчисление (Hn-nvcnvlyuny)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

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

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

[править | править код]

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

  • конкуренция, обозначается , где и  — два процесса или потока, выполняемых конкурентно.
  • связь, где
    • префикс ввода  — процесс, ожидающий сообщение, отправленное по каналу связи , перед тем как продолжаться как , привязывающий полученное имя к имени . Как правило, это моделирует процесс ожидания связи из сети, или метку c, которую можно использовать с помощью операции goto c.
    • префикс вывода описывает, что имя передаётся через канал , перед тем как продолжаться как . Как правило, это моделирует отправку сообщения через сеть или операцию goto c.
  • репликация, обозначается , которая может быть рассмотрена как процесс, который может всегда создавать новую копию . Как правило, эти модели или сетевой сервис или метка c, ожидающая любое число goto c операций.
  • создание нового имени, обозначается , которое может быть рассмотрено как процесс, размещающий новую константу внутри . Константы -исчисления определяются только через своё имя и всегда являются каналами связи.
  • ноль процесс, обозначается 0, процесс, выполнение которого завершено и остановлено.

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

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

[править | править код]

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

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

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

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

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

[править | править код]

Применение

[править | править код]

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

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

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

[править | править код]

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

Клиент(заказ,клиент)=
заказ<клиент>.клиент(блюдо)
ОфициантПринимаетЗаказ(заказ,заказГотов,заказНеГотов,кухня)=
заказ(клиент).кухня<заказГотов,заказНеГотов>
.ОфициантПриноситЕду(заказГотов,заказНеГотов,клиент)
ОфициантПриноситЕду(заказГотов,заказНеГотов,клиент)=
заказГотов(блюдо).клиент<блюдо>
+ заказНеГотов(извинения).клиент<извинения>
Кухня(кухня,заказГотов,заказНеГотов)=
кухня(заказГотов,заказНеГотов).заказГотов<"борщ">
Ресторан=
(ν зкз,клнт,готов,неГотов,кух)
Клиент(зкз,клнт)
| ОфициантПринимаетЗаказ(зкз,готов,неГотов,кух)
| Кухня(кух,готов,неГотов)

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

Примечания

[править | править код]
  1. 1 2 3 4 Havey, 2005.
  2. Matthias Radestock, L.G. Meredith. A Reflective Higher-order Calculus // Electronic Notes in Theoretical Computer Science. — 2005. — № 141.
  3. W.M.P. van der Aalst. Pi calculus versus Petri nets: Let us eat “humblepie” rather than further inflate the “Pi hype”. Дата обращения: 2 апреля 2021. Архивировано 17 мая 2021 года.
  4. Regev A., Shapiro E. The π-calculus as an Abstraction for Biomolecular Systems // Modelling in Molecular Biology. Natural Computing Series / Ciobanu G., Rozenberg G.. — Berlin, Heidelberg : Springer, 2004.

Литература

[править | править код]
  • 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.