Модель акторов

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

История

В отличие от предыдущих моделей вычислений, появление модели акторов было стимулировано физикой, в том числе общей теорией относительности и квантовой механикой. На процесс формирования модели оказали также влияние языки программирования Lisp, Симула и ранние версии Smalltalk, а также методы параметрической защиты и коммутации пакетов. Развитие модели было «мотивировано перспективой высокопараллельных вычислительных машин, состоящих из десятков, сотен и даже тысяч независимых микропроцессоров, каждый со своей собственной локальной памятью и коммуникационным процессором, общающихся через сеть высокопроизводительной связи».^[2] С массовым распространением параллелизма, возникшего благодаря развитию многоядерных архитектур, интерес к модели акторов значительно возрос.

После публикации Хьюитта, Бишопа и Штайгера в 1973 г. Ирен Грейф разработала операционную семантику для модели акторов как часть своей докторской диссертации.^[3] Два года спустя Генри Бейкер и Хьюитт опубликовали множество аксиоматических законов для систем акторов.^[4] Другие значимые вехи включают диссертацию Уильяма Клингера в 1981 году,^[2] представившего денотативную семантику, основанную на мощности доменов, и диссертацию Гуля Ага 1985 г., в который дано дальнейшее развитие семантической модели Клингера.^[5] В результате этих работ теория модели акторов получила полное развитие.

Фундаментальные концепции

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

Актор является вычислительной сущностью, которая в ответ на полученное сообщение может одновременно:

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

Может существовать произвольная последовательность вышеописанных действий, и все они могут выполняться параллельно.

Развязка отправителя и посланных сообщений стала фундаментальным достижением модели акторов, обеспечившая асинхронную связь и управление структурами как прототип передачи сообщений.^[6]

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

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

Формальные системы

За прошедшие годы были разработаны несколько различных формальных систем, которые позволяют описать модели акторов. К ним относятся:

• Операционная семантика^[3][7]
• Законы для систем акторов^[4]
• Денотационная семантика^[2][8]
• Семантика переходов.^[5]

Есть также формализмы, которые не полностью соответствуют модели акторов в том аспекте, что они не формализуют гарантированную доставку сообщений. К ним, в частности, относятся:

• Несколько различных алгебр акторов^[9][10]
• Линейная логика.^[11]

Применения

Модель акторов может быть использована в качестве основы для моделирования, понимания и аргументации по широкому спектру параллельных систем, например:

