Historia modelu aktora

W informatyce model aktora , opublikowany po raz pierwszy w 1973 r., jest matematycznym modelem obliczeń współbieżnych .

Kolejność zdarzeń a stan globalny

Podstawowym wyzwaniem przy definiowaniu modelu aktora jest to, że nie uwzględniał on stanów globalnych, więc krok obliczeniowy nie mógł być zdefiniowany jako przejście od jednego stanu globalnego do następnego, jak to miało miejsce we wszystkich poprzednich modelach obliczeniowych.

W 1963 roku w dziedzinie sztucznej inteligencji John McCarthy wprowadził zmienne sytuacyjne do logiki w rachunku sytuacyjnym . W McCarthy i Hayes 1969 sytuacja jest zdefiniowana jako „całkowity stan wszechświata w danej chwili”. Pod tym względem sytuacje McCarthy'ego nie nadają się do wykorzystania w modelu aktora, ponieważ nie ma on stanów globalnych.

Z definicji Aktora wynika, że ma miejsce wiele zdarzeń: lokalne decyzje, tworzenie Aktorów, wysyłanie wiadomości, odbieranie wiadomości oraz wyznaczanie sposobu odpowiedzi na kolejną otrzymaną wiadomość. Częściowe uporządkowania takich zdarzeń zostały aksjomatyzowane w modelu aktora i zbadano ich związek z fizyką (patrz teoria modelu aktora ).

Związek z fizyką

Według Hewitta (2006) model aktora jest oparty na fizyce, w przeciwieństwie do innych modeli obliczeń, które były oparte na logice matematycznej, teorii mnogości, algebrze itp. Fizyka wpłynęła na model aktora na wiele sposobów, zwłaszcza fizyka kwantowa i fizyka relatywistyczna . Jednym z problemów jest to, co można zaobserwować w systemach aktorów. Pytanie nie ma oczywistej odpowiedzi, ponieważ stawia wyzwania zarówno teoretyczne, jak i obserwacyjne, podobne do tych, które pojawiły się przy konstruowaniu podstaw fizyki kwantowej. Mówiąc konkretnie, w przypadku systemów Aktora zazwyczaj nie możemy obserwować szczegółów, na podstawie których określana jest kolejność nadejścia komunikatów dla Aktora (patrz Nieokreśloność w obliczeniach współbieżnych ). Próba zrobienia tego wpływa na wyniki, a nawet może przesunąć nieokreśloność w inne miejsce. np . zobacz metastabilność w elektronice . Zamiast obserwować wnętrze procesów arbitrażowych obliczeń aktora, czekamy na wyniki.

Modele przed modelem aktora

Model Actor opiera się na poprzednich modelach obliczeniowych.

rachunek lambda

Rachunek lambda Alonzo Churcha może być postrzegany jako najwcześniejszy język programowania przekazujący wiadomości (zob. Hewitt, Bishop i Steiger 1973; Abelson i Sussman 1985 ). Na przykład poniższe wyrażenie lambda implementuje strukturę danych drzewa, jeśli jest dostarczane z parametrami dla leftSubTree i rightSubTree . Kiedy takie drzewo otrzyma komunikat parametru „getLeft” , zwraca leftSubTree i podobnie, gdy otrzyma komunikat „getRight” zwraca rightSubTree .

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

Jednak semantyka rachunku lambda została wyrażona za pomocą podstawienia zmiennych , w którym wartości parametrów zostały podstawione w treść wywołanego wyrażenia lambda. Model substytucyjny nie nadaje się do współbieżności, ponieważ nie pozwala na współdzielenie zmieniających się zasobów. Zainspirowany rachunkiem lambda, interpreter języka programowania Lisp wykorzystał strukturę danych zwaną środowiskiem, dzięki czemu wartości parametrów nie musiały być podstawione w treści wywoływanego wyrażenia lambda. Pozwoliło to na współdzielenie efektów aktualizacji współdzielonych struktur danych, ale nie zapewniało współbieżności.

symulacja

Simula 67 była pionierem w wykorzystywaniu przekazywania komunikatów do obliczeń, motywowanym aplikacjami do symulacji zdarzeń dyskretnych. Aplikacje te stały się duże i niemodułowe w poprzednich językach symulacji. Na każdym etapie duży program centralny musiałby przechodzić i aktualizować stan każdego obiektu symulacji, który zmieniał się w zależności od stanu obiektów symulacji, z którymi współdziałał na tym etapie. Kristen Nygaard i Ole-Johan Dahl opracowali pomysł (po raz pierwszy opisany na warsztatach IFIP w 1967 r.) posiadania metod na każdym obiekcie który aktualizowałby swój własny stan lokalny na podstawie komunikatów z innych obiektów. Ponadto wprowadzili strukturę klasową dla obiektów z dziedziczeniem . Ich innowacje znacznie poprawiły modułowość programów.

