Модель акторов и история расчетов процессов - Actor model and process calculi history

В Актерская модель и технологические расчеты поделитесь интересным история и совместная эволюция.

Ранняя работа

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

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

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

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

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

Публикация Тони Хора в 1978 году оригинала Связь последовательных процессов отличался от модели Actor, которая гласила:^[3]

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

...

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

...

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

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

• Примитивами параллелизма CSP были ввод, вывод, защищенные команды и параллельная композиция. тогда как модель актора основана на асинхронном одностороннем обмене сообщениями.
• Основной единицей исполнения был последовательный процесс. в отличие от модели Актера, в которой выполнение было принципиально параллельным. Последовательное выполнение проблематично, потому что многопроцессорные компьютеры по своей природе работают одновременно.
• Процессы имели фиксированную топологию связи. тогда как у Актеров была динамически изменяющаяся топология коммуникаций. Наличие фиксированной топологии проблематично, поскольку она исключает возможность динамической адаптации к изменяющимся условиям.
• Процессы были иерархически структурированы с использованием параллельной композиции. в то время как Актеры разрешили создание неиерархического исполнения с использованием фьючерсы [Бейкер и Хьюитт 1977]. Иерархическая параллельная композиция проблематична, потому что она исключает возможность создания процесса, который переживает своего создателя. Также передача сообщений является фундаментальным механизмом для создания параллелизма в модели акторов; отправка большего количества сообщений создает возможность большего параллелизма.
• Общение было синхронным тогда как общение с актерами было асинхронным. Синхронное общение проблематично, поскольку взаимодействующие процессы могут быть далеко друг от друга.
• Связь была между процессами тогда как в модели «Актер» связь с Актерами односторонняя. Синхронная связь между процессами проблематична, поскольку требует от процесса ожидания нескольких процессов.
• Структуры данных состояли из чисел, строк и массивов тогда как в модели «Актер» структуры данных были «Актерами». Ограничение структур данных числами, строками и массивами проблематично, потому что это запрещает программируемые структуры данных.
• Сообщения содержат числа и строки тогда как в модели Актера сообщения могут включать адреса Актеров. Не разрешать адреса в сообщениях проблематично, потому что это препятствует гибкости связи, потому что нет способа предоставить другому процессу возможность взаимодействовать с уже известным процессом.
• Модель CSP намеренно имела ограниченный недетерминизм. [Francez, Hoare, Lehmann, and de Roever, 1979], тогда как в модели «Актер» неограниченный недетерминизм. Дейкстра [1976] убедил Хора, что язык программирования с неограниченным недетерминизмом не может быть реализован. Следовательно, было невозможно гарантировать, что серверы, реализованные с использованием CSP, будут предоставлять услуги нескольким клиентам.

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

Милнер, и другие.

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

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

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

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

Хоар, и другие.

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

Хьюитт, и другие.

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

Дальнейшая совместная эволюция

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

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

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

• Гаспари и Заваттаро^[9][10]
• Ага и Тати^[11]

Смотрите также

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

Рекомендации

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

