The primitive concepts of a computer

The most effective way to impart knowledge to someone else is to express it using concepts he or she is familiar with. The same method applies to computers.

Our goal since our last lecture has been to give computers a full comprehension of the abstract syntax of the Empathy Canvas. We have prepared for them a detailed description thereof, but they will be unable to understand it if they have no notion of what booleans, integers, reals, and strings are. In this post, we are going to see that they do know these concepts.

Physical computers

The main function of a computer is to make good use of every piece of information it gets its hands on through its input peripheral devices (Figure 1). For example, the text that is being typed on the keyboard (Figure 1), movements of the mouse (Figure 1), sounds being picked up by the microphone, and the video that the web camera is capturing.

All this information flows towards the processor (Figure 1), which takes care of it.

The processor, however, does not decide itself what to do with it. It merely waits for the user to choose some software, programs, and applications (these terms are synonymous) to run (by clicking for example on their icons); indeed, the programmers who developed them have left therein the instructions it has to follow.

The program being executed by the processor—and which has thus temporary control of it—will at some point (otherwise it would serve no purpose) make the latter transmit this information, or some new information computed from it, to one of the output or input/output computer peripherals, such as a monitor to display it (Figure 1), a loudspeaker to create sounds out of it (Figure 1), a printer to print it on a sheet of paper, a modem to share it on the internet (Figure 1), or a hard disk drive to save it in a safe place (Figure 1).

What differentiates an input peripheral from an output one is the direction of information flow between them and the processor (Figure 1): to the processor—and the program it is running—an input peripheral is an information source (Figure 1), whereas an output peripheral is an information receiver (Figure 1). An input/output peripheral is both an input and an output peripheral at the same time, i.e. it not only provides the processor with information but also receives information from it (Figure 1).

As shown in Figure 1, the processor does not directly communicate with peripheral devices because this would require it to know their respective specificities. It delegates this task to controllers (Figure 1), each controller being specially designed to cope with a specific type of peripheral (Figure 1).

The processor is not the only essential component of the computer; there is another one: the memory (Figure 1): the storage space where the processor and, more precisely, the programs that are given control of it, temporarily hold the information with which they are working. They prefer it over the hard disk drive because it is much easier and faster to access (Figure 1).

But these advantages come with two downsides: the available space is (1) significantly smaller and (2) volatile, in the sense that as soon as a program terminates (for example, because it has no more instructions to execute, an error has occurred, or the user has decided to stop it), all the information it has stored into the memory is automatically “cleaned”, i.e. deleted. If it has not transferred it to the hard disk drive or an equivalent non-volatile device, it is permanently lost.

From all that we have just said, a programmer, or at least every person who aspires to become one, needs to remember the following points:

• Programming is giving instructions to the processor; a program is a sequence of instructions.
• When the user of the computer starts our program, he or she de facto gives us temporary control of the processor. As a result:
  • we benefit from all its computing power;
  • information obtained by input peripherals is routed to us through controllers;
  • through these, we can additionally send information to output peripherals;
  • the memory is at our disposal for easy and fast information storage, but things we write into it will be ultimately lost if we forget to also save them into a non-volatile device like the hard disk drive.

The memory consists of numbered cells (Figure 2). The number assigned to a cell is called its address because it enables programs to know where to retrieve information (Tanembaum, 2006, p. 70).

A concept is primitive for a computer if each cell of its memory can contain an instance thereof.

The different devices composing a computer (Figure 1) exchange information by sending signals to each other. They communicate using solely two signals known as bits: the signal 0 and the signal 1. The green arrows in Figure 1 represent flows of 0 and 1; the memory is tasked with recording sequences of 0 and 1.

The longest sequences of bits able to fit into a memory cell are referred to as bytes. At one time, the byte size (the number of bits per cell) varied from one computer to another (Table 3). But nowadays, all computers have eight-bit memory cells (Figure 4).

Computer	Release date	Byte size
Honeywell 6180	1963	36
CDC 3600	1963	48
Electrologica X8	1964	27
DEC PDP-8	1965	12
IBM 1130	1965	16
SDS 940	1966	24
CDC Cyber 70	1970–1980	60
DEC PDP-15	1970	18
XDS Sigma 9	1971	32
Burroughs B1700	≈1972	1
IBM PC	1981	8

Because the sequence of eight bits became the standard byte size, it was given a name: the octet. And since the primitive concepts of a computer are those whose instances can be placed into a cell of its memory, then we must acknowledge that the octet is the only primitive concept of contemporary computers.

Virtual computers

Yet, modern programming languages give the impression that computers are inherently proficient with booleans, integers, reals, and strings. Take a look at the instructions below. They are addressed to the processor in JavaScript (one of the languages we will learn):

let cell1;
cell1 = 2020;
cell1 = "Voilà!";
cell1 = false;

let cell2 = 3.14;
cell2 = true;

Code Fragment 5—Example of a JavaScript program.

These instructions ask the processor to perform the following actions:

1. reserve a cell somewhere in the memory, at an indeterminate address, and let cell1 be its name for future reference (line 1, Figure 6.1);
2. put into this cell the integer 2020 (line 2, Figure 6.2);
3. replace its content consecutively with the string "Voilà!" (line 3, Figure 6.3) and the boolean false (line 4, Figure 6.4);
4. reserve another cell somewhere in the memory, at an indeterminate address distinct from that of cell1, initialise it with the real 3.14, and let cell2 be its name for future reference (line 6, Figure 6.5);
5. replace this 3.14 with the boolean true (line 7, Figure 6.6).

