История модели Актера

В информатике модель Актера , впервые опубликованная в 1973 году, представляет собой математическую модель параллельных вычислений .

Порядок событий и глобальное состояние

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

В 1963 году в области искусственного интеллекта Джон Маккарти представил ситуационные переменные в логике в Ситуационном исчислении. В McCarthy and Hayes 1969 ситуация определяется как «полное состояние Вселенной в данный момент времени». В этом отношении ситуации Маккарти не подходят для использования в модели Актера, поскольку она не имеет глобальных состояний.

Из определения Актера видно, что происходят многочисленные события: локальные решения, создание Актеров, отправка сообщений, получение сообщений и определение того, как реагировать на следующее полученное сообщение. Частичное упорядочение таких событий было аксиоматизировано в модели Актера, и исследована их связь с физикой (см. Теорию модели Актера ).

Отношение к физике

Согласно Хьюитту (2006), модель Актера основана на физике в отличие от других моделей вычислений, основанных на математической логике, теории множеств, алгебре и т. д. Физика во многом повлияла на модель Актера, особенно квантовая физика и релятивистская физика. . Одна из проблем заключается в том, что можно наблюдать в отношении акторных систем. Этот вопрос не имеет очевидного ответа, поскольку он ставит как теоретические, так и наблюдательные проблемы, аналогичные тем, которые возникли при построении основ квантовой физики. Говоря конкретно, для систем Актеров обычно мы не можем наблюдать детали, с помощью которых определяется порядок прибытия сообщений для Актера (см. Неопределенность в параллельных вычислениях ). Попытка сделать это влияет на результаты и может даже привести к возникновению неопределенности в другом месте. например , см. метастабильность в электронике . Вместо того, чтобы наблюдать за внутренностями арбитражных процессов вычислений Actor, мы ждем результатов.

Модели до модели Актера

Модель актера основана на предыдущих моделях вычислений.

Лямбда-исчисление

Лямбда -исчисление Алонзо Чёрча можно рассматривать как самый ранний для передачи сообщений язык программирования (см. Hewitt, Bishop и Steiger 1973; Abelson and Sussman 1985 ). Например, приведенное ниже лямбда-выражение реализует древовидную структуру данных, если оно снабжено параметрами для leftSubTree и rightSubTree . Когда такому дереву дается сообщение параметра «getLeft» , он возвращает leftSubTree и аналогично при получении сообщения «getRight» он возвращает rightSubTree .

 λ(leftSubTree,rightSubTree)
   λ(message)
     if (message == "getLeft") then leftSubTree
     else if (message == "getRight") then rightSubTree

Однако семантика лямбда-исчисления выражалась с помощью подстановки переменных , при которой значения параметров подставлялись в тело вызванного лямбда-выражения. Модель замещения не подходит для параллелизма, поскольку она не допускает возможности совместного использования изменяющихся ресурсов. Вдохновленный лямбда-исчислением, интерпретатор языка программирования Lisp использовал структуру данных, называемую средой, чтобы значения параметров не приходилось подставлять в тело вызываемого лямбда-выражения. Это позволяло совместно использовать результаты обновления общих структур данных, но не обеспечивало параллелизма.

начало

Simula 67 впервые использовала передачу сообщений для вычислений, мотивированную приложениями моделирования дискретных событий. В предыдущих языках моделирования эти приложения становились большими и немодульными. На каждом временном этапе большая центральная программа должна была бы проходить и обновлять состояние каждого объекта моделирования, которое менялось в зависимости от состояния тех объектов моделирования, с которыми она взаимодействовала на этом этапе. Кристен Найгаард и Оле-Йохан Даль разработали идею (впервые описанную на семинаре ИФИП в 1967 году) наличия методов для каждого объекта , которые обновляли бы его собственное локальное состояние на основе сообщений от других объектов. Кроме того, они представили структуру классов для объектов с наследованием . Их нововведения значительно улучшили модульность программ.

Однако Simula использовала структуру управления сопрограммами вместо настоящего параллелизма.

Смолток

Алан Кей на основе шаблонов находился под влиянием передачи сообщений при вызове Planner при разработке Smalltalk -71. Хьюитт был заинтригован Smalltalk-71, но его оттолкнула сложность коммуникации, которая включала вызовы со многими полями, включая global , sender , получатель , стиль ответа , статус , ответ , селектор оператора и т. д.

В 1972 году Кей посетил Массачусетский технологический институт и обсудил некоторые из своих идей для Smalltalk-72, основанных на и работе Сеймура Паперта «Логотип» модели вычислений «маленького человека», используемой для обучения детей программированию. Однако передача сообщений в Smalltalk-72 была довольно сложной. Код языка рассматривался интерпретатором как просто поток токенов. Как позже описал это Дэн Ингаллс :

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

