Historie modelu herce - History of the Actor model - Wikipedia

v počítačová věda, Herecký model, který byl poprvé publikován v roce 1973, je matematickým modelem souběžný výpočet.

Pořadí událostí versus globální stav

Zásadní výzvou při definování aktorského modelu je to, že neposkytoval globální stavy, takže výpočetní krok nemohl být definován jako přechod z jednoho globálního stavu do dalšího globálního stavu, jak tomu bylo ve všech předchozích modelech výpočtu.

V roce 1963 v oboru Umělá inteligence, John McCarthy představil situační proměnné v logice v Situačním počtu. V McCarthy a Hayes 1969 je situace definována jako „úplný stav vesmíru v okamžiku“. V tomto ohledu nejsou situace McCarthyho vhodné pro použití v hereckém modelu, protože nemá žádné globální státy.

Z definice herce je vidět, že dochází k mnoha událostem: místní rozhodnutí, vytváření aktérů, odesílání zpráv, přijímání zpráv a určování, jak reagovat na další přijatou zprávu. Částečné uspořádání takových událostí bylo axiomatizováno v modelu herce a byl prozkoumán jejich vztah k fyzice (viz Teorie modelu herce ).

Vztah k fyzice

Podle Hewitta (2006) je herecký model založen na fyzice na rozdíl od jiných modelů výpočtu, které byly založeny na matematické logice, teorii množin, algebře, atd. Fyzika ovlivnila herecký model mnoha způsoby, zejména kvantová fyzika a relativistická fyzika. Jedním z problémů je to, co lze pozorovat u hereckých systémů. Tato otázka nemá zjevnou odpověď, protože představuje teoretické i pozorovací výzvy podobné těm, které vyvstaly při konstrukci základů kvantové fyziky. Konkrétně pro hercovy systémy obvykle nemůžeme sledovat podrobnosti, podle kterých je určeno pořadí příchodu zpráv pro herce (viz Neurčitost při souběžném výpočtu ). Pokus o to má vliv na výsledky a může dokonce posunout neurčitost jinam. např.viz metastabilita v elektronice. Místo pozorování vnitřních částí rozhodčích procesů výpočtů Actor, čekáme na výsledky.

Modely před hercovým modelem

Herecký model navazuje na předchozí modely výpočtu.

Lambda kalkul

The lambda kalkul z Alonzo Church lze zobrazit jako nejdříve předávání zpráv programovací jazyk (viz Hewitt, Bishop a Steiger 1973; Abelson a Sussman 1985 ). Například výraz lambda níže implementuje stromovou datovou strukturu, když je dodáván s parametry pro a leftSubTree a rightSubTree. Když je takovému stromu dána zpráva s parametrem "getLeft", vrátí se leftSubTree a podobně, když dostal zprávu "getRight" vrací se rightSubTree.

 λ (leftSubTree, rightSubTree) λ (zpráva) -li (zpráva == "getLeft") pak leftSubTree jinak pokud (zpráva == "getRight") pak rightSubTree

Sémantika lambda kalkulu však byla vyjádřena pomocí variabilní substituce ve kterém byly hodnoty parametrů nahrazeny do těla vyvolaného výrazu lambda. Substituční model není vhodný pro souběžnost, protože neumožňuje funkci sdílení změny zdrojů. Inspirován lambda kalkulem, tlumočník pro programovací jazyk Lisp využil datovou strukturu zvanou prostředí, takže hodnoty parametrů nemusel být nahrazen do těla vyvolaného výrazu lambda. To umožnilo sdílení účinky aktualizace sdílených datových struktur, ale neposkytoval souběžnost.

Simula

Simula 67 propagován pomocí předávání zpráv pro výpočet, motivován aplikacemi pro diskrétní simulaci událostí. Tyto aplikace se v předchozích simulačních jazycích staly velkými a nemodulárními. V každém časovém kroku by musel velký centrální program projít a aktualizovat stav každého simulačního objektu, který se změnil v závislosti na stavu libovolných simulačních objektů, se kterými v daném kroku interagoval. Kristen Nygaard a Ole-Johan Dahl vyvinuli myšlenku (poprvé popsanou na workshopu IFIP v roce 1967) mít metody na každém objekt který by aktualizoval svůj vlastní místní stav na základě zpráv z jiných objektů. Kromě toho zavedli a struktura třídy pro objekty s dědictví. Jejich inovace výrazně zlepšily modularitu programů.