Jednak Simula używał struktury kontroli coroutine zamiast prawdziwej współbieżności.

Pogawędka

Alan Kay był pod wpływem przekazywania wiadomości w kierowanym na wzorce wywołaniu Plannera podczas opracowywania Smalltalk -71. Hewitt był zaintrygowany Smalltalk-71, ale zniechęciła go złożoność komunikacji, która obejmowała wywołania z wieloma polami, w tym global , nadawca , odbiorca , styl odpowiedzi , status , odpowiedź , selektor operatora itp .

W 1972 roku Kay odwiedził MIT i omówił niektóre ze swoich pomysłów na Smalltalk-72 oparty na pracy Logo Seymoura Paperta i modelu obliczeń „małej osoby” używanym do nauczania dzieci programowania. Jednak przekazywanie wiadomości przez Smalltalk-72 było dość skomplikowane. Kod w tym języku był postrzegany przez tłumacza jako po prostu strumień tokenów. Jak opisał to później Dan Ingalls :

Pierwszy (token) napotkany (w programie) został wyszukany w kontekście dynamicznym, aby określić odbiorcę kolejnego komunikatu. Wyszukiwanie nazw rozpoczęło się od słownika klas bieżącej aktywacji. Jeśli tam się nie udało, został przeniesiony do nadawcy tej aktywacji i tak dalej w górę łańcucha nadawcy. Kiedy w końcu znaleziono powiązanie dla tokena, jego wartość stała się odbiorcą nowej wiadomości, a interpreter aktywował kod dla klasy tego obiektu.

Tak więc model przekazywania wiadomości w Smalltalk-72 był ściśle powiązany z konkretnym modelem maszyny i składnią języka programowania, która nie nadawała się do współbieżności. Ponadto, chociaż system został uruchomiony samodzielnie, konstrukcje językowe nie zostały formalnie zdefiniowane jako obiekty odpowiadające na Eval (patrz omówienie poniżej). Doprowadziło to niektórych do przekonania, że nowy model matematyczny współbieżnych obliczeń oparty na przekazywaniu wiadomości powinien być prostszy niż Smalltalk-72.

Kolejne wersje języka Smalltalk w dużej mierze podążały ścieżką wykorzystania wirtualnych metod Simuli w strukturze przesyłania komunikatów programów. Jednak Smalltalk-72 uczynił prymitywy, takie jak liczby całkowite, liczby zmiennoprzecinkowe itp. , w obiektach . Autorzy Simuli rozważali przekształcenie takich prymitywów w obiekty, ale powstrzymali się od tego głównie ze względów wydajnościowych. Java początkowo korzystała z wygody posiadania zarówno prymitywnych, jak i obiektowych wersji liczb całkowitych, liczb zmiennoprzecinkowych itp. Język C# język programowania (i późniejsze wersje Javy, począwszy od Javy 1.5) przyjęły mniej eleganckie rozwiązanie polegające na użyciu boksowania i rozpakowywania , którego wariant był używany wcześniej w niektórych implementacjach Lispa .

System Smalltalk stał się bardzo wpływowy, wprowadzając innowacje w wyświetlaczach bitmapowych, komputerach osobistych, interfejsie przeglądarki klas i na wiele innych sposobów. Aby uzyskać szczegółowe informacje, zobacz Kay's The Early History of Smalltalk . Tymczasem wysiłki Actora w MIT koncentrowały się na rozwoju nauki i inżynierii współbieżności wyższego poziomu. (Zobacz artykuł Jean-Pierre'a Briota, aby zapoznać się z pomysłami, które zostały opracowane później, jak włączyć niektóre rodzaje współbieżności aktorów do późniejszych wersji Smalltalk).

sieci Petriego

