Abstract 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. It is similar to a 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. Abstract machines are "machines" because they allow step-by-step execution of programs; they are "abstract" because they ignore many aspects of actual machines. 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. In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyse the complexity of algorithms. This use of abstract machines is fundamental to the field of computational complexity theory, such as with finite state machines, Mealy machines, push-down automata, and Turing machines.
Classification
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 and non-deterministic abstract machines. 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. In contrast, a non-deterministic abstract machine can provide various outputs for the same input on different executions. 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 at different outputs. Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.Turing machines, for example, are some of the most fundamental abstract machines in computer science. These machines conduct operations on a tape 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. This basic Turing machine is deterministic; however, nondeterministic Turing machines that can execute several actions given the same input may also be built.
Implementation
Any implementation of an abstract machine in the case of physical implementation uses some kind of physical device 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.- 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. A CPU may be thought of as a concrete hardware realisation of an abstract machine, particularly the processor's design.
- 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. An abstract machine implemented as a software simulation, or for which an interpreter exists, is called a virtual machine.
- Emulation using firmware: Firmware implementation sits between hardware and software implementation. It consists of microcode simulations of data structures and algorithms for abstract machines. Microcode allows a computer programmer to write machine instructions without needing to fabricate electrical circuitry.
Programming language implementation
Imperative languages
In the late 1950s, the Association for Computing Machinery and other allied organisations developed many proposals for Universal Computer Oriented Language, such as 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 in the late 1990s. Algol Object Code, P4-machine, UCSD P-machine, and Forth are some successful abstract machines of this kind.Object-oriented languages
Abstract machines for object-oriented programming languages are often stack-based and have special access instructions for object fields and methods. In these machines, memory management is often implicit performed by a garbage collector. Smalltalk-80, Self, and Java are examples of this implementation.String processing languages
A 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 command shells, programming tools, macro processors, and scripting languages for decades. Using a suitable abstract machine has two benefits: increased execution speed and enhanced portability. Snobol4 and ML/I are two notable instances of early string processing languages that use an abstract machine to gain machine independence.Functional programming languages
The early abstract machines for functional languages, including the SECD machine and Cardelli's Functional Abstract Machine, defined strict evaluation, also known as eager or call-by-value evaluation, in which function arguments are evaluated before the call and precisely once. Recently, the majority of research has been on lazy evaluation, such as the G-machine, Krivine machine, and Three Instruction Machine, 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.Logical languages
is the foundation of 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 WAM, 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.Structure
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.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:
- Operations for processing primitive data:
- Operations and data structures for controlling the sequence of execution of operations;
- Operations and data structures for controlling data transfers;
- Operations and data structures for memory management.
Processing primitive data