Incomputer science, anabstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions.[1] It is similar to amathematical 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 ofhardware.[2] Abstract machines are "machines" because they allow step-by-step execution ofprograms; they are "abstract" because they ignore many aspects of actual (hardware) machines.[3] 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.[2] In thetheory of computation, abstract machines are often used inthought experiments regardingcomputability or to analyse the complexity ofalgorithms.[3] This use of abstract machines is fundamental to the field ofcomputational complexity theory, such as withfinite state machines,Mealy machines,push-down automata, andTuring machines.[4]
Abstract machines are typically categorized into two types based on the quantity of operations they can execute simultaneously at any given moment:deterministic abstract machines andnon-deterministic abstract machines.[2] Adeterministic 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.[5] In contrast, anon-deterministic abstract machine can provide various outputs for the same input on different executions.[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.[6] Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.[7]
Turing machines, for example, are some of the most fundamental abstract machines in computer science.[2] These machines conduct operations on atape (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.[8] This basic Turing machine is deterministic; however,nondeterministic Turing machines that can execute several actions given the same input may also be built.[2]
Any implementation of an abstract machine in the case of physical implementation (inhardware) uses some kind of physical device (mechanical or electronic) to execute the instructions of aprogramming language. An abstract machine, however, can also be implemented insoftware orfirmware at levels between the abstract machine and underlying physical device.[9]
An abstract machine is, intuitively, just anabstraction of the idea of a physical computer.[13] For actual execution,algorithms must be properly formalised using the constructs offered by aprogramming language. This implies that the algorithms to be executed must be expressed using programming language instructions.[3] Thesyntax of a programming language enables the construction ofprograms using a finite set of constructs known as instructions. Most abstract machines sharea program store anda state, which often includesa stack and registers.[9][14] In digital computers, the stack is simply amemory 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 asa stack pointer because its value always refers to the top item on the stack.[15] The program consists of a series of instructions, witha stack pointer indicating the next instruction to be performed. When the instruction is completed,a stack pointer is advanced. This fundamental control mechanism of an abstract machine is also known as itsexecution loop.[3] Thus, an abstract machine for a programming language is any collection ofdata structures and algorithms capable of storing and running programs written in the programming language. It bridges the gap between thehigh level of a programming language and thelow level of an actual machine by providing an intermediate language step forcompilation. 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.[9]
In the late 1950s, theAssociation for Computing Machinery (ACM) and other allied organisations developed many proposals forUniversal Computer Oriented Language (UNCOL), such asConway's machine. The UNCOL concept is good, but it has not been widely used due to the poor performance of the generatedcode. In many areas of computing, its performance will continue to be an issue despite the development of theJava Virtual Machine in the late 1990s.Algol Object Code (1964), P4-machine (1976),UCSD P-machine (1977), andForth (1970) are some successful abstract machines of this kind.[3]
Abstract machines forobject-oriented programming languages are oftenstack-based and have special access instructions forobject fields andmethods. In these machines,memory management is often implicit performed by agarbage collector (memory recovery feature built into programming languages).[16]Smalltalk-80 (1980),Self (1989), andJava (1994) are examples of this implementation.[3]
Astring processing language is a computer language that focuses on processing strings rather than numbers. There have been string processing languages in the form ofcommand shells,programming tools,macro processors, andscripting languages for decades.[17] Using a suitable abstract machine has two benefits: increasedexecution speed and enhanced portability.Snobol4 andML/I are two notable instances of early string processing languages that use an abstract machine to gain machine independence.[3]
The early abstract machines forfunctional languages, including theSECD machine (1964) and Cardelli's Functional Abstract Machine (1983), defined strict evaluation, also known aseager or call-by-value evaluation,[3] in which function arguments are evaluated before the call and precisely once. Recently, the majority of research has been onlazy (or call-by-need) evaluation,[18] 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.[3]
Predicate calculus (first order logic) is the foundation oflogic programming languages. The most well-known logic programming language isProlog.[citation needed] 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. TheWarren Abstract Machine WAM (1983),[3] 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).[19]
A generic abstract machine is made up of amemory and aninterpreter. The memory is used to store data and programs, while the interpreter is the component that executes the instructions included in programs.[9]
The interpreter must carry out the operations that are unique to thelanguage it is interpreting. However, given the variety of languages, it is conceivable to identify categories of operations and an "execution mechanism" shared by all interpreters. The interpreter's operations and accompanying data structures are divided into the following categories:[9][20]
An abstract machine must contain operations for manipulating primitive data types such as strings and integers.[9] For example, integers are nearly universally considered a basic data type for both physical abstract machines and the abstract machines used by manyprogramming languages. The machine carries out thearithmetic operations necessary, such as addition and multiplication, within a single time step.[21]
Operations and structures for "sequence control" allow controlling theexecution flow of program instructions. When certainconditions are met, it is necessary to change the typical sequential execution of a program.[9] Therefore, theinterpreter employs data structures (such as those used to store theaddress 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).[22]
Data transfer operations are used to control how operands and data are transported frommemory to the interpreter and vice versa. These operations deal with thestore and the retrieval order of operands from the store.[9]
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.[9]
 | This sectionrelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Abstract machine" – news ·newspapers ·books ·scholar ·JSTOR(January 2023) |
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. Ahardware computer, constructed with physical electronic devices, can be added at the most basic level. Above this level, the abstractmicroprogrammed machine level may be introduced. The abstract machine supplied by theoperating system, which is implemented by a program written inmachine language, is located immediately above (or directly above thehardware if thefirmware 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). Thehost machine is formed by the abstract machine given by the operating system, on which ahigh-level programming language is implemented using anintermediary machine, such as the Java Virtual machine and its byte code language. The level given by the abstract machine for thehigh-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 (communications protocols orHTML code presentation). The "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 theBusiness 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.[9]