Model aktora i historia rachunku procesów

Model aktora i rachunek procesów mają ciekawą historię i wspólną ewolucję.

Wczesna praca

Model aktora, opublikowany po raz pierwszy w 1973 r., jest matematycznym modelem obliczeń współbieżnych . Model aktora traktuje „aktorów” jako uniwersalne prymitywy współbieżnych obliczeń cyfrowych: w odpowiedzi na otrzymaną wiadomość aktor może podejmować lokalne decyzje, tworzyć więcej aktorów, wysyłać więcej wiadomości i określać, jak odpowiedzieć na następną otrzymaną wiadomość .

W przeciwieństwie do dotychczasowego podejścia opartego na komponowaniu procesów sekwencyjnych, model Actor został opracowany jako model z natury współbieżny. W modelu aktora sekwencyjność była szczególnym przypadkiem wywodzącym się z obliczeń współbieżnych, jak wyjaśniono w teorii modelu aktora .

Robina Milnera na temat współbieżności z tego samego roku była również godna uwagi, ponieważ przedstawia matematyczną semantykę procesów komunikacji jako ramy do zrozumienia różnych agentów interakcji, w tym interakcji komputera z pamięcią. Ramy modelowania zostały oparte na modelu domen Scotta i jako takie nie były oparte na procesach sekwencyjnych. Jego praca różniła się od modelu aktora w następujący sposób:

Istnieje stała liczba procesów, w przeciwieństwie do modelu Aktora, który pozwala na dynamiczną zmianę liczby Aktorów
Jedynymi wielkościami, które mogą być przekazywane w wiadomościach są liczby całkowite i łańcuchy znaków w przeciwieństwie do modelu aktora, który pozwala na przekazywanie adresów aktorów w wiadomościach
Procesy mają stałą topologię, w przeciwieństwie do modelu aktora, który pozwala na zmianę topologii
Komunikacja jest synchroniczna w przeciwieństwie do modelu aktora, w którym między wysłaniem a odebraniem wiadomości może upłynąć nieograniczony czas.
Semantyka zapewniła ograniczony niedeterminizm, w przeciwieństwie do modelu aktora z nieograniczonym niedeterminizmem. Jednak przy ograniczonym niedeterminizmie serwer nie jest w stanie zagwarantować usług swoim klientom, tzn . klient może umrzeć z głodu .

Milner później usunął niektóre z tych ograniczeń w swojej pracy nad rachunkiem Pic (patrz sekcja Milner i in. Poniżej).

Publikacja przez Tony'ego Hoare'a w 1978 roku oryginalnych Communicating Sequential Processes różniła się od modelu aktora, który stwierdza:

Ten artykuł sugeruje, że wejście i wyjście są podstawowymi prymitywami programowania i że równoległe składanie komunikujących się sekwencyjnych procesów jest podstawową metodą strukturyzowania programu. W połączeniu z rozwojem strzeżonego dowództwa Dijkstry koncepcje te są zaskakująco wszechstronne. Ich zastosowanie ilustrują przykładowe rozwiązania różnych znanych ćwiczeń programistycznych.

...

Programy wyrażone w proponowanym języku mają być realizowane zarówno przez konwencjonalną maszynę z jednym głównym magazynem, jak i przez stałą sieć procesorów połączonych kanałami wejścia / wyjścia (chociaż w różnych przypadkach odpowiednie są bardzo różne optymalizacje ). W rezultacie jest to raczej język statyczny: tekst programu określa stałą górną granicę liczby procesów działających jednocześnie; nie ma rekurencji ani możliwości dla zmiennych o wartościach procesowych. Również pod innymi względami język został okrojony do minimum niezbędnego do wyjaśnienia jego bardziej nowatorskich cech.

...

W tym artykule zasugerowano, że dane wejściowe, wyjściowe i współbieżność należy traktować jako prymitywy programowania, które leżą u podstaw wielu znanych i mniej znanych koncepcji programowania. Jednak byłoby nieuzasadnione stwierdzenie, że te prymitywy mogą całkowicie zastąpić inne pojęcia w języku programowania. Tam, gdzie bardziej rozbudowana konstrukcja (taka jak procedura lub monitor) jest często użyteczna, ma właściwości, które są łatwiejsze do udowodnienia i może być również zaimplementowana wydajniej niż przypadek ogólny, istnieje silny powód do włączenia do języka programowania specjalny zapis dla tej konstrukcji. Fakt, że konstrukcja może być zdefiniowana w kategoriach prostszych podstawowych prymitywów, jest użyteczną gwarancją, że jej włączenie jest logicznie spójne z resztą języka.

