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

В комп'ютерних науках модель акторів являє собою математичну модель паралельних обчислень, яка трактує поняття "актор" як універсальний примітив паралельного чисельного розрахунку: у відповідь на повідомлення, які він отримує, актор може приймати локальні рішення, створювати нових акторів, посилати свої повідомлення, а також встановлювати, як слід реагувати на подальші повідомлення. Модель акторів виникла в 1973 році. [1] Вона використовувалася як основа для розуміння обчислення процесів і як теоретична база для ряду практичних реалізацій паралельних систем.


1. Історія

На відміну від попередніх моделей обчислень, поява моделі акторів було стимульовано фізикою, в тому числі загальною теорією відносності та квантовою механікою. На процес формування моделі зробили також вплив мови програмування Lisp, Симула і ранні версії Smalltalk, а також методи параметричної захисту і комутації пакетів. Розвиток моделі було "мотивовано перспективою високопараллельних обчислювальних машин, що складаються з десятків, сотень і навіть тисяч незалежних мікропроцесорів, кожен зі своєю власною локальною пам'яттю і комунікаційним процесором, що спілкуються через мережу високопродуктивної зв'язку". [2] З масовим поширенням паралелізму, що виник завдяки розвитку багатоядерних архітектур, інтерес до моделі акторів значно зріс.

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


2. Фундаментальні концепції

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

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

  • відправити кінцеве число повідомлень іншим акторам;
  • створити кінцеве число нових акторів;
  • вибрати тип поведінки, яке буде використовуватися для наступного повідомлення на свою адресу.

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

Розв'язка відправника і посланих повідомлень стала фундаментальним досягненням моделі акторів, що забезпечила асинхронну зв'язок і керування структурами як прототип передачі повідомлень. [6]

Одержувачі повідомлень ідентифікуються за адресою, яку іноді називають "поштовою адресою". Таким чином, актор може взаємодіяти тільки з тими акторами, адреси яких він має. Він може витягти адреси з отриманих повідомлень або знати їх заздалегідь, якщо актор створений ним самим.

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


3. Формальні системи

За минулі роки були розроблені кілька різних формальних систем, які дозволяють описати моделі акторів. До них відносяться:

Є також формалізму, які не повністю відповідають моделі акторів в тому аспекті, що вони не формалізують гарантовану доставку повідомлень. До них, зокрема, відносяться:

  • Кілька різних алгебр акторів [9] [10]
  • Лінійна логіка. [11]

4. Застосування

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

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

5. Попередні моделі

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

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

Лямбда-числення Алонзо Черча можна розглядати як найперший мова програмування обміну повідомленнями. [1]). Наприклад, нижчевикладене лямбда-вираз реалізує деревоподібну структуру даних, якщо воно використовується з параметрами leftSubTree і rightSubTree. Якщо на вході такого дерева дати в якості параметра повідомлення "getLeft", воно поверне leftSubTree, а якщо дати повідомлення "" getRight ", то повернеться rightSubTree.

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

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


5.2. Симула

Мова Симула був піонером у використанні передачі повідомлень для обчислень, пов'язаних з дискретними додатками моделювання подій. У попередніх мовах моделювання ці програми були громіздкими і немодульнимі. На кожному кроці часу потрібно було виконувати велику центральну програму і оновлювати стану кожного модельованого об'єкта, залежні від стану інших об'єктів, з якими даний об'єкт взаємодіяв на поточному кроці моделювання. Крістен Нюгорд і Оле-Йохан Даль першими розвинули ідею (вперше викладена на семінарі IFIP в 1967 р.) застосування методів, вбудованих в кожен об'єкт, які оновлюють свої власні стану на підставі повідомлень від інших об'єктів. Крім того, вони ввели структури класів для об'єктів з спадкуванням. Їх нововведення значно підвищили модульність програм.

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


5.3. 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 зосередилися на розвитку наукових і технічних основ більш високого рівня паралелізму.


5.4. Мережі Петрі

