Abstrakte Maschine

Nicht zu verwechseln mit Virtuelle Maschine.

Ein abstrakte Maschine ist ein Informatik theoretisches Modell, das eine detaillierte und präzise Analyse darüber ermöglicht, wie a Computer Systemfunktionen.[1] Es ist analog zu a Mathematische Funktion Da es Eingaben erhält und Ausgaben erzeugt, die auf vordefinierten Regeln basieren. Abstrakte Maschinen variieren von buchstäblichen Maschinen darin, dass sie korrekt und unabhängig von Hardware-.[2] Abstrakte Maschinen sind “MaschinenWeil sie eine Schritt-für-Schritt-Ausführung von zulassen Programme; sie sind "abstraktWeil sie viele Aspekte von tatsächlich ignorieren (Hardware-) Maschinen.[3] Eine typische abstrakte Maschine besteht aus einer Definition in Bezug auf Eingabe, Ausgabe und die Menge der zulässigen Vorgänge, mit denen das erstere in letztere verwandelt wird. Sie können aus rein theoretischen Gründen sowie Modellen für Computersysteme realer Welt verwendet werden.[2] In dem Theorie der Berechnung, abstrakte Maschinen werden häufig in verwendet Gedankenexperimente bezüglich Berechnbarkeit oder um die Komplexität von zu analysieren Algorithmen.[3] Diese Verwendung abstrakter Maschinen ist mit dem Gebiet von verbunden Computerkomplexitätstheorie, wie zum Beispiel endliche Staatsmaschinen , Mehlige Maschinen, Push-Down-Automaten, und Turing -Maschinen.[4]


Einstufung

Abstrakte Maschinen werden in der Regel in zwei Typen eingeteilt, abhängig von der Anzahl der Vorgänge, die sie zu einem bestimmten Zeitpunkt durchführen dürfen: deterministische abstrakte Maschinen und Nichtdeterministische abstrakte Maschinen.[2] A deterministisch Abstract Machine ist ein System, in dem ein bestimmter Anfangszustand oder eine bestimmte Bedingung immer die gleichen Ausgänge liefert. Es gibt keine Zufälligkeit oder Variation in der Art und Weise, wie Eingaben in Ausgänge umgewandelt werden.[5] Inzwischen a nicht deterministisch Abstract Machine kann verschiedene Ausgänge für dieselbe Eingabe für verschiedene Ausführungen bereitstellen.[2] Im Gegensatz zu einem deterministischen Algorithmus, der das gleiche Ergebnis für denselben Eingang ergibt, unabhängig von der Anzahl der Iterationen, erfordert ein nicht detministischer Algorithmus verschiedene Wege, um zu unterschiedlichen Ausgängen zu gelangen.[6] Nichtdeterministische Algorithmen sind hilfreich, um ungefähre Antworten zu erhalten, wenn eine präzise Lösung unter Verwendung eines deterministischen Ansatzes schwierig oder kostspielig ist[7].

Ein Lauf von a Turing Maschine.

Die Turing -MaschineZum Beispiel ist eine der grundlegendsten abstrakten Maschinen der Informatik.[2] Dies ist eine Maschine, die Operationen auf a durchführen kann Klebeband (eine Zeichenfolge von Symbolen) irgendeiner Länge. Es enthält Anweisungen zum Ändern der Symbole und zum Ändern des Symbols, auf dem es basiert. Der einzelne Befehl auf einem rudimentären Turing -Computer wäre "Symbol in 1 und dann nach rechts", und diese Maschine würde nur eine 1s -Zeichenfolge erzeugen.[8] Diese grundlegende Turing -Maschine ist jedoch deterministisch Nichtdeterministische Turing -Maschinen Dies kann mehrere Aktionen ausführen, da dieselbe Eingabe auch erstellt werden kann.[2]

Implementierung einer abstrakten Maschine

Jede Implementierung einer abstrakten Maschine im Fall einer physischen Implementierung (in Hardware-) Verwenden Sie eine Art physikalisches Gerät (mechanisch, elektronisch usw.), um die Anweisungen von a auszuführen Programmiersprache. Abstrakte Maschine kann jedoch auch in implementiert werden Software oder Firmware Auf Ebenen intermediieren die abstrakte Maschine und die zugrunde liegende physikalische Vorrichtung.[9]

  • Simulation mit Software: Implementierung einer abstrakten Maschine mit Software beinhaltet das Schreiben von Programmen in einem anderen Sprache um die zu implementieren Datenstrukturen und Algorithmen benötigt von der abstrakten Maschine. Dies bietet die größte Flexibilität, da Programme, die abstrakte Maschinenkonstrukte implementieren, leicht verändert werden können.[9] Eine abstrakte Maschine als Softwaresimulation implementiert oder für die eine Dolmetscher existiert, wird genannt virtuelle Maschine.[11]

