Editing Abstract machine

{{Short description|Theoretical computer used for defining a model of computation}}
{{Distinguish|Virtual machine}}
In [[computer science]], an '''abstract machine''' is a theoretical model that allows for a detailed and precise analysis of how a computer system functions.<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Abstract Machine |url=https://mathworld.wolfram.com/ |access-date=2022-05-16 |website=mathworld.wolfram.com |language=en}}</ref> It is similar to a [[Function (mathematics)|mathematical function]] in that it receives inputs and produces outputs based on predefined rules. Abstract machines vary from literal machines in that they are expected to perform correctly and independently of [[Hardware description language|hardware]].<ref name=":2">{{Cite web |title=What is an Abstract Machine? |url=http://www.easytechjunkie.com/what-is-an-abstract-machine.htm |access-date=2022-05-16 |website=EasyTechJunkie |language=en-US}}</ref> Abstract machines are "[[machine]]s" because they allow step-by-step execution of [[Programming language|programs]]; they are "[[Abstraction (computer science)|abstract]]" because they ignore many aspects of actual ([[Hardware description language|hardware]]) machines.<ref name=":1">{{Cite journal |last1=Diehl |first1=Stephan |last2=Hartel |first2=Pieter |last3=Sestoft |first3=Peter |date=May 2000 |title=Abstract machines for programming language implementation |url=https://linkinghub.elsevier.com/retrieve/pii/S0167739X99000886 |journal=Future Generation Computer Systems |language=en |volume=16 |issue=7 |pages=739–751 |doi=10.1016/S0167-739X(99)00088-6}}</ref> A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter. They can be used for purely theoretical reasons as well as models for real-world computer systems.<ref name=":2" /> In the [[theory of computation]], abstract machines are often used in [[thought experiments]] regarding [[computability]] or to analyse the complexity of [[algorithm]]s.<ref name=":1" /> This use of abstract machines is fundamental to the field of [[computational complexity theory]], such as with [[Finite-state machine|finite state machines]], [[Mealy machine|Mealy machines]], [[Pushdown automaton|push-down automata]], and [[Turing machine|Turing machines]].<ref>{{Cite web |date=2021-04-29 |title=9.1.1: Finite-State Machine Overview |url=https://eng.libretexts.org/Under_Construction/Book%3A_Discrete_Structures/09%3A_Finite-State_Automata/9.01%3A_Introduction/9.1.01%3A_Finite-State_Machine_Overview |access-date=2022-05-31 |website=Engineering LibreTexts |language=en}}</ref>