Simula však použila korutin kontrolní struktura místo skutečné souběžnosti.

Pokec

Alan Kay bylo ovlivněno předáváním zpráv při vzoru směrovaného vyvolání Plánovač ve vývoji Pokec -71. Hewitta zaujal Smalltalk-71, ale odradila ho složitost komunikace, která zahrnovala vyvolání s mnoha poli, včetně globální, odesílatel, přijímač, styl odpovědi, postavení, odpověď, volič operátorů, atd.

V roce 1972 navštívil Kay MIT a projednal některé ze svých nápadů pro budovu Smalltalk-72 na dálnici Logo práce Seymour Papert a „malý člověk“ model výpočtu používaný k výuce programování dětí. Předávání zpráv Smalltalk-72 však bylo docela složité. Kód v jazyce tlumočník považoval pouze za tok tokenů. Tak jako Dan Ingalls později to popsal:

První (token), se kterým se setkal (v programu), byl vyhledán v dynamickém kontextu, aby se určil příjemce následující zprávy. Hledání názvu začalo slovníkem tříd aktuální aktivace. Pokud tam nedojde, přesunulo se to k odesílateli této aktivace atd. Nahoru do řetězce odesílatele. Když byla pro token konečně nalezena vazba, její hodnota se stala přijímačem nové zprávy a tlumočník aktivoval kód pro třídu daného objektu.

Model předávání zpráv v Smalltalk-72 byl tedy úzce svázán s konkrétním modelem stroje a syntaxí programovacího jazyka, která se nehodila pro souběžnost. I když byl systém bootstrapován sám na sebe, jazykové konstrukce nebyly formálně definovány jako objekty, na které reagují Eval zprávy (viz diskuse níže). To vedlo některé k přesvědčení, že nový matematický model souběžného výpočtu založený na předávání zpráv by měl být jednodušší než Smalltalk-72.

Následné verze jazyka Smalltalk do značné míry sledovaly cestu používání virtuálního metody Simula ve struktuře programů předávajících zprávy. Smalltalk-72 však vytvořil primitiva, jako jsou celá čísla, čísla s plovoucí desetinnou čárkou, atd. do předměty. Autoři Simuly uvažovali o tom, že se z takových primitiv stanou objekty, ale zdrželi se převážně z důvodů efektivity. Jáva zpočátku používal účel mít primitivní i objektovou verzi celých čísel, čísla s plovoucí desetinnou čárkou, atd. The C# programovací jazyk (a novější verze Javy, počínaje Javou 1.5) přijal méně elegantní řešení používání box a rozbalení, jehož varianta byla u některých použita dříve Lisp implementace.

Systém Smalltalk se stal velmi vlivným a inovoval v bitmapových displejích, osobních počítačích, rozhraní prohlížeče tříd a mnoha dalších způsobech. Podrobnosti viz Kay's Raná historie Smalltalk.[1] Mezitím úsilí herců na MIT zůstalo zaměřeno na rozvoj vědy a techniky vyšší úrovně souběžnosti. (V příspěvku od Jean-Pierra Briota najdete nápady, které byly vyvinuty později, jak začlenit některé druhy herců do jiných verzí Smalltalku.)

Petriho sítě

Před vývojem modelu herce Petriho sítě byly široce používány k modelování nedeterministických výpočtů. Všeobecně se však uznávalo, že mají důležité omezení: modelovali tok řízení, ale nikoli tok dat. V důsledku toho nebyly snadno skladatelné, což omezovalo jejich modularitu. Hewitt poukázal na další problém s Petriho sítěmi: současná akce. Tj., atomový krok výpočtu v Petriho sítích je přechod, ve kterém tokeny zároveň zmizí ze vstupních míst přechodu a objeví se na výstupních místech. Fyzický základ použití primitiva s tímto druhem simultánnosti mu připadal pochybný. Navzdory těmto zjevným obtížím jsou Petriho sítě i nadále oblíbeným přístupem k modelování souběžnosti a jsou stále předmětem aktivního výzkumu.