Programmiersprache Implementierung

Der Begriff "Maschine"Bezieht sich auf eine Computermaschine, die eine physische Maschine ist, die Algorithmen ausführt, die ausreichend formalisiert sind, damit die Maschine" Verständnis "ist. Eine abstrakte Maschine ist intuitiv nichts weiter als eine Abstraktion der Idee eines physischen Computers.[13] Für die tatsächliche Ausführung, Algorithmen muss mit den von a angebotenen Konstrukten ordnungsgemäß formalisiert werden Programmiersprache. Dies impliziert, dass die zu ausgeführten Algorithmen unter Verwendung von Programmiersprachenanweisungen ausgedrückt werden müssen.[3] Das Syntax einer Programmiersprache ermöglicht den Bau von Programme Verwenden eines endlichen Satzes von Konstrukten, die als Anweisungen bezeichnet werden. Die meisten abstrakten Maschinen teilen sich Ein Programm Store und ein Staat, was oft beinhaltet ein Stapel und Register.[9][14] In digitalen Computern ist der Stapel einfach ein Speichereinheit mit einem Adressregister, das nur positive Ganzzahlen zählen kann (nachdem ein Anfangswert hineingeladen wurde). Das Adressregister für den Stack ist als bekannt als Ein Stapelzeiger Weil sich sein Wert immer auf das obere Element auf dem Stapel bezieht.[15] Das Programm besteht aus einer Reihe von Anweisungen mit Ein Stapelzeiger Zeigen Sie den nächsten Anweisungen an. Wenn die Anweisung abgeschlossen ist, Ein Stapelzeiger ist fortgeschritten. Dieser grundlegende Kontrollmechanismus einer abstrakten Maschine ist auch als ihre bekannt Ausführungsschleife.[3] Somit ist eine abstrakte Maschine für die Programmiersprache jede Sammlung von Datenstrukturen und Algorithmen, die in der Programmiersprache Programme speichern und ausführen können. Es überbrückt die Lücke zwischen den Hohe Ebene einer Programmiersprache und die niedriger Ebene einer tatsächlichen Maschine durch Bereitstellung eines Zwischensprachenschritts für Zusammenstellung. Die Anweisungen einer abstrakten Maschine werden an die einzigartigen Vorgänge angepasst, die zur Implementierung von Operationen einer bestimmten Quellsprache oder einer Reihe von Quellsprachen erforderlich sind.[9]

Imperative Programmiersprachen

In den späten 1950er Jahren die Assoziation für Computermaschinen (ACM) und andere alliierte Organisationen entwickelten viele Vorschläge für Universelle computerorientierte Sprache (UNCOL), wie zum Beispiel Conways Maschine. Das Uncol -Konzept ist gut, aber es wurde aufgrund der schlechten Leistung des Erzeugten nicht weit verbreitet Code. In vielen Bereichen des Computers wird seine Leistung trotz der Entwicklung dessen weiterhin ein Problem sein Java virtuelle Maschine In den späten 1990er Jahren.[16] Algol -Objektcode (1964), p4-machine (1976), UCSD P-Machine (1977) und Weiter (1970) sind einige erfolgreiche abstrakte Maschinen dieser Art.[3]

Objektorientierte Programmiersprachen

Abstrakte Maschinen für objektorientierte Programmiersprachen sind oft Stackbasiert und haben spezielle Zugangsanweisungen für Objektfelder und Methoden. In diesen Maschinen, Speicherverwaltung wird oft implizit von a durchgeführt Müllsammler (Memory Recovery -Funktion in Programmiersprachen integriert).[17] Smalltalk-80 (1980), Selbst (1989) und Java (1994) sind Beispiele für diese Implementierung.[3]

String -Verarbeitungssprachen

A String -Verarbeitungssprache ist eine Computersprache, die sich eher auf die Verarbeitung von Zeichenfolgen als auf Zahlen konzentriert. Es gab String -Verarbeitungssprachen in Form von Befehlsschalen, Programmierwerkzeuge, Makroprozessoren, und Skriptsprachen für Jahrzehnte.[18] Die Verwendung einer geeigneten abstrakten Maschine hat zwei Vorteile: Erhöht Ausführungsgeschwindigkeit und verbesserte Portabilität. Snobol4 und Ml/i sind zwei bemerkenswerte Fälle von frühen String -Verarbeitungssprachen, die eine abstrakte Maschine verwenden, um die Unabhängigkeit von Maschinen zu gewinnen.[3]

