Abstrakt maskin

Ej att förväxla med virtuell maskin .

Inom datavetenskap är en abstrakt maskin en teoretisk modell som möjliggör en detaljerad och exakt analys av hur ett datorsystem fungerar. Den liknar en matematisk funktion genom att den tar emot indata och producerar utdata baserat på fördefinierade regler. Abstrakta maskiner skiljer sig från bokstavliga maskiner genom att de förväntas fungera korrekt och oberoende av hårdvara . Abstrakta maskiner är " maskiner " eftersom de tillåter steg-för-steg exekvering av program ; de är " abstrakta " eftersom de ignorerar många aspekter av faktiska ( hårdvaru )maskiner. En typisk abstrakt maskin består av en definition i termer av input, output och uppsättningen tillåtna operationer som används för att förvandla den förra till den senare. De kan användas av rent teoretiska skäl såväl som modeller för verkliga datorsystem. I beräkningsteorin används abstrakta maskiner ofta i tankeexperiment angående beräkningsbarhet eller för att analysera komplexiteten i algoritmer . Denna användning av abstrakta maskiner är grundläggande för området beräkningskomplexitetsteori , såsom finita tillståndsmaskiner , Mealy-maskiner , push-down-automater och Turing-maskiner .


Klassificering

Abstrakta maskiner klassificeras generellt i två typer beroende på antalet operationer som de får utföra vid ett tillfälle: deterministiska abstrakta maskiner och icke-deterministiska abstrakta maskiner . En deterministisk abstrakt maskin är ett system där ett visst starttillstånd eller tillstånd alltid ger samma utdata. Det finns ingen slumpmässighet eller variation i hur input omvandlas till output. Däremot kan en icke-deterministisk abstrakt maskin tillhandahålla olika utdata för samma indata på olika exekveringar. Till skillnad från en deterministisk algoritm, som ger samma resultat för samma ingång oavsett antalet iterationer, tar en icke-deterministisk algoritm olika vägar för att komma till olika utgångar. Icke-deterministiska algoritmer är användbara för att få ungefärliga svar när det är svårt eller kostsamt att härleda en exakt lösning med hjälp av en deterministisk metod.

En körning av en Turing-maskin .

Turingmaskiner , till exempel, är några av de mest grundläggande abstrakta maskinerna inom datavetenskap. Dessa maskiner utför operationer på ett band (en sträng av symboler) av valfri längd. Deras instruktioner innehåller både ändring av symbolerna och ändring av symbolen som maskinens pekare befinner sig på. Till exempel kan en rudimentär Turing-maskin ha ett enda kommando, "konvertera symbol till 1 och flytta sedan åt höger", och den här maskinen skulle bara producera en sträng med 1:or. Denna grundläggande Turing-maskin är deterministisk; men icke-deterministiska Turing-maskiner som kan utföra flera åtgärder med samma input kan också byggas.

Genomförande

Varje implementering av en abstrakt maskin i fallet med fysisk implementering (i hårdvara ) använder någon form av fysisk enhet (mekanisk eller elektronisk) för att utföra instruktionerna för ett programmeringsspråk . Abstrakt maskin kan dock också implementeras i programvara eller firmware på nivåer mellan den abstrakta maskinen och den underliggande fysiska enheten.

  • Simulering med programvara : Implementering av en abstrakt maskin med programvara innebär att man skriver program på ett annat språk för att implementera de datastrukturer och algoritmer som behövs av den abstrakta maskinen. Detta ger den största flexibiliteten eftersom program som implementerar abstrakta maskinkonstruktioner lätt kan ändras. En abstrakt maskin implementerad som en mjukvarusimulering, eller för vilken det finns en tolk , kallas en virtuell maskin .

Implementering av programmeringsspråk

