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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Неформальное определение[править | править вики-текст]

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

Конструкции процесса[править | править вики-текст]

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

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

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

Небольшой пример[править | править вики-текст]

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

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

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

Формальное определение[править | править вики-текст]