Wersja CSP z 1978 r. różniła się od modelu Actor pod następującymi względami [Clinger 1981]:

Elementami podstawowymi współbieżności CSP były dane wejściowe, wyjściowe, polecenia strzeżone i kompozycja równoległa, podczas gdy model aktora jest oparty na asynchronicznym jednokierunkowym przesyłaniu komunikatów.
Podstawową jednostką wykonania był proces sekwencyjny, w przeciwieństwie do modelu aktora, w którym wykonanie było zasadniczo współbieżne. Wykonywanie sekwencyjne jest problematyczne, ponieważ komputery wieloprocesorowe są z natury współbieżne.
Procesy miały ustaloną topologię komunikacji, podczas gdy Aktorzy mieli dynamicznie zmieniającą się topologię komunikacji. Posiadanie stałej topologii jest problematyczne, ponieważ wyklucza możliwość dynamicznego dostosowywania się do zmieniających się warunków.
Procesy były ustrukturyzowane hierarchicznie przy użyciu kompozycji równoległej, podczas gdy Aktorzy pozwalali na tworzenie niehierarchicznej realizacji przy użyciu przyszłości [Baker i Hewitt 1977]. Hierarchiczna kompozycja równoległa jest problematyczna, ponieważ wyklucza możliwość stworzenia procesu, który przeżyje swojego twórcę. Również przekazywanie komunikatów jest podstawowym mechanizmem generowania równoległości w modelu aktora; wysyłanie większej liczby komunikatów generuje możliwość większej równoległości.
Komunikacja była synchroniczna, podczas gdy komunikacja aktora była asynchroniczna. Komunikacja synchroniczna jest problematyczna, ponieważ procesy interakcji mogą być daleko od siebie.
Komunikacja odbywała się między procesami , podczas gdy w modelu Aktora komunikacja jest jednokierunkowa z Aktorami. Synchroniczna komunikacja między procesami jest problematyczna, ponieważ wymaga od procesu oczekiwania na wiele procesów.
Struktury danych składały się z liczb, ciągów znaków i tablic, podczas gdy w modelu aktorów struktury danych były aktorami. Ograniczanie struktur danych do liczb, łańcuchów i tablic jest problematyczne, ponieważ zabrania programowalnych struktur danych.
Komunikaty zawierają liczby i ciągi znaków, podczas gdy w modelu Actor komunikaty mogą zawierać adresy Aktorów. Niedopuszczanie adresów w komunikatach jest problematyczne, ponieważ wyklucza elastyczność w komunikacji, ponieważ nie ma możliwości dostarczenia innemu procesowi możliwości komunikowania się z już znanym procesem.
Model CSP celowo miał ograniczony niedeterminizm [Francez, Hoare, Lehmann i de Roever 1979], podczas gdy model aktora miał nieograniczony niedeterminizm . Dijkstra [1976] przekonał Hoare'a, że język programowania z nieograniczonym niedeterminizmem nie może zostać zaimplementowany. W związku z tym nie można było zagwarantować, że serwery wdrożone przy użyciu CSP będą obsługiwać wielu klientów.

Rachunek procesowy i model aktora

Milnera i in.

W swoim wykładzie Turinga Milner zauważył, co następuje:

Czysty rachunek lambda składa się tylko z dwóch rodzajów elementów: terminów i zmiennych . Czy możemy osiągnąć taką samą ekonomię dla rachunku procesów? Carl Hewitt ze swoim modelem Actors już dawno temu odpowiedział na to wyzwanie; zadeklarował, że wartość, operator wartości i proces powinny być tym samym rodzajem rzeczy: Aktorem . Ten cel zrobił na mnie wrażenie, ponieważ implikuje jednorodność i kompletność wypowiedzi… Ale minęło dużo czasu, zanim mogłem zobaczyć, jak osiągnąć cel w kategoriach rachunku algebraicznego… Tak więc, w duchu Hewitta, nasz pierwszy krok polega na żądaniu, aby wszystkie rzeczy oznaczane terminami lub dostępne za pomocą nazw – wartości, rejestry, operatory, procesy, przedmioty – były tego samego rodzaju; wszystkie powinny być procesami. Następnie traktujemy dostęp według nazwy jako surowiec do obliczeń ...