En abstrakt maskin är, intuitivt, bara en abstraktion av idén om en fysisk dator. För faktisk exekvering måste algoritmer formaliseras korrekt med hjälp av de konstruktioner som erbjuds av ett programmeringsspråk . Detta innebär att algoritmerna som ska exekveras måste uttryckas med hjälp av programmeringsspråksinstruktioner. Syntaxen för ett programmeringsspråk möjliggör konstruktion av program med hjälp av en ändlig uppsättning konstruktioner som kallas instruktioner. De flesta abstrakta maskiner delar en programbutik och en stat , som ofta inkluderar en stack och register. I digitala datorer är stacken helt enkelt en minnesenhet med ett adressregister som endast kan räkna positiva heltal (efter att ett initialt värde har laddats in i det). Adressregistret för stacken är känt som en stackpekare eftersom dess värde alltid refererar till det översta objektet i stacken. Programmet består av en serie instruktioner, med en stackpekare som indikerar nästa instruktion som ska utföras. När instruktionen är klar flyttas en stackpekare fram. Denna grundläggande kontrollmekanism för en abstrakt maskin är också känd som dess exekveringsloop . Således är en abstrakt maskin för programmeringsspråk vilken samling av datastrukturer och algoritmer som helst som kan lagra och köra program skrivna på programmeringsspråket. Den överbryggar gapet mellan den höga nivån på ett programmeringsspråk och den låga nivån på en verklig maskin genom att tillhandahålla ett mellanspråksteg för kompilering . En abstrakt maskins instruktioner är anpassade till de unika operationer som är nödvändiga för att implementera operationer för ett visst källspråk eller uppsättning källspråk.

Imperativa språk

I slutet av 1950-talet utvecklade Association for Computing Machinery (ACM) och andra allierade organisationer många förslag för Universal Computer Oriented Language (UNCOL), som Conways maskin . UNCOL-konceptet är bra, men det har inte använts i stor utsträckning på grund av den dåliga prestandan för den genererade koden . Inom många områden av datorer kommer dess prestanda att fortsätta att vara ett problem trots utvecklingen av Java Virtual Machine i slutet av 1990-talet. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977) och Forth (1970) är några framgångsrika abstrakta maskiner av detta slag.

Objektorienterade språk

Abstrakta maskiner för objektorienterade programmeringsspråk är ofta stackbaserade och har speciella åtkomstinstruktioner för objektfält och metoder . I dessa maskiner minneshantering ofta implicit av en sophämtare (minnesåterställningsfunktion inbyggd i programmeringsspråk). Smalltalk-80 (1980), Self (1989) och Java (1994) är exempel på denna implementering.

Strängbearbetningsspråk

Ett strängbearbetningsspråk är ett datorspråk som fokuserar på bearbetning av strängar snarare än siffror. Det har funnits strängbearbetningsspråk i form av kommandoskal , programmeringsverktyg , makroprocessorer och skriptspråk i decennier. Att använda en lämplig abstrakt maskin har två fördelar: ökad körhastighet och förbättrad portabilitet. Snobol4 och ML/I är två anmärkningsvärda instanser av tidiga strängbehandlingsspråk som använder en abstrakt maskin för att få maskinoberoende.

Funktionella programmeringsspråk

Bildrepresentation av en Krivine-maskin .

De tidiga abstrakta maskinerna för funktionella språk , inklusive SECD-maskinen (1964) och Cardelli's Functional Abstract Machine (1983), definierade strikt utvärdering, även känd som eager eller call-by-value evaluation , där funktionsargument utvärderas före anropet och exakt en gång. Under de senaste åren har majoriteten av forskningen handlat om lat (eller kalla efter behov) utvärdering , såsom G-maskinen (1984), Krivine-maskinen (1985) och Three Instruction Machine (1986), i vilka funktionsargument utvärderas endast vid behov och högst en gång. En anledning är att effektiv implementering av strikt utvärdering nu är välkänd, därför har behovet av en abstrakt maskin minskat.

Logiska språk

Predikatkalkyl (första ordningens logik) är grunden för logiska programmeringsspråk . Det mest kända logiska programmeringsspråket är Prolog . Reglerna i Prolog är skrivna i ett enhetligt format som kallas universellt kvantifierade 'hornsatser', vilket betyder att påbörja beräkningen som försöker hitta ett bevis på målet. Warren Abstract Machine WAM (1983), som har blivit de facto-standarden i Prolog-programsammanställningen, har varit i fokus för de flesta studier. Den tillhandahåller instruktioner för speciella ändamål såsom instruktioner för datasammanslutning och instruktioner för kontrollflöde för att stödja backtracking (sökalgoritm).

Strukturera

En generisk abstrakt maskin består av ett minne och en tolk . Minnet används för att lagra data och program, medan tolken är den komponent som exekverar instruktionerna som ingår i program.

Strukturen av en abstrakt maskin