Funktionale Programmiersprachen

Bildliche Darstellung von a Krivinmaschine.

Die frühen abstrakten Maschinen für Funktionssprachen, einschließlich der SECD -Maschine (1964) und Cardellis funktionaler abstrakter Maschine (1983) definierte strenge Bewertung, auch bekannt als eifrige oder Anrufbewertung,[3] in welchen Funktionsargumenten werden zuvor auf den Anruf und genau einmal bewertet. In den letzten Jahren war der Großteil der Forschung an faule (oder rufe) Bewertung,[19] so wie die G-Machine (1984), Krivinmaschine (1985) und drei Unterrichtsmaschine (1986), in denen Funktionsargumente nur bei Bedarf und höchstens erforderlich bewertet werden. Ein Grund dafür ist, dass eine effektive Implementierung der strengen Bewertung jetzt gut verstanden ist, daher hat die Notwendigkeit einer abstrakten Maschine verringert.[3]

Logische Programmiersprachen

Prädikatkalkül (Logik erster Ordnung) ist die Grundlage von Logische Programmiersprachen. Die bekannteste logische Programmiersprache ist Prolog. Die Regeln im Prolog sind in einem einheitlichen Format geschrieben, das als allgemein quantifizierte „Horn -Klauseln“ bezeichnet wird, was bedeutet, die Berechnung zu beginnen, die versucht, einen Beweis des Ziels zu ermitteln. Das Warren abstrakte Maschine WAM (1983),[3] Dies war der De -facto -Standard in der Prolog -Programmzusammenstellung geworden, war der Schwerpunkt der meisten Studien. Es enthält spezielle Anweisungen für Zwecke wie Anweisungen zur Datenvereinigung und Steuerungsanweisungen zur Unterstützung von Backtracking (Suchalgorithmus).[20]

Struktur einer abstrakten Maschine

Eine generische abstrakte Maschine besteht aus a Erinnerung und ein Dolmetscher. Der Speicher wird verwendet, um Daten und Programme zu speichern, während der Dolmetscher die Komponente ist, die die in den Programmen enthaltenen Anweisungen ausführt.[9]

Die Struktur einer abstrakten Maschine

Der Dolmetscher muss die Operationen ausführen, die einzigartig für die Sprache es interpretiert. Angesichts der Vielfalt der Sprachen ist es jedoch denkbar, Kategorien von Operationen und eins zu identifizieren.Ausführungsmechanismus"Von allen Dolmetschern geteilt. Die Operationen und Begleitdatenstrukturen des Dolmetschers sind in die folgenden Kategorien unterteilt:[9][21]

  1. Operationen zur Verarbeitung Primitive Daten:
  2. Operationen und Datenstrukturen zur Steuerung der Abfolge von Ausführung von Operationen;
  3. Operationen und Datenstrukturen für die Steuerung Datenübertragungen;
  4. Operationen und Datenstrukturen für Speicherverwaltung.

Vorgänge zur Verarbeitung primitiver Daten

Sogar eine abstrakte Maschine arbeitet durch Ausführen von Algorithmen, daher muss sie Operationen zum Manipulieren enthalten Primitive Datentypen wie Saiten und Ganzzahlen.[9] Zum Beispiel werden Ganzzahlen (Ganzzahl oder Real) nahezu allgemein als grundlegende Daten für sowohl für physikalische abstrakte Maschinen als auch für die abstrakten Maschinen, die von vielen verwendet werden Programmiersprachen. Die Maschine macht sofort die verschiedenen Rechenoperationen notwendig (Zugabe, Multiplikation usw.)[22].

Operationen und Datenstrukturen für die Sequenzsteuerung

Operationen und Strukturen für die "Sequenzsteuerung" ermöglichen die Steuerung der Ausführungsfluss von Programmanweisungen. Wenn sicher Bedingungen sind erfüllt, es ist notwendig, die typische sequentielle Ausführung eines Programms zu ändern.[9] deshalb, die Dolmetscher verwendet Datenstrukturen (z. die Anschrift von der nächsten Ausführung), die durch Operationen geändert werden, die sich von den für die Datenmanipulation verwendeten Operationen unterscheiden (z. B. Vorgänge zum Aktualisieren der Adresse der nächsten Ausführung).[23]

Vorgänge und Datenstrukturen zur Steuerung von Datenübertragungen

Datenübertragungsvorgänge werden verwendet, um zu steuern, wie Operanden und Daten von Daten transportiert werden Erinnerung zum Dolmetscher und umgekehrt. Diese Operationen befassen sich mit dem Laden und die Abrufreihenfolge der Operanden aus dem Geschäft.[9]