До появи моделі акторів мережі Петрі широко використовувалися для моделювання недетермінованих обчислень. Однак, було визнано, що вони мають важливе обмеження: вони моделюють керування потоком, але не сам потік даних. Отже, вони не були легко компонуються, що тим самим обмежувало їх модульність. Хьюітт відзначив ще одну проблему мереж Петрі: складність одночасних дій. Елементарний крок обчислень в мережі Петрі являє собою перехід, при якому ознаки одночасності зникають на входах переходу і з'являються на його виходах. Фізичні основи використання примітивів з такого роду одночасністю виявилися сумнівними. Незважаючи на ці очевидні труднощі, метод сіток Петрі залишається популярним підходом до моделювання паралелізму, і все ще є предметом активних досліджень.


5.5. Нитки, блокування і буфери (канали)

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


6. Семантика передачі повідомлень

Ось що можна сказати щодо семантики переданих повідомлень в моделі акторів.

6.1. Необмежені недетермінірованние розбіжності

Можливо, першими паралельними програмами були обробники переривань. У процесі нормальної роботи комп'ютера необхідно отримувати інформацію ззовні (символи з клавіатури, пакети з мережі і т.д.). Коли отримано інформацію, виконання поточної програми "переривається" і запускається спеціальний код, званий обробником переривання, який поміщає інформацію в буфер, звідки вона може бути згодом лічена.

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

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

Едсгер Дейкстра розвинув далі підхід з недетермінованої глобальними станами. Модель Дейкстри породила суперечки про необмеженій індетермінізм. Необмежений індетермінізм (званий також необмеженим недетермінізмом) є властивістю співпадаючих обчислень, при якому величина затримки в обслуговуванні запиту може стати необмеженою в результаті арбітражного суперництва за спільні ресурси, в ​​той же час гарантується, що запит в кінцевому підсумку буде обслужений. Хьюітт стверджує, що модель акторів повинна забезпечити гарантії на надання послуги. Хоча в моделі Дейкстри не може бути необмеженої кількості часу між виконанням послідовних операцій на комп'ютері, паралельно виконувана програма, яка розпочала свою роботу в строго певному стані, може бути перервана лише в обмеженому числі станів [Dijkstra 1976]. Отже, модель Дейкстри не може забезпечити гарантії надання послуги. Дейкстра стверджував, що неможливо здійснити необмежений індетермінізм.

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

Необмежений індетермінізм є характерною рисою моделі акторів, в якій використовується математична модель Білла Клингера, заснована на теорії доменів. [2] У моделі акторів не існує глобального стану.


6.2. Прямий зв'язок і асинхронність

Повідомлення в моделі акторів не обов'язково буферизуются. У цьому її велика відмінність з попередніми підходами до моделі одночасних обчислень. Відсутність буферизації викликало велике непорозуміння під час розвитку моделі акторів, і до цих пір ця тема є предметом суперечок. Деякі дослідники стверджують, що повідомлення буферизуются в "ефірі" або "навколишньому середовищу". Крім того, повідомлення в моделі акторів просто надсилаються (наприклад, пакети в IP). Ніяких вимог на синхронне рукостискання з одержувачем не існує.


6.3. Створення нових акторів плюс передача адрес в повідомленнях означають змінювану топологію

Природним розвитком моделі акторів була можливість передачі адрес в повідомленнях. Під впливом мереж з комутацією пакетів Хьюітт запропонував розробити нову модель одночасних обчислень, в якій зв'язок не буде мати взагалі ніяких обов'язкових полів, всі вони можуть бути порожніми. Звичайно, якщо відправник повідомлення бажає, щоб одержувач мав доступ до адрес, яких він ще не має, адреса має бути відправлений у повідомленні.

У процесі обчислень, можливо, буде потрібно відправити повідомлення одержувачу, від якого пізніше потрібно отримати відповідь. Спосіб зробити це полягає в тому, щоб відправити повідомлення, в якому записаний адресу іншого актора, званого поновленням (іноді його також називають продовженням або стеком викликів). Одержувач може потім зробити відповідне повідомлення, яке буде відправлено на відновлення.

Створення акторів плюс включення адрес учасників в повідомлення означає, що модель акторів має потенційно змінну топологію в своїх відносинах один з одним, мимохідь на об'єкти в мові Симула, які в своїх відносинах один з одним також мають змінну топологію.


6.4. По суті одночасно

На відміну від попереднього підходу, заснованого на комбінуванні послідовних процесів, модель акторів була розроблена як одночасна модель за своєю суттю. Як написано в теорії моделей акторів, послідовність в ній являє собою особливий випадок, який випливає з одночасних обчислень.

6.5. Жодних вимог про порядок надходження повідомлень

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