Tolken ska utföra de operationer som är unika för det språk den tolkar. Men med tanke på de olika språken är det tänkbart att identifiera kategorier av operationer och en " exekveringsmekanism " som delas av alla tolkar. Tolkens verksamhet och tillhörande datastrukturer är indelade i följande kategorier:

  1. Operationer för bearbetning av primitiva data :
  2. Operationer och datastrukturer för att styra sekvensen för utförande av operationer ;
  3. Operationer och datastrukturer för kontroll av dataöverföringar ;
  4. Operationer och datastrukturer för minneshantering .

Bearbetar primitiva data

En abstrakt maskin måste innehålla operationer för att manipulera primitiva datatyper som strängar och heltal. Till exempel anses heltal nästan universellt vara en grundläggande datatyp för både fysiska abstrakta maskiner och de abstrakta maskiner som används av många programmeringsspråk . Maskinen utför aritmetiska operationer , såsom addition och multiplikation, inom ett enda tidssteg.

Sekvenskontroll

Operationer och strukturer för "sekvenskontroll" tillåter styrning av exekveringsflödet av programinstruktioner. När vissa villkor är uppfyllda är det nödvändigt att ändra den typiska sekventiella exekveringen av ett program. Därför tolken datastrukturer (som de som används för att lagra adressen till nästa instruktion som ska köras) som modifieras av operationer som skiljer sig från de som används för datamanipulation (till exempel operationer för att uppdatera adressen till nästa instruktion som ska köras ).

Kontroll av dataöverföringar

Dataöverföringsoperationer används för att styra hur operander och data transporteras från minnet till tolken och vice versa. Dessa operationer handlar om butiken och hämtningsordningen för operander från butiken.

Minneshantering

Minneshantering handlar om de operationer som utförs i minnet för att allokera data och applikationer. I den abstrakta maskinen kan data och program hållas på obestämd tid, eller i fallet med programmeringsspråk kan minne allokeras eller omallokeras med hjälp av en mer komplex mekanism.

Hierarkier

En hierarki av abstrakta maskiner

Abstrakta maskinhierarkier används ofta, där varje maskin använder funktionaliteten på nivån omedelbart under och lägger till ytterligare funktioner för att möta nivån omedelbart ovanför. En hårdvarudator , konstruerad med fysiska elektroniska enheter, kan läggas till på den mest grundläggande nivån. Ovanför denna nivå kan den abstrakta mikroprogrammerade maskinnivån introduceras. Den abstrakta maskinen som tillhandahålls av operativsystemet , som implementeras av ett program skrivet på maskinspråk , är placerad omedelbart ovanför (eller direkt ovanför hårdvaran om firmwarenivån inte finns där). Å ena sidan utökar operativsystemet den fysiska maskinens kapacitet genom att tillhandahålla primitiver på högre nivå som inte är tillgängliga på den fysiska maskinen (till exempel primitiver som verkar på filer). Värdmaskinen bildas av den abstrakta maskinen som ges av operativsystemet, på vilken ett programmeringsspråk på hög nivå implementeras med hjälp av en mellanliggande maskin , såsom Java Virtual-maskinen och dess bytekodspråk . Den nivå som ges av den abstrakta maskinen för högnivåspråket (till exempel Java) är vanligtvis inte den slutliga nivån av hierarki. Vid denna tidpunkt kan en eller flera applikationer som levererar tilläggstjänster tillsammans introduceras. En "webbmaskin"-nivå, till exempel, kan läggas till för att implementera de funktioner som krävs för att hantera webbkommunikation ( kommunikationsprotokoll eller HTML-kodpresentation ). Nivån " Web Service " är placerad ovanför denna, och den tillhandahåller de funktioner som krävs för att få webbtjänster att kommunicera, både när det gäller interaktionsprotokoll och beteendet hos de involverade processerna. På denna nivå kan helt nya språk som specificerar beteendet hos så kallade "affärsprocesser" baserade på webbtjänster utvecklas (ett exempel är Business Process Execution Language ). Slutligen kan en specialiserad applikation hittas på högsta nivå (till exempel E-handel ) som har mycket specifik och begränsad funktionalitet.