W 2003 roku Ken Kahn wspominał w wiadomości o rachunku Pi :

Rachunek Pi jest oparty na komunikacji synchronicznej (uzgadnianie). Jakieś 25 lat temu poszedłem na kolację z Carlem Hewittem i Robinem Milnerem (znanym z CCS i rachunku różniczkowego) i kłócili się o prymitywy komunikacji synchronicznej i asynchronicznej. Carl użył metafory na poczcie, podczas gdy Robin skorzystał z telefonu. Obaj szybko przyznali, że jedno można zaimplementować w drugim.

Hoare i in.

Tony Hoare , Stephen Brookes i AW Roscoe opracowali i udoskonalili teorię CSP do jej nowoczesnej postaci. Na podejście przyjęte przy opracowywaniu teoretycznej wersji CSP duży wpływ miały prace Robina Milnera nad rachunkiem systemów komunikacyjnych (CCS) i odwrotnie. Na przestrzeni lat doszło do wielu owocnych wymian pomysłów między naukowcami pracującymi zarówno nad CSP, jak i CCS.

Hewitt i in.

Will Clinger [1981] opracował pierwszy denotacyjny model aktora do obliczeń współbieżnych, który zawierał nieograniczony niedeterminizm . Bill Kornfeld i Carl Hewitt [1981] wykazali, że model aktora może obejmować współbieżność na dużą skalę. Agha opracowała aktorów jako podstawowy model obliczeń współbieżnych. Na jego pracę nad reprezentacją abstrakcji i kompozycji aktora oraz nad opracowaniem semantyki operacyjnej dla aktorów w oparciu o asynchroniczne drzewa komunikacyjne wyraźny wpływ wywarła praca Milnera nad rachunkiem systemów komunikacyjnych (CCS). a także praca Clingera.

Dalsza koewolucja

Rachunek π , częściowo zainspirowany modelem aktora opisanym powyżej przez Milnera, wprowadził dynamiczną topologię do rachunku procesów, umożliwiając dynamiczne tworzenie procesów i przekazywanie nazw między różnymi procesami. Jednak cel Milnera i Hoare'a, jakim było osiągnięcie rachunku algebraicznego, doprowadził do krytycznej rozbieżności z modelem aktora: komunikacja w rachunkach procesów nie jest bezpośrednia, jak w modelu aktora, ale raczej pośrednio przez kanały (patrz model aktora i rachunki procesów ) . Natomiast ostatnie prace nad modelem aktora [Hewitt 2006, 2007a] kładły nacisk na modele denotacyjne i twierdzenie o reprezentacji .

Niemniej jednak istnieje interesująca koewolucja między Modelem Aktora a Rachunkiem Procesu. Montanari i Talcott dyskutowali, czy model aktora i rachunek π są ze sobą kompatybilne. Sangiorgi i Walker ^{[ potrzebne źródło ]} pokazali, w jaki sposób Actor pracuje nad traktowaniem struktur kontrolnych jako wzorców przekazywanych komunikatów, które można modelować za pomocą rachunku π.

Chociaż prawa algebraiczne zostały opracowane dla modelu aktora, nie obejmują one kluczowej właściwości gwarantowanego dostarczania komunikatów wysyłanych do serializatorów. Zobacz na przykład:

Gaspariego i Zavattaro
Aga i Thati

Zobacz też

Dalsza lektura