Vlákna, zámky a vyrovnávací paměti (kanály)

Před modelem herce byla souběžnost definována z hlediska nízkoúrovňového stroje vlákna, zámky a Nárazníky (kanály ). Určitě je tomu tak, že implementace modelu Actor obvykle tyto hardwarové funkce využívají. Neexistuje však žádný důvod, proč by model nemohl být implementován přímo v hardwaru bez odhalení jakýchkoli hardwarových vláken a zámků. Neexistuje také žádný nezbytný vztah mezi počtem aktérů, vláken a zámků, které by mohly být součástí výpočtu. Implementace modelu Actor mohou využívat vlákna a zámky jakýmkoli způsobem, který je kompatibilní s právními předpisy pro herce.

Odstraňování detailů implementace

Důležitou výzvou při definování modelu Actor bylo odebrat podrobnosti implementace.

Zvažte například následující otázku: „Má každý herec a fronta ve kterém jsou uloženy jeho komunikace, dokud nejsou přijaty hercem ke zpracování? “ Carl Hewitt namítal proti zařazení takových front jako nedílné součásti modelu herce. Jedním z úvah bylo, že takové fronty by mohly být samy modelovány jako Herci, kteří přijímali zprávy zařadit do fronty a dequeue komunikace. Další úvaha spočívala v tom, že někteří herci takové fronty při skutečné implementaci nepoužijí. Např., herec může mít síť arbitři namísto. Samozřejmě existuje matematická abstrakce, kterou je sekvence komunikace, které přijal herec. Ale tato sekvence se objevila, až když operoval herec. Ve skutečnosti může být pořadí této sekvence neurčité (viz Neurčitost při souběžném výpočtu ).

Dalším příkladem abstrahování od detailů implementace byla otázka výklad: „Měla by být interpretace nedílnou součástí hereckého modelu?“ Myšlenka interpretace spočívá v tom, že herec by byl definován způsobem zpracování jeho programového skriptu eval zprávy. (Tímto způsobem by byli herci definováni analogickým způsobem jako Lisp který byl „definován“ metakruhovou interpretací s názvem eval napsáno v Lisp.) Hewitt argumentoval proti tomu, aby interpretace byla integrální s hereckým modelem. Jedním z úvah bylo, že zpracování eval zprávy, programový skript herce by sám měl programový skript (který by zase měl ...)! Další úvaha spočívala v tom, že někteří herci nepoužijí tlumočení ve své skutečné interpretaci. Např., herec může být místo toho implementován do hardwaru. S výkladem samozřejmě není nic špatného per se. Také implementace tlumočníků pomocí eval zprávy je modulárnější a rozšiřitelnější než přístup Lispa k monolitickému tlumočníkovi.

Provozní model

Pokrok ve vývoji modelu byl nicméně stabilní. V roce 1975 vydala Irene Greif první provozní model ve své disertační práci.

Systém

Gerald Sussman a Guy Steele poté se zajímali o Herce a publikovali dokument o jejich Systém tlumočník, ve kterém dospěli k závěru, „zjistili jsme, že„ herci “a výrazy lambda byly identické v implementaci. “Podle Hewitta je lambda kalkul schopen vyjádřit určité druhy paralelismu, ale obecně ne souběžnost vyjádřená v modelu herce. Na druhé straně je model Actor schopen vyjádřit veškerý paralelismus v lambda kalkulu.

Zákony pro herce

Dva roky poté, co Greif zveřejnila svůj operační model, Carl Hewitt a Henry Baker zveřejnil zákony pro herce.

Důkaz kontinuity vypočítatelných funkcí

Pomocí zákonů modelu herce Hewitt a Baker dokázali, že každý herec, který se chová jako funkce, je kontinuální ve smyslu definovaném Dana Scott (vidět denotační sémantika ).