Se även

  1. ^ Weisstein, Eric W. "Abstract Machine" . mathworld.wolfram.com . Hämtad 2022-05-16 .
  2. ^ a b c d e f "Vad är en abstrakt maskin?" . EasyTechJunkie . Hämtad 2022-05-16 .
  3. ^ a b c d e f g h i j Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (maj 2000). "Abstrakta maskiner för implementering av programmeringsspråk" . Framtida generationens datorsystem . 16 (7): 739–751. doi : 10.1016/S0167-739X(99)00088-6 .
  4. ^ "9.1.1: Översikt över maskin med ändlig tillstånd" . Engineering LibreTexts . 2021-04-29 . Hämtad 2022-05-31 .
  5. ^ "Vad är deterministiskt system? - Definition från Techopedia" . Techopedia.com . Hämtad 2022-05-30 .
  6. ^    Stearns, Richard E. (januari 2003). "Deterministisk kontra icke-deterministisk tid och lägre gränsproblem" . Journal of the ACM . 50 (1): 91–95. doi : 10.1145/602382.602409 . ISSN 0004-5411 . S2CID 2194820 .
  7. ^    Armoni, Michal; Gal-Ezer, Judith (december 2007). "Icke-determinism: ett abstrakt begrepp i datavetenskapliga studier" . Datavetenskaplig utbildning . 17 (4): 243–262. Bibcode : 2007CSEd...17..243A . doi : 10.1080/08993400701442885 . ISSN 0899-3408 . S2CID 41928460 .
  8. ^   Gill, John (december 1977). "Beräkningskomplexitet hos probabilistiska turingmaskiner" . 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   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 , hämtad 2022-05-16
  10. ^   Bair, Ray; Chien, Andrew; Cook, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, John; Vetter, Jeff (2018-02-01). "Hårdvaruutvärdering: abstrakta maskinmodeller och proxyarkitekturer för Exascale Computing" . doi : 10.2172/1733300 . OTI 1733300 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
  11. ^ "abstrakt maskin från FOLDOC" . foldoc.org . Hämtad 2021-08-07 .
  12. ^    Gee, J.; Melvin, SW; Patt, YN (1986). "Implementeringen av Prolog via VAX 8600 mikrokod" . Handlingar från den 19:e årliga workshopen om mikroprogrammering - MICRO 19 . New York, New York, USA: ACM Press: 68–74. doi : 10.1145/19551.19538 . ISBN 081860736X . S2CID 3846072 .
  13. ^ "abstrakt maskin" . Oxford Referens . Hämtad 2022-05-16 .
  14. ^ García-Martín, Julio Manuel; Sutil-Martin, Miguel (1999-08-15). "Ett mönster för att designa abstrakta maskiner" . doi : 10.13140/RG.2.1.3680.5203 ​​. {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
  15. ^ upscfever.com (2017-01-25). "Datororganisation och -arkitektur (Stackorganisation) - UPSC FEVER" . upscfever.com . Hämtad 2022-05-31 .
  16. ^ "Vad är objektorienterad programmering (OOP)?" . SearchAppArchitecture . Hämtad 2022-05-31 .
  17. ^   "Designöverväganden för strängbearbetningsspråk" , En studie i strängbearbetningsspråk , föreläsningsanteckningar i datavetenskap, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 205, s. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN 978-3-540-16041-0 , hämtad 2022-05-31
  18. ^    Hackett, Jennifer; Hutton, Graham (2019-07-26). "Call-by-need är klärvoajant call-by-value" . Proceedings of ACM on Programming Languages ​​. 3 (ICFP): 1–23. doi : 10.1145/3341718 . ISSN 2475-1421 . S2CID 195782686 .
  19. ^ "Prolog | En introduktion" . GeeksforGeeks . 2018-05-26 . Hämtad 2022-05-31 .
  20. ^    Accattoli, Beniamino; Barenbaum, Pablo; Mazza, Damiano (2014-11-26). "Destillering av abstrakta maskiner" . ACM SIGPLAN-meddelanden . 49 (9): 363–376. doi : 10.1145/2692915.2628154 . ISSN 0362-1340 . S2CID 234775413 .
  21. ^ baeldung (2018-01-11). "Introduktion till Java Primitives | Baeldung" . www.baeldung.com . Hämtad 2022-05-31 .
  22. ^   "Interpreter" , Software Architecture Design Patterns in Java , Auerbach Publications, 2004-04-27, doi : 10.1201/9780203496213.ch34 , ISBN 978-0-8493-2142-9 , hämtad 5021-02-03496213.ch34
  23. ^   DB Skillicorn (2005). Grunderna för parallell programmering . Cambridge University Press. sid. 18. ISBN 978-0-521-01856-2 .

Vidare läsning

  • Peter van Emde Boas, Machine Models and Simulations s. 3–66, med i:
Jan van Leeuwen , ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity   , The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volym A). QA 76.H279 1990
Hämtad från " https://en.wikipedia.org/w/index.php?title=Abstract_machine&oldid=1135484418 "