Введение
Модель параллельных вычислений
Модель актора в информатике — это математическая модель параллельных вычислений, рассматривающая актор как основной строительный блок параллельных вычислений. В ответ на полученное сообщение актор может: принимать локальные решения, создавать других акторов, отправлять сообщения и определять, как реагировать на следующее полученное сообщение. Акторы могут изменять свое собственное приватное состояние, но могут влиять друг на друга только косвенно посредством обмена сообщениями (что устраняет необходимость в синхронизации на основе блокировок). Модель актора возникла в 1973 году. Она использовалась как основа для теоретического понимания вычислений, так и как теоретическая база для нескольких практических реализаций параллельных систем. Связь модели с другими подходами обсуждается в статьях об акторной модели и процессах исчисления.
История
Согласно Карлу Хьюиту, в отличие от предыдущих моделей вычислений, модель актора была вдохновлена физикой, включая общую теорию относительности и квантовую механику. На нее также оказали влияние языки программирования Lisp, Simula, ранние версии Smalltalk, системы, основанные на возможностях, и коммутация пакетов. Ее разработка была "мотивирована перспективой высокопараллельных вычислительных машин, состоящих из десятков, сотен или даже тысяч независимых микропроцессоров, каждый из которых имеет свою собственную локальную память и процессор связи, взаимодействующих посредством высокопроизводительной сети связи". С тех пор появление массовой параллельности благодаря многоядерным и многопроцессорным компьютерным архитектурам возродило интерес к модели актора. После публикации Хьюитта, Бишопа и Штайгера в 1973 году, Ирен Грайф разработала операционную семантику для модели актора в рамках своей докторской диссертации. Два года спустя Генри Бейкер и Хьюитт опубликовали набор аксиоматических законов для систем акторов. Другие важные этапы включают диссертацию Уильяма Клингера 1981 года, представляющую денотационную семантику, основанную на силовых областях. Это привело к полному развитию теории модели актора. Основные работы по программной реализации были выполнены Рассом Аткинсоном, Джузеппе Атарди, Генри Бейкером, Джерри Барбером, Питером Бишопом, Питером де Йонгом, Кеном Каном, Генри Либерманом, Карлом Мэннингом, Томом Рейнхардтом, Ричардом Штайгером и Дэном Терио в группе семантики передачи сообщений в Массачусетском технологическом институте (MIT). Исследовательские группы под руководством Чака Сейца в Калифорнийском технологическом институте (Caltech) и Билла Далли в MIT создали компьютерные архитектуры, которые дополнительно развили передачу сообщений в модели. См. реализацию модели актора. Исследования модели актора проводились в Калифорнийском технологическом институте, лаборатории Токоро Киотского университета, Корпорации микроэлектроники и компьютерных технологий (MCC), Лаборатории искусственного интеллекта MIT, SRI, Стэнфордском университете, Университете Иллинойса в Урбана-Шампейн, Университете Пьера и Марии Кюри (University of Paris 6), Университете Пизы, лаборатории Йонезава Токийского университета, Центре математики и информатики (CWI) и в других учреждениях.
Приложения
Модель актора может использоваться как основа для моделирования, понимания и рассуждений о широком спектре конкурентных систем. Например:
Электронную почту можно смоделировать как систему акторов. Учетные записи моделируются как акторы, а адреса электронной почты – как адреса акторов. Веб-сервисы можно смоделировать как акторы, при этом конечные точки протокола простого доступа к объектам (SOAP) моделируются как адреса акторов. Объекты с блокировками (например, в Java и C#) можно смоделировать как сериализатор, при условии, что их реализация позволяет сообщениям непрерывно поступать (например, путем хранения во внутренней очереди). Сериализатор – это важный тип актора, определяемый тем, что он постоянно доступен для приема новых сообщений; каждое сообщение, отправленное сериализатору, гарантированно будет доставлено. Языки и нотации для тестирования и контроля испытаний (TTCN), как TTCN 2, так и TTCN 3, в значительной степени основаны на модели актора. В TTCN актор является компонентом тестирования: либо параллельным компонентом тестирования (PTC), либо главным компонентом тестирования (MTC). Компоненты тестирования могут отправлять и получать сообщения от удаленных партнеров (других компонентов тестирования или интерфейса тестовой системы), причем последний идентифицируется по адресу. Каждый компонент тестирования имеет связанное с ним дерево поведения; компоненты тестирования выполняются параллельно и могут быть динамически созданы родительскими компонентами тестирования. Встроенные языковые конструкции позволяют определить действия, которые необходимо выполнить при получении ожидаемого сообщения из внутренней очереди сообщений, например, отправку сообщения другому участнику или создание новых компонентов тестирования.
Семантика передачи сообщений
Модель акторов описывает семантику обмена сообщениями.
Спор о неограниченном недетерминизме
Первыми программами, работающими одновременно, можно считать обработчики прерываний. В процессе нормальной работы компьютеру необходимо было получать информацию извне (символы с клавиатуры, пакеты из сети и т. д.). Поэтому, когда информация поступала, выполнение компьютера прерывалось, и вызывался специальный код (называемый обработчиком прерывания) для помещения информации в буфер данных, откуда она могла быть впоследствии извлечена. В начале 1960-х годов прерывания стали использоваться для имитации одновременного выполнения нескольких программ на одном процессоре. Наличие параллелизма с общей памятью породило проблему управления параллелизмом. Изначально эта проблема рассматривалась как проблема взаимного исключения на одном компьютере. Эдсгер Дейкстра разработал семафоры, а позднее, в период с 1971 по 1973 год, Тони Хоар и Пер Бринч Хансен разработали мониторы для решения проблемы взаимного исключения. Однако ни одно из этих решений не предоставило конструкцию языка программирования, инкапсулирующую доступ к общим ресурсам. Эта инкапсуляция была позже реализована с помощью конструкции сериализатора ([Hewitt and Atkinson 1977, 1979] и [Atkinson 1980]). Первые модели вычислений (например, машины Тьюринга, постпродукции, лямбда-исчисление и т. д.) были основаны на математике и использовали глобальное состояние для представления вычислительного шага (позже обобщенное в [McCarthy and Hayes 1969] и [Dijkstra 1976] см. Порядок событий и глобальное состояние). Каждый вычислительный шаг представлял собой переход от одного глобального состояния вычисления к следующему. Подход, основанный на глобальном состоянии, был продолжен в теории автоматов для конечных автоматов и автоматов с нисходящим стеком, включая их недетерминированные версии. Такие недетерминированные автоматы обладают свойством ограниченного недетерминизма; то есть, если автомат всегда останавливается при запуске в начальном состоянии, то существует предел количества состояний, в которых он может остановиться. Эдсгер Дейкстра развил подход, основанный на недетерминированном глобальном состоянии. Модель Дейкстры вызвала споры относительно неограниченного недетерминизма (также называемого неограниченной непредсказуемостью), свойства параллелизма, при котором время ожидания обработки запроса может стать неограниченным в результате разрешения конфликтов за общие ресурсы, при этом гарантируется, что запрос в конечном итоге будет обработан. Хьюитт утверждал, что модель акторов должна обеспечивать гарантию обслуживания. В модели Дейкстры, хотя между выполнением последовательных инструкций на компьютере может пройти неограниченное время, параллельная программа, начавшаяся в хорошо определенном состоянии, может завершиться только в ограниченном количестве состояний [Dijkstra 1976]. Следовательно, его модель не могла обеспечить гарантию обслуживания. Дейкстра утверждал, что реализация неограниченного недетерминизма невозможна. Хьюитт возражал: не существует предела времени, необходимого для установления состояния вычислительной схемы, называемой арбитром (см. метастабильность (электроника)). Арбитры используются в компьютерах для обработки ситуации, когда компьютерные часы работают асинхронно по отношению к внешним входным данным, например, к вводу с клавиатуры, доступу к диску, сетевому вводу и т. д. Таким образом, для получения сообщения, отправленного на компьютер, может потребоваться неограниченное время, и в течение этого времени компьютер может пройти через неограниченное количество состояний. Модель акторов характеризуется неограниченным недетерминизмом, который был формализован в математической модели Уиллом Клингером с использованием теории доменов.
Теорема вычислительного представления
В модели акторов существует теорема вычислительного представления для систем, которые являются замкнутыми в том смысле, что они не получают сообщений извне. Математическое обозначение замкнутой системы строится из начального поведения и функции аппроксимации поведения. Эти функции получают все более точные приближения и строят обозначение (значение) следующим образом [Хьюит 2008; Клингер 1981]:
Таким образом, может быть математически охарактеризовано с точки зрения всех его возможных поведений (включая те, которые включают в себя неограниченный недетерминизм). Хотя не является реализацией , оно может быть использовано для доказательства обобщения тезиса Черча-Тьюринга-Россера-Клине [Клине 1943]:
Следствием вышеуказанной теоремы является то, что конечный актор может недетерминированно выдавать конечное число различных результатов.
Отношение к логическому программированию
Одной из ключевых мотиваций для разработки модели актора было понимание и решение проблем структуры управления, возникших при разработке языка программирования Planner. После того, как модель актора была изначально определена, важной задачей стало понимание возможностей модели в сравнении с тезисом Роберта Ковальски о том, что «вычисления могут быть сведены к дедукции». Хьюитт утверждал, что тезис Ковальски оказался ложным для параллельных вычислений в модели актора (см. Неопределенность в параллельных вычислениях). Тем не менее, предпринимались попытки расширить логическое программирование на параллельные вычисления. Однако Хьюитт и Агха [1991] утверждали, что полученные системы не являются дедуктивными в следующем смысле: вычислительные шаги параллельных систем логического программирования не вытекают дедуктивно из предыдущих шагов (см. Неопределенность в параллельных вычислениях). В последнее время логическое программирование было интегрировано в модель актора таким образом, чтобы сохранять логическую семантику. Также примечательно, что эта модель не основывалась на композиции последовательных процессов. Его работа отличалась от модели актора тем, что базировалась на фиксированном числе процессов с фиксированной топологией, обменивающихся числами и строками посредством синхронной связи. Оригинальная модель взаимодействующих последовательных процессов (CSP), опубликованная Тони Хоаром, отличалась от модели актора тем, что основывалась на параллельной композиции фиксированного числа последовательных процессов, соединенных в фиксированной топологии, и осуществляющих связь посредством синхронной передачи сообщений на основе имен процессов (см. История модели актора и исчислений процессов). Более поздние версии CSP отказались от связи на основе имен процессов в пользу анонимной связи через каналы, подход, также использованный в работе Милнера над исчислением взаимодействующих систем и π-исчислением. Эти ранние модели Милнера и Хоара обладали свойством ограниченного недетерминизма. Современная теоретическая CSP ([Hoare 1985] и [Roscoe 2005]) явно обеспечивает неограниченный недетерминизм. Сети Петри и их расширения (например, цветные сети Петри) схожи с акторами тем, что основаны на асинхронной передаче сообщений и неограниченном недетерминизме, а схожи с ранними CSP тем, что определяют фиксированные топологии элементарных этапов обработки (переходов) и хранилищ сообщений (мест).
Влияние
Модель акторов оказала значительное влияние как на развитие теории, так и на практическую разработку программного обеспечения.
Теория
Актерская модель оказала влияние на развитие π-исчисления и последующих исчислений процессов. В своей Тьюринг-лекции Робин Милнер писал: "Чистое лямбда-исчисление построено всего лишь на двух типах сущностей: термах и переменным. Возможно ли достичь той же лаконичности для исчисления процессов? Карл Хьюитт, с его моделью акторов, ответил на этот вызов задолго до этого; он утверждал, что значение, оператор над значениями и процесс должны быть сущностями одного и того же типа: актором. Эта цель произвела на меня впечатление, поскольку она подразумевает однородность и полноту выразительности. Но мне потребовалось много времени, чтобы понять, как достичь этой цели в терминах алгебраического исчисления. Итак, в духе Хьюитта, наш первый шаг – потребовать, чтобы все сущности, обозначаемые термами или доступные по именам – значения, регистры, операторы, процессы, объекты – были одного и того же типа; все они должны быть процессами."
Now, the pure lambda calculus is built with just two kinds of thing: terms and variables. Can we achieve the same economy for a process calculus? Carl Hewitt, with his actors model, responded to this challenge long ago; he declared that a value, an operator on values, and a process should all be the same kind of thing: an actor. This goal impressed me, because it implies the homogeneity and completeness of expression But it was long before I could see how to attain the goal in terms of an algebraic calculus
So, in the spirit of Hewitt, our first step is to demand that all things denoted by terms or accessed by names—values, registers, operators, processes, objects—are all of the same kind of thing; they should all be processes.
Практика
Модель акторов оказала значительное влияние на коммерческую практику. Например, Twitter использовал акторов для обеспечения масштабируемости. Также, Microsoft использовала модель акторов при разработке своей библиотеки асинхронных агентов. Ниже, в разделе «Библиотеки акторов и фреймворки», представлен список многих других библиотек акторов.
Программирование с актерами
В ряде различных языков программирования используется модель акторов или её вариации. К таким языкам относятся:
Библиотеки и структуры акторов
Актерские библиотеки или фреймворки также были реализованы для обеспечения возможности программирования в стиле актера на языках, в которых нет встроенных актеров. Некоторые из этих фреймворков:
Имя Статус Последний выпуск Лицензия Языки Otavia 2024 01 02 Apache 2.0 Scala Abstractor 2024 03 04 Apache 2.0 Java Xcraft Goblins 2022 08 30 MIT JavaScript ReActed 2022 11 30 Apache 2.0 Java Acteur 2020 04 16 Apache 2.0 / MIT Rust Bastion 2020 08 12 Apache 2.0 / MIT Rust Actix 2020 09 11 MIT Rust Aojet 2016 10 17 MIT Swift Actor 2017 03 09 MIT Java Actor4j 2020 01 31 Apache 2.0 Java Actr 2019 04 09 Apache 2.0 Java Vert.x 2018 02 13 Apache 2.0 Java, Groovy, Javascript, Ruby, Scala, Kotlin, Ceylon ActorFx 2013 11 13 Apache 2.0 .NET Akka (инструментарий) 2022 09 06 Коммерческая (с 2.7.0, Apache 2.0 до 2.6.20) Java и Scala Akka.NET 2020 08 20 Apache 2.0 .NET Apache Pekko 2023 07 26 Apache 2.0 Java и Scala Dapr 2019 10 16 Apache 2.0 Java, .NET Core, Go, Javascript, Python, Rust и C++ DOTNETACTORS 2021 06 14 MIT .NET, C#, Azure Service Bus Remact.Net 2016 06 26 MIT .NET, Javascript Ateji PX ? ? Java czmq 2016 11 10 MPL 2 C F# MailboxProcessor такой же, как F# (встроен в основную библиотеку) Apache License F# Korus 2010 02 04 GPL 3 Java Kilim 2018 11 09 MIT Java ActorFoundry (на основе Kilim) 2008 12 28 ? Java ActorKit 2011 09 13 BSD Objective C Cloud Haskell 2024 04 30 BSD Haskell CloudI 2023 10 27 MIT ATS, C/C++, Elixir/Erlang/LFE, Go, Haskell, Java, Javascript, OCaml, Perl, PHP, Python, Ruby, Rust Clutter 2017 05 12 LGPL 2.1 C, C++ (cluttermm), Python (pyclutter), Perl (perl Clutter) NAct 2012 02 28 LGPL 3.0 .NET Nact 2018 06 06 Apache 2.0 JavaScript/ReasonML Retlang 2011 05 18 New BSD .NET JActor 2013 01 22 LGPL Java Jetlang 2013 05 30 New BSD Java Haskell Actor 2008 New BSD Haskell GPars 2014 05 09 Apache 2.0 Groovy OOSMOS 2019 05 09 GPL 2.0 и коммерческая (двойная лицензия) C, C++ friendly Panini 2014 05 22 MPL 1.1 Язык программирования сам по себе PARLEY 2007 22 07 GPL 2.1 Python Peernetic 2007 06 29 LGPL 3.0 Java Picos 2020 02 04 MIT KRL PostSharp 2014 09 24 Коммерческая / Freemium .NET Pulsar 2016 07 09 New BSD Python Pulsar 2016 02 18 LGPL/Eclipse Clojure Pykka 2019 05 07 Apache 2.0 Python Termite Scheme 2009 05 21 LGPL Scheme (реализация Gambit) Theron 2014 01 18 MIT C++ Thespian 2020 03 10 MIT Python Quasar 2018 11 02 LGPL/Eclipse Java Libactor 2009 GPL 2.0 C Actor CPP 2012 03 10 GPL 2.0 C++ S4 2012 07 31 Apache 2.0 Java C++ Actor Framework (CAF) 2020 02 08 Boost Software License 1.0 и BSD 3 Clause C++11 Celluloid 2018 12 20 MIT Ruby LabVIEW Actor Framework 2012 03 01 National Instruments SLA LabVIEW LabVIEW Messenger Library 2021 05 24 BSD LabVIEW Orbit 2019 05 28 New BSD Java QP frameworks for real time embedded systems 2019 05 25 GPL 2.0 и коммерческая (двойная лицензия) C и C++ libprocess 2013 06 19 Apache 2.0 C++ SObjectizer 2021 12 28 New BSD C++17 rotor 2022 04 23 MIT License C++17 Orleans 2023 07 11 MIT License C#/.NET Skynet 2020 12 10 MIT License C/Lua Reactors.IO 2016 06 14 BSD License Java/Scala libagents 2020 03 08 Free software license C++11 Proto.Actor 2021 01 05 Free software license Go, C#, Python, JavaScript, Kotlin FunctionalJava 2018 08 18 BSD 3 Clause Java Riker 2019 01 04 MIT License Rust Comedy 2019 03 09 EPL 1.0 JavaScript VLINGO XOOM Actors 2023 02 15 Mozilla Public License 2.0 Java, Kotlin, JVM languages, C# .NET wasmCloud 2021 03 23 Apache 2.0 WebAssembly (Rust, TinyGo, Zig, AssemblyScript) ray 2020 08 27 Apache 2.0 Python cell 2012 08 02 New BSD License Python go actor 2022 08 16 GPL 3.0 Go Sento 2022 11 21 Apache 2.0 Common Lisp Tarant 2023 04 17 MIT Typescript, Javascript