Модель актера и история расчетов процессов

Модель актора и исчисление процессов имеют интересную историю и совместную эволюцию.

Ранние работы

Модель актера, впервые опубликованная в 1973 году, представляет собой математическую модель параллельных вычислений . Модель Актеров рассматривает «Актеров» как универсальные примитивы параллельных цифровых вычислений: в ответ на полученное сообщение Актер может принимать локальные решения, создавать больше Актеров, отправлять больше сообщений и определять, как реагировать на следующее полученное сообщение. .

В отличие от предыдущего подхода, основанного на составлении последовательных процессов, модель Актера была разработана как по своей сути конкурентная модель. В модели актера последовательность была особым случаем, возникшим в результате параллельных вычислений, как описано в теории модели актера .

Первая опубликованная работа Робина Милнера по параллелизму того же года. был также примечателен тем, что он позиционирует математическую семантику процессов связи как основу для понимания различных агентов взаимодействия, включая взаимодействие компьютера с памятью. Структура моделирования была основана на модели доменов Скотта и как таковая не была основана на последовательных процессах. Его работа отличалась от модели Актера следующим образом:

• Существует фиксированное количество процессов, в отличие от модели Актеров, которая позволяет количеству Актеров динамически изменяться.
• Единственными величинами, которые можно передавать в сообщениях, являются целые числа и строки, в отличие от модели Актеров, которая позволяет передавать адреса Актеров в сообщениях.
• Процессы имеют фиксированную топологию в отличие от модели актеров, которая позволяет изменять топологию.
• Коммуникация является синхронной, в отличие от модели актера, в которой между отправкой и получением сообщения может пройти неограниченное время.
• Семантика обеспечивала ограниченный недетерминизм в отличие от модели Актера с неограниченным недетерминизмом. Однако при ограниченном недетерминизме сервер не может гарантировать обслуживание своих клиентов, т. е . клиент может умереть от голода .

Позже Милнер снял некоторые из этих ограничений в своей работе по исчислению числа Пи (см. раздел Милнер и др. ниже).

Публикация Тони Хоаром в 1978 году оригинальной книги « Коммуникирующие последовательные процессы» отличалась от модели актера, которая гласит:

В этой статье предполагается, что ввод и вывод являются основными примитивами программирования и что параллельная композиция взаимодействующих последовательных процессов является фундаментальным методом структурирования программы. В сочетании с развитием защищенной команды Дейкстры эти концепции становятся удивительно универсальными. Их использование иллюстрируется примерами решений множества знакомых упражнений по программированию.

...

Программы, выраженные на предлагаемом языке, предназначены для реализации как на обычной машине с одним основным хранилищем, так и на фиксированной сети процессоров, соединенных каналами ввода/вывода (хотя в разных случаях подходят очень разные оптимизации). Следовательно, это довольно статический язык: текст программы определяет фиксированную верхнюю границу количества одновременно работающих процессов; здесь нет рекурсии и возможностей для переменных, имеющих значения процесса. В других отношениях язык был сокращен до минимума, необходимого для объяснения его более новых особенностей.

...

В этой статье предлагается рассматривать ввод, вывод и параллелизм как примитивы программирования, лежащие в основе многих знакомых и менее знакомых концепций программирования. Однако было бы неоправданно заключить, что эти примитивы могут полностью заменить другие понятия в языке программирования. Там, где более сложная конструкция (например, процедура или монитор) часто оказывается полезной, имеет свойства, которые легче доказуемы, а также может быть реализована более эффективно, чем в общем случае, существует веская причина для включения в язык программирования специальное обозначение для этой конструкции. Тот факт, что конструкция может быть определена в терминах более простых базовых примитивов, является полезной гарантией того, что ее включение логически согласуется с остальной частью языка.

Версия CSP 1978 года отличалась от модели Actor в следующих отношениях [Clinger 1981]:

• Примитивами параллелизма CSP были ввод, вывод, защищенные команды и параллельная композиция, тогда как модель актеров основана на асинхронном одностороннем обмене сообщениями.
• Фундаментальной единицей выполнения был последовательный процесс в отличие от модели Актера, в которой выполнение было принципиально параллельным. Последовательное выполнение проблематично, поскольку многопроцессорные компьютеры по своей сути являются параллельными.
• Процессы имели фиксированную топологию связи , тогда как Актеры имели динамически изменяющуюся топологию связи. Наличие фиксированной топологии проблематично, поскольку исключает возможность динамической адаптации к изменяющимся условиям.
• Процессы были иерархически структурированы с использованием параллельной композиции , тогда как Актеры позволяли создавать неиерархическое выполнение с использованием фьючерсов [Baker and Hewitt 1977]. Иерархическая параллельная композиция проблематична, поскольку она исключает возможность создания процесса, переживающего своего создателя. Кроме того, передача сообщений является фундаментальным механизмом создания параллелизма в модели Актера; отправка большего количества сообщений создает возможность большего параллелизма.
• Общение было синхронным, тогда как общение актеров было асинхронным. Синхронная коммуникация проблематична, поскольку взаимодействующие процессы могут находиться далеко друг от друга.
• Связь осуществлялась между процессами , тогда как в модели актеров связь является односторонней к актерам. Синхронная связь между процессами проблематична, поскольку процесс требует ожидания нескольких процессов.
• Структуры данных состояли из чисел, строк и массивов, тогда как в модели Актеров структуры данных были Актерами. Ограничение структур данных числами, строками и массивами проблематично, поскольку это запрещает программируемые структуры данных.
• Сообщения содержат числа и строки , тогда как в модели Актеров сообщения могут включать адреса Актеров. Не разрешать адреса в сообщениях проблематично, поскольку это исключает гибкость связи, поскольку нет способа предоставить другому процессу возможность взаимодействовать с уже известным процессом.
• Модель CSP намеренно имела ограниченный недетерминизм [Франсез, Хоар, Леманн и де Ровер, 1979], тогда как модель Актера имела неограниченный недетерминизм . Дейкстра [1976] убедил Хоара в том, что язык программирования с неограниченным недетерминизмом не может быть реализован. Следовательно, невозможно было гарантировать, что серверы, реализованные с использованием CSP, будут обслуживать множество клиентов.