Operationen und Datenstrukturen für die Speicherverwaltung

Speicherverwaltung befasst sich mit den im Speicher ausgeführten Vorgängen, um Daten und Anwendungen zuzuweisen. In der abstrakten Maschine können Daten und Programme auf unbestimmte Zeit oder im Fall von Programmiersprachen mithilfe eines komplexeren Mechanismus zugewiesen oder verkauft werden.[9]

Hierarchien abstrakter Maschinen

Eine Hierarchie abstrakter Maschinen

Es werden häufig abstrakte Maschinenhierarchien verwendet, bei denen jede Maschine die Funktionalität der Ebene unmittelbar darunter verwendet und die eigene zusätzliche Funktionalität hinzufügt, um die Ebene unmittelbar darüber zu erfüllen.[9] A Hardwarecomputer, konstruiert mit physikalischen elektronischen Geräten, können auf der grundlegendsten Ebene hinzugefügt werden. Über diesem Niveau die Zusammenfassung mikroprogrammierter Maschinenstand kann eingeführt werden. Die abstrakte Maschine, die von der geliefert wird Betriebssystem, was durch Programm geschrieben wurde in implementiert wird Maschinensprachebefindet sich unmittelbar oben (oder direkt über dem Hardware- Wenn die Firmware Level ist nicht da).[9][24] Einerseits erweitert das Betriebssystem die Fähigkeit der physischen Maschine, indem sie höhere Primitive bereitstellt, die auf der physischen Maschine nicht verfügbar sind (z. B. Primitive, die auf Dateien reagieren). Das Hostmaschine wird von der abstrakten Maschine gebildet, die vom Betriebssystem gegeben wird, auf dem a Programmiersprache auf hoher Ebene wird mit einem implementiert Zwischenmaschine, wie die java virtuelle Maschine und ihre Bytecode -Sprache.[16][25] Die Ebene der abstrakten Maschine für die hochrangige Sprache (Zum Beispiel Java) ist normalerweise nicht die endgültige Hierarchiestufe. Zu diesem Zeitpunkt kann ein oder mehrere Anwendungen eingeführt werden, die zusätzliche Dienste anbieten. Zum Beispiel kann eine "Webmaschinenstufe" hinzugefügt werden, um die Funktionen zu implementieren, die für die Verarbeitung von Webkommunikationen erforderlich sind (Kommunikationsprotokolle oder HTML -Codepräsentation). Das "Internetservice"Die Ebene befindet sich darüber und bietet die Funktionen, die für die Kommunikation von Webdiensten erforderlich sind, sowohl in Bezug auf Interaktionsprotokolle als auch das Verhalten der beteiligten Prozesse.[26] Auf dieser Ebene können völlig neue Sprachen, die das Verhalten sogenannter "Geschäftsprozesse" angeben, basierend auf Webdiensten Geschäftsprozess -Ausführungssprache). Schließlich findet sich eine spezielle Anwendung auf höchstem Niveau (zum Beispiel, zum Beispiel, E-Commerce) was sehr spezifische und begrenzte Funktionen hat.[9]

Siehe auch

