Abstract machine

In computer science, an abstract machine is a theoretical model that helps us understand how computer systems work. Think of it like a set of rules that tells us exactly what a computer can do and how it does it, without worrying about the real parts inside the computer.

Abstract machines are special because they focus only on the steps a computer follows to run programs, ignoring things like the actual chips or wires. They are like a blueprint that shows us the basic idea behind a computer’s work. This makes it easier to study and talk about computers in a clear and exact way.

These machines are very important in the theory of computation. They help scientists explore what computers can and cannot do, and how complicated certain tasks might be. Famous examples include finite state machines, Mealy machines, push-down automata, and Turing machines. By using abstract machines, we can better understand the limits and power of computing.

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. There is no surprise or change in how it works.

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, which is useful when finding an exact answer is hard or takes too much time.

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. A simple Turing machine might have one rule, like "change a symbol to 1 and move right," and it would only create a string of 1s. This basic Turing machine is deterministic, but more complex ones can do many actions with the same input.

Implementation

An abstract machine can be created using physical devices like memory, arithmetic, and logic circuits. This is called implementation in hardware. Think of a CPU as a real example of this idea.

It can also be made 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 like 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 is used to store data and programs, while the interpreter is the part that runs the instructions in programs.

The interpreter does tasks that are special to the language it is running. 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. For example, numbers are a basic type for both real machines and the ones used by 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. So, 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.