Таким образом, модель передачи сообщений в Smalltalk-72 была тесно связана с конкретной моделью машины и синтаксисом языка программирования, который не допускал параллелизма. Кроме того, хотя система была загружена сама по себе, языковые конструкции не были формально определены как объекты, отвечающие на сообщения Eval (см. обсуждение ниже). Это заставило некоторых поверить, что новая математическая модель параллельных вычислений, основанная на передаче сообщений, должна быть проще, чем Smalltalk-72.

Последующие версии языка Smalltalk во многом пошли по пути использования виртуальных методов Simula в структуре передачи сообщений программ. Однако Smalltalk-72 превратил примитивы, такие как целые числа, числа с плавающей запятой и т. д. , в объекты . Авторы Simula рассматривали возможность превращения таких примитивов в объекты, но воздержались от этого в основном из соображений эффективности. Java сначала использовала способ использования как примитивных, так и объектных версий целых чисел, чисел с плавающей запятой и т. д. Язык программирования C# (и более поздние версии Java, начиная с Java 1.5) принял менее элегантное решение использования упаковки и распаковки , вариант которого использовался ранее в некоторых реализациях Lisp .

Система Smalltalk стала очень влиятельной, внеся инновации в растровые дисплеи, персональные компьютеры, интерфейс браузера классов и во многих других аспектах. Подробности см. в книге Кея « Ранняя история Smalltalk» . ^[1] Тем временем усилия Актеров в Массачусетском технологическом институте по-прежнему были сосредоточены на развитии науки и техники параллелизма более высокого уровня. (См. статью Жана-Пьера Брио, где представлены идеи, которые были развиты позже о том, как включить некоторые виды параллельного выполнения актеров в более поздние версии Smalltalk.)

Сети Петри

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

Потоки, блокировки и буферы (каналы)

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

Абстрагируем детали реализации

Важной проблемой при определении модели Актера было абстрагирование деталей реализации.

Например, рассмотрим следующий вопрос: «Есть ли у каждого актера очередь , в которой его сообщения хранятся до тех пор, пока актер не получит их для обработки?» Карл Хьюитт выступал против включения таких очередей в качестве неотъемлемой части модели Актера. Одним из соображений было то, что такие очереди сами по себе могут быть смоделированы как Актеры, получающие сообщения для поставить в очередь и отменить связь. Еще одно соображение заключалось в том, что некоторые актеры не будут использовать такие очереди в своей фактической реализации. Например, вместо этого у Актера может быть сеть арбитров . Конечно, существует математическая абстракция, представляющая собой последовательность сообщений , полученных Актером. Но эта последовательность возникла только во время действия Актера. Фактически порядок этой последовательности может быть неопределенным (см. Неопределенность в параллельных вычислениях ).

Еще одним примером абстрагирования деталей реализации был вопрос интерпретации : «Должна ли интерпретация быть неотъемлемой частью модели Актера?» Идея интерпретации состоит в том, что Актер будет определяться тем, как обрабатывается его программный сценарий. оценочные сообщения. (Таким образом, Актеры будут определены аналогично Лиспу , который «определен» процедурой метациклического интерпретатора с именем eval, написанный на Lisp.) Хьюитт выступал против того, чтобы интерпретация была неотъемлемой частью модели Актера. Одним из соображений было то, что для обработки eval , программный сценарий Актера сам по себе будет иметь программный сценарий (который, в свою очередь, будет иметь...)! Еще одно соображение заключалось в том, что некоторые актеры не будут использовать интерпретацию в своей реальной интерпретации. Например, вместо этого актер может быть реализован аппаратно. Конечно, нет ничего плохого в интерпретации как таковой . Также реализация интерпретаторов с использованием Сообщения eval более модульны и расширяемы, чем подход монолитного интерпретатора Lisp.

Операционная модель

Тем не менее, прогресс в разработке модели был устойчивым. первую операционную В 1975 году Ирен Грайф опубликовала в своей диссертации модель.

Схема

Затем Джеральд Сассман и Гай Стил заинтересовались актерами и опубликовали статью о своем интерпретаторе Scheme , в которой пришли к выводу, что «мы обнаружили, что «актеры» и лямбда-выражения идентичны по реализации». По мнению Хьюитта, лямбда-исчисление способно выражать некоторые виды параллелизма, но в целом не параллелизм, выраженный в модели Актера. С другой стороны, модель Актера способна выразить весь параллелизм в лямбда-исчислении.