• Эдсгер Дейкстра. Дисциплина программирования Prentice Hall. 1976.
• Карл Хьюитт, и другие. Актерская индукция и мета-оценка Запись конференции ACM Symposium по принципам языков программирования, январь 1974 г.
• Карл Хьюитт, и другие. Поведенческая семантика нерекурсивной структуры управления Proceedings of Colloque sur la Programmation, апрель 1974 г.
• Ирен Грейф и Карл Хьюитт. Актерская семантика ПЛАНЕРА-73 Запись конференции ACM Symposium on Principles of Programming Languages. Январь 1975 г.
• Ирен Грейф. Семантика взаимодействующих параллельных процессов Докторская диссертация MIT EECS. Август 1975 г.
• Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы Материалы рабочей конференции ИФИП по формальному описанию концепций программирования. 1–5 августа 1977 г.
• Карл Хьюитт и Генри Бейкер Законы взаимодействия параллельных процессов ИФИП-77, август 1977 г.
• Генри Бейкер и Карл Хьюитт Инкрементная сборка мусора для процессов Материалы симпозиума по языкам программирования с искусственным интеллектом. Уведомления SIGPLAN от 12 августа 1977 г.
• Аки Ёнэдзава Методы спецификации и проверки параллельных программ на основе семантики передачи сообщений Докторская диссертация MIT EECS. Декабрь 1977 г.
• Генри Бейкер. Актерские системы для вычислений в реальном времени Докторская диссертация MIT EECS. Январь 1978 г.
• Джордж Милн и Робин Милнер. Параллельные процессы и их синтаксис JACM. Апрель 1979 г.
• Ниссим Франсез, МАШИНА. Hoare, Даниэль Леманн и Виллем де Ровер. Семантика недетермизма, параллелизма и коммуникации Журнал компьютерных и системных наук. Декабрь 1979 г.
• Нэнси Линч и Майкл Фишер. Об описании поведения распределенных систем в семантике параллельных вычислений. Springer-Verlag. 1979 г.
• Уилл Клингер. Основы актерской семантики Докторская диссертация по математике Массачусетского технологического института. Июнь 1981 г.
• J.A. Бергстра и Дж. Клоп. Алгебра процессов для синхронной связи Информация и контроль. 1984 г.
• Эйке Бест. Параллельное поведение: последовательности, процессы и аксиомы Конспект лекций по информатике, том 197 1984.
• Лука Карделли. Модель реализации рандеву-общения Семинар по параллелизму. Конспект лекций по информатике 197. Springer-Verlag. 1985 г.
• Робин Милнер, Иоахим Парроу и Дэвид Уокер. Расчет мобильных процессов Департамент компьютерных наук Эдинбург. Отчеты ECS-LFCS-89-85 и ECS-LFCS-89-86. Июнь 1989 г. Пересмотрено в сентябре 1990 г. и в октябре 1990 г. соответственно.
• Робин Милнер. Полиадическое исчисление пи: Учебное пособие Эдинбургский университет. Отчет LFCS ECS-LFCS-91-180. 1991 г.
• Кохей Хонда и Марио Токоро. Объектное исчисление для асинхронной связи ЕКООП 91.
• Бенджамин Пирс, Дидье Реми и Дэвид Тернер. Типизированный язык программирования высшего порядка на основе пи-исчисления Практикум по теории типов и ее применению в компьютерных системах. Киотский университет. Июль 1993 г.
• Седрик Фурне и Жорж Гонтье. Рефлексивная химическая абстрактная машина и объединенное исчисление ПОПЛ 1996.
• Седрик Фурне, Жорж Гонтье, Жан-Жак Леви, Люк Маранге и Дидье Реми. Подсчет мобильных агентов КОНКУР 1996.
• Жерар Будоль. Пи-исчисление в прямом стиле POPL 1997
• Тацуро Секигучи и Акинори Ёнэдзава. Исчисление с мобильностью кода FMOODS 1997.
• Лука Карделли и Эндрю Д. Гордон. Мобильная среда Основы науки о программном обеспечении и вычислительных структур, Морис Нива (ред.), Конспект лекций по информатике, Vol. 1378, Springer, 1998.
• Робин Милнер. Коммуникационные и мобильные системы: Пи-исчисление Издательство Кембриджского университета. 1999 г.
• J. C. M. Baeten. Краткая история алгебры процессов Теоретическая информатика. 2005. (ссылка действительна с 2015_26_5_0004)
• J.C.M. Baeten, T. Basten и M.A. Reniers. Алгебра коммуникационных процессов Издательство Кембриджского университета. 2005 г.
• Хэ Цзифэн и C.A.R. Хоар. Связывание теорий параллелизма Международный институт программных технологий Университета Организации Объединенных Наций Отчет № 328 УООН-МИПО, июль 2005 г.
• Лука Ачето и Эндрю Д. Гордон (редакторы). Вычисления алгебраических процессов: первые двадцать пять лет и далее Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
• Карл Хьюитт. Что такое обязательство? Физические, организационные и социальные МОНЕТА @ AAMAS. 27 апреля 2006 г.b.
• Карл Хьюитт (2007a) Что такое обязательство? Физический, организационный и социальный (пересмотренный) Пабло Норьега и др. редакторы. LNAI 4386. Springer-Verlag. 2007 г.
• Карл Хьюитт (2007b) Для крупномасштабных организационных вычислений требуется нестратифицированная параконсистентность и отражение МОНЕТА @ AAMAS'07.