У цьому відношенні модель акторів дзеркально відображає систему комутації пакетів, яка не гарантує, що пакети будуть отримані в порядку відправлення. Відсутність гарантій порядку доставки повідомлень дозволяє системі комутації пакетів буферізованние пакетів, використовувати декілька шляхів відправки пакетів, повторно пересилати пошкоджені пакети і використовувати інші методи оптимізації.

Наприклад, актори можуть використовувати конвеєр обробки повідомлень. Це означає, що в процесі обробки повідомлення M1 актор може варіювати поведінку, яка буде використовуватися для обробки наступного повідомлення. Зокрема, це означає, що він може почати обробку ще одного повідомлення M2 до завершення обробки M1. На тій підставі, що актору надано право використання конвеєра обробки повідомлень, ще не означає, що він цей конвеєр зобов'язаний використовувати. Чи буде повідомлення конвейерізовано чи ні - належить до завдань технічного компромісу. Як зовнішній спостерігач може дізнатися, що обробка повідомлення актора пройшла через конвеєр? На цей рахунок не існує ніякої двозначності щодо застосування актором можливості конвейеризации. Тільки якщо в конкретній реалізації виконання конвеєрної оптимізації зроблено неправильно, в цьому випадку може відбутися не очікуване поведінка, а щось інше.


6.6. Локальність

Іншою важливою характеристикою моделі акторів є локальність. Локальність означає, що при обробці повідомлення актор може відправляти повідомлення тільки за тими адресами, які він отримав з цього повідомлення, за адресами, які він вже мав до отримання повідомлення, і за адресами, які він створив при обробці повідомлення.

Локальність також означає, що не може одночасно відбутися кілька змін адрес. У цьому відношенні модель акторів відрізняється від деяких інших моделей паралелізму, наприклад, від мереж Петрі, в яких реалізації одночасно можуть бути видалені з декількох позицій і розміщені по інших адресах.


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

Ідея композиції систем акторів в більші утворення є важливим аспектом модульності, яка була розроблена в докторській дисертації Гуля Ага [5], пізніше розвиненою їм же разом з Іаном Мейсоном, Скоттом Смітом і Каролін Талкотт. [7]

6.8. Поведінка

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

Поведінка також звільняє модель акторів від деталей реалізації, як, наприклад, в Smalltalk-72 це робить маркер інтерпретатора потоку. Однак, важливо розуміти, що ефективне впровадження систем, що описуються моделлю акторів, вимагає розширену оптимізацію.


6.9. Моделювання інших паралельних систем

Інші системи паралелізму (наприклад, числення процесів) можуть бути змодельовані в моделі акторів з використанням двофазного протоколу фіксації. [17]

6.10. Теорема обчислювальних уявлень

У моделі акторів існує теорема обчислювальних уявлень для замкнутих систем, в тому сенсі, що вони не отримують повідомлень ззовні. В математичного запису замкнута система, що позначається як S, будується як найкраще наближення для початкового поведінки, званого S, з використанням апроксимуючої функції поведінки progression S, побудованої для S наступним чином (згідно публікації Хьюїтта 2008 р.):

Denote S ≡ ⊔ i ∈ ω progression S i (⊥ S)

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

Теорема перечислимого: якщо примітив актора замкнутої системи акторів є ефективним, то його можливі виходи рекурсивно перечислимого.
Доказ: безпосередньо випливає з теореми обчислювальних уявлень.

6.11. Зв'язок з математичною логікою

Розвиток моделі акторів має цікаву зв'язок з математичною логікою. Однією з ключових мотивацій для її розвитку була необхідність управління аспектами, які виникли в процесі розвитку мови програмування Planner. Після того, як модель акторів була спочатку сформульована, стало важливо визначити потужність моделі у відношенні тези Роберта Ковальського про те, що "обчислення можуть бути згруповані за логічним висновків". Теза Ковальського виявився хибним для одночасних обчислень в моделі акторів. Цей результат все ще є спірним, і він суперечить деяким попереднім уявленням, оскільки теза Ковальського вірним для послідовних обчислень і навіть для деяких видів паралельних обчислень, наприклад, для лямбда-числень.

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


6.12. Міграція

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

6.13. Безпека

Безпека акторів може бути забезпечена одним із таких способів:


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