• Электронная почта (e-mail) может быть смоделирована как система акторов. Клиенты моделируется как акторы, а адреса электронной почты — как адреса акторов.
• Веб-сервисы с конечными точками SOAP могут быть смоделированы как адреса акторов.
• Объекты с семафорами (например, в Java и C#) могут быть смоделированы как параллельно-последовательный преобразователь, при условии, что их реализация такова, что сообщения могут приходить постоянно (возможно, они хранятся во внутренней очереди). Параллельно-последовательный преобразователь является важным видом актора, характеризующийся тем, что он постоянно доступен для прихода новых сообщений. Каждое сообщение, отправленное на параллельно-последовательный преобразователь гарантированно будет получено.
• Нотация тестирования и управления тестами (как TTCN-2, так и TTCN-3) довольно близко соответствует модели акторов. В TTCN актором является тест компонента: либо параллельной тест компонента (PTC), либо главный тест компонента (MTC). Тесты компонентов могут отправлять и получать сообщения на/от удалённых партнеров (равноправные тесты компонентов или тест интерфейса системы), причём последний идентифицируется по его адресу. Каждый тест компонента имеет дерево поведения, связанное с ним. Тесты компонентов запускаются параллельно, и могут быть динамически созданы родительскими тестами компонентов. Встроенные языковые конструкции позволяют определить действия, которые необходимо выполнить, когда сообщение получено из внутренней очереди сообщений, а также отправить сообщения другим равноправным субъектом или создать новые тесты компонентов.

Предшествующие модели

Модель акторов сформировалась на базе предшествующих моделей вычислений.

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

Лямбда-исчисление Алонзо Чёрча можно рассматривать как самый первый язык программирования обмена сообщениями.^[1] (см. также Абельсон и Суссман 1985). Например, нижеприведённое лямбда-выражение реализует древовидную структуру данных, если оно используется с параметрами leftSubTree и rightSubTree. Если на входе такого дерева дать в качестве параметра сообщение "getLeft", оно возвратит leftSubTree, а если дать сообщение ""getRight", то возвратится rightSubTree.

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

Семантика лямбда-исчислений выражается при помощи подстановок переменных, в которых значения параметров заменяются в теле вызываемых лямбда-выражений. Модель подстановок непригодна для параллелизма, поскольку она не обеспечивает возможность совместного использования ресурсов. Под влиянием лямбда-исчислений интерпретатор языка программирования Lisp использует структуры данных, называемые средой (environment ), такие, что значения параметров не должны заменяться в теле запускаемых лямбда-выражений. Это обеспечивает совместное использование эффектов обновления общих структур данных, но не обеспечивает параллелизм.

Симула

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

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

Smalltalk

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

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

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

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

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

Система Smalltalk впоследствии стала очень популярной и влиятельной, оказав инновационное воздействие на растровые дисплеи, персональные компьютеры, интерфейс браузеров и на многое другое.^[12] Тем временем усилия разработчиков модели акторов в MTI сосредоточились на развитии научных и технических основ более высокого уровня параллелизма.

Сети Петри

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

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

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

Семантика передачи сообщений

Вот что можно сказать относительно семантики передаваемых сообщений в модели акторов.

Неограниченные недетерминированные разногласия

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

В начале 1960-х прерывания стали использовать для имитации одновременного выполнения нескольких программ на одном процессоре.^[13] Наличие параллелизма с общей памятью привело к проблеме управления параллелизмом. Первоначально эта задача задумывалась как один из мьютексов на отдельном компьютере. Эдсгер Дейкстра разработал семафоры, а позднее, в период между 1971 и 1973 годах, Чарльз Хоар и Пер Хансен для решения проблемы мьютексов разработали мониторы.^[14][15][16] Однако, ни одно из этих решений не создавало в языках программирования конструкций, которые бы инкапсулировали доступ к совместным ресурсам. Инкапсуляцию сделали позже Хьюитт и Аткинсон, построив параллельно-последовательный преобразователь ([Hewitt, Atkinson 1977, 1979] и [Atkinson 1980]).

Первые модели вычислений (например, машина Тьюринга, машина Поста, лямбда-исчисление и т.д.) были основаны на математике и использовали понятие глобального состояния, чтобы определить шаг вычисления (позднее эти понятия обобщены в работах [McCarthy and Hayes 1969] и [Dijkstra 1976]). Каждый шаг вычисления шёл от одного глобального состояния вычислений до следующего. Глобальный подход к состоянию был продолжен в теории автоматов для конечных автоматов и машин со стеком, в том числе их недетерминированные версии. Такие недетерминированные автоматы имеют свойство ограниченного индетерминизма. То есть, если машина всегда стоит перед тем, как она переходит в исходное состояние, то имеется ограничение на число состояний, в которых она может находиться.

Эдсгер Дейкстра развил дальше подход с недетерминированными глобальными состояниями. Модель Дейкстры породила споры о неограниченном индетерминизме. Неограниченный индетерминизм (называемый также неограниченным недетерминизмом) является свойством совпадающих вычислений, при котором величина задержки в обслуживании запроса может стать неограниченной в результате арбитражного соперничества за общие ресурсы, в то же время гарантируется, что запрос в конечном итоге будет обслужен. Хьюитт утверждает, что модель акторов должна обеспечить гарантии на предоставление услуги. Хотя в модели Дейкстры не может быть неограниченного количества времени между выполнением последовательных операций на компьютере, параллельно выполняемая программа, которая начала свою работу в строго определённом состоянии, может быть прервана лишь в ограниченном числе состояний [Dijkstra 1976]. Следовательно, модель Дейкстры не может обеспечить гарантии предоставления услуги. Дейкстра утверждал, что невозможно осуществить неограниченный индетерминизм.

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

Неограниченный индетерминизм является характерной чертой модели акторов, в которой используется математическая модель Билла Клингера, основанная на теории доменов.^[2] В модели акторов не существует глобального состояния.

Прямая связь и асинхронность

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

Создание новых акторов плюс передача адресов в сообщениях означают изменяемую топологию

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

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

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

По сути одновременно

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

Никаких требований о порядке поступления сообщений

Хьюитт был против включения требований о том, что сообщения должны прибывать в том порядке, в котором они отправлены на модель актора. Если желательно упорядочить входящие сообщения, то это можно смоделировать с помощью очереди акторов, которая обеспечивает такую функциональность. Такие очереди акторов упорядочивали бы поступающие сообщений так, чтобы они были получены в порядке FIFO. В общем же случае, если актор X отправляет сообщение M1 актору Y, а затем тот же актор X отправляет другое сообщение M2 к Y, то не существует никаких требований о том, что M1 придёт к Y раньше M2.

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

Например, акторы могут использовать конвейер обработки сообщений. Это означает, что в процессе обработки сообщения M1 актор может варьировать поведение, которое будет использоваться для обработки следующего сообщения. В частности, это означает, что он может начать обработку ещё одного сообщения M2 до завершения обработки M1. На том основании, что актору предоставлено право использования конвейера обработки сообщений, ещё не означает, что он этот конвейер обязан использовать. Будет ли сообщение конвейеризовано или нет — относится к задачам технического компромисса. Как внешний наблюдатель может узнать, что обработка сообщения актора прошла через конвейер? На этот счёт не существует никакой двусмысленности в отношении применения актором возможности конвейеризации. Только если в конкретной реализации выполнение конвейерной оптимизации сделано неправильно, в этом случае может произойти не ожидаемое поведение, а нечто другое.

Локальность

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

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

Композиция систем акторов

Идея композиции систем акторов в более крупные образования является важным аспектом модульности, которая была разработана в докторской диссертации Гуля Ага^[5], позже развитой им же вместе с Ианом Мейсоном, Скоттом Смитом и Каролин Талкотт.^[7]

Поведение

Основным новшеством модели акторов было введение понятия поведения, определённое как математическая функция, выражающая действия актора, когда он обрабатывает сообщения, включая определение нового поведения на обработку следующего поступившего сообщения. Поведение обеспечивает функционирование математической модели параллелизма.

Поведение также освобождает модель акторов от деталей реализации, как, например, в Smalltalk-72 это делает маркер интерпретатора потока. Однако, важно понимать, что эффективное внедрение систем, описываемых моделью акторов, требует расширенную оптимизацию.

Моделирование других параллельных систем

Другие системы параллелизма (например, исчисление процессов) могут быть смоделированы в модели акторов с использованием двухфазного протокола фиксации.^[17]

Теорема вычислительных представлений

В модели акторов существует теорема вычислительных представлений для замкнутых систем, в том смысле, что они не получают сообщений извне. В математической записи замкнутая система, обозначаемая как S, строится как наилучшее приближение для начального поведения, называемого ⊥_S, с использованием аппроксимирующей функции поведения progression_S, построенной для S следующим образом (согласно публикации Хьюитта 2008 г.):

Denote_S ≡ ⊔_i∈ω progression_Sⁱ(⊥_S)

Таким образом, S может быть математически охарактеризована в терминах всех его возможных поведений (в том числе с учётом неограниченного индетерминизма). Хотя Denote_S не является реализацией S, она может быть использована для доказательства обобщения тезиса Чёрча-Тьюринга-Россера-Клини (см. Клини, 1943):

Теорема перечислимости: если примитив актора замкнутой системы акторов являются эффективным, то его возможные выходы рекурсивно перечислимы.

Доказательство: непосредственно вытекает из теоремы вычислительных представлений.

Связь с математической логикой

Развитие модели акторов имеет интересную связь с математической логикой. Одной из ключевых мотиваций для её развития была необходимость управления аспектами, которые возникли в процессе развития языка программирования Planner. После того как модель акторов была первоначально сформулирована, стало важно определить мощность модели в отношении тезиса Роберта Ковальского о том, что «вычисления могут быть сгруппированы по логическим выводам». Тезис Ковальского оказался ложным для одновременных вычислений в модели акторов. Этот результат всё ещё является спорным, и он противоречит некоторым предыдущим представлениям, поскольку тезис Ковальского верен для последовательных вычислений и даже для некоторых видов параллельных вычислений, например, для лямбда-исчислений.

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

Миграция

Миграцией в модели акторов называется способность актора изменить своё местоположение. Например, Аки Йонезава в своей диссертации моделировал почтовую службу, в которой акторы-клиенты могли войти, измененить местоположение во время работы и выйти. Актор, который мог мигрировать, моделировался как актор с определённым местом, изменяющемся при миграции актора. Однако достоверность этого моделирования является спорной и служит предметом исследований.

Безопасность

Безопасность акторов может быть обеспечена одним из следующих способов:

• аппаратным управлением, к которому акторы подключены физически;
• через специальное оборудование, как, например, в Барроуз B5000, Лисп-машине и т.д.
• через виртуальную машину, как, например, в виртуальной машине Java, в общеязыковой исполняющей среде и т.д.
• через операционную систему, как, например, в системах с параметрической защитой;
• использованием электронной цифровой подписи и/или шифрования для акторов и их адресов.

Синтез адресов акторов

Тонким моментом в модели акторов является возможность синтеза адреса актора. В некоторых случаях система безопасности может запрещать синтез адресов. Поскольку адрес актора это просто битовая строка, то, очевидно, его можно синтезировать, хотя, если битовая строка достаточно длинная, подобрать адрес актора довольно трудно или даже невозможно. SOAP в качестве адреса конечной точки использует URL, по которому актор расположен. Так как URL является строкой символов, то, очевидно, её можно синтезировать, хотя если применить шифрование, то подобрать строку практически невозможно.

Синтезирование адресов акторов обычно моделируются с помощью отображения. Идея состоит в использовании системы акторов для выполнения отображения на фактические адреса акторов. Например, структура памяти компьютера может быть смоделирована как система акторов, которая даёт отображение. В случае адресов SOAP это моделирование DNS и отображение URL.

Отличие от других моделей параллельной передачи сообщений

Первая из опубликованных работ Робина Милнера о параллелизме^[18] была примечательна тем, что она не была основана на композиции последовательных процессов. Его работа отличалась от модели акторов, потому что она была основана на фиксированном количестве процессов фиксированного числа связей в топологии строк, используемых для синхронизации связи. Оригинальная модель взаимодействующих последовательных процессов (CSP), опубликованная Энтони Хоаром^[19], отличается от модели акторов, потому что она основана на параллельной композиции фиксированного числа последовательных процессов, связанных в фиксированную топологию и общающихся с помощью синхронной передачи сообщений на основе имён процессов. Более поздние версии CSP отказались от связи на основе имён процессов, приняв принцип анонимной связи по каналам. Этот подход используется также в работе Милнера об исчислении общающихся систем и пи-исчислении.

Этим обеим ранним моделям Милнера и Хоара свойствен ограниченный индетерминизм. Современные теоретические CSP ([Hoare 1985] и [Roscoe 2005]) прямо предусматривают неограниченный индетерминизм.

Актуальность в настоящий момент

Через сорок лет после публикации закона Мура продолжающееся возрастание производительности микросхем происходит благодаря методам локального и глобального массового параллелизма. Локальный параллелизм задействован в новых микросхемах для 64-разрядных многоядерных микропроцессоров, в мульти-чиповых модулях и высокопроизводительных системах связи. Глобальный параллелизм в настоящее время задействован в новом оборудовании для проводной и беспроводной широкополосной пакетной коммутации сообщений (см. Wi-Fi и Ultra Wideband). Ёмкость хранения за счёт как локального, так и глобального паралеллизма, растёт в геометрической прогрессии.

По словам Хьюитта (см. Carl Hewitt, 2006a), модель акторов ставит вопросы в области компьютеров и архитектуры связи, языков параллельного программирования и веб-сервисов, включая следующие:

• масштабируемость: проблема расширения параллелизма, как локального, так и нелокального.
• прозрачность: преодоление пропасти между локальным и нелокальным параллелизмом. Прозрачность в настоящее время является спорным вопросом. Некоторые исследователи выступают за строгое разделение между локальным параллелизмом, используемом в языках параллельного программирования (например, Java и C#), и нелокальным параллелизмом, используемом в SOAP для веб-сервисов. Строгое разделение приводит к отсутствию прозрачности, что вызывает проблемы, когда желательно/необходимо внести изменения в локальные и нелокальные методы доступа к веб-службам.
• противоречивость: противоречивость является нормой, потому что все очень большие системы знаний о взаимодействии информационных систем человечества противоречивы. Эта противоречивость распространяется на документацию и технические характеристики очень больших систем (например, программное обеспечение Microsoft Windows, и т.д.), которые являются внутренне противоречивыми.

Многие идеи, введённые в модели акторов, в настоящее время находят также применение в многоагентных системах по этим же причинам (см. Хьюитт, 2006b, 2007b). Ключевым отличием является то, что агент системы (в большинстве определений) накладывает дополнительные ограничения на акторов, как правило, требуя, чтобы они использовали обязательства и цели.

Модель акторов применяется также в клиентах облачных вычислений.^[20]

Программирование с акторами

Большое число различных языков программирования используют модель акторов или её варианты. Среди них:

Ранние программные языки с акторами

• Act 1, 2 и 3 ^[21][22]
• Acttalk ^[23]
• Ani ^[24]
• Cantor ^[25]
• Rosette^[26]

Более поздние программные языки с акторами

• Actor-Based Concurrent Language (ABCL)
• ActorScript
• AmbientTalk^[27]
• Axum (язык программирования)^[28]
• E (язык программирования)
• Erlang
• Io
• Ptolemy Project
• Rebeca Modeling Language
• Reia (язык программирования)
• SALSA (язык программирования)^[29]
• Scala^[30][31]
• Go

Библиотеки и табличные структуры с акторами

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

• Akka - Java и Scala табличные структуры с акторами, обработка транзакций
• Ateji PX - Ateji PX обеспечивает модель акторов для Java
• Korus - параллельная распределённая табличная структура для Java, основанная на модели актора
• Kilim - табличные структуры на методе передачи сообщений для Java^[32]
• ActorFoundry - библиотека языка Java для программирования акторов
• Retlang для .NET
• Jetlang для Java
• Haskell-Actor для Haskell
• GPars - паралеллизм и библиотека актора для Groovy (бывшая GParallelizer)
• PARLEY - Python Actor Runtime Library
• Termite Scheme - обеспечивает Erlang-подобный паралеллизм для представления схем Gambit
• Theron - обеспечивает модель актора для C++.
• Celluloid - для Ruby

См. также

• Многоагентная система

Примечания

1. ↑ ^{1 2} Карл Хьюитт, Питер Бишоп, Ричард Штайгер: Универсальный модульный формализм акторов для искусственного интеллекта. IJCAI, 1973 (англ.)
2. ↑ ^{1 2 3 4} Уильям Клингер, Основы семантики акторов. MIT, докторская диссертация по математике, июнь 1981 (англ.)
3. ↑ ^{1 2} [Ирен Грейф, Семантика коммуникативных параллельных процессов. MIT, докторская диссертация, август 1975] (англ.)
4. ↑ ^{1 2} Г. Бейкер, К. Хьюитт. Законы взаимодействующих параллельных процессов. IFIP, август 1977 (англ.)
5. ↑ ^{1 2 3} Гуль Ага, Акторы: Модель параллельных вычислений в распределенных системах. MIT Press, докторская диссертация, 1986 (англ.)
6. ↑ Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
7. ↑ ^{1 2} Г. Ага, И. Мейсон, С. Смит, К. Талкотт. Основания для вычислений акторов. Journal of Functional Programming, январь, 1993 (англ.)
8. ↑ Карл Хьюитт. Что такое обязательство? Физическое, организационное и социальное. (англ.)
9. ↑ M. Gaspari, G. Zavattaro. An Algebra of Actors. Technical Report UBLCS-97-4. University of Bologna, 1997
10. ↑ G. Agha, P. Thati. An Algebraic Theory of Actors and Its Application to a Simple Object-Based Language.
11. ↑ John Darlington; Y. K. Guo (1994). «Formalizing Actors in Linear Logic» (International Conference on Object-Oriented Information Systems).
12. ↑ Алан Кэй. Ранняя история Smalltalk. ACM SIGPLAN, v. 28 (3), March, 1993, рр. 69–75 (англ.)
13. ↑ П. Хансен. Истоки параллельного программирования: от семафоров к удаленному вызову процедур. Springer, 2002 (англ.)
14. ↑ Per Hansen, Monitors and Concurrent Pascal: A Personal History, Comm. ACM 1996, pp 121-172
15. ↑ Hansen, P., Operating System Principles, Prentice-Hall, July 1973.
16. ↑ C.A.R. Hoare, Monitors: An Operating System Structuring Concept, Comm. ACM Vol. 17, No. 10. October 1974, pp. 549-557
17. ↑ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
18. ↑ Robin Milner. Processes: A Mathematical Model of Computing Agents in Logic Colloquium 1973.
19. ↑ C.A.R. Hoare. Communicating sequential processes CACM. August 1978.
20. ↑ Карл Хьюитт. Организация масштабируемых, надёжных, конфиденциальных клиентов для облачных вычислений. IEEE Internet Computing, v. 12 (5), 2008 (англ.)
21. ↑ Генри Либерман. Обзор Act 1. MIT AI, июнь 1981 (англ.)
22. ↑ Генри Либерман. Мышление о многом сразу без путаницы: Параллелизм в Act 1. MIT AI, июнь 1981 (англ.)
23. ↑ Jean-Pierre Briot. Acttalk: A framework for object-oriented concurrent programming-design and experience 2nd France-Japan workshop. 1999.
24. ↑ Ken Kahn. A Computational Theory of Animation MIT EECS Doctoral Dissertation. August 1979.
25. ↑ William Athas and Nanette Boden Cantor: An Actor Programming System for Scientific Computing in Proceedings of the NSF Workshop on Object-Based Concurrent Programming. 1988. Special Issue of SIGPLAN Notices.
26. ↑ Darrell Woelk. Developing InfoSleuth Agents Using Rosette: An Actor Based Language Proceedings of the CIKM '95 Workshop on Intelligent Information Agents. 1995.
27. ↑ Dedecker J., Van Cutsem T., Mostinckx S., D'Hondt T., De Meuter W. Ambient-oriented Programming in AmbientTalk. In “Proceedings of the 20th European Conference on Object-Oriented Programming (ECOOP), Dave Thomas (Ed.), Lecture Notes in Computer Science Vol. 4067, pp. 230-254, Springer-Verlag.”, 2006
28. ↑ Microsoft Cooking Up New Parallel Programming Language - Application Development - News & Reviews - eWeek.com
29. ↑ Carlos Varela and Gul Agha. Programming Dynamically Reconfigurable Open Systems with SALSA. ACM SIGPLAN Notices. OOPSLA’2001 Intriguing Technology Track Proceedings, 2001
30. ↑ Philipp Haller and Martin Odersky, Event-Based Programming without Inversion of Control, Proc. JMLC, September, 2006
31. ↑ Philipp Haller and Martin Odersky, Actors that Unify Threads and Events. Technical report LAMP, January, 2007
32. ↑ Srinivasan, Sriram; Alan Mycroft (2008). "Kilim: Isolation-Typed Actors for Java" (PDF). European Conference on Object Oriented Programming ECOOP 2008. .

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

• Stephen Kleene Recursive Predicates and Quantifiers American Mathematical Society Transactions. 1943.
• Paul Baran. On Distributed Communications Networks IEEE Transactions on Communications Systems, March 1964.
• Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation. 1998.
• Edsger Dijkstra Solution of a Problem in Concurrent Programming Control Communications of the ACM, 1965.
• Jack Dennis and Earl Van Horn. Programming Semantics for Multiprogrammed Computations CACM. March 1966.
• Ole-Johan Dahl and Kristen Nygaard. Class and subclass declarations IFIP TC2 Conference on Simulation Programming Languages. May 1967.
• Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969
• William A. Woods. Transition network grammars for natural language analysis CACM. 1970.
• Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
• Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
• G.M. Birtwistle, Ole-Johan Dahl, B. Myhrhaug and Kristen Nygaard. SIMULA Begin Auerbach Publishers Inc, 1973.
• Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
• Carl Hewitt, et al. Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, January 1974.
• Carl Hewitt, et al. Behavioral Semantics of Nonrecursive Control Structure Proceedings of Colloque sur la Programmation, April 1974.
• Irene Greif and Carl Hewitt. Actor Semantics of PLANNER-73 Conference Record of ACM Symposium on Principles of Programming Languages. January 1975.
• Carl Hewitt. How to Use What You Know IJCAI. September, 1975.
• Alan Kay and Adele Goldberg. Smalltalk-72 Instruction Manual Xerox PARC Memo SSL-76-6. May 1976.
• Edsger Dijkstra. A discipline of programming Prentice Hall. 1976. Рус. пер. Эдсгер Дейкстра Дисциплина программирования, М.: Мир, 1978
• Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1–5, 1977.
• Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceeding of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977.
• Gilles Kahn and David MacQueen. Coroutines and networks of parallel processes IFIP. 1977
• Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
• Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
• Carl Hewitt and Russ Atkinson. Synchronization in Actor Systems Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. 1977
• Carl Hewitt and Russ Atkinson. Specification and Proof Techniques for Serializers IEEE Journal on Software Engineering. January 1979.
• Ken Kahn. A Computational Theory of Animation MIT EECS Doctoral Dissertation. August 1979.
• Carl Hewitt, Beppe Attardi, and Henry Lieberman. Delegation in Message Passing Proceedings of First International Conference on Distributed Systems Huntsville, AL. October 1979.
• Nissim Francez, C.A.R. Hoare, Daniel Lehmann, and Willem-Paul de Roever. Semantics of nondetermiism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
• George Milne and Robin Milner. Concurrent processes and their syntax JACM. April 1979.
• Russ Atkinson. Automatic Verification of Serializers MIT Doctoral Dissertation. June, 1980.
• Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
• Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
• Daniel Theriault. A Primer for the Act-1 Language MIT AI memo 672. April 1982.
• Daniel Theriault. Issues in the Design and Implementation of Act 2 MIT AI technical report 728. June 1983.
• Henry Lieberman. An Object-Oriented Simulator for the Apiary Conference of the American Association for Artificial Intelligence, Washington, D. C., August 1983
• Carl Hewitt and Peter de Jong. Analyzing the Roles of Descriptions and Actions in Open Systems Proceedings of the National Conference on Artificial Intelligence. August 1983.
• Carl Hewitt and Henry Lieberman. Design Issues in Parallel Architecture for Artificial Intelligence MIT AI memo 750. Nov. 1983.
• Daniel Ingalls. The Evolution of the Smalltalk Virtual Machine in Smalltalk-80: Bits of History, Words of Advice. Addison Wesley. 1983.
• Hal Abelson, Gerald Jay Sussman and Julie Sussman, Structure and Interpretation of Computer Programs MIT Press and McGraw-Hill, 1985.
• C.A.R. Hoare. Communicating Sequential Processes Prentice Hall. 1985.
• Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985. Reprinted in The foundation of artificial intelligence---a sourcebook Cambridge University Press. 1990.
• Carl Manning. Traveler: the actor observatory ECOOP 1987. Also appears in Lecture Notes in Computer Science, vol. 276.
• William Athas and Charles Seitz Multicomputers: message-passing concurrent computers IEEE Computer August 1988.
• William Athas and Nanette Boden Cantor: An Actor Programming System for Scientific Computing in Proceedings of the NSF Workshop on Object-Based Concurrent Programming. 1988. Special Issue of SIGPLAN Notices.
• Jean-Pierre Briot. From objects to actors: Study of a limited symbiosis in Smalltalk-80 Rapport de Recherche 88-58, RXF-LITP, Paris, France, September 1988
• William Dally and Wills, D. Universal mechanisms for concurrency PARLE 1989.
• W. Horwat, A. Chien, and W. Dally. Experience with CST: Programming and Implementation PLDI. 1989.
• Carl Hewitt. Towards Open Information Systems Semantics Proceedings of 10th International Workshop on Distributed Artificial Intelligence. October 23–27, 1990. Bandera, Texas.
• Akinori Yonezawa, Ed. ABCL: An Object-Oriented Concurrent System MIT Press. 1990.
• K. Kahn and Vijay A. Saraswat, "Actors as a special case of concurrent constraint (logic) programming", in SIGPLAN Notices, October 1990. Describes Janus computer programming language.
• Carl Hewitt. Open Information Systems Semantics Journal of Artificial Intelligence. January 1991.
• Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From "Intelligent Agents" to Open Systems Science IEEE Transactions on Systems, Man, and Cybernetics. Nov./Dec. 1991.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
• William Dally, et al. The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms IEEE Micro. April 1992.
• S. Miriyala, G. Agha, and Y.Sami. Visulatizing actor programs using predicate transition nets Journal of Visual Programming. 1992.
• Alan Kay. The Early History of Smalltalk The second ACM conference on history of programming languages. 1993.
• Carl Hewitt and Carl Manning. Negotiation Architecture for Large-Scale Crisis Management AAAI-94 Workshop on Models of Conflict Management in Cooperative Problem Solving. Seattle, WA. Aug. 4, 1994.
• Darrell Woelk. Developing InfoSleuth Agents Using Rosette: An Actor Based Language Proceedings of the CIKM '95 Workshop on Intelligent Information Agents. 1995.
• Carl Hewitt and Carl Manning. Synthetic Infrastructures for Multi-Agency Systems Proceedings of ICMAS '96. Kyoto, Japan. December 8–13, 1996.
• S. Frolund. Coordinating Distributed Objects: An Actor-Based Approach for Synchronization MIT Press. November 1996.
• W. Kim. ThAL: An Actor System for Efficient and Scalable Concurrent Computing PhD thesis. University of Illinois at Urbana Champaign. 1997.
• Jean-Pierre Briot. Acttalk: A framework for object-oriented concurrent programming-design and experience 2nd France-Japan workshop. 1999.
• N. Jamali, P. Thati, and G. Agha. An actor based architecture for customizing and controlling agent ensembles IEEE Intelligent Systems. 14(2). 1999.
• Don Box, David Ehnebuske, Gopal Kakivaya, Andrew Layman, Noah Mendelsohn, Henrik Nielsen, Satish Thatte, Dave Winer. Simple Object Access Protocol (SOAP) 1.1 W3C Note. May 2000.
• M. Astley, D. Sturman, and G. Agha. Customizable middleware for modular distributed software CACM. 44(5) 2001.
• Carlos Varela. Worldwide Computing with Universal Actors: Linguistic Abstractions for Naming, Migration, and Coordination PhD thesis. U. of Illinois at Urbana-Champaign. 2001.
• N. Venkatasubramanian, C. Talcott, and G. Agha. A formal model for reasoning about adaptive QoS-enabled middleware Formal Methods Europe (FME). 2001.
• Edward Lee, S. Neuendorffer, and M. Wirthlin. Actor-oriented design of embedded hardware and software systems Journal of circuits, systems, and computers. 2002.
• P. Thati, R. Ziaei, and G. Agha. A Theory of May Testing for Actors Formal Methods for Open Object-based Distributed Systems. March 2002.
• P. Thati, R. Ziaei, and G. Agha. A theory of may testing for asynchronous calculi with locality and no name matching Algebraic Methodology and Software Technology. Springer Verlag. September 2002. LNCS 2422.
• Gul Agha and Carlos Varela. Worldwide Computing Middleware Practical Handbook on Internet Computing. CRC Press, 2004.
• Stephen Neuendorffer. Actor-Oriented Metaprogramming PhD Thesis. University of California, Berkeley. December, 2004
• Carl Hewitt (2006a) The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.
• Carl Hewitt (2006b) What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006b.
• Carl Hewitt (2007a) What is Commitment? Physical, Organizational, and Social (Revised) Pablo Noriega .et al. editors. LNAI 4386. Springer-Verlag. 2007.
• Carl Hewitt (2007b) Large-scale Organizational Computing requires Unstratified Paraconsistency and Reflection COIN@AAMAS'07.

Ссылки

• Программная модель акторов
• A now dated set of speculations by Paul Mackay can be found at Why has the actor model not succeeded?
• JavAct - a Java library for programming concurrent, distributed, and mobile applications using the actor model (and open implementation principles).
• Functional Java - a Java library of that includes an implementation of concurrent actors with code examples in standard Java and Java 7 BGGA style.
• ActorFoundry - a Java-based library for Actor programming. The familiar Java syntax, an ant build file and a bunch of example make the entry barrier very low.
• ActiveJava - a prototype Java language extension for Actor programming.
• Исходные тексты примера реализации модели акторов на C++.