An abstract machine is a

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

theoretical model that allows for a detailed and precise analysis of how a

computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations ( computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...

system functions. It is analogous 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 “

machine A machine is a physical system using power to apply forces and control movement to perform an action. The term is commonly applied to artificial devices, such as those employing engines or motors, but also to natural biological macromolecul ...

s” because they allow step-by-step execution of programmes; they are “ abstract” because they ignore many aspects of actual ( hardware) 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 A thought experiment is a hypothetical situation in which a hypothesis, theory, or principle is laid out for the purpose of thinking through its consequences. History The ancient Greek ''deiknymi'' (), or thought experiment, "was the most anci ...

regarding

computability Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clo ...

or to analyse the complexity of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s. This use of abstract machines is connected to the field of

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, such as

finite state machines A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...

, Mealy machines, push-down automata, and Turing machines. __FORCETOC__

Classification

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. A

deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and cons ...

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. Meanwhile, a non-deterministic abstract machine can provide various outputs for the same input on different executions. 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. Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly. 2-state 3-symbol Turing Machine

The

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...

, for example, is one of the most fundamental abstract machines in computer science. 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. This basic Turing machine is deterministic, however

nondeterministic Turing machines In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

that can execute several actions given the same input may also be built.

Implementation of an Abstract Machine

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 A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

. Abstract machine however can also be implemented in

software Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work. At the lowest programming level, executable code consist ...

firmware In computing, firmware is a specific class of computer software that provides the low-level control for a device's specific hardware. Firmware, such as the BIOS of a personal computer, may contain basic functions of a device, and may provide h ...

at levels intermediate 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 Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remember ...

arithmetic Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...

and logic circuits, buses, etc., to implement a physical machine whose machine language coincides with the

. Once constructed, it would be virtually hard to change such a machine. A computer processor (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 Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...

to implement the

data structures In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, ...

and

algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

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 In computing, a virtual machine (VM) is the virtualization/ emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized h ...

. * Emulation Using Firmware: Firmware implementation sits between hardware and software implementation. It consists of

microcode In processor design, microcode (μcode) is a technique that interposes a layer of computer organization between the central processing unit (CPU) hardware and the programmer-visible instruction set architecture of a computer. Microcode is a la ...

simulations of

and

for abstract machines.

Microcode In processor design, microcode (μcode) is a technique that interposes a layer of computer organization between the central processing unit (CPU) hardware and the programmer-visible instruction set architecture of a computer. Microcode is a la ...

allows a computer programmer to write machine instructions without needing to fabricate electrical circuitry.

Programming Language Implementation

The term "

" 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 Abstraction in its main sense is a conceptual process wherein general rules and concepts are derived from the usage and classification of specific examples, literal ("real" or " concrete") signifiers, first principles, or other methods. "An abst ...

of the idea of a physical computer. For actual execution,

s must be properly formalised using the constructs offered by a

. This implies that the algorithms to be executed must be expressed using programming language instructions. The syntax of a programming language enables the construction of

programs Program, programme, programmer, or programming may refer to: Business and management * Program management, the process of managing several related projects * Time management * Program, a part of planning Arts and entertainment Audio * Progra ...

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. 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. 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. Thus, an abstract machine for programming language is any collection of

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, ...

s 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.

Imperative Programming Languages

In the late 1950s, the Association for Computing Machinery (ACM) and other allied organisations developed many proposals for Universal Computer Oriented Language (UNCOL), 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 communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communicati ...

. In many areas of computing, its performance will continue to be an issue despite the development of the

Java Virtual Machine A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally describe ...

in the late 1990s. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977), and

Forth Forth or FORTH may refer to: Arts and entertainment * ''forth'' magazine, an Internet magazine * ''Forth'' (album), by The Verve, 2008 * ''Forth'', a 2011 album by Proto-Kaw * Radio Forth, a group of independent local radio stations in Scotla ...

(1970) are some successful abstract machines of this kind.

Object-oriented Programming Languages

Abstract machines for object-oriented programming languages are often

stack-based Stack-oriented programming, is a programming paradigm which relies on a stack machine model for passing parameters. Stack-oriented languages operate on one or more stacks, each of which may serve a different purpose. Programming constructs i ...

and have special access instructions for object fields and

methods Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...

. In these machines, memory management is often implicit performed by a

garbage collector A waste collector, also known as a garbageman, garbage collector, trashman (in the US), binman or (rarely) dustman (in the UK), is a person employed by a public or private enterprise to collect and dispose of municipal solid waste (refuse) and ...

(memory recovery feature built into programming languages). Smalltalk-80 (1980),

Self The self is an individual as the object of that individual’s own reflective consciousness. Since the ''self'' is a reference by a subject to the same subject, this reference is necessarily subjective. The sense of having a self—or ''selfhoo ...

(1989), and

Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...

(1994) 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 In computing, a shell is a computer program that exposes an operating system's services to a human user or other programs. In general, operating system shells use either a command-line interface (CLI) or graphical user interface (GUI), depend ...

, 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 (1964) and Cardelli's Functional Abstract Machine (1983), defined strict evaluation, also known as eager or call-by-value evaluation, 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, 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.

Logic Programming Languages

Predicate calculus (first order logic) is the foundation of

logic programming languages Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...

. 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 (1983), 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).

Structure of an Abstract Machine

A generic abstract machine is made up of a

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_structure_of_an_abstract_machine

The interpreter must carry out the operations that are unique to the

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.

Operations for processing primitive data

Even an abstract machine operates by executing algorithms, therefore it must contain operations for manipulating primitive data types such as strings and integers. For example, integers (integer or real) are nearly universally considered basic data for both physical abstract machines and the abstract machines used by many

programming languages A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

. The machine immediately does the different arithmetic operations necessary (addition, multiplication, etc.).

Operations and data structures for sequence control

Operations and structures for "sequence control" allow controlling the execution flow of program instructions. When certain conditions are met, it is necessary to change the typical sequential execution of a program. Therefore, the interpreter employs data structures (such as those used to store the 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).

Operations and data structures for controlling data transfers

Data transfer operations are used to control how operands and data are transported from

to the interpreter and vice versa. These operations deal with the store and the retrieval order of operands from the store.

Operations and data structures for 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.

Hierarchies 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 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 An operating system (OS) is system software that manages computer hardware, software resources, and provides common daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for ef ...

, which is implemented by program written in

machine language In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a ver ...

, is located immediately above (or directly above the hardware if the

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 host machine is formed by the abstract machine given by the operating system, on which a

high-level programming language In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to u ...

is implemented using an intermediary machine, such as the Java Virtual machine and its bytecode language. 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. 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 The Web Services Business Process Execution Language (WS-BPEL), commonly known as BPEL (Business Process Execution Language), is an OASIS standard executable language for specifying actions within business processes with web services. Process ...

). Finally, a specialised application can be found at the highest level (for example,

E-commerce E-commerce (electronic commerce) is the activity of electronically buying or selling of products on online services or over the Internet. E-commerce draws on technologies such as mobile commerce, electronic funds transfer, supply chain manag ...

) which has very specific and limited functionality.