Исчисление процессов и модель актера

Милнер и др.

В своей лекции Тьюринга Мильнер заметил следующее:

Теперь чистое лямбда-исчисление состоит всего из двух типов вещей: терминов и переменных . Можем ли мы добиться такой же экономии при исчислении процессов? Карл Хьюитт со своей моделью актеров уже давно ответил на этот вызов; он заявил, что значение, оператор значений и процесс должны быть одним и тем же: Актером . Эта цель произвела на меня впечатление, потому что она предполагает однородность и полноту выражения... Но прошло много времени, прежде чем я смог увидеть, как достичь этой цели с точки зрения алгебраического исчисления... Итак, в духе Хьюитта, наш первый шаг значит требовать, чтобы все вещи, обозначаемые терминами или доступные по именам — значения, регистры, операторы, процессы, объекты — были объектами одного и того же типа; они должны все быть процессами. После этого мы рассматриваем доступ по имени как исходный материал для вычислений...

В 2003 году Кен Кан вспоминал в сообщении об исчислении Пи :

Исчисление Пи основано на синхронном общении (рукопожатие). Около 25 лет назад я пошел на ужин с Карлом Хьюиттом и Робином Милнером (известными в области CCS и исчисления чисел Пи), и они спорили о синхронных и асинхронных коммуникационных примитивах. Карл использовал метафору почтового отделения, а Робин использовала телефон. Оба быстро признались, что одно можно реализовать в другом.

Хоар и др.

Тони Хоар , Стивен Брукс и А.В. Роско разработали и усовершенствовали теорию CSP до ее современной формы. Подход, использованный при разработке теоретической версии CSP, находился под сильным влиянием Робина Милнера работы по исчислению коммуникационных систем (CCS), и наоборот. За прошедшие годы между исследователями, работающими как над CSP, так и над CCS, произошло много плодотворных обменов идеями.

Хьюитт и др.

Уилл Клингер [1981] разработал первую модель денотационного актера для параллельных вычислений, которая воплощала неограниченный недетерминизм . Билл Корнфельд и Карл Хьюитт [1981] показали, что модель актера может охватывать крупномасштабный параллелизм. Ага разработал Актеров как фундаментальную модель для параллельных вычислений. На его работу по представлению абстракции и композиции Актеров, а также по разработке операционной семантики для Актеров на основе асинхронных коммуникационных деревьев явно повлияла работа Милнера по Исчислению коммуникационных систем (CCS). а также работа Клингера.

Дальнейшая коэволюция

π -исчисление , частично вдохновленное моделью актера, описанной Милнером выше, ввело динамическую топологию в исчисление процессов, позволяя динамически создавать процессы и передавать имена между различными процессами. Однако цель Милнера и Хоара - достичь алгебраического исчисления привела к критическому расхождению с моделью Актера: коммуникация в исчислениях процессов происходит не напрямую, как в модели Актера, а скорее косвенно через каналы (см. Модель Актера и исчисления процессов ). Напротив, недавняя работа над моделью актеров [Hewitt 2006, 2007a] уделяет особое внимание денотационным моделям и теореме о представлении .

Тем не менее, между моделью актора и исчислением процессов произошла интересная совместная эволюция. Монтанари и Талкотт обсудили, совместимы ли друг с другом модель актера и π-исчисление. Санджорджи и Уокер показал, как Actor обрабатывает структуры управления как шаблоны передачи сообщений. можно смоделировать с помощью π-исчисления.

Хотя для модели Актера были разработаны алгебраические законы, они не отражают важнейшее свойство гарантированной доставки сообщений, отправляемых сериализаторам. Например, см. следующее:

• Гаспари и Заваттаро
• Ага и Тати

См. также

• История денотационной семантики
• История модели Актера

Дальнейшее чтение