Законы для актеров

Через два года после того, как Грайф опубликовала свою операционную модель, Карл Хьюитт и Генри Бейкер опубликовали «Законы для актеров».

Доказательство непрерывности вычислимых функций

Используя законы модели Актера, Хьюитт и Бейкер доказали, что любой Актер, ведущий себя как функция, непрерывен в смысле, определенном Даной Скотт (см. денотатационная семантика ).

Технические характеристики и доказательства

Аки Йонезава опубликовал свою спецификацию и методы проверки для актеров. Расс Аткинсон и Карл Хьюитт опубликовали статью о методах спецификации и доказательства для сериализаторов, предоставляющую эффективное решение для инкапсуляции общих ресурсов для управления параллелизмом .

Математическая характеристика с использованием теории предметной области

Наконец, через восемь лет после первой публикации «Актер», Уилл Клингер (основываясь на работах Ирен Грейф 1975, Гордона Плоткина 1976, Майкла Смита 1978, Генри Бейкера 1978, Франсеса, Хоара , Леманна и де Ровера 1979 и Милна и Милнора 1979) первую удовлетворительную математическую денотационную модель, включающую неограниченный недетерминизм , используя теорию предметной области опубликовал в своей диссертации в 1981 году (см. Модель Клингера ). Впоследствии Хьюитт [2006] дополнил диаграммы временем прибытия, чтобы построить технически более простую денотационную модель , которую легче понять. См. Историю денотационной семантики .

См. также

Ссылки

^ Кей, Алан (март 1993 г.). «Ранняя история Smalltalk» (PDF) . Уведомления ACM SIGPLAN . 28 (3): 69–75. дои : 10.1145/155360.155364 . Архивировано из оригинала (PDF) 5 февраля 2012 г.