Think one second about this program. In the previous section, we established that there cannot be anything other than an octet inside a memory cell. So what is going on here?

Well, there are several levels of programming languages.

The processor, for instance, has its own programming language: the machine language; a language where instructions are sequences of 0 and 1 (Code Fragment 7). It is the lowest-level programming language.

11100011101000000001011111100100
11100101100000000001000000000000

Code Fragment 7—Example of a program written in machine language.

When programming in machine language, we really have to manage eight-bit memory cells. An ARM Cortex-A7 MPCore processor (Photo 8) will, for example, decode Code Fragment 7 as being the order to write the four octets 00000000, 00000000, 00000111 and 11100100 in four adjacent memory cells, one octet per cell. Experts on the ARMv7-A architecture and its assembly language (Arm, 2018) will recognise the instructions mov r1, #2020 (Arm, 2018, p. 485) and str r1, [r0] (Arm, 2018, p. 675).

Machine language may differ from one processor to another: two processors do not necessarily interpret a piece of machine code the same way. No one can tell what the program in Code Fragment 7 is supposed to do if the identity of the processor that will run it is not indicated.

Processor manufacturers have chosen to support machine language because it simplifies greatly their work: to read it their products only have to differentiate electronically the signal 0 from the signal 1. But at the same time, it complicates considerably the job of programmers. That is why they started to invent high-level programming languages like JavaScript. A programming language L is of a higher level than a programming language P if, by using L, programmers no longer need to worry about certain programming constraints imposed by P.

A higher-level language generally presents the computer under a new face: it changes our perception of its processor, memory, or peripherals in order to make them more programmer-friendly. The distorted but practical view it gives us of them is described as virtual (Tanembaum, 2006, p. 3), as opposed to the less pleasant reality of physical computers.

For example, thanks to JavaScript we can forget physical computers and their one-octet memory cells (Figure 4), and program instead a virtual computer where booleans, integers, reals, and strings are primitive concepts (Code Fragment 5, Figure 6).

To keep our programs executable by physical computers, JavaScript will explain to them for us in machine language (Code Fragment 7) the meaning of each high-level instructions they contain (Code Fragment 5, Figure 6), and meanwhile encode—i.e. convert—into octets (Figure 4) all the high-level concepts they refer to (Code Fragment 5, Figure 6).

It is the existence of virtual computers, like the one of JavaScript, where booleans, integers, reals, and strings are available, that allows us to say that computers know these concepts.

In the next three posts, we will study the most prevalent techniques for encoding booleans, integers, reals, and strings; in particular those used by JavaScript. I must warn you that we will have to do a little math, so please make sure you have a calculator. Stay tuned!

Questions

Why did the octet become the standard byte size?

Quotations

There is a large gap between what is convenient for people and what is convenient for computers. People want to do X, but computers can only do Y. This leads to a problem. […]

The problem can be attacked in two ways: both involve designing a new set of instructions that is more convenient for people to use than the set of built-in machine instructions. Taken together, these new instructions also form a language, which we will call L1, just as the built-in machine instructions form a language, which we will call L0. The two approaches differ in the way programs written in L1 are executed by the computer, which, after all, can only execute programs written in its machine language, L0.

One method of executing a program written in L1 is first to replace each instruction in it by an equivalent sequence of instructions in L0. The resulting program consists entirely of L0 instructions. The computer then executes the new L0 program instead of the old L1 program. This technique is called translation.

The other technique is to write a program in L0 that takes programs in L1 as input data and carries them out by examining each instruction in turn and executing the equivalent sequence of L0 instructions directly. This technique does not require first generating a new program in L0. It is called interpretation and the program that carries it out is called an interpreter.

Translation and interpretation are similar. In both methods, the computer carries out instructions in L1 by executing equivalent sequences of instructions in L0. The difference is that, in translation, the entire L1 program is first converted to an L0 program, the L1 program is thrown away, and then the new L0 program is loaded into the computer’s memory and executed. During execution, the newly generated L0 program is running and in control of the computer.

In interpretation, after each L1 instruction is examined and decoded, it is carried out immediately. No translated program is generated. Here, the interpreter is in control of the computer. To it, the L1 program is just data. Both methods, and increasingly, a combination of the two, are widely used.

Rather than thinking in terms of translation or interpretation, it is often simpler to imagine the existence of a hypothetical computer or virtual machine whose machine language is L1. […] If such a machine could be constructed cheaply enough, there would be no need for having language L0 or a machine that executed programs in L0 at all. People could simply write their programs in L1 and have the computer execute them directly. Even if the virtual machine whose language is L1 is too expensive or complicated to construct out of electronic circuits, people can still write programs for it. These programs can either be interpreted or translated by a program written in L0 that itself can be directly executed by the existing computer. In other words, people can write programs for virtual machines, just as though they really existed.

To make translation or interpretation practical, the languages L0 and L1 must not be “too” different. This constraint often means that L1, although better than L0, will still be far from ideal for most applications. This result is perhaps discouraging in light of the original purpose for creating L1—relieving the programmer of the burden of having to express algorithms in a language more suited to machines than people. However, the situation is not hopeless.

The obvious approach is to invent still another set of instructions that is more people-oriented and less machine-oriented than L1. This third set also forms a language, which we will call L2 […]. People can write programs in L2 just as though a virtual machine with L2 as its machine language really existed. Such programs can either be translated to L1 or executed by an interpreter written in L1.

The invention of a whole series of languages, each one more convenient than its predecessors, can go on indefinitely until a suitable one is finally achieved.

Bibliography

Photographic credits