• Эдсгер Дейкстра. Дисциплина программирования Прентис Холл . 1976.
• Карл Хьюитт и др. Отчет конференции по индукции и метаоценке актеров симпозиума ACM по принципам языков программирования, январь 1974 г.
• Карл Хьюитт и др. Поведенческая семантика нерекурсивной структуры управления. Материалы конференции по программированию, апрель 1974 г.
• Ирен Грейф и Карл Хьюитт. Акторная семантика PLANNER-73 Протокол конференции симпозиума ACM по принципам языков программирования. Январь 1975 года.
• Ирен Грейф. Семантика взаимодействия параллельных процессов Докторская диссертация MIT EECS. Август 1975 года.
• Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы. Материалы рабочей конференции ИФИП по формальному описанию концепций программирования. 1–5 августа 1977 г.
• Законы Карла Хьюитта и Генри Бейкера для связи параллельных процессов ИФИП-77, август 1977 г.
• Генри Бейкер и Карл Хьюитт. Инкрементная сборка мусора процессов. Материалы симпозиума по языкам программирования искусственного интеллекта. Уведомления SIGPLAN от 12 августа 1977 г.
• Аки Йонезава Методы спецификации и проверки параллельных программ на основе семантики передачи сообщений Докторская диссертация MIT EECS. Декабрь 1977 года.
• Генри Бейкер . Акторные системы для вычислений в реальном времени. Докторская диссертация MIT EECS. Январь 1978 года.
• Джордж Милн и Робин Милнер . Параллельные процессы и их синтаксис JACM. Апрель 1979 года.
• Ниссим Франсез , КАР Хоар , Дэниел Леманн и Виллем де Ровер. Семантика недетерминизма, параллелизма и коммуникации. Журнал компьютерных и системных наук. Декабрь 1979 года.
• Нэнси Линч и Майкл Фишер. Об описании поведения распределенных систем в семантике параллельных вычислений. Спрингер-Верлаг. 1979.
• Уилл Клингер. Основы акторной семантики Докторская диссертация по математике Массачусетского технологического института. Июнь 1981 года.
• Дж. А. Бергстра и Дж. В. Клоп. Алгебра процессов для синхронной связи . Информация и управление. 1984.
• Эйке Бест . Параллельное поведение: последовательности, процессы и аксиомы. Конспект лекций по информатике, том 197, 1984.
• Лука Карделли. Модель реализации рандеву-коммуникации. Семинар по параллелизму. Конспект лекций по информатике 197. Springer-Verlag. 1985 г.
• Робин Милнер, Джоахим Пэрроу и Дэвид Уокер. Расчет мобильных процессов. Кафедра компьютерных наук, Эдинбург. Отчеты ECS-LFCS-89-85 и ECS-LFCS-89-86. Июнь 1989 г. Пересмотрено в сентябре 1990 г. и октябре 1990 г. соответственно.
• Робин Милнер. Полиадическое пи-исчисление: учебное пособие Эдинбургский университет. Отчет LFCS ECS-LFCS-91-180. 1991.
• Кохей Хонда и Марио Токоро. Объектное исчисление для асинхронной связи ECOOP 91 .
• Бенджамин Пирс, Дидье Реми и Дэвид Тернер. Типизированный язык программирования высшего порядка, основанный на семинаре по пи-исчислению по теории типов и ее применению в компьютерных системах. Киотский университет. Июль 1993 года.
• Седрик Фурне и Жорж Гонтье . Рефлексивная химическая абстрактная машина и исчисление соединений POPL 1996.
• Седрик Фурне, Жорж Гонтье, Жан-Жак Леви, Люк Маранже и Дидье Реми. Расчет мобильных агентов CONCUR 1996.
• Жерар Будоль. Пи-исчисление в прямом стиле POPL 1997.
• Тацуро Секигути и Акинори Ёнезава . Расчет с мобильностью кода FMOODS 1997.
• Лука Карделли и Эндрю Д. Гордон . Mobile Ambient Foundations of Software Science и вычислительные структуры, Морис Ниват (ред.), Конспекты лекций по информатике, Vol. 1378, Спрингер, 1998.
• Робин Милнер. Коммуникационные и мобильные системы: Pi-Calculus Издательство Кембриджского университета. 1999.
• JCM Баетен. Краткая история алгебры процессов . Теоретическая информатика. 2005 г. (ссылка действительна по состоянию на 26_5_0004 2015 г.)
• Ж. К. М. Бэтен, Т. Бастен и М. А. Ренье. Алгебра коммуникационных процессов Издательство Кембриджского университета. 2005.
• Хэ Цзифэн и КАР Хоар. Связывание теорий параллелизма, Международный институт программных технологий Университета Организации Объединенных Наций, Отчет UNU-IIST № 328. Июль 2005 г.
• Лука Ачето и Эндрю Д. Гордон (редакторы). Исчисление алгебраических процессов: первые двадцать пять лет и далее Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
• Карл Хьюитт. Что такое приверженность? Физический, организационный и социальный COIN@AAMAS. 27 апреля 2006б.
• Карл Хьюитт (2007a) Что такое приверженность? Физические, организационные и социальные (пересмотренные) Пабло Норьега и др. редакторы. LNAI 4386. Шпрингер-Верлаг. 2007.
• Карл Хьюитт (2007b) Крупномасштабные организационные вычисления требуют нестратифицированной паранепротиворечивости и отражения COIN@AAMAS'07.