Specifikace a důkazy

Aki Yonezawa zveřejnil své specifikace a techniky ověřování pro herce. Russ Atkinson a Carl Hewitt zveřejnil dokument o specifikacích a důkazních technikách pro serializátory poskytující efektivní řešení pro zapouzdření sdílené zdroje pro řízení souběžnosti.

Matematická charakterizace pomocí teorie domén

A konečně osm let po první herecké publikaci Will Clinger (navazující na dílo Irene Greif 1975, Gordon Plotkin 1976, Michael Smyth 1978, Henry Baker 1978, Francez, Hoare Lehmann a de Roever 1979 a Milne a Milnor 1979) publikoval první uspokojivou matematiku denotační začlenění modelu neomezený nedeterminismus použitím teorie domény ve své disertační práci v roce 1981 (viz Clingerův model ). Hewitt [2006] následně rozšířil diagramy o časy příjezdu, aby vytvořil a technicky jednodušší denotační model to je snazší pochopit. Vidět Historie denotační sémantiky.

Viz také

Reference

  1. ^ Kay, Alan (Březen 1993). "Raná historie Smalltalk" (PDF). Oznámení ACM SIGPLAN. 28 (3): 69–75. doi:10.1145/155360.155364. Archivovány od originál (PDF) dne 2012-02-05.
  • Carl Hewitt; Peter Bishop; Richard Steiger (1973). „Formalismus univerzálního modulárního herce pro umělou inteligenci“. IJCAI: 235–245. Citovat deník vyžaduje | deník = (Pomoc)
  • McCarthy, John (1963). „Situace, jednání a kauzální zákony“. Zpráva o technické zprávě. Laboratoř umělé inteligence na Stanfordské univerzitě (2).
  • McCarthy, John; Hayes, Patrick (1969). „Některé filozofické problémy z hlediska umělé inteligence“. Inteligence strojů. Edunburgh University Press (4): 463–502. CiteSeerX  10.1.1.85.5082.
  • Heisenberg, Werner (1971). Fyzika a další: Setkání a konverzace. Přeložil A. J. Pomerans. New York: Harper & Row. str. 63–64. ISBN  978-0061316227.
  • Hewitt, Carl; Bishop, Peter; Greif, Irene; Smith, Brian; Matson, Todd; Steiger, Richard (leden 1974). "Indukce herce a meta-hodnocení". Záznam konference ze sympozia ACM o zásadách programovacích jazyků: 153–168. CiteSeerX  10.1.1.104.295. doi:10.1145/512927.512942.
  • Hewitt, Carl (duben 1974). "Behaviorální sémantika nerekurzivní struktury řízení". Proceedings of Colloque Sur la Programmation: 385–407. ISBN  9783540068594.
  • Greif, Irene; Hewitt, Carl (leden 1975). "Herecká sémantika PLANNERU-73". Záznam konference ze sympozia ACM o zásadách programovacích jazyků: 67–77. doi:10.1145/512976.512984.
  • Hewitt, Carl (září 1975). "Jak používat to, co víte". Sborník ze 4. mezinárodní společné konference o umělé inteligenci. 1: 189–198.
  • Greif, Irene (1975). Sémantika komunikace paralelních profesí (Ph.D.). MIT EECS.
  • Baker, Henry; Hewitt, Carl (srpen 1977). „Postupné sbírání procesů“. Sborník ze sympozia o programovacích jazycích umělé inteligence.[trvalý mrtvý odkaz ]
  • Hewitt, Carl; Baker, Henry (srpen 1977). "Zákony pro komunikaci paralelních procesů". Mezinárodní federace pro zpracování informací. hdl:1721.1/41962.
  • Yonezawa, Aki (1977). Specifikace a ověřovací techniky pro paralelní programy založené na sémantice předávání zpráv (Ph.D.). MIT EECS.
  • Bishop, Peter (1977). Modulárně rozšiřitelné počítačové systémy s velmi velkým adresním prostorem (Ph.D.). MIT EECS.
  • Hewitt, Carl (červen 1977). "Prohlížení řídicích struktur jako vzorů předávání zpráv". Journal of Artificial Intelligence. hdl:1721.1/6272.
  • Baker, Henry (1978). Herecké systémy pro výpočet v reálném čase (Ph.D.). MIT EECS.
  • Hewitt, Carl; Atkinson, Russ (leden 1979). "Specifikace a zkušební techniky pro serializátory". IEEE Journal on Software Engineering: 10–23. doi:10.1109 / TSE.1979.234149. hdl:1721.1/5756.
  • Kahn, Ken (1979). Výpočetní teorie animace (Ph.D.). MIT EECS.
  • Hewitt, Carl; Attardi, Beppe; Lieberman, Henry (říjen 1979). Msgstr "Delegování při předávání zpráv". Sborník z první mezinárodní konference o distribuovaných systémech. Huntsville, AL.
  • Atkinson, Russ (1980). Automatické ověřování serializátorů (Ph.D.). MIT.
  • Kornfeld, Bill; Hewitt, Carl (leden 1981). „Metafora vědecké komunity“ (PDF). Transakce IEEE na systémech, člověku a kybernetice. 11: 24–33. doi:10.1109 / TSMC.1981.4308575. hdl:1721.1/5693.
  • Lieberman, Henry (květen 1981). „Přemýšlíte o spoustě věcí najednou, aniž byste se nechali zmást: Rovnoběžnost v 1. dějství“. Memo AI MIT (626). hdl:1721.1/6351.
  • Lieberman, Henry (červen 1981). "Náhled zákona 1". Memo AI MIT (625). hdl:1721.1/6350.
  • Barber, Gerry (1981). Důvod ke změně ve znalostních kancelářských systémech (Ph.D.). MIT EECS.
  • Kornfeld, Bill (1981). Rovnoběžnost při řešení problémů (Ph.D.). MIT EECS.
  • Clinger, Will (1981). Základy herecké sémantiky (Ph.D.). MIT Matematika.
  • Theriault, Daniel (duben 1982). „Základní jazyk pro jazyk Act-1“. Memo AI MIT (672). hdl:1721.1/5675.
  • Lieberman, Henry; Hewitt, Carl (červen 1983). "Sběratel odpadků v reálném čase na základě životnosti objektů". Komunikace ACM. 26 (6): 419. CiteSeerX  10.1.1.123.5055. doi:10.1145/358141.358147.
  • Theriault, Daniel (červen 1983). „Problémy při navrhování a provádění zákona 2“. Technická zpráva MIT AI (728). hdl:1721.1/6940.
  • Lieberman, Henry (srpen 1983). „Objektově orientovaný simulátor pro včelín“ (PDF). Konference Americké asociace pro umělou inteligenci. Washington DC.
  • Hewitt, Carl; de Jong, Peter (srpen 1983). "Analýza rolí popisů a akcí v otevřených systémech". Sborník z Národní konference o umělé inteligenci. hdl:1721.1/5649.
  • Jammer, M. (1985). „Problém EPR v historickém vývoji“. P. Lahti, P. Mittelstaedt (ed.). Sympózium o základech moderní fyziky: 50 let experimentu Einstein-Podolsky-Rosen Gedanken. Singapur: World Scientific. str. 129–149.
  • Fine, A. (1986). Nejistá hra: Einsteinův realismus a kvantová teorie. Chicago: University of Chicago Press. ISBN  978-0226249476.
  • Hewitt, Carl; Lieberman, Henry (listopad 1983). "Problémy s designem v paralelní architektuře pro umělou inteligenci". Memo AI MIT (750). hdl:1721.1/5653.
  • Fuchs, Christopher (2002). "Kvantová mechanika jako kvantová informace (a jen o něco více)". V A. Khrenikov (ed.). Kvantová teorie: Rekonstrukce základů. Växjo: Växjo University Press.
  • Hewitt, Carl (27. dubna 2006). „Co je to závazek? Fyzický, organizační a sociální“ (PDF). COIN @ AAMAS.