Тонким моментом в моделі акторів є можливість синтезу адреси актора. У деяких випадках система безпеки може забороняти синтез адрес. Оскільки адресу актора це просто бітова рядок, то, очевидно, його можна синтезувати, хоча, якщо бітова рядок досить довга, підібрати адресу актора досить важко або навіть неможливо. SOAP в якості адреси кінцевої точки використовує URL, по якому актор розташований. Так як URL є рядком символів, то, очевидно, її можна синтезувати, хоч якщо застосувати шифрування, то підібрати рядок практично неможливо.

Синтезування адрес акторів зазвичай моделюються за допомогою відображення. Ідея полягає у використанні системи акторів для виконання відображення на фактичні адреси акторів. Наприклад, структура пам'яті комп'ютера може бути змодельована як система акторів, яка дає відображення. У разі адрес SOAP це моделювання DNS і відображення URL.


6.15. Відміну від інших моделей паралельної передачі повідомлень

Перша з опублікованих робіт Робіна Мілнера про паралелізм [18] була примітна тим, що вона не була заснована на композиції послідовних процесів. Його робота відрізнялася від моделі акторів, тому що вона була заснована на фіксованій кількості процесів фіксованого числа зв'язків у топології рядків, використовуваних для синхронізації зв'язку. Оригінальна модель взаємодіючих послідовних процесів (CSP), опублікована Ентоні Хоаром [19], відрізняється від моделі акторів, тому що вона заснована на паралельній композиції фіксованого числа послідовних процесів, пов'язаних в фіксовану топологію і спілкуються за допомогою синхронної передачі повідомлень на основі імен процесів. Пізніші версії CSP відмовилися від зв'язку на основі імен процесів, прийнявши принцип анонімної зв'язку по каналах. Цей підхід використовується також у роботі Мілнера про обчисленні спілкуються систем і пі-вирахуванні.

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


7. Актуальність зараз

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

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

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

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

Модель акторів застосовується також в клієнтах хмарних обчислень. [20]


8. Програмування з акторами

Велике число різних мов програмування використовують модель акторів або її варіанти. Серед них:

8.1. Ранні програмні мови з акторами

8.2. Пізніші програмні мови з акторами

  • 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

8.3. Бібліотеки та табличні структури з акторами

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

  • 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. Карл Хьюітт. Що таке зобов'язання? Фізичне, організаційне і соціальне. - www.pcs.usp.br/ ~ coin-aamas06/10_commitment-43_16pages.pdf (Англ.)
  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. - formal.cs.uiuc.edu / papers / ATactors_festschrift.pdf
  11. John Darlington; YK 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 - www.link9 (Англ.)
  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. CAR 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. CAR Hoare. Communicating sequential processes - portal.acm.org / citation.cfm? id = 359585 & dl = GUIDE & coll = GUIDE & CFID = 19884966 & CFTOKEN = 55490895 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 - lampwww.epfl.ch / ~ odersky/papers/jmlc06.pdf
  31. Philipp Haller and Martin Odersky, Actors that Unify Threads and Events. Technical report LAMP, January, 2007 - lamp.epfl.ch / ~ phaller/doc/haller07coord.pdf
  32. Srinivasan, Sriram; Alan Mycroft (2008). " Kilim: Isolation-Typed Actors for Java - www.malhar.net/sriram/kilim/kilim_ecoop08.pdf "(PDF). European Conference on Object Oriented Programming ECOOP 2008. .

10. Подальше читання

  • 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.
  • GM 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 - www.bitsavers.org.nyud.net/pdf/xerox/parc/techReports/link9 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 - www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-194.pdf 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 - portal.acm.org / citation.cfm? id = 512975 & coll = portal & dl = ACM 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, CAR 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, DC, 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.
  • CAR Hoare. Communicating Sequential Processes - www.usingcsp.com/ 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 - doi.acm.org/10.1145/97946.97955 ", 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 - www.link9 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 - www.ifs.uni-linz.ac.at/ ~ ecoop/cd/papers/ec89/ec890109.pdf 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 - ptolemy.eecs.berkeley.edu/papers/02/actorOrientedDesign/newFinal.pdf 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 - www.eecs.berkeley.edu/Pubs/TechRpts/2005/ERL-05-1.pdf 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 - www.pcs.usp.br/ ~ coin-aamas06/10_commitment-43_16pages.pdf 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.