Przed opracowaniem modelu aktora sieci Petriego były szeroko stosowane do modelowania obliczeń niedeterministycznych. Jednak powszechnie uznano, że mają one ważne ograniczenie: modelowały przepływ sterowania, ale nie przepływ danych. W konsekwencji nie nadawały się one do łatwego komponowania, co ograniczało ich modułowość. Hewitt zwrócił uwagę na inną trudność związaną z sieciami Petriego: jednoczesne działanie. To znaczy atomowy krok obliczeń w sieciach Petriego jest przejściem, w którym tokeny są jednocześnie znikają z miejsc wejściowych przejścia i pojawiają się w miejscach wyjściowych. Fizyczne podstawy używania prymitywu z tego rodzaju jednoczesnością wydawały mu się wątpliwe. Pomimo tych widocznych trudności, sieci Petriego nadal są popularnym podejściem do modelowania współbieżności i nadal są przedmiotem aktywnych badań.

Wątki, blokady i bufory (kanały)

Przed modelem Actor współbieżność była definiowana w kategoriach maszynowych niskiego poziomu wątków , blokad i buforów ( kanałów ). Z pewnością jest tak, że implementacje modelu Actor zazwyczaj wykorzystują te możliwości sprzętowe. Nie ma jednak powodu, dla którego model nie mógłby zostać zaimplementowany bezpośrednio w sprzęcie bez ujawniania jakichkolwiek wątków i blokad sprzętowych. Ponadto nie ma koniecznego związku między liczbą aktorów, wątków i blokad, które mogą być zaangażowane w obliczenia. Implementacje modelu Actor mogą swobodnie wykorzystywać wątki i blokady w dowolny sposób zgodny z prawami dla Aktorów.

Abstrahowanie szczegółów implementacji

Ważnym wyzwaniem w definiowaniu modelu aktora było wyabstrahowanie szczegółów implementacji.

Rozważmy na przykład następujące pytanie: „Czy każdy aktor ma kolejkę, w której jego komunikacja jest przechowywana do czasu odebrania jej przez aktora w celu przetworzenia?” Carl Hewitt sprzeciwiał się uznawaniu takich kolejek za integralną część modelu aktora. Jedną z kwestii było to, że takie kolejki można modelować jako aktorów, którzy otrzymywali komunikaty w celu dodania i usunięcia z kolejki komunikacji. Inną kwestią było to, że niektórzy Aktorzy nie używaliby takich kolejek w ich rzeczywistej implementacji. Np. Aktor może mieć sieć arbitrów Zamiast. Oczywiście istnieje matematyczna abstrakcja, która jest sekwencją komunikatów otrzymanych przez Aktora. Ale ta sekwencja pojawiła się dopiero podczas działania Aktora. W rzeczywistości kolejność tej sekwencji może być nieokreślona (patrz Nieokreśloność w obliczeniach współbieżnych ).

Innym przykładem abstrakcji szczegółów implementacji była kwestia interpretacji : „Czy interpretacja powinna być integralną częścią modelu aktora?” Idea interpretacji polega na tym, że Aktor byłby definiowany przez sposób, w jaki jego skrypt programu przetwarzał eval . (W ten sposób Aktorzy byliby definiowani w sposób analogiczny do Lispa , który został „zdefiniowany” przez meta-kolistą procedurę interpretera o nazwie eval napisaną w Lispie). Hewitt argumentował przeciwko uczynieniu interpretacji integralną z modelem Aktora. Jedną z kwestii było przetworzenie ewaluacji wiadomości, skrypt programu Aktora sam miałby skrypt programu (który z kolei miałby ...)! Inną kwestią było to, że niektórzy Aktorzy nie używali interpretacji w swojej rzeczywistej interpretacji. Np. zamiast tego aktor może zostać zaimplementowany sprzętowo. Oczywiście nie ma nic złego w interpretacji jako takiej . Również implementacja tłumaczy wykorzystujących eval jest bardziej modułowa i rozszerzalna niż monolityczne podejście do interpretera w Lispie.

Model operacyjny

Niemniej jednak postęp w opracowaniu modelu był stały. W 1975 roku Irene Greif opublikowała w swojej rozprawie pierwszy model operacyjny .

Schemat

Gerald Sussman i Guy Steele zainteresowali się następnie aktorami i opublikowali artykuł na temat ich interpretera schematu , w którym doszli do wniosku, że „odkryliśmy, że„ aktorzy ”i wyrażenia lambda były identyczne w implementacji”. Według Hewitta rachunek lambda jest w stanie wyrazić pewne rodzaje równoległości, ale ogólnie nie współbieżności wyrażonej w modelu aktora. Z drugiej strony model aktora jest w stanie wyrazić całą równoległość w rachunku lambda.

Prawa dla aktorów

Dwa lata po tym, jak Greif opublikowała swój model operacyjny, Carl Hewitt i Henry Baker opublikowali Prawa dla aktorów.

Dowód ciągłości funkcji obliczalnych

