Abstraktní stroj -Abstract machine

Nezaměňujte s virtuálním strojem .

Abstraktní stroj je teoretický model počítačové vědy , který umožňuje podrobnou a přesnou analýzu fungování počítačového systému. Je analogická matematické funkci v tom, že přijímá vstupy a vytváří výstupy na základě předem definovaných pravidel. Abstraktní stroje se liší od doslovných strojů v tom, že se od nich očekává, že budou fungovat správně a nezávisle na hardwaru . Abstraktní stroje jsou „ stroje “, protože umožňují provádění programů krok za krokem ; jsou „ abstraktní “, protože ignorují mnoho aspektů skutečného ( hardwaru) stroje. Typický abstraktní stroj se skládá z definice z hlediska vstupu, výstupu a sady přípustných operací používaných k přeměně prvního na druhý. Mohou být použity z čistě teoretických důvodů i jako modely pro reálné počítačové systémy. V teorii počítání se abstraktní stroje často používají v myšlenkových experimentech ohledně vyčíslitelnosti nebo k analýze složitosti algoritmů . Toto použití abstraktních strojů je spojeno s polem teorie výpočetní složitosti , jako jsou konečné automaty , Mealyho stroje , zásobníkové automaty a Turingovy stroje .


Klasifikace

Abstraktní stroje jsou obecně klasifikovány do dvou typů v závislosti na počtu operací, které mohou v kterémkoli okamžiku provádět: deterministické abstraktní stroje a nedeterministické abstraktní stroje . Deterministický abstraktní stroj je systém , ve kterém konkrétní počáteční stav nebo podmínka vždy poskytuje stejné výstupy. Neexistuje žádná náhodnost nebo variace v tom, jak jsou vstupy transformovány na výstupy. Mezitím může nedeterministický abstraktní stroj poskytovat různé výstupy pro stejný vstup při různých provedeních. Na rozdíl od deterministického algoritmu, který dává stejný výsledek pro stejný vstup bez ohledu na počet iterací, nedeterministický algoritmus prochází různými cestami, aby dospěl k různým výstupům. Nedeterministické algoritmy jsou užitečné pro získání přibližných odpovědí, když je odvození přesného řešení pomocí deterministického přístupu obtížné nebo nákladné.

Běh Turingova stroje .

Turingův stroj je například jedním z nejzákladnějších abstraktních strojů v informatice. Toto je stroj, který může provádět operace na pásce (řetězec symbolů) libovolné délky. Zahrnuje instrukce jak pro úpravu symbolů, tak pro změnu symbolu, na kterém je založen. Jediný příkaz na základním Turingově počítači by byl „převést symbol na 1 a poté se pohnout doprava“ a tento stroj by produkoval pouze řetězec 1s. Tento základní Turingův stroj je deterministický, lze však sestavit i nedeterministické Turingovy stroje , které mohou provádět několik akcí při stejném vstupu.

Implementace abstraktního stroje

Jakákoli implementace abstraktního stroje v případě fyzické implementace (v hardwaru ) používá nějaký druh fyzického zařízení (mechanického, elektronického atd.) k provádění instrukcí programovacího jazyka . Abstraktní stroj však může být také implementován v softwaru nebo firmwaru na úrovních mezi abstraktním strojem a základním fyzickým zařízením.

  • Simulace pomocí softwaru : Implementace abstraktního stroje se softwarem vyžaduje psaní programů v jiném jazyce pro implementaci datových struktur a algoritmů , které abstraktní stroj potřebuje. To poskytuje největší flexibilitu, protože programy implementující abstraktní strojové konstrukce lze snadno změnit. Abstraktní stroj implementovaný jako softwarová simulace nebo pro který existuje interpret se nazývá virtuální stroj .

Implementace programovacího jazyka

