- Пи-исчисление
-
-исчисление в теоретической информатике — исчисление процессов, изначально разработанное Робином Милнером, Иоахимом Парровом и Дэвидом Уолкером как продолжение работы над исчислением общающихся систем. Целью -исчисления является возможность описать параллельные вычисления, конфигурация которых может меняться на протяжении вычисления.
Содержание
Неформальное определение
-исчисление принадлежит к семейству исчислений процессов. Фактически -исчисление, как λ-исчисление настолько минимально, что не содержит примитивов, таких как номера, булевы выражения, структуры данных, переменные, функции или операторы управления потоком (например, if-then-else, while).
Конструкции процесса
Центральным для -исчисления является понятие имени. Простота исчисления заключается в двойной роли имён, которые выступают и как каналы связи и как переменные. В исчислении доступны следующие конструкции процесса (точные определения даны в следующих секциях):
- конкуренция, обозначается , где и — два процесса или потока выполняемых конкурентно.
- связь, где
- префикс ввода — процесс, ожидающий сообщение, отправленное по каналу связи , перед тем как продолжаться как , привязывающий полученное имя к имени . Как правило, это моделирует процесс ожидания связи из сети, или метку
c
, которую можно использовать с помощью операцииgoto c
. - префикс вывода описывает, что имя передается через канал , перед тем как продолжаться как . Как правило, это моделирует отправку сообщения через сеть, или операцию
goto c
.
- префикс ввода — процесс, ожидающий сообщение, отправленное по каналу связи , перед тем как продолжаться как , привязывающий полученное имя к имени . Как правило, это моделирует процесс ожидания связи из сети, или метку
- репликация, обозначается , которая может быть рассмотрена как процесс, который может всегда создавать новую копию . Как правило, эти модели или сетевой сервис, или метка
c
ожидающая любое числоgoto c
операций. - создание нового имени , обозначается , которое может быть рассмотрено как процесс, размещающий новую константу внутри . Константы -исчисления определяются только через своё имя и всегда являются каналами связи.
- ноль процесс, обозначается 0, процесс выполнение которого завершено и остановлено.
Однако минимализм -исчисления не позволяет писать программы в обычном смысле слова, но исчисление может легко расширяться. В частности, просто определить структуры управления (такие как рекурсия, циклы и секвенциальная композиция) и типы данных (такие как функции первого порядка, значения истинности, списки и целые числа). Кроме того, были предложены расширения -исчисления, которые принимают во внимание распределение и криптографию с публичным ключом. Применяется -исчисление благодаря Абади и Фурнье внёсших эти различные дополнения на формальной основе, посредством расширения -исчисления с произвольными типами данных.
Небольшой пример
Ниже расположен пример процесса, который состоит из трёх параллельных компонент. Канал известен только из двух первых компонент.
Первые две компоненты способны связываться через канал , при этом связывается с . Следующий шаг процесса следующий:
В этом примере не затрагивается, потому что это определено во внутреннем объёме[уточнить]. Теперь вторая и третья параллельные компоненты могут связаться через канал , при этом связывается . Следующий шаг процесса
Формальное определение
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.Для улучшения этой статьи желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
- Викифицировать статью.
- Проверить качество перевода с иностранного языка.
Категории:- Исчисление процессов
- Теория информации
Wikimedia Foundation. 2010.