Verweise

  1. ^ Weisstein, Eric W. "Abstract Machine". mathworld.wolfram.com. Abgerufen 2022-05-16.
  2. ^ a b c d e f "Was ist eine abstrakte Maschine?". EasyTechjunkie. Abgerufen 2022-05-16.
  3. ^ a b c d e f g h i j Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (Mai 2000). "Abstrakte Maschinen für die Programmiersprache Implementierung". Computersysteme zukünftige Generation. 16 (7): 739–751. doi:10.1016/s0167-739x (99) 00088-6.
  4. ^ "9.1.1: Übersicht über Finite-State-Maschine". Engineering Libretexten. 2021-04-29. Abgerufen 2022-05-31.
  5. ^ "Was ist deterministisches System? - Definition aus Techopedia". Techopedia.com. Abgerufen 2022-05-30.
  6. ^ Stearns, Richard E. (Januar 2003). "Deterministisch versus nichtdeterministische Zeit und Probleme mit der unteren gebundenen Probleme". Journal of the ACM. 50 (1): 91–95. doi:10.1145/602382.602409. ISSN 0004-5411. S2CID 2194820.
  7. ^ Armoni, Michal; Gal-Ezer, Judith (Dezember 2007). "Nichtdeterminismus: Ein abstraktes Konzept in Informatikstudien". Informatikausbildung. 17 (4): 243–262. Bibcode:2007CSED ... 17..243a. doi:10.1080/08993400701442885. ISSN 0899-3408. S2CID 41928460.
  8. ^ Gill, John (Dezember 1977). "Berechnungskomplexität probabilistischer Turing -Maschinen". Siam Journal über 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), "Abstrakte Maschinen", Programmiersprachen: Prinzipien und Paradigmen, London: Springer London, S. 1–25, doi:10.1007/978-1-84882-914-5_1, ISBN 978-1-84882-913-8, abgerufen 2022-05-16
  10. ^ Bair, Ray; Chien, Andrew; Koch, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, John; Vetter, Jeff (2018-02-01). "Hardware -Bewertung: Abstrakte Maschinenmodelle und Proxy -Architekturen für Exascale Computing". doi:10.2172/1733300. Osti 1733300. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  11. ^ "Abstract Machine aus firthOC". fctoc.org. Abgerufen 2021-08-07.
  12. ^ Gee, J.; Melvin, S. W.; Patt, Y. N. (1986). "Die Implementierung von Prolog über VAX 8600 Microcode". Verfahren des 19. jährlichen Workshops zur Mikroprogrammen - Micro 19. New York, New York, USA: ACM Press: 68–74. doi:10.1145/19551.19538. ISBN 081860736X. S2CID 3846072.
  13. ^ "Abstract Machine". Oxford Referenz. Abgerufen 2022-05-16.
  14. ^ García-Martín, Julio Manuel; Sutil-Martin, Miguel (1999-08-15). "Ein Muster zum Entwerfen abstrakter Maschinen". doi:10.13140/rg.2.1.3680.5203. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  15. ^ Upscfever.com (2017-01-25). "Computerorganisation und Architektur (Stack Organization) - UPSC -Fieber". Upscfever.com. Abgerufen 2022-05-31.
  16. ^ a b Tyson, Matthew (2020-01-17). "Was ist die JVM? Einführung der virtuellen Java -Maschine". InfoWorld. Abgerufen 2022-05-31.
  17. ^ "Was ist objektorientierte Programmierung (OOP)?". SearchApparchitecture. Abgerufen 2022-05-31.
  18. ^ "Konstruktionsüberlegungen für String -Verarbeitungssprachen", Eine Studie in String -Verarbeitungssprachen, Vorlesungen in Informatik, 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, abgerufen 2022-05-31
  19. ^ Hackett, Jennifer; Hutton, Graham (2019-07-26). "Call-by-Need ist hellseherer Call-by-Wert". Verfahren der ACM auf Programmiersprachen. 3 (ICFP): 1–23. doi:10.1145/3341718. ISSN 2475-1421. S2CID 195782686.
  20. ^ "Prolog | Eine Einführung". Geeksforgeeks. 2018-05-26. Abgerufen 2022-05-31.
  21. ^ Accattoli, Beniamino; Barenbaum, Pablo; Mazza, Damiano (2014-11-26). "Abstrakte Maschinen destillieren". ACM Sigplan nennt. 49 (9): 363–376. doi:10.1145/2692915.2628154. ISSN 0362-1340. S2CID 234775413.
  22. ^ Baeldung (2018-01-11). "Einführung in Java Primitive | Baeldung". www.baeldung.com. Abgerufen 2022-05-31.
  23. ^ "Dolmetscher", Software -Architektur -Designmuster in Java, Auerbach Publications, 2004-04-27, doi:10.1201/9780203496213.Ch34, ISBN 978-0-8493-2142-9, abgerufen 2022-05-31
  24. ^ "Hardware gegen Software gegen Firmware: Was ist der Unterschied?". Lebenswire. Abgerufen 2022-05-31.
  25. ^ Accattoli, Beniamino;BARRAS, Bruno (2017-10-09). "Umgebungen und die Komplexität abstrakter Maschinen". Verfahren des 19. Internationalen Symposiums über Prinzipien und Praxis der deklarativen Programmierung. Namur Belgien: ACM: 4–16. doi:10.1145/3131851.3131855. ISBN 978-1-4503-5291-8. S2CID 11953081.
  26. ^ "Internetdienste". reference.wolfram.com. Abgerufen 2022-05-31.
  27. ^ D. B. Skilicorn (2005). Grundlagen der parallelen Programmierung. Cambridge University Press. p. 18. ISBN 978-0-521-01856-2.

Weitere Lektüre

  • Peter van Emde Boas, Maschinenmodelle und Simulationen S. 3–66, erscheinen in:
Jan van Leeuwen, ed."Handbuch der theoretischen Informatik. Band A: Algorithmen und Komplexität, The MIT Press/Elsevier, 1990. ISBN0-444-88071-2 (Band A).QA 76.H279 1990