Abstract machine

Abstract machines are generally classified into two types depending on the number of operations they are allowed to undertake at any one time: deterministic abstract machines and non-deterministic abstract machines.[2] A 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.[5] Meanwhile, a non-deterministic abstract machine can provide various outputs for the same input on different executions.[2] In contrast to 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]

A run of a Turing machine.

The Turing machine, for example, is one of the most fundamental abstract machines in computer science.[2] This is a machine that can conduct operations on a tape (a string of symbols) of any length. It includes instructions for both modifying the symbols and changing the symbol that it is based on. The single command on a rudimentary Turing computer would be "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 (in hardware) use some kind of physical device (mechanical, electronic, etc) to execute the instructions of a programming language. Abstract machine however can also be implemented in software or firmware at levels intermediate the abstract machine and underlying physical device.[9]

• Implementation in Hardware: The direct implementation of abstract machine in hardware is a matter of using physical devices such as memory, arithmetic and 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.[9] A computer processor (CPU) may be thought of as a concrete hardware realisation of an abstract machine, particularly the processor's design.[10]

• Simulation Using Software: Implementing an abstract machine with software entails writing programmes in a different language to implement the data structures and algorithms needed by the abstract machine. This provides the most flexibility since programmes implementing abstract machine constructs can be easily changed.[9] An abstract machine implemented as a software simulation, or for which an interpreter exists, is called a virtual machine.[11]

• Emulation Using Firmware: Firmware implementation sits between hardware and software implementation. It consists of microcode simulations of data structures and algorithms for abstract machines.[9] Microcode allows a computer programmer to write machine instructions without needing to fabricate electrical circuitry.[12]

The term "machine" refers to a computing machine, which is a physical machine that executes algorithms that have been sufficiently formalised for the machine to "understand". An abstract machine is, intuitively, nothing more than an abstraction of the idea of a physical computer.[13] For actual execution, algorithms 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.[3] The syntax of a programming language enables the construction of programs using a finite set of constructs known as instructions. Most abstract machines share a program store and a state, which often includes a stack and registers.[9][14] In digital computers, the stack is simply a 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 a stack pointer because its value always refers to the top item on the stack.[15] The program consists of a series of instructions, with a 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 its execution loop.[3] Thus, an abstract machine for programming language is any collection of data structures and algorithms capable of storing and running programs written in the programming language. It bridges the gap between the high level of a programming language and the low level of an actual machine by providing an intermediate language step for 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.[9]

Functional Programming Languages

Pictorial representation of a Krivine machine.

The early abstract machines for functional languages, including the SECD machine (1964) and Cardelli's Functional Abstract Machine (1983), defined strict evaluation, also known as eager or call-by-value evaluation,[3] in which function arguments are evaluated before to the call and precisely once. In recent years, the majority of research has been on lazy (or call-by-need) evaluation,[19] 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]

A generic abstract machine is made up of a memory and an interpreter. The memory is used to store data and programs, while the interpreter is the component that executes the instructions included in programs.[9]

The structure of an abstract machine

The interpreter must carry out the operations that are unique to the language 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][21]

1. Operations for processing primitive data:
2. Operations and data structures for controlling the sequence of execution of operations;
3. Operations and data structures for controlling data transfers;
4. Operations and data structures for memory management.

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.[9] A hardware computer, constructed with physical electronic devices, can be added at the most basic level. Above this level, the abstract microprogrammed machine level may be introduced. The abstract machine supplied by the operating system, which is implemented by program written in machine language, is located immediately above (or directly above the hardware if the firmware level is not there).[9][24] 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 host machine is formed by the abstract machine given by the operating system, on which a high-level programming language is implemented using an intermediary machine, such as the Java Virtual machine and its bytecode language.[16][25] The level given by the abstract machine for the 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 (communications protocols or HTML 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.[26] 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.[9]

• Abstraction (computer science)
• Abstract interpretation
• Bulk synchronous parallel
• Discrete time
• Finite-state machine
• Flynn's taxonomy
• Formal models of computation
• Krivine machine
• Model of computation
• Parallel random-access machine, the de facto standard model.[27]
• SECD machine
• State space
• Turing machine

• Peter van Emde Boas, Machine Models and Simulations pp. 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, Abstract Machines for Programming Language Implementation, Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.
• Werner Kluge (2006). Abstract Computing Machines: A Lambda Calculus Perspective. Springer. ISBN 978-3-540-27359-2.