Карл Хьюитт; Питер Бишоп; Ричард Штайгер (1973). «Универсальный модульный формализм актеров для искусственного интеллекта» . IJCAI: 235–245. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
Маккарти, Джон (1963). «Ситуации, действия и причинные законы». Памятка технического отчета (2). Лаборатория искусственного интеллекта Стэнфордского университета.
Маккарти, Джон; Хейс, Патрик (1969). «Некоторые философские проблемы с точки зрения искусственного интеллекта». Машинный интеллект (4). Издательство Эдунбургского университета: 463–502. CiteSeerX 10.1.1.85.5082 .
Гейзенберг, Вернер (1971). Физика и не только: встречи и беседы . Перевод Эй Джей Померанса. Нью-Йорк: Харпер и Роу. стр. 63–64. ISBN 978-0061316227 .
Хьюитт, Карл; Епископ Питер; Грейф, Ирен; Смит, Брайан; Мэтсон, Тодд; Штайгер, Ричард (январь 1974 г.). «Актерская индукция и метаоценка». Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования — POPL '73 . стр. 153–168. CiteSeerX 10.1.1.104.295 . дои : 10.1145/512927.512942 . S2CID 33611569 .
Хьюитт, Карл (апрель 1974 г.). «Поведенческая семантика нерекурсивной структуры управления» . Материалы коллока по программе Sur la Programmation : 385–407. ISBN 9783540068594 .
Грейф, Ирен; Хьюитт, Карл (январь 1975 г.). «Актерская семантика ПЛАНЕР-73». Материалы 2-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования — POPL '75 . стр. 67–77. дои : 10.1145/512976.512984 . S2CID 18178340 .
Хьюитт, Карл (сентябрь 1975 г.). «Как использовать то, что вы знаете». Материалы 4-й Международной совместной конференции по искусственному интеллекту . 1 : 189–198.
Грейф, Ирен (1975). Семантика общения параллельных профессий (доктор философии). MIT EECS .
Бейкер, Генри; Хьюитт, Карл (август 1977 г.). «Инкрементная сборка мусора процессов» . Материалы симпозиума по языкам программирования искусственного интеллекта : 55–59. дои : 10.1145/800228.806932 . hdl : 1721.1/41969 . S2CID 1557419 . ^{[ постоянная мертвая ссылка ]}
Хьюитт, Карл; Бейкер, Генри (август 1977 г.). «Законы связи параллельных процессов». Международная федерация обработки информации . hdl : 1721.1/41962 .
Ёнезава, Аки (1977). Методы спецификации и проверки параллельных программ, основанных на семантике передачи сообщений (доктор философии). MIT EECS .
Епископ, Питер (1977). Модульно расширяемые компьютерные системы с очень большим адресным пространством (доктор философии). MIT EECS .
Хьюитт, Карл (июнь 1977 г.). «Просмотр структур управления как шаблонов передачи сообщений». Журнал искусственного интеллекта . 8 (3): 323–364. дои : 10.1016/0004-3702(77)90033-9 . hdl : 1721.1/6272 .
Бейкер, Генри (1978). Актерские системы для вычислений в реальном времени (доктор философии). MIT EECS .
Хьюитт, Карл; Аткинсон, Расс (январь 1979 г.). «Техники спецификации и доказательства для сериализаторов». Транзакции IEEE по разработке программного обеспечения : 10–23. дои : 10.1109/TSE.1979.234149 . hdl : 1721.1/5756 . S2CID 15272353 .
Кан, Кен (1979). Вычислительная теория анимации (доктор философии). MIT EECS .
Хьюитт, Карл; Аттарди, Беппе; Либерман, Генри (октябрь 1979 г.). «Делегирование при передаче сообщений». Материалы первой международной конференции по распределенным системам . Хантсвилл, Алабама.
Аткинсон, Расс (1980). Автоматическая проверка сериализаторов (доктор философии). Массачусетский технологический институт .
Корнфельд, Билл; Хьюитт, Карл (январь 1981 г.). «Метафора научного сообщества» (PDF) . Транзакции IEEE по системам, человеку и кибернетике . 11 : 24–33. дои : 10.1109/TSMC.1981.4308575 . hdl : 1721.1/5693 . S2CID 1322857 .
Либерман, Генри (май 1981 г.). «Думать о множестве вещей одновременно, не запутываясь: параллелизм в акте 1». Памятка MIT AI (626). hdl : 1721.1/6351 .
Либерман, Генри (июнь 1981 г.). «Предварительный просмотр акта 1». Памятка MIT AI (625). HDL : 1721,1/6350 .
Барбер, Джерри (1981). Рассуждения об изменениях в интеллектуальных офисных системах (доктор философии). MIT EECS .
Корнфельд, Билл (1981). Параллелизм в решении задач (доктор философии). MIT EECS .
Клингер, Уилл (1981). Основы семантики актеров (доктор философии). институт Массачусетского технологического института Математический .
Терио, Дэниел (апрель 1982 г.). «Букварь для языка Акт-1». Памятка MIT AI (672). hdl : 1721.1/5675 .
Либерман, Генри; Хьюитт, Карл (июнь 1983 г.). «Сборщик мусора в реальном времени, основанный на времени жизни объектов». Коммуникации АКМ . 26 (6): 419. CiteSeerX 10.1.1.123.5055 . дои : 10.1145/358141.358147 . S2CID 14161480 .
Терио, Дэниел (июнь 1983 г.). «Проблемы разработки и реализации Закона 2». Технический отчет MIT AI (728). hdl : 1721.1/6940 .
Либерман, Генри (август 1983 г.). «Объектно-ориентированный симулятор пасеки» (PDF) . Конференция Американской ассоциации искусственного интеллекта . Вашингтон, округ Колумбия
Хьюитт, Карл; де Йонг, Питер (август 1983 г.). «Анализ роли описаний и действий в открытых системах». Материалы Национальной конференции по искусственному интеллекту . hdl : 1721.1/5649 .
Джаммер, М. (1985). «Проблема ЭПР в ее историческом развитии». В П. Лахти, П. Миттельштадт (ред.). Симпозиум по основам современной физики: 50 лет мысленному эксперименту Эйнштейна-Подольского-Розена . Сингапур: World Scientific. стр. 129–149.
Файн, А. (1986). Шатающаяся игра: эйнштейновский реализм и квантовая теория . Чикаго: Издательство Чикагского университета. ISBN 978-0226249476 .
Хьюитт, Карл; Либерман, Генри (ноябрь 1983 г.). «Проблемы проектирования в параллельной архитектуре для искусственного интеллекта». Памятка MIT AI (750). hdl : 1721.1/5653 .
Фукс, Кристофер (2002). «Квантовая механика как квантовая информация (и только немного больше)». В А. Хреникове (ред.). Квантовая теория: реконструкция основ . Векшо: Издательство Университета Векшо.
Хьюитт, Карл (27 апреля 2006 г.). «Что такое обязательства? Физические, организационные и социальные» (PDF) . МОНЕТА@AAMAS .

[kay1996-1] Кей, Алан (март 1993 г.). «Ранняя история Smalltalk» (PDF) . Уведомления ACM SIGPLAN . 28 (3): 69–75. дои : 10.1145/155360.155364 . Архивировано из оригинала (PDF) 5 февраля 2012 г.

[1]