== Classification ==
Abstract machines are typically categorized into two types based on the quantity of operations they can execute simultaneously at any given moment: [[Deterministic algorithm|deterministic abstract machines]] and [[Nondeterministic algorithm|non-deterministic abstract machines]].<ref name=":2" /> A [[Deterministic algorithm|deterministic]] abstract machine is a system in which a particular beginning state or condition always yields the same outputs. There is no randomness or variation in how inputs are transformed into outputs.<ref>{{Cite web |title=What is Deterministic System? - Definition from Techopedia |url=http://www.techopedia.com/definition/602/deterministic-system |access-date=2022-05-30 |website=Techopedia.com |date=29 August 2019 |language=en}}</ref> In contrast, a [[Nondeterministic algorithm|non-deterministic]] abstract machine can provide various outputs for the same input on different executions.<ref name=":2" /> Unlike a deterministic algorithm, which gives the same result for the same input regardless of the number of iterations, a non-deterministic algorithm takes various paths to arrive to different outputs.<ref>{{Cite journal |last=Stearns |first=Richard E. |date=January 2003 |title=Deterministic versus nondeterministic time and lower bound problems |url=http://dx.doi.org/10.1145/602382.602409 |journal=Journal of the ACM |volume=50 |issue=1 |pages=91–95 |doi=10.1145/602382.602409 |s2cid=2194820 |issn=0004-5411}}</ref> Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.<ref>{{Cite journal |last1=Armoni |first1=Michal |last2=Gal-Ezer |first2=Judith |date=December 2007 |title=Non-determinism: An abstract concept in computer science studies |url=http://dx.doi.org/10.1080/08993400701442885 |journal=Computer Science Education |volume=17 |issue=4 |pages=243–262 |doi=10.1080/08993400701442885 |bibcode=2007CSEd...17..243A |s2cid=41928460 |issn=0899-3408}}</ref>

[[File:2-state 3-symbol Turing Machine.png|thumb|A run of a [[Turing machine]]]]
[[Turing machine|Turing machines]], for example, are some of the most fundamental abstract machines in computer science.<ref name=":2" /> These machines conduct operations on a [[String (computer science)|tape (a string of symbols)]] of any length. Their instructions provide for both modifying the symbols and changing the symbol that the machine’s pointer is currently at. For example, a rudimentary Turing machine could have a single command, "convert symbol to 1 then move right", and this machine would only produce a string of 1s.<ref>{{Cite journal |last=Gill |first=John |date=December 1977 |title=Computational Complexity of Probabilistic Turing Machines |url=http://epubs.siam.org/doi/10.1137/0206049 |journal=SIAM Journal on Computing |language=en |volume=6 |issue=4 |pages=675–695 |doi=10.1137/0206049 |issn=0097-5397}}</ref> This basic Turing machine is deterministic; however, [[Nondeterministic Turing machine|nondeterministic Turing machines]] that can execute several actions given the same input may also be built.<ref name=":2" />

== Implementation ==
Any implementation of an abstract machine in the case of physical implementation (in [[Hardware description language|hardware]]) uses some kind of physical device (mechanical or electronic) to execute the instructions of a [[programming language]]. An abstract machine, however, can also be implemented in [[software]] or [[firmware]] at levels between the abstract machine and underlying physical device.<ref name=":3">{{Citation |last1=Gabbrielli |first1=Maurizio |title=Abstract Machines |date=2010 |url=http://link.springer.com/10.1007/978-1-84882-914-5_1 |work=Programming Languages: Principles and Paradigms |pages=1–25 |place=London |publisher=Springer London |doi=10.1007/978-1-84882-914-5_1 |isbn=978-1-84882-913-8 |access-date=2022-05-16 |last2=Martini |first2=Simone}}</ref> 

* [[Hardware description language|Implementation in hardware]]: The direct implementation of abstract machine in hardware is a matter of using physical devices such as [[Memory cell (computing)|memory]], [[Arithmetic logic unit|arithmetic]] and [[Logic gate|logic circuits]], buses, etc., to implement a physical machine whose machine language coincides with the [[programming language]]. Once constructed, it would be virtually hard to change such a machine.<ref name=":3" /> A [[Central processing unit|CPU]] may be thought of as a concrete hardware realisation of an abstract machine, particularly the [[Processor (computing)|processor's design]].<ref>{{Cite report |last1=Bair |first1=Ray |last2=Chien |first2=Andrew |last3=Cook |first3=Jeanine |last4=Donofrio |first4=Dave |last5=Grider |first5=Gary |last6=Kuehn |first6=Jeff |last7=Moore |first7=Shirley |last8=Shalf |first8=John |last9=Vetter |first9=Jeff |date=2018-02-01 |title=Hardware Evaluation: Abstract Machine Models and Proxy Architectures for Exascale Computing |doi=10.2172/1733300 |osti=1733300 |url=http://dx.doi.org/10.2172/1733300|type=Technical report|publisher=U.S. Department of Energy Office of Scientific and Technical Information}}</ref>

* [[Software|Simulation using software]]: Implementing an abstract machine with software entails writing programmes in a different [[Programming language|language]] to implement the [[Data structure|data structures]] and [[Algorithm|algorithms]] needed by the abstract machine. This provides the most flexibility since programmes implementing abstract machine constructs can be easily changed.<ref name=":3" /> An abstract machine implemented as a software simulation, or for which an [[Interpreter (computing)|interpreter]] exists, is called a [[virtual machine]].<ref name=":0">{{Cite web |title=abstract machine from FOLDOC |url=http://foldoc.org/Abstract+machine |access-date=2021-08-07 |website=foldoc.org}}</ref>

* [[Firmware|Emulation using firmware]]: Firmware implementation sits between hardware and software implementation. It consists of [[microcode]] simulations of [[Data structure|data structures]] and [[Algorithm|algorithms]] for abstract machines.<ref name=":3" /> [[Microcode]] allows a computer programmer to write machine [[Machine code|instructions]] without needing to fabricate [[Electronic circuit|electrical circuitry]].<ref>{{Cite book |last1=Gee |first1=J. |last2=Melvin |first2=S. W. |last3=Patt |first3=Y. N. |title=Proceedings of the 19th annual workshop on Microprogramming |chapter=The implementation of Prolog via VAX 8600 microcode |date=1986 |chapter-url=http://dx.doi.org/10.1145/19551.19538 |pages=68–74 |location=New York, New York, USA |publisher=ACM Press |doi=10.1145/19551.19538|isbn=081860736X |s2cid=3846072 }}</ref>

== Programming language implementation ==
An abstract machine is, intuitively, just an [[Abstraction (computer science)|abstraction]] of the idea of a physical computer.<ref>{{Cite web |title=abstract machine |url=https://www.oxfordreference.com/view/10.1093/oi/authority.20110803095345129 |access-date=2022-05-16 |website=Oxford Reference |language=en}}</ref> For actual execution, [[algorithm]]s must be properly formalised using the constructs offered by a [[programming language]]. This implies that the algorithms to be executed must be expressed using programming language instructions.<ref name=":1" /> The [[Syntax (programming languages)|syntax of a programming language]] enables the construction of [[Computer program|programs]] using a finite set of constructs known as instructions. Most abstract machines share [[Stored-program computer|a program store]] and [[State (computer science)|a state]], which often includes [[Stack (abstract data type)|a stack]] and registers.<ref name=":3" /><ref>{{Cite conference |last1=García-Martín |first1=Julio Manuel |last2=Sutil-Martin |first2=Miguel |date=August 15, 1999 |contribution=The Abstract Machine: A Pattern for Designing Abstract Machines |contribution-url=https://hillside.net/plop/plop99/proceedings/garcia/garcia.pdf|title=Proceedings of Pattern Languages of Programs '99}}</ref> In digital computers, the stack is simply a [[Memory cell (computing)|memory unit]] with an address register that can count only positive integers (after an initial value is loaded into it). The address register for the stack is known as [[Program counter|a stack pointer]] because its value always refers to the top item on the stack.<ref>{{Cite web |last=upscfever.com |date=2017-01-25 |title=Computer Organization and Architecture (Stack Organization) - UPSC FEVER |url=http://upscfever.com/upsc-fever/en/gatecse/en-gatecse-chp159.html |access-date=2022-05-31 |website=upscfever.com |language=en}}</ref> The program consists of a series of instructions, with [[Program counter|a stack pointer]] indicating the next instruction to be performed. When the instruction is completed, [[Program counter|a stack pointer]] is advanced. This fundamental control mechanism of an abstract machine is also known as its [[Execution (computing)|execution loop]].<ref name=":1" /> Thus, an abstract machine for a programming language is any collection of [[data structure]]s and algorithms capable of storing and running programs written in the programming language. It bridges the gap between the [[High-level programming language|high level of a programming language]] and the [[Low-level programming language|low level of an actual machine]] by providing an intermediate language step for [[Compiler|compilation]]. An abstract machine's instructions are adapted to the unique operations necessary to implement operations of a certain source language or set of source languages.<ref name=":3" />

=== Imperative languages ===
In the late 1950s, the [[Association for Computing Machinery|Association for Computing Machinery (ACM)]] and other allied organisations developed many proposals for [[UNCOL|Universal Computer Oriented Language (UNCOL)]], such as [[Conway's Game of Life|Conway's machine]]. The UNCOL concept is good, but it has not been widely used due to the poor performance of the generated [[code]]. In many areas of computing, its performance will continue to be an issue despite the development of the [[Java virtual machine|Java Virtual Machine]] in the late 1990s. [[ALGOL|Algol Object Code]] (1964), P4-machine (1976), [[UCSD Pascal|UCSD P-machine]] (1977), and [[Forth (programming language)|Forth]] (1970) are some successful abstract machines of this kind.<ref name=":1" />

=== Object-oriented languages ===
Abstract machines for [[Object-oriented programming|object-oriented programming languages]] are often [[Stack-based memory allocation|stack-based]] and have special access instructions for [[Object (computer science)|object fields]] and [[Method (computer programming)|methods]]. In these machines, [[memory management]] is often implicit performed by a [[Garbage collection (computer science)|garbage collector]] (memory recovery feature built into programming languages).<ref>{{Cite web |title=What is Object-Oriented Programming (OOP)? |url=https://www.techtarget.com/searchapparchitecture/definition/object-oriented-programming-OOP |access-date=2022-05-31 |website=SearchAppArchitecture |language=en}}</ref> [[Smalltalk|Smalltalk-80]] (1980), [[Self (programming language)|Self]] (1989), and [[Java (programming language)|Java]] (1994) are examples of this implementation.<ref name=":1" /> 

=== String processing languages ===
A [[String (computer science)|string processing language]] is a computer language that focuses on processing strings rather than numbers. There have been string processing languages in the form of [[Shell (computing)|command shells]], [[Programming tool|programming tools]], [[General-purpose macro processor|macro processors]], and [[Scripting language|scripting languages]] for decades.<ref>{{Citation |title=Design considerations for string processing languages |date=1985 |url=http://dx.doi.org/10.1007/3-540-16041-8_2 |work=A Study in String Processing Languages |series=Lecture Notes in Computer Science |volume=205 |pages=17–37 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-16041-8_2 |isbn=978-3-540-16041-0 |access-date=2022-05-31}}</ref> Using a suitable abstract machine has two benefits: increased [[Execution (computing)|execution speed]] and enhanced portability. [[SNOBOL|Snobol4]] and [[ML/I]] are two notable instances of early string processing languages that use an abstract machine to gain machine independence.<ref name=":1" />

=== Functional programming languages ===
[[File:Machine de Krivine.jpg|thumb|Pictorial representation of a [[Krivine machine]]]]The early abstract machines for [[Functional programming|functional languages]], including the [[SECD machine]] (1964) and Cardelli's Functional Abstract Machine (1983), defined strict evaluation, also known as [[Evaluation strategy|eager or call-by-value evaluation]],<ref name=":1" /> in which function arguments are evaluated before the call and precisely once. Recently, the majority of research has been on [[Lazy evaluation|lazy (or call-by-need) evaluation]],<ref>{{Cite journal |last1=Hackett |first1=Jennifer |last2=Hutton |first2=Graham |date=2019-07-26 |title=Call-by-need is clairvoyant call-by-value |journal=Proceedings of the ACM on Programming Languages |volume=3 |issue=ICFP |pages=1–23 |doi=10.1145/3341718 |s2cid=195782686 |issn=2475-1421|doi-access=free }}</ref> such as the G-machine (1984), [[Krivine machine]] (1985), and Three Instruction Machine (1986), in which function arguments are evaluated only if necessary and at most once. One reason is because effective implementation of strict evaluation is now well-understood, therefore the necessity for an abstract machine has diminished.<ref name=":1" />

=== Logical languages ===
[[First-order logic|Predicate calculus (first order logic)]] is the foundation of [[Logic programming|logic programming languages]]. The most well-known logic programming language is [[Prolog]]. The rules in Prolog are written in a uniform format known as universally quantified 'Horn clauses', which means to begin the calculation that attempts to discover a proof of the objective. The [[Warren Abstract Machine|Warren Abstract Machine WAM]] (1983),<ref name=":1" /> which has become the de facto standard in Prolog program compilation, has been the focus of most study. It provides special purpose instructions such as data unification instructions and control flow instructions to support backtracking (searching algorithm).<ref>{{Cite web |date=2018-05-26 |title=Prolog {{!}} An Introduction |url=https://www.geeksforgeeks.org/prolog-an-introduction/ |access-date=2022-05-31 |website=GeeksforGeeks |language=en-us}}</ref>
== Structure ==
A generic abstract machine is made up of a [[Memory cell (computing)|memory]] and an [[Interpreter (computing)|interpreter]]. The memory is used to store data and programs, while the interpreter is the component that executes the instructions included in programs.<ref name=":3" /> 
[[File:The_structure_of_an_abstract_machine.png|thumb|The structure of an abstract machine]]
The interpreter must carry out the operations that are unique to the [[Programming language|language]] it is interpreting. However, given the variety of languages, it is conceivable to identify categories of operations and an "[[Execution (computing)|execution mechanism]]" shared by all interpreters. The interpreter's operations and accompanying data structures are divided into the following categories:<ref name=":3" /><ref>{{Cite journal |last1=Accattoli |first1=Beniamino |last2=Barenbaum |first2=Pablo |last3=Mazza |first3=Damiano |date=2014-11-26 |title=Distilling abstract machines |url=https://dl.acm.org/doi/10.1145/2692915.2628154 |journal=ACM SIGPLAN Notices |language=en |volume=49 |issue=9 |pages=363–376 |doi=10.1145/2692915.2628154 |s2cid=234775413 |issn=0362-1340}}</ref>

# Operations for processing [[Primitive data type|primitive data]]: 
# Operations and data structures for controlling the sequence of [[Execution (computing)|execution of operations]];
# Operations and data structures for controlling [[Data communication|data transfers]];
# Operations and data structures for [[memory management]].

=== Processing primitive data ===
An abstract machine must contain operations for manipulating primitive data types such as strings and integers.<ref name=":3" /> For example, integers are nearly universally considered a basic data type for both physical abstract machines and the abstract machines used by many [[Programming language|programming languages]]. The machine carries out the [[Arithmetic|arithmetic operations]] necessary, such as addition and multiplication, within a single time step.<ref>{{Cite web |last=baeldung |date=2018-01-11 |title=Introduction to Java Primitives {{!}} Baeldung |url=https://www.baeldung.com/java-primitives |access-date=2022-05-31 |website=www.baeldung.com |language=en-US}}</ref>

=== Sequence control ===
Operations and structures for "sequence control" allow controlling the [[execution (computing)|execution flow]] of program instructions. When certain [[Conditional (computer programming)|conditions]] are met, it is necessary to change the typical sequential execution of a program.<ref name=":3" /> Therefore, the [[interpreter (computing)|interpreter]] employs data structures (such as those used to store the [[Address (programming language)|address]] of the next instruction to execute) that are modified by operations distinct from those used for data manipulation (for example, operations to update the address of the next instruction to execute).<ref>{{Citation |title=Interpreter |date=2004 |work=Software Architecture Design Patterns in Java |publisher=Auerbach Publications |doi=10.1201/9780203496213 |isbn=978-0-8493-2142-9 |last1=Kuchana |first1=Partha }}</ref>

=== Controlling data transfers ===
Data transfer operations are used to control how operands and data are transported from [[Memory cell (computing)|memory]] to the interpreter and vice versa. These operations deal with the [[Stored-program computer|store]] and the retrieval order of operands from the store.<ref name=":3" />

=== Memory management ===
[[Memory management]] is concerned with the operations performed in memory to allocate data and applications. In the abstract machine, data and programmes can be held indefinitely, or in the case of programming languages, memory can be allocated or deallocated using a more complex mechanism.<ref name=":3" />

== Hierarchies ==
{{One source|section|date=January 2023}}
[[File:A_hierarchy_of_abstract_machines.png|thumb|A hierarchy of abstract machines]]
Abstract machine hierarchies are often employed, in which each machine uses the functionality of the level immediately below and adds additional functionality of its own to meet the level immediately above. A [[Computer hardware|hardware computer]], constructed with physical electronic devices, can be added at the most basic level. Above this level, the abstract [[Microcode|microprogrammed machine level]] may be introduced. The abstract machine supplied by the [[operating system]], which is implemented by a program written in [[Machine code|machine language]], is located immediately above (or directly above the [[Computer hardware|hardware]] if the [[firmware]] level is not there). On the one hand, the operating system extends the capability of the physical machine by providing higher-level primitives that are not available on the physical machine (for example, primitives that act on files). The [[Hypervisor|host machine]] is formed by the abstract machine given by the operating system, on which a [[high-level programming language]] is implemented using an [[Virtual machine|intermediary machine]], such as the Java Virtual machine and its byte code language. The level given by the abstract machine for the [[High-level programming language|high-level language]] (for example, Java) is not usually the final level of hierarchy. At this point, one or more applications that deliver additional services together may be introduced. A "web machine" level, for example, can be added to implement the functionalities necessary to handle Web communications ([[Communication protocol|communications protocols]] or [[HTML|HTML code presentation]]). The "[[Web service|Web Service]]" level is located above this, and it provides the functionalities necessary to make web services communicate, both in terms of interaction protocols and the behaviour of the processes involved. At this level, entirely new languages that specify the behaviour of so-called "business processes" based on Web services may be developed (an example is the [[Business Process Execution Language]]). Finally, a specialised application can be found at the highest level (for example, [[E-commerce]]) which has very specific and limited functionality.<ref name=":3" />

==See also==
* {{Annotated link|Abstract interpretation}}
* {{Annotated link|Bulk synchronous parallel}}
* {{Annotated link|Discrete time}}
* {{Annotated link|Flynn's taxonomy}} 
* {{Annotated link|Computability#Formal models of computation|Formal models of computation}}
* {{Annotated link|Model of computation}}
* {{Annotated link|Parallel random-access machine}}, the de facto standard model
* {{Annotated link|SECD machine}}
* {{Annotated link|State space}}

==References==
<references />

==Further reading==
*Peter van Emde Boas, ''Machine Models and Simulations'' pp.&nbsp;3–66, appearing in:
::[[Jan van Leeuwen]], ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', The MIT PRESS/Elsevier, 1990. {{ISBN|0-444-88071-2}} (volume A). QA 76.H279 1990''
* Stephan Diehl, Pieter Hartel and Peter Sestoft, [http://www.inf.ed.ac.uk/teaching/courses/lsi/diehl_abstract_machines.pdf ''Abstract Machines for Programming Language Implementation''], Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.
* {{cite book|author=Werner Kluge|title=Abstract Computing Machines: A Lambda Calculus Perspective|year=2006|publisher=Springer|isbn=978-3-540-27359-2}}

{{Authority control}}

{{DEFAULTSORT:Abstract Machine}}
[[Category:Abstract machines| ]]
[[Category:Automata (computation)]]
[[Category:Models of computation]]