Меню Главная Случайная статья Настройки Пи-исчисление Материал из https://ru.wikipedia.org ${\displaystyle \pi }$-исчисление в теоретической информатике  — исчисление процессов, изначально разработанное Робином Милнером, Иоахимом Пэрроу и Дэвидом Уокером как продолжение работы над исчислением общающихся систем. Целью ${\displaystyle \pi }$-исчисления является возможность описать параллельные вычисления, конфигурация которых может меняться на протяжении вычисления. Содержание 1 Неформальное определение 1.1 Конструкции процесса 1.2 Небольшой пример 2 Формальное определение 3 Применение 4 Пример бизнес-процесса 5 Примечания 6 Литература Неформальное определение ${\displaystyle \pi }$-исчисление принадлежит к семейству исчислений процессов. Фактически ${\displaystyle \pi }$-исчисление как -исчисление настолько минимально, что не содержит примитивов, таких как числа, булевы выражения, структуры данных, переменные, функции или операторы управления потоком (например, if-then-else, while). ${\displaystyle \pi }$-исчисление определяет динамически взаимодействующие друг с другом параллельные процессы. Каждый процесс может состоять из одного или нескольких действий, расположенных последовательно или параллельно, а также альтернативно или рекурсивно. Действием может быть отправка или получение данных по каналу. Сообщение от одного процесса другому включает имя канала, который может быть использован для ответа. Имя является переменной[1]. Можно также сказать, что ${\displaystyle \pi }$-исчисление — это открытая теория, которая зависит от некоторой теории имен. Например, с операционной точки зрения -исчислении можно представить как процедуру, которая для данной теории имен даёт теорию процессов над этими именами[2]. Конструкции процесса Центральным для ${\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}}}$ Формальное определение Применение