Termín " stroj " se týká výpočetního stroje, což je fyzický stroj, který provádí algoritmy, které byly dostatečně formalizovány, aby je stroj "pochopil". Abstraktní stroj není intuitivně nic jiného než abstrakce myšlenky fyzického počítače. Pro skutečné provedení musí být algoritmy řádně formalizovány pomocí konstrukcí nabízených programovacím jazykem . To znamená, že algoritmy, které mají být provedeny, musí být vyjádřeny pomocí instrukcí programovacího jazyka. Syntaxe programovacího jazyka umožňuje konstrukci programů pomocí konečné množiny konstrukcí známých jako instrukce. Většina abstraktních strojů sdílí úložiště programů a stav , který často zahrnuje zásobník a registry. V digitálních počítačích je zásobník jednoduše paměťová jednotka s registrem adres, který může počítat pouze kladná celá čísla (po načtení počáteční hodnoty). Registr adres pro zásobník je známý jako ukazatel zásobníku, protože jeho hodnota vždy odkazuje na horní položku zásobníku. Program se skládá ze série instrukcí, přičemž ukazatel zásobníku označuje další instrukci, která má být provedena. Po dokončení instrukce se posune ukazatel zásobníku . Tento základní kontrolní mechanismus abstraktního stroje je také známý jako jeho prováděcí smyčka . Abstraktní stroj pro programovací jazyk je tedy jakýkoli soubor datových struktur a algoritmů schopných ukládat a spouštět programy napsané v programovacím jazyce. Překlenuje propast mezi vysokou úrovní programovacího jazyka a nízkou úrovní skutečného stroje tím, že poskytuje přechodný jazykový krok pro kompilaci . Instrukce abstraktního stroje jsou přizpůsobeny jedinečným operacím nezbytným k implementaci operací určitého zdrojového jazyka nebo sady zdrojových jazyků.

Imperativní programovací jazyky

Koncem 50. let Asociace pro výpočetní stroje (ACM) a další přidružené organizace vyvinuly mnoho návrhů na Universal Computer Oriented Language (UNCOL) , jako je Conwayův stroj . Koncept UNCOL je dobrý, ale nebyl široce používán kvůli špatnému výkonu generovaného kódu . V mnoha oblastech výpočetní techniky bude její výkon i nadále problémem navzdory vývoji Java Virtual Machine na konci 90. let. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977) a Forth (1970) jsou některé úspěšné abstraktní stroje tohoto druhu.

Objektově orientované programovací jazyky

Abstraktní stroje pro objektově orientované programovací jazyky jsou často založené na zásobníku a mají speciální přístupové instrukce pro objektová pole a metody . V těchto počítačích je správa paměti často implicitně prováděna pomocí garbage collectoru (funkce obnovy paměti zabudovaná do programovacích jazyků). Smalltalk-80 (1980), Self (1989) a Java (1994) jsou příklady této implementace.

Jazyky pro zpracování řetězců

Jazyk pro zpracování řetězců je počítačový jazyk, který se zaměřuje spíše na zpracování řetězců než čísel. Po desetiletí existují jazyky pro zpracování řetězců ve formě příkazových shellů , programovacích nástrojů , makroprocesorů a skriptovacích jazyků . Použití vhodného abstraktního stroje má dvě výhody: vyšší rychlost provádění a lepší přenositelnost. Snobol4 a ML/I jsou dva pozoruhodné příklady raných jazyků pro zpracování řetězců, které používají abstraktní stroj k získání nezávislosti na stroji.

Funkční programovací jazyky

Obrazové znázornění stroje Krivine .

Rané abstraktní stroje pro funkcionální jazyky , včetně stroje SECD (1964) a Cardelliho Functional Abstract Machine (1983), definovaly přísné vyhodnocování, známé také jako eager nebo call-by-value evaluation , ve kterém jsou argumenty funkcí vyhodnocovány před voláním. a to přesně jednou. V posledních letech se většina výzkumů zabývala líným (nebo call-by-need) hodnocením , jako je G-machine (1984), Krivine machine (1985) a Three Instruction Machine (1986), ve kterých argumenty fungují se vyhodnocují pouze v případě potřeby a nejvýše jednou. Jedním z důvodů je, že efektivní implementace přísného hodnocení je nyní dobře srozumitelná, a proto se zmenšila potřeba abstraktního stroje.