Korzystając z praw modelu aktora, Hewitt i Baker udowodnili, że każdy aktor, który zachowuje się jak funkcja, jest ciągły w sensie zdefiniowanym przez Danę Scott (patrz semantyka denotacyjna ).

Specyfikacje i dowody

Aki Yonezawa opublikował swoją specyfikację i techniki weryfikacji dla aktorów. Russ Atkinson i Carl Hewitt opublikowali artykuł na temat specyfikacji i technik sprawdzania serializatorów, dostarczając wydajnego rozwiązania do enkapsulacji współdzielonych zasobów do kontroli współbieżności .

Charakterystyka matematyczna z wykorzystaniem teorii dziedzin

Wreszcie osiem lat po pierwszej publikacji aktora, Will Clinger (opierając się na pracach Irene Greif 1975, Gordona Plotkina 1976, Michaela Smytha 1978, Henry'ego Bakera 1978, Franceza, Hoare'a , Lehmanna i de Roevera 1979 oraz Milne'a i Milnora 1979) opublikował pierwszy zadowalający matematyczny model denotacyjny obejmujący nieograniczony niedeterminizm przy użyciu teorii domeny w swojej rozprawie w 1981 r. (patrz model Clingera ). Następnie Hewitt [2006] rozszerzył diagramy o czasy przybycia, aby skonstruować technicznie prostszy model denotacyjny , który jest łatwiejszy do zrozumienia. Zobacz Historia semantyki denotacyjnej .

Zobacz też

Carla Hewitta; Piotr Biskup; Richarda Steigera (1973). „Uniwersalny modułowy formalizm aktora dla sztucznej inteligencji” . IJCAI: 235–245. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
McCarthy, John (1963). „Sytuacje, działania i prawa przyczynowe”. Notatka dotycząca raportu technicznego . Laboratorium sztucznej inteligencji Uniwersytetu Stanforda (2).
McCarthy, John; Hayes, Patrick (1969). „Niektóre problemy filozoficzne z punktu widzenia sztucznej inteligencji”. Inteligencja maszynowa . Edunburgh University Press (4): 463–502. CiteSeerX 10.1.1.85.5082 .
Heisenberg, Werner (1971). Fizyka i nie tylko: spotkania i rozmowy . Przetłumaczone przez AJ Pomerans. Nowy Jork: Harper & Row. s. 63–64. ISBN 978-0061316227 .
Hewitt, Carl; Biskup Piotr; Greif, Irena; Smith, Brian; Matson, Todd; Steiger, Richard (styczeń 1974). „Indukcja i metaocena aktora”. Zapis konferencji z sympozjum ACM na temat zasad języków programowania : 153–168. CiteSeerX 10.1.1.104.295 . doi : 10.1145/512927.512942 . S2CID 33611569 .
Hewitt, Carl (kwiecień 1974). „Semantyka behawioralna nierekurencyjnej struktury sterowania” . Proceedings of Colloque Sur la Programmation : 385–407. ISBN 9783540068594 .
Greif, Irena; Hewitt, Carl (styczeń 1975). „Semantyka aktora PLANNER-73”. Zapis konferencji z sympozjum ACM na temat zasad języków programowania : 67–77. doi : 10.1145/512976.512984 . S2CID 18178340 .
Hewitt, Carl (wrzesień 1975). „Jak wykorzystać to, co wiesz”. Materiały z 4. Międzynarodowej Wspólnej Konferencji na temat Sztucznej Inteligencji . 1 : 189–198.
Greif, Irene (1975). Semantyka komunikowania się profesji równoległych (doktorat). MIT EECS .
Piekarz, Henryk; Hewitt, Carl (sierpień 1977). „Przyrostowe zbieranie śmieci procesów” . Materiały z sympozjum na temat języków programowania sztucznej inteligencji : 55–59. doi : 10.1145/800228.806932 . hdl : 1721.1/41969 . S2CID 1557419 . ^{[ stały martwy link ]}
Hewitt, Carl; Baker, Henry (sierpień 1977). „Prawa dotyczące komunikowania procesów równoległych”. Międzynarodowa Federacja Przetwarzania Informacji . hdl : 1721.1/41962 .
Yonezawa, Aki (1977). Techniki specyfikacji i weryfikacji programów równoległych oparte na semantyce przekazywania wiadomości (doktorat). MIT EECS .
Biskup Piotr (1977). Modułowo rozszerzalne systemy komputerowe o bardzo dużej przestrzeni adresowej (doktorat). MIT EECS .
Hewitt, Carl (czerwiec 1977). „Wyświetlanie struktur kontrolnych jako wzorców przekazywania wiadomości”. Dziennik sztucznej inteligencji . 8 (3): 323–364. doi : 10.1016/0004-3702(77)90033-9 . hdl : 1721.1/6272 .
Piekarz, Henry (1978). Systemy aktorów do obliczeń w czasie rzeczywistym (doktorat). MIT EECS .
Hewitt, Carl; Atkinson, Russ (styczeń 1979). „Techniki specyfikacji i dowodu dla serializatorów”. IEEE Journal o inżynierii oprogramowania : 10–23. doi : 10.1109/TSE.1979.234149 . hdl : 1721.1/5756 . S2CID 15272353 .
Kahna, Kena (1979). Obliczeniowa teoria animacji (doktorat). MIT EECS .
Hewitt, Carl; Attardi, Beppe; Lieberman, Henry (październik 1979). „Delegacja w przekazywaniu wiadomości”. Materiały z pierwszej międzynarodowej konferencji poświęconej systemom rozproszonym . Huntsville, AL.
Atkinson, Russ (1980). Automatyczna weryfikacja serializatorów (doktorat). MIT .
Kornfeld, Bill; Hewitt, Carl (styczeń 1981). „Metafora społeczności naukowej” (PDF) . Transakcje IEEE dotyczące systemów, człowieka i cybernetyki . 11 : 24–33. doi : 10.1109/TSMC.1981.4308575 . hdl : 1721.1/5693 . S2CID 1322857 .
Lieberman, Henry (maj 1981). „Myślenie o wielu rzeczach naraz bez dezorientacji: paralelizm w akcie 1”. Notatka AI MIT (626). hdl : 1721.1/6351 .
Lieberman, Henry (czerwiec 1981). „Zapowiedź aktu 1” . Notatka AI MIT (625). hdl : 1721.1/6350 .
Fryzjer, Gerry (1981). Rozumowanie o zmianach w kompetentnych systemach biurowych (doktorat). MIT EECS .
Kornfeld, Bill (1981). Paralelizm w rozwiązywaniu problemów (doktorat). MIT EECS .
Clinger, Will (1981). Podstawy semantyki aktora (doktorat). Matematyka MIT .
Theriault, Daniel (kwiecień 1982). „Podstawówka do języka Act-1”. Notatka AI MIT (672). hdl : 1721.1/5675 .
Lieberman, Henry; Hewitt, Carl (czerwiec 1983). „Gabage Collector w czasie rzeczywistym oparty na czasie życia obiektów” . Komunikaty ACM . 26 (6): 419. CiteSeerX 10.1.1.123.5055 . doi : 10.1145/358141.358147 . S2CID 14161480 .
Theriault, Daniel (czerwiec 1983). „Problemy w projektowaniu i wdrażaniu ustawy 2”. Raport techniczny MIT AI (728). hdl : 1721.1/6940 .
Lieberman, Henry (sierpień 1983). „Obiektowy symulator pasieki” (PDF) . Konferencja Amerykańskiego Stowarzyszenia Sztucznej Inteligencji . Waszyngton
Hewitt, Carl; de Jong, Peter (sierpień 1983). „Analiza ról opisów i działań w systemach otwartych”. Materiały z Krajowej Konferencji Sztucznej Inteligencji . hdl : 1721.1/5649 .
Jammer, M. (1985). „Problem EPR w jego rozwoju historycznym”. W P. Lahti, P. Mittelstaedt (red.). Sympozjum na temat podstaw współczesnej fizyki: 50 lat eksperymentu Einsteina-Podolskiego-Rosena Gedankena . Singapur: świat naukowy. s. 129–149.
Dobrze, A. (1986). Niepewna gra: realizm Einsteina i teoria kwantowa . Chicago: University of Chicago Press. ISBN 978-0226249476 .
Hewitt, Carl; Lieberman, Henry (listopad 1983). „Problemy projektowe w architekturze równoległej dla sztucznej inteligencji”. Notatka AI MIT (750). hdl : 1721.1/5653 .
Fuchs, Christopher (2002). „Mechanika kwantowa jako informacja kwantowa (i tylko trochę więcej)”. W A. Chrenikow (red.). Teoria kwantowa: rekonstrukcja podstaw . Växjo: Växjo University Press.
Hewitt, Carl (27 kwietnia 2006). „Czym jest zaangażowanie? Fizyczne, organizacyjne i społeczne” (PDF) . COIN@AAMAS .