Abstract machine

An abstract machine is a simple idea that helps us learn about how computers work. It is like a list of rules that explains what a computer can do and how it does it, without thinking about the real parts inside the computer.

Abstract machines are special because they only care about the steps a computer takes to run programs. They ignore things like the actual chips or wires. They are like a plan that shows the basic idea of how a computer works. This makes it easier to study and discuss computers clearly.

These machines are very useful in the theory of computation. They help scientists learn what computers can and cannot do, and how hard some tasks can be. Famous examples include finite state machines, Mealy machines, push-down automata, and Turing machines. Using abstract machines helps us understand what computers can do and their limits.

Classification

Abstract machines are sorted into two main types depending on how many tasks they can handle at once. The first type is called a deterministic abstract machine. This means that if you start with the same setting, the machine will always give you the same result.

The second type is a non-deterministic abstract machine. This type can give different results even if you start with the same setting. It can choose different paths to reach various answers.

One important example of an abstract machine is the Turing machine. It works on a long tape filled with symbols. It can change symbols and move along the tape.

Implementation

An abstract machine can be built using physical parts like memory, arithmetic, and logic circuits. This is called implementation in hardware. A CPU is a real example of this.

It can also be created using programs written in another language. This is called simulation using software. It is very flexible because the programs can be changed easily. When an abstract machine is made this way, it is called a virtual machine.

Another way is to use special microcode, which sits between hardware and software. This is called emulation using firmware. It lets programmers write instructions without building new electrical circuitry.

Programming language implementation

An abstract machine is a simple idea of a real computer. It helps us understand how computers run programs by using steps and rules set by the programming language. These machines have parts like memory and a special pointer that keeps track of where we are in the program.

Different types of programming languages use abstract machines in their own ways. For example, some machines help with objects and methods, while others focus on processing text. These machines make programs run faster and work on different computers. Examples include languages like Java and Prolog, each with its own special machine to help it work.

Structure

A generic abstract machine is made up of a memory and an interpreter. The memory stores data and programs. The interpreter runs the instructions in programs.

The interpreter does tasks that are special to the language it runs. But because there are many languages, we can group these tasks into categories that all interpreters share. The interpreter’s tasks and the data it uses are split into these groups:

1. Tasks for handling primitive data;
2. Tasks and data for controlling the order of execution of operations;
3. Tasks and data for managing data transfers;
4. Tasks and data for memory management.

An abstract machine needs tasks to work with basic data types like words and numbers. Numbers are a basic type for both real machines and many programming languages. The machine does math tasks, such as adding and multiplying, in one step.

Tasks for “sequence control” help manage the order of program steps. When certain conditions are met, the usual order of the program must change. The interpreter uses data (like the location of the next step to run) that changes with special tasks, not the usual data tasks.

Data transfer tasks control how information moves between memory and the interpreter. These tasks handle storing and getting data from memory.

Memory management deals with how data and programs are kept in memory. In an abstract machine, data and programs can stay forever, or for languages, memory can be given out and taken back using more detailed steps.

Hierarchies

Abstract machine hierarchies help us understand how computers work by stacking layers of functionality. At the bottom, we have the hardware computer, made from physical parts. Above this, we might add the microprogrammed machine level.

The operating system sits above, adding useful features not found in the hardware, like working with files. This creates a host machine where high-level programming language runs, often using an intermediary machine like the Java Virtual Machine.

Even higher, we can add layers for web use, like handling communications protocols or HTML code presentation. The "Web Service" layer helps web services talk to each other. At the top, special applications like E-commerce provide focused services.