Logické programovací jazyky

Predikátový počet (logika prvního řádu) je základem logických programovacích jazyků . Nejznámějším logickým programovacím jazykem je Prolog . Pravidla v Prologu jsou napsána v jednotném formátu známém jako univerzálně kvantifikované „klauzule o rohu“, což znamená zahájit výpočet, který se pokouší objevit důkaz cíle. Většina studií byla zaměřena na Warren Abstract Machine WAM (1983), který se stal de facto standardem v kompilaci programu Prolog. Poskytuje speciální instrukce, jako jsou instrukce pro sjednocení dat a instrukce řídicího toku pro podporu zpětného sledování (algoritmus vyhledávání).

Struktura abstraktního stroje

Obecný abstraktní stroj se skládá z paměti a interpretu . Paměť se používá k ukládání dat a programů, zatímco interpret je komponenta, která provádí instrukce obsažené v programech.

Struktura abstraktního stroje

Tlumočník musí provádět operace, které jsou jedinečné pro jazyk , který tlumočí. Vzhledem k rozmanitosti jazyků je však možné identifikovat kategorie operací a „ mechanismus provádění “ sdílený všemi tlumočníky. Operace tlumočníka a doprovodné datové struktury jsou rozděleny do následujících kategorií:

  1. Operace pro zpracování primitivních dat :
  2. Operace a datové struktury pro řízení posloupnosti provádění operací ;
  3. Operace a datové struktury pro řízení datových přenosů ;
  4. Operace a datové struktury pro správu paměti .

Operace pro zpracování primitivních dat

I abstraktní stroj funguje na základě provádění algoritmů, proto musí obsahovat operace pro manipulaci s primitivními datovými typy , jako jsou řetězce a celá čísla. Například celá čísla (celé nebo reálné) jsou téměř všeobecně považovány za základní data jak pro fyzické abstraktní stroje, tak pro abstraktní stroje používané mnoha programovacími jazyky . Stroj okamžitě provede různé nezbytné aritmetické operace (sčítání, násobení atd.).

Operace a datové struktury pro řízení sekvencí

Operace a struktury pro "řízení sekvence" umožňují řídit tok provádění programových instrukcí. Když jsou splněny určité podmínky , je nutné změnit typické sekvenční provádění programu. Proto interpret využívá datové struktury (jako jsou ty, které se používají k uložení adresy další instrukce, která se má provést), které jsou modifikovány operacemi odlišnými od operací používaných pro manipulaci s daty (například operacemi pro aktualizaci adresy další instrukce, která se má provést). ).

Operace a datové struktury pro řízení datových přenosů

Operace přenosu dat se používají k řízení toho, jak jsou operandy a data přenášeny z paměti do interpretu a naopak. Tyto operace se zabývají úložištěm a pořadím načítání operandů z úložiště.

Operace a datové struktury pro správu paměti

Správa paměti se týká operací prováděných v paměti za účelem alokace dat a aplikací. V abstraktním stroji mohou být data a programy drženy neomezeně dlouho, nebo v případě programovacích jazyků může být paměť alokována nebo uvolněna pomocí složitějšího mechanismu.

Hierarchie abstraktních strojů

Hierarchie abstraktních strojů