Edsger Dijkstra. Dyscyplina programowania Prentice Hall . 1976.
Carla Hewitta i in. Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, styczeń 1974.
Carla Hewitta i in. Behavioural Semantics of Nonrecursive Control Structure Proceedings of Colloque sur la Programmation, kwiecień 1974.
Irene Greif i Carla Hewitta. Semantyka aktora PLANNER-73 Konferencja Zapis sympozjum ACM na temat zasad języków programowania. styczeń 1975.
Irena Greif. Semantyka komunikowania procesów równoległych Rozprawa doktorska MIT EECS. sierpień 1975.
Carl Hewitt i Henry Baker Aktorzy i ciągłe działania funkcjonalne konferencji roboczej IFIP na temat formalnego opisu koncepcji programowania. 1-5 sierpnia 1977.
Carl Hewitt i Henry Baker Prawa dotyczące komunikowania procesów równoległych IFIP-77, sierpień 1977.
Henry Baker i Carl Hewitt Przyrostowe zbieranie śmieci procesów Proceedings of the Symposium on Artificial Intelligence Programming Languages. Zawiadomienia SIGPLAN 12, sierpień 1977.
Aki Yonezawa Techniki specyfikacji i weryfikacji programów równoległych oparte na semantyce przekazywania wiadomości Rozprawa doktorska MIT EECS. grudzień 1977.
Henryk Baker . Systemy aktorów do obliczeń w czasie rzeczywistym Rozprawa doktorska MIT EECS. styczeń 1978.
George'a Milne'a i Robina Milnera . Procesy współbieżne i ich składnia JACM. kwiecień 1979.
Nissim Francez , CAR Hoare , Daniel Lehmann i Willem de Roever. Semantyka niedeterminizmu, współbieżności i komunikacji Journal of Computer and System Sciences . grudzień 1979.
Nancy Lynch i Michaela Fischera. O opisywaniu zachowania systemów rozproszonych w semantyce obliczeń współbieżnych. Springer-Verlag. 1979.
Willa Clingera. Podstawy semantyki aktora Rozprawa doktorska z matematyki MIT . czerwiec 1981.
JA Bergstra i JW Klop. Algebra procesów dla komunikacji synchronicznej Informacji i Sterowania. 1984.
Eike Best . Zachowanie współbieżne: sekwencje, procesy i aksjomaty Notatki z wykładów z informatyki, tom 197 1984.
Luca Cardelli. Model implementacji komunikacji rendezvous Seminarium na temat współbieżności. Notatki z wykładów z informatyki 197. Springer-Verlag. 1985
Robina Milnera, Joachima Parrowa i Davida Walkera. Rachunek procesów mobilnych Wydział Informatyki Edynburg. Raporty ECS-LFCS-89-85 i ECS-LFCS-89-86. Czerwiec 1989. Poprawione odpowiednio we wrześniu 1990 i październiku 1990.
Robina Milnera. The Polyadic pi-Calculus: A Tutorial Edinburgh University. Raport LFCS ECS-LFCS-91-180. 1991.
Kohei Honda i Mario Tokoro. Rachunek obiektowy dla komunikacji asynchronicznej ECOOP 91.
Benjamin Pierce, Didier Rémy i David Turner. Typowany język programowania wyższego rzędu oparty na warsztacie pi-calculus na temat teorii typów i jej zastosowania w systemach komputerowych. Uniwersytet w Kioto. lipiec 1993.
Cedrica Fourneta i Georgesa Gonthiera . Refleksyjna abstrakcyjna maszyna chemiczna i rachunek łączenia POPL 1996.
Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget i Didier Rémy. Rachunek agentów mobilnych CONCUR 1996.
Gerarda Boudola. Rachunek pi w stylu bezpośrednim POPL 1997
Tatsurou Sekiguchi i Akinori Yonezawa . Rachunek z mobilnością kodu FMOODS 1997.
Luca Cardelli i Andrew D. Gordon . Mobile Ambients Foundations of Software Science and Computational Structures, Maurice Nivat (red.), Notatki z wykładów z informatyki, tom. 1378, Springer, 1998.
Robina Milnera. Systemy komunikacyjne i mobilne: Pi-Calculus Cambridge University Press. 1999.
JCM Baeten. Krótka historia algebry procesów Informatyka teoretyczna . 2005. (link ważny od 2015_26_5_0004)
JCM Baeten, T. Basten i MA Reniers. Algebra procesów komunikacyjnych Cambridge University Press. 2005.
He Jifeng i CAR Hoare. Linking Theories of Concurrency Międzynarodowy Instytut Technologii Oprogramowania Uniwersytetu Narodów Zjednoczonych Raport UNU-IIST nr 328. Lipiec 2005 r.
Luca Aceto i Andrew D. Gordon (redaktorzy). Obliczenia procesów algebraicznych: pierwsze dwadzieścia pięć lat i więcej algebry procesów . Bertinoro, Forl`ı, Włochy, 1–5 sierpnia 2005.
Carla Hewitta. Co to jest zaangażowanie? Fizyczne, organizacyjne i społeczne COIN@AAMAS. 27 kwietnia 2006b.
Carl Hewitt (2007a) Czym jest zaangażowanie? Fizyczne, organizacyjne i społeczne (poprawione) Pablo Noriega .et al. redaktorzy. LNAI 4386. Springer-Verlag. 2007.
Carl Hewitt (2007b) Obliczenia organizacyjne na dużą skalę wymagają niestratyfikowanej parakonsystencji i refleksji COIN@AAMAS'07.