В компьютерной науке , то процесс исчисления (или процесс алгебры ) представляют собой разнородное семейство родственных подходов к формально моделированию параллельных систем . Вычисления процессов предоставляют инструмент для высокоуровневого описания взаимодействий, коммуникаций и синхронизации между набором независимых агентов или процессов. Они также предоставляют алгебраические законы, которые позволяют манипулировать описаниями процессов и анализировать их, а также позволяют формально рассуждать об эквивалентности между процессами (например, используя бимимуляцию ). Ведущие примеры расчетов процессов включают CSP , CCS , ACP и LOTOS .[1] Более поздние дополнения к семейству включают π-исчисление , внешнее исчисление , PEPA , слияние и объединенное исчисление .
Важные особенности
Хотя разнообразие существующих вычислений процессов очень велико (включая варианты, которые включают стохастическое поведение, информацию о времени и специализации для изучения молекулярных взаимодействий), есть несколько общих черт, которые имеют все вычисления процессов: [2]
- Представление взаимодействия между независимыми процессами как коммуникации (передача сообщений ), а не как изменение общих переменных.
- Описание процессов и систем с использованием небольшого набора примитивов и операторов для объединения этих примитивов.
- Определение алгебраических законов для операторов процесса, которые позволяют манипулировать выражениями процесса с помощью эквациональных рассуждений .
Математика процессов
Чтобы определить процесс исчисления , нужно начать с набора имен (или каналов ), цель которых - предоставить средства связи. Во многих реализациях каналы имеют богатую внутреннюю структуру для повышения эффективности, но в большинстве теоретических моделей это абстрагируется. Помимо имен, нужны средства для формирования новых процессов из старых. Основные операторы, всегда присутствующие в той или иной форме, позволяют: [3]
- параллельная композиция процессов
- спецификация каналов для отправки и получения данных
- секвенирование взаимодействий
- скрытие точек взаимодействия
- рекурсия или репликация процесса
Параллельная композиция
Параллельная композиция двух процессов а также , обычно пишется , является ключевым примитивом, отличающим вычисления процесса от последовательных моделей вычислений. Параллельная композиция позволяет проводить вычисления в а также действовать одновременно и независимо. Но это также позволяет взаимодействие, то есть синхронизацию и поток информации от к (или наоборот) на канале, совместно используемом обоими. Важно отметить, что агент или процесс могут быть подключены более чем к одному каналу одновременно.
Каналы могут быть синхронными или асинхронными. В случае синхронного канала агент, отправляющий сообщение, ожидает, пока другой агент не получит сообщение. Асинхронные каналы не требуют такой синхронизации. В некоторых процессах исчисления (особенно π-исчислении ) сами каналы могут быть отправлены в сообщениях через (другие) каналы, что позволяет изменять топологию взаимосвязей процессов. Некоторые исчисления процесса также позволяют каналы , которые будут созданы во время выполнения вычислений.
Коммуникация
Взаимодействие может быть (но не всегда) направленным потоком информации. То есть ввод и вывод можно разделить как примитивы двойного взаимодействия. Вычисления процесса, которые делают такие различия, обычно определяют оператор ввода ( например, ) и оператор вывода ( например, ), оба из которых называют точку взаимодействия (здесь ), который используется для синхронизации с примитивом двойного взаимодействия.
Если происходит обмен информацией, она будет переходить от процесса вывода к процессу ввода. Примитив вывода будет указывать данные для отправки. В, эти данные . Точно так же, если вход ожидает получения данных, одна или несколько связанных переменных будут действовать как заполнители, которые будут заменены данными, когда они поступят. В, играет эту роль. Выбор типа данных, которыми можно обмениваться во время взаимодействия, является одной из ключевых особенностей, отличающих различные вычисления процесса.
Последовательная композиция
Иногда взаимодействия необходимо временно упорядочить. Например, может быть желательно указать такие алгоритмы, как: сначала получить данные о а затем отправьте эти данные на . Для таких целей можно использовать последовательную композицию . Это хорошо известно из других моделей вычислений. В расчетах процесса оператор секвенирования обычно интегрируется с вводом или выводом, либо с обоими. Например, процесс будет ждать ввода на . Только когда этот ввод произойдет, процесс быть активированным, с полученными данными через заменен на идентификатор .
Семантика редукции
Ключевое правило операционного сокращения, содержащее вычислительную сущность вычислений процесса, может быть задано исключительно в терминах параллельной композиции, упорядочивания, ввода и вывода. Детали этой редукции различаются между исчислениями, но суть остается примерно той же. Правило редукции:
Интерпретация этого правила сокращения:
- Процесс отправляет сообщение, здесь , вдоль канала . Вдвойне процесс получает это сообщение на канале .
- Как только сообщение будет отправлено, становится процессом , пока становится процессом , который с заполнителем заменен , данные, полученные на .
Класс процессов, которые может изменяться, поскольку продолжение операции вывода существенно влияет на свойства исчисления.
Прячется
Процессы не ограничивают количество соединений, которые могут быть установлены в данной точке взаимодействия. Но точки взаимодействия допускают вмешательство (т.е. взаимодействие). Для синтеза компактных, минимальных и композиционных систем решающее значение имеет способность ограничивать интерференцию. Операции сокрытия позволяют контролировать связи между точками взаимодействия при параллельном составлении агентов. Сокрытие можно обозначить по-разному. Например, в π-исчислении сокрытие имени в можно выразить как , а в CSP это можно было бы записать как.
Рекурсия и репликация
Представленные до сих пор операции описывают только конечное взаимодействие и, следовательно, недостаточны для полной вычислимости, которая включает в себя поведение без завершения. Рекурсия и репликация - это операции, которые позволяют конечное описание бесконечного поведения. Рекурсия хорошо известна из мира последовательностей. Репликация можно понимать как сокращение параллельной композиции счетно бесконечного числа процессы:
Нулевой процесс
Вычисления процесса обычно также включают нулевой процесс (по-разному обозначаемый, , , , или другой подходящий символ), не имеющий точек взаимодействия. Он совершенно неактивен, и его единственная цель - действовать как индуктивный якорь, на котором могут генерироваться более интересные процессы.
Алгебра дискретных и непрерывных процессов
Алгебра процессов изучалась для дискретного времени и непрерывного времени (реального времени или плотного времени). [4]
История
В первой половине 20-го века были предложены различные формализмы, отражающие неформальную концепцию вычислимой функции , с μ-рекурсивными функциями , машинами Тьюринга и лямбда-исчислением, возможно, наиболее известными примерами сегодня. Удивительный факт, что они по существу эквивалентны в том смысле, что все они кодируются друг в друге, поддерживает тезис Черча-Тьюринга . Еще одна общая особенность комментируется реже: все они легче всего воспринимаются как модели последовательных вычислений. Последующая консолидация информатики потребовала более тонкой формулировки понятия вычислений, в частности явного представления параллелизма и коммуникации. Модели параллелизма, такие как исчисления процессов, сети Петри в 1962 году и модель акторов в 1973 году, возникли в результате этого исследования.
Исследование процесса исчислений начали всерьез с Робин Милнер «плодотворную работу с по исчислению сообщающихся систем (CCS) в период с 1973 по 1980. Хоар » s процессы Взаимодействующие последовательные (НСП) впервые появился в 1978 году и впоследствии был разработан в полноценный процесс исчисления в начале 1980-х годов. По мере развития между CCS и CSP происходил обмен идеями. В 1982 году Ян Бергстра и Ян Виллем Клоп начали работу над тем, что стало известно как алгебра коммуникационных процессов (ACP), и ввели термин « алгебра процессов» для описания своей работы. [1] CCS, CSP и ACP составляют три основные ветви семейства вычислений процессов: большинство других вычислений процессов могут прослеживать свои корни до одного из этих трех исчислений.
Текущее исследование
Были изучены различные исчисления процессов, и не все они соответствуют обрисованной здесь парадигме. Наиболее ярким примером может быть окружающее исчисление . Этого следовало ожидать, поскольку расчеты процессов являются активной областью изучения. В настоящее время исследования процессов исчисления сосредоточены на следующих проблемах.
- Разработка новых расчетов процессов для лучшего моделирования вычислительных явлений.
- Нахождение корректных субсчетов данного исчисления процесса. Это ценно, потому что (1) большинство исчислений довольно дикие в том смысле, что они довольно общие и мало что можно сказать о произвольных процессах; и (2) вычислительные приложения редко исчерпывают все исчисления. Скорее они используют только очень ограниченные по форме процессы. Ограничение формы процессов в основном изучается с помощью систем типов .
- Логика для процессов, позволяющая рассуждать о (по сути) произвольных свойствах процессов, следуя идеям логики Хоара .
- Теория поведения: что означает совпадение двух процессов? Как мы можем определить, являются ли два процесса разными или нет? Можем ли мы найти представителей классов эквивалентности процессов? Обычно процессы считаются одинаковыми, если никакой контекст, то есть другие процессы, выполняющиеся параллельно, не может обнаружить разницу. К сожалению, сделать эту интуицию точной сложно, и в большинстве случаев она дает громоздкие характеристики равенства (которые в большинстве случаев также должны быть неразрешимыми из-за проблемы остановки ). Бисимуляции - это технический инструмент, который помогает рассуждать об эквивалентности процессов.
- Выразительность исчислений. Опыт программирования показывает, что на одних языках определенные проблемы решить легче, чем на других. Этот феномен требует более точной характеристики выразительности вычислений, моделирующих вычисления, чем та, которую дает тезис Черча-Тьюринга . Один из способов сделать это - рассмотреть кодировки между двумя формализмами и посмотреть, какие кодировки свойств потенциально могут сохранить. Чем больше свойств может быть сохранено, тем более выразительной будет цель кодирования. Для процесса конкрементов, прославленные результаты , что синхронное π-исчисление является более выразительным , чем его асинхронным вариантом, имеет ту же самую выразительную силу, что и более высокий порядок п-исчисление , [5] , но меньше , чем окружающий воздух исчисление . [ необходима цитата ]
- Использование процесса исчисления для моделирования биологических систем (стохастическое π-исчисление, BioAmbients, Beta Binders, BioPEPA, исчисление Брана). Некоторые считают, что композиционность, предлагаемая инструментами теории процессов, может помочь биологам организовать свои знания более формально.
Программные реализации
Идеи, лежащие в основе алгебры процессов, привели к появлению нескольких инструментов, включая:
- CADP
- Инструментальные средства параллелизма
- набор инструментов mCRL2
Связь с другими моделями параллелизма
История Моноид является свободным объектом , который в общем состоянии представлять историю отдельных процессов сообщающихся. Таким образом, исчисление процессов представляет собой формальный язык, наложенный на исторический моноид последовательным образом. [6] То есть, исторический моноид может записывать только последовательность событий с синхронизацией, но не определяет разрешенные переходы между состояниями. Таким образом, исчисление процессов для моноида истории то же самое, что формальный язык для свободного моноида (формальный язык - это подмножество множества всех возможных строк конечной длины в алфавите, порожденном звездой Клини ).
Использование каналов для коммуникации - одна из особенностей, отличающих вычисления процессов от других моделей параллелизма , таких как сети Петри и модель акторов (см. Модель акторов и вычисления процессов ). Одним из основных мотивов включения каналов в вычисления процессов было включение определенных алгебраических методов, тем самым облегчая алгебраические рассуждения о процессах.
Смотрите также
- Стохастический зонд
- Язык темпорального процесса
Рекомендации
- ^ а б Баэтен, JCM (2004). «Краткая история алгебры процессов» (PDF) . Сообщение CSR 04-02 . Vakgroep Informatica, Технический университет Эйндховена.
- ^ Пирс, Бенджамин (1996-12-21). «Основы исчисления для языков программирования». Справочник по информатике и инженерии . CRC Press. С. 2190–2207. ISBN 0-8493-2909-4.
- ^ Baeten, JCM; Браветти, М. (август 2005 г.). «Общая алгебра процессов» . Вычисления алгебраических процессов: первые двадцать пять лет и далее (Серия заметок БРИКС NS-05-3) . Бертиноро, Форли, Италия: БРИКС, Департамент компьютерных наук, Орхусский университет . Проверено 29 декабря 2007 .
- ^ Baeten, JCM; Мидделбург, Калифорния "Алгебра процессов с таймингом: реальное и дискретное время". CiteSeerX 10.1.1.42.729 . Цитировать журнал требует
|journal=
( помощь ) - ^ Санджорджи, Давиде (1993). Gaudel, M. -C .; Жуанно, Ж. -П. (ред.). «От π-исчисления к π-исчислению более высокого порядка - и обратно» . ТАПСОФТ'93: Теория и практика разработки программного обеспечения . Конспект лекций по информатике. Springer Berlin Heidelberg. 668 : 151–166. DOI : 10.1007 / 3-540-56610-4_62 . ISBN 9783540475989.
- ^ Мазуркевич, Антони (1995). «Введение в теорию трассировки» (PostScript) . В Diekert, V .; Розенберг, Г. (ред.). Книга следов . Сингапур: World Scientific. С. 3–41. ISBN 981-02-2058-8.
дальнейшее чтение
- Мэтью Хеннесси : алгебраическая теория процессов , MIT Press , ISBN 0-262-08171-7 .
- Карл Хоар : Коммуникационные последовательные процессы , Прентис Холл , ISBN 0-13-153289-8 .
- Эта книга была обновлена Джимом Дэвисом из вычислительной лаборатории Оксфордского университета, и новое издание доступно для загрузки в виде файла PDF на веб-сайте Using CSP .
- Робин Милнер : расчет коммуникационных систем , Springer Verlag, ISBN 0-387-10235-3 .
- Робин Милнер : Коммуникационные и мобильные системы: исчисление Пи , Springer Verlag, ISBN 0-521-65869-1 .
- Валк, Рюдигер ; Молдт, Дэниел; Кёлер-Бусмайер, Майкл, ред. (2011). "Глава 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF) . Formale Grundlagen der Informatik II: Modellierung und Analyze von Informatiksystemen . Theoretische Grundlagen der Informatik (на немецком языке). Часть 2. Гамбургский университет . FGI2. Архивировано (PDF) из оригинала на 2019-07-09 . Проверено 13 июля 2019 .