Často se používají abstraktní hierarchie strojů, ve kterých každý stroj využívá funkcionalitu úrovně bezprostředně pod a přidává další vlastní funkce, aby splnil úroveň bezprostředně nad úrovní. Hardwarový počítač , konstruovaný s fyzickými elektronickými zařízeními, může být přidán na nejzákladnější úrovni. Nad touto úrovní může být zavedena úroveň abstraktního mikroprogramovaného stroje . Abstraktní stroj dodávaný operačním systémem , který je implementován programem napsaným ve strojovém jazyce , je umístěn bezprostředně nad hardwarem (nebo přímo nad hardwarem , pokud tam není úroveň firmwaru ). Na jedné straně operační systém rozšiřuje možnosti fyzického stroje tím, že poskytuje primitiva vyšší úrovně, která nejsou na fyzickém stroji dostupná (například primitiva, která působí na soubory). Hostitelský stroj je tvořen abstraktním strojem daným operačním systémem, na kterém je implementován vysokoúrovňový programovací jazyk pomocí zprostředkujícího stroje , jako je Java Virtual machine a jeho bytecode jazyk. Úroveň daná abstraktním strojem pro jazyk vysoké úrovně (například Java) není obvykle konečnou úrovní hierarchie. V tomto okamžiku může být představena jedna nebo více aplikací, které společně poskytují další služby. K implementaci funkcí nezbytných pro zpracování webové komunikace ( komunikační protokoly nebo prezentace HTML kódu ) lze například přidat úroveň „webového stroje“ . Úroveň „ Web Service “ se nachází nad touto úrovní a poskytuje funkce nezbytné k tomu, aby webové služby komunikovaly, a to jak z hlediska interakčních protokolů, tak z hlediska chování příslušných procesů. Na této úrovni mohou být vyvinuty zcela nové jazyky, které specifikují chování takzvaných "obchodních procesů" založených na webových službách (příkladem je Business Process Execution Language ). Konečně lze nalézt specializovanou aplikaci na nejvyšší úrovni (například E-commerce ), která má velmi specifické a omezené funkce.

Viz také

Reference

  1. ^ Weisstein, Eric W. "Abstraktní stroj" . mathworld.wolfram.com . Získáno 2022-05-16 .
  2. ^ a b c d e f "Co je to abstraktní stroj?" . EasyTechJunkie . Získáno 2022-05-16 .
  3. ^ a b c d e f g h i j Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (květen 2000). "Abstraktní stroje pro implementaci programovacího jazyka" . Počítačové systémy budoucí generace . 16 (7): 739–751. doi : 10.1016/S0167-739X(99)00088-6 .
  4. ^ "9.1.1: Přehled stroje konečného stavu" . Engineering LibreTexts . 2021-04-29 . Získáno 2022-05-31 .
  5. ^ „Co je deterministický systém? - Definice z Techopedia“ . Techopedia.com . Staženo 2022-05-30 .
  6. ^ Stearns, Richard E. (leden 2003). „Deterministický versus nedeterministický čas a problémy s dolní hranicí“ . Věstník ACM . 50 (1): 91–95. doi : 10.1145/602382.602409 . ISSN  0004-5411 . S2CID  2194820 .
  7. ^ Armoni, Michal; Gal-Ezer, Judith (prosinec 2007). „Nedeterminismus: abstraktní pojem ve studiích informatiky“ . Výuka informatiky . 17 (4): 243–262. Bibcode : 2007CSEd...17..243A . doi : 10.1080/08993400701442885 . ISSN  0899-3408 . S2CID  41928460 .
  8. ^ Gill, John (prosinec 1977). „Výpočetní složitost pravděpodobnostních Turingových strojů“ . SIAM Journal on Computing . 6 (4): 675–695. doi : 10.1137/0206049 . ISSN  0097-5397 .
  9. ^ a b c d e f g h i j k l m n o Gabbrielli, Maurizio; Martini, Simone (2010), "Abstract Machines" , Programming Languages: Principles and Paradigms , London: Springer London, s. 1–25, doi : 10.1007/978-1-84882-914-5_1 , ISBN 978-1-84882-913-8, staženo 2022-05-16
  10. ^ Bair, Ray; Chien, Andrew; Kuchařka, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, John; Vetter, Jeff (2018-02-01). "Hardwarové hodnocení: Abstraktní modely strojů a proxy architektury pro Exascale Computing" . doi : 10.2172/1733300 . OSTI 1733300  . {{cite journal}}:Citovat deník vyžaduje |journal=( nápovědu )
  11. ^ "Abstraktní stroj z FOLDOC" . Foldoc.org . Staženo 2021-08-07 .
  12. ^ Gee, J.; Melvin, SW; Patt, YN (1986). "Implementace Prologu prostřednictvím mikrokódu VAX 8600" . Sborník příspěvků z 19. výročního workshopu o mikroprogramování - MICRO 19 . New York, New York, USA: ACM Press: 68–74. doi : 10.1145/19551.19538 . ISBN 081860736X. S2CID  3846072 .
  13. ^ "abstraktní stroj" . Oxford Reference . Získáno 2022-05-16 .
  14. ^ García-Martín, Julio Manuel; Sutil-Martin, Miguel (15. 8. 1999). "Vzor pro navrhování abstraktních strojů" . doi : 10.13140/RG.2.1.3680.5203 . {{cite journal}}:Citovat deník vyžaduje |journal=( nápovědu )
  15. ^ upscfever.com (2017-01-25). "Organizace a architektura počítače (organizace zásobníku) - HOŘEČKA UPSC" . upscfever.com . Získáno 2022-05-31 .
  16. ^ ab Tyson , Matthew (2020-01-17). "Co je JVM? Představujeme virtuální stroj Java" . InfoWorld . Získáno 2022-05-31 .
  17. ^ "Co je objektově orientované programování (OOP)?" . SearchAppArchitecture . Získáno 2022-05-31 .
  18. ^ "Konstrukční aspekty jazyků pro zpracování řetězců" , Studie o jazycích pro zpracování řetězců , Poznámky k přednáškám z informatiky, Berlín, Heidelberg: Springer Berlin Heidelberg, sv. 205, s. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN 978-3-540-16041-0, staženo 2022-05-31
  19. ^ Hackett, Jennifer; Hutton, Graham (26. 7. 2019). "Call-by-need je jasnozřivý call-by-value" . Sborník ACM o programovacích jazycích . 3 (ICFP): 1–23. doi : 10.1145/3341718 . ISSN  2475-1421 . S2CID  195782686 .
  20. ^ "Prolog | Úvod" . GeeksforGeeks . 2018-05-26 . Získáno 2022-05-31 .
  21. ^ Accattoli, Beniaamino; Barenbaum, Pablo; Mazza, Damiano (2014-11-26). "Destilace abstraktních strojů" . Upozornění ACM SIGPLAN . 49 (9): 363–376. doi : 10.1145/2692915.2628154 . ISSN  0362-1340 . S2CID  234775413 .
  22. ^ baeldung (2018-01-11). "Úvod do Java Primitives | Baeldung" . www.baeldung.com . Získáno 2022-05-31 .
  23. ^ "Interpreter" , Software Architecture Design Patterns in Java , Auerbach Publications, 2004-04-27, doi : 10.1201/9780203496213.ch34 , ISBN 978-0-8493-2142-9, staženo 2022-05-31
  24. ^ "Hardware vs software vs Firmware: Jaký je rozdíl?" . Lifewire . Získáno 2022-05-31 .
  25. ^ Accattoli, Beniaamino; Barras, Bruno (2017-10-09). „Prostředí a složitost abstraktních strojů“ . Sborník příspěvků z 19. mezinárodního sympozia o principech a praxi deklarativního programování . Namur Belgie: ACM: 4–16. doi : 10.1145/3131851.3131855 . ISBN 978-1-4503-5291-8. S2CID  11953081 .
  26. ^ "Webové služby" . reference.wolfram.com . Získáno 2022-05-31 .
  27. ^ DB Skillicorn (2005). Základy paralelního programování . Cambridge University Press. p. 18. ISBN 978-0-521-01856-2.

Další čtení

  • Peter van Emde Boas, Machine Models and Simulations , str. 3–66, vycházející v:
Jan van Leeuwen , ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (svazek A). QA 76.H279 1990