Andreas Bærentzen (ver. 2.5, September 2022)
Prompt to Diffusion Bee:
"powerful computer in the style of Lichtenstein"
It is clearly possible to write computer programs without knowing anything about computers. However, this text is based on the belief that the resulting computer program is going to be much better if the programmer has some idea about how the computer works. Unfortunately, describing all aspects of a modern computer right down to the electronics is a very tall order that would require an entire book (e.g. Petzold's book [1]). Since this is a much shorter text than a book, we will ignore electronics completely and focus on the basic principles of a computer. Moreover, to make these principles concrete we will describe them in terms of an example. In fact, this text is simply a description of the Super Simple Model Computer (SSMC).
To make the SSMC a bit more tangible, I made a simple simulator which is shown below. The program run by the SSMC computes powers of 2 and stops when it reaches 1024. For the time being this simulation may seem a little mysterious, and if you are wondering about the little arrow, it simply points to the instruction currently being executed, and in the following all the rest will be explained.
You may wonder if it is really worth your time to understand the workings of a computer that does not and will never exist? After all, the SSMC is a model computer, and any real computer you will be working with is surely different and much more advanced. This is true, but if you understand the SSMC, you also understand the machine on your desk (or in your pocket). Those computers are indeed much more advanced, but the basic principles are roughly the same.
At the highest level of abstraction, the SSMC (along with any other computer) consists of a central processing unit (CPU) and random access memory (RAM). In the following, we will refer to these two entities simply as the processor and the memory. The main goal of this text is to explain in very broad terms what these two things are and how they work together.
The figure below shows the relationship between processor and memory. At the most abstract level, the processor reads instructions and data from memory, executes the instructions, and then writes output back to memory. The "execution of the instructions" is where the computation happens.
The terminology is a little confusing when it comes to computer memory. Some would argue storage is a better word than memory since a computer does not remember in the human sense. On the other hand, the type of memory that is used in modern computers is Random Access Memory, or simply RAM, and since memory is part of that name, we will stick to that. Also, the word storage is broader and used, for instance, in "disk storage" and "tape storage".
We can think of computer memory as a list of cells, each of which may contain either a number or an instruction encoded as a number. Admittedly, the instructions might take up more space than a single number, but that is a detail which we will cheerfully ignore. However, it is very important that the cells are numbered and that we can access any cell in the memory simply by specifying its number. It is also important that it is equally fast to access any cell in the memory. In fact, that is the whole point of "random access", and it can be seen as the opposite of a storage system where you have to read through all of the preceding memory cells in order to get to the one you want.
It may be helpful to think of memory cells as the cells of a spreadsheet for readers who are familiar with spreadsheets such as Microsoft Excel. In a spreadsheet, we can also access a cell by specifying its row and column number, and each cell can contain either an instruction, a number, or something else. An even simpler way to understand computer memory is that each cell is like a box with a number on it. This number serves as a label and ensures that the processor can always find the box and either read the information inside it or replace it with new information.
In addition to the ordinary memory, which is outside of the processor, the processor also has a "short-term" memory. We identify cells in the short-term memory by letters, but otherwise they are similar to those of the long-term memory. We will assume that the SSMC has nine short-term cells labelled a, b, c, i, j, k, x, y, and z. We could make do with less, but it turns out to be convenient to have a generous amount of short-term memory.
To simplify things a bit, all computations are performed on the short-term memory in our SSMC, but since most of the data is going to be in the ordinary memory, we need a way to transfer from long-term to short-term and also the other way. Transferring between the two types of memory is done by the processor, and we will discuss the instructions for this in the next section.
Like any microprocessor, the SSMC processor simply works its way through the cells of the long-term memory (i.e. RAM) executing the instructions that it finds in each cell. To be precise, the processor starts at cell number 0, it executes the instruction found in that cell and then moves on to cell number 1, then cell number 2, and so on. Of course, it could be that the processor encounters a cell that does not contain an instruction. In this case it might fail or simply ignore the cell and move on. However, there are also instructions which change the "flow of execution". These instructions are crucial, and we will get to them in a moment, but first we will describe the instructions needed for memory transfer and arithmetic.
We can divide the instructions that are understood by the processor into three groups:
Very often, when instructions for a processor are described, three and four letter codes are used as the names of the instructions. We find this hard to understand, and instead we will write the instructions more or less like you might see in a high level programming language such as Python. However, in reality the instructions below are machine code, but that does not make them complicated. In fact, machine code instructions are typically much simpler than the instructions of a high level language, and here we have simplified things further, leaving out exotic instructions that are not essential to computation.
Memory Transfer
We need a way to refer to a specific cell in the memory of the SSMC. We will do so by writing memory[n] where n is the number of the cell that we wish to access. If you prefer to think of memory as a labelled box, n is the label.
With that in place, the following instruction tells the processor to transfer from long-term memory to short-term memory:
x = memory[n]
where, again, n is a number and x is the label of the cell in the processor's short-term memory. For instance, if n is 23, the instruction above tells the processor to move whatever is in cell 23 to x in the short-term memory. In place of n we could also have had one of the cells of the short-term memory, for instance i, and we could also transfer to another short-term cell. For example, y = memory[i] would also have been valid. The significant thing here is that the value of i is not known beforehand. Only when the program is actually running do we know what cell in memory, we move to y.
It is convenient to be able to assign a value directly to a short-term memory cell. In order to store 123 in the cell labelled x we simply write:
x = 123
Of course, this operation could also have been carried out by storing 123 in some memory cell, say 678, and then issuing the instruction x = memory[678].
We have seen how it is possible to transfer from long-term to short-term memory. We can also transfer the other way:
memory[n] = x
Before we describe other types of instructions, we will address three sources of potential confusion.
memory[n], looks like we are accessing entry n in a list, and x seems to be a variable. The similarity is intentional, and we can, indeed, think of short-term memory as variables and long-term memory as a list of numbers. The instructions look similar to high level programming language statements, but here they are instructions to the processor. The transfer of memory is carried out directly by the hardware of our hypothetical computer.memory[23] = x as numbers? While the details are complicated, the principle is simple. The instruction, memory[23] = x, can be described as "transfer contents of short-term memory cell x to long-term memory cell 23". Let us arbitrarily assume that the generic part of the instruction, i.e. "transfer contents of short-term memory cell to long-term memory cell", on its own is instruction number 17. That gives us an encoding of the instruction as a number, but we are still missing the two parameters 23 and x. Fortunately, 23 is clearly already a number, and we can assign a number to x; let us say that x is short-term memory cell 6. Now, we can encode the instruction with its parameters using just the three number 17, 23, 6. For a human being, memory[23] = x is much nicer to read than 17, 23, 6, but the processor would only understand the numerical encoding.x = memory[23] means that x is the same as memory[23], and all of a sudden, we are saying that it means store the value of memory[23] in x?! We agree that this usage of = is confusing, and we could have used another symbol. However, in computer programs, a single equal sign is almost always used to indicate that the right hand side is stored in the memory location indicated by the left hand side. This is called assignment, and by introducing the use of = for assignment already now, we hope to avoid confusion later as you learn about programming.Arithmetic
The SSMC can perform all of the four basic arithmetic instructions:
z = x + y
z = x - y
z = x * y
z = x / y
In the instructions above, the inputs, which we call operands, are always taken from x and y, and the output is stored in z. However, the SSMC is clever enough that you can use any cell in short-term memory as input or output for an arithmetic operation, for instance, z = a + i would be perfectly fine. You can also use numbers directly, and it is legal to assign back to the same short-term cell. For instance, to multiply a number by two, just write k = 2 * k.
There are no more mathematical instructions. This might seem surprising since there is a lot of mathematical functions that one might think we would need, but it turns out that with elementary school arithmetic, we can approximate the rest.
Flow Control
What is now needed are instructions that control the flow of execution. The following instruction changes the cell in memory where the processor reads its next instruction.
goto(m)
Normally, we would execute the instruction in cell n+1 after the instruction in cell n, but if cell number n contains the goto(m) instruction, the instruction in cell m is executed next.
Why would we want to jump like that? This might seem completely pointless, but the thing is that programmers hate to repeat code. If some bit of code for computing, say, the square root of a number is needed in a few different places, we can use the goto instruction to jump to the appropriate place from several other places in the program - rather than placing the same code in multiple groups of cells.
In fact, we can also use goto as a simple way to stop execution. Consider what would happen if we put goto(n) into cell number n? Clearly, the next cell whose instruction should be executed would then be n but we are in n already so we simply repeatedly visit the same cell. This is not very elegant, though, so let us add a halt instruction:
halt
The next instruction is also a goto statement, but this time it is conditional.
if x < y: goto(m)
This instruction means that if x is less than y, then we transfer execution to cell m. Otherwise, we continue with the instruction in the next cell as usual. Without this instruction the program would always follow the same flow of execution. With this instruction, we can let the data decide where the program goes next. It is a simple mechanism, but it turns out to be the essential ingredient of computing. As was the case for the arithmetic operations, we can use any of the short-term memory cells in the conditions of conditional goto statements, and we can also replace x or y with a specific number if needed.
You may wonder if less than is the only type of comparison we need? The answer is yes since we can use less than to perform other tests too. For instance, we can test for equality using two less than comparisons: if x < y is not true and y < x is also not true, then x must be equal to y. For convenience, though, we might add more comparisons to an actual processor.
That's it!
As noted, we only have the simple arithmetic instructions and not for instance square root, logarithm or other useful mathematical functions. Is there anything else we might have included but did not? Well, some readers may suggest that we also need instructions for input and output. Surely there is a display and a keyboard somewhere and a hard disk? That is very true, but input and output is not a part of the SSMC. The SSMC is blind, deaf, and mute. It has no way of communicating with the outside world. Simply put, communication is not essential to understanding basic computation, and we just assume that there is some other system that takes care of input and output.
Let us now consider a simple task. For instance, we might want to compute the sum of three pairs of numbers multiplied together. In the usual mathematical notation, we would write this operation in the following way,
where each pair of numbers, and , are multiplied and then added.
We can write x'es and y's as two vectors and . In this case, the answer is , but how would SSMC arrive at that?
The following program performs the computation. The output is then written to cell number 20. The simulator has also been adapted to this program, and you can see it running here. The source for the SSMC simulator may also be of interest and is available here.
Program: Sum of Products
00: a = 0
01: i = 0
02: j = 14
03: k = 17
04: x = memory[j]
05: y = memory[k]
06: z = x * y
07: a = a + z
08: i = i + 1
09: j = j + 1
10: k = k + 1
11: if i < 3: goto(4)
12: memory[20] = a
13: halt
14: 0.1
15: 0.8
16: 0.2
17: 0.9
18: 0.1
19: 0.1
20: 0
There are several things to note here. First of all, everything is in memory before the program starts. The instructions come first in lines 0 through 13, and the next six lines contain the input (the two lists of numbers), and finally cell 20 awaits the output. We are clearly seeing the contents of the memory before the program is executed since cell 20 contains 0!
Next, the program is surprisingly long. That is because the instructions that a processor understands are very simple. Each instruction does only a single thing whereas in a high level programming language, each line of code might result in quite a lot of computation. Moreover, we have to take care of every little thing. For instance, we cannot be sure what is in the short-term memory when the program starts, so we even have to explicitly assign 0 to a and i.
The following lines of Python code could have been used instead of the SSMC code above:
x = [0.1, 0.8, 0.2]
y = [0.9, 0.1, 0.1]
a = 0
for i in range(3):
a += x[i] * y[i]
See how the last line fetches a pair of numbers from the two lists and multiplies them together and adds the result to a. This looks much simpler because each line does a lot more work, but under the hood, the Python code is transformed to something similar to SSMC code.
The SSMC processor does not understand many instructions. The point is that it does not take many instructions for a processor to be able to perform any computation we could desire. Perhaps the best way to understand it is as follows: with the very simple instructions of the SSMC, we can simulate a more advanced machine. For instance, we could simulate a machine that knows how to compute cosine and sine and many other mathematical functions. With that more advanced machine, we could compute anything that we could do by hand with a pocket calculator.
The essential ingredient is the conditional goto statements. It might be surprising that this is so powerful, but giving the computer a way to decide what to do next is key to general computation. It is very analogous to the difference between a joy ride in an amusement park and a rail system where you can change tracks. The joy ride is always the same whereas a rail switch which allows you to change tracks can take you wherever you have laid down tracks.
We have explicitly said that we ignore input and output, but we ignore many more things as well. For instance, we ignore the important notions of an operating system which is basically the program that serves as a janitor, ensuring that the computer's resources are available to the program. We also ignore the problems that come with scaling up computation and especially parallelism. However, a parallel computer is not different except that it contains many processors and it requires a fair bit of engineering to ensure that they play nicely together. Moreover, it is much harder to write parallel programs because we have to think about several threads of execution and how they interact.
There are however, a few things that we should not ignore. The first is about memory. Modern processors are so fast that it often takes much longer to get information from memory than to execute an instruction. Fetching from disk or network is, of course, much slower still. The software engineer Colin Scott has made a visualization of the time it takes to access various types of memory.
To mitigate the issues with slow memory access, real-world computers have yet another form of memory called cache. The cache is just a copy of cells in the memory that we have used recently, and this copy is kept on the processor itself. We are likely to use those cells again in the near future, and keeping copies very close to the processor is a really good idea. Of course, this means that the cache also has to record not just the contents of the cached cells but also their numbers. Fortunately, we do not have to store the number of each individual cell, since cells are actually stored in the cache in contiguous chunks called cache lines. This means that we only need to record where in the long-term memory the cache line is from and not each individual cell. It is also great because if we have just used one cell, we are likely to use the next. Thus, the cache lines tend to contain not just information we have used but also cells we will use in the near future. Below is an image illustrating how the cache is wedged between processor and memory.
Note that physically the processor's cache is generally on the same chip as the processor itself. In fact, a large part of a modern CPU is cache.
The final thing that we should also briefly consider is about what sort of data that we can store in our computer's memory. The sad fact is that we can only store integers (meaning numbers such as 1, 2, 3, 4, ... ) in computer memory. This means that anything else has to be encoded as an integer. This also goes for instructions, and we have already discussed how an instruction can be encoded as a short list of numbers, and when we have many instructions, we simply string those numbers together in a much longer list. Unfortunately, this machine code is completely incomprehensible to human beings, but since the dawn of computers, engineers have assigned (usually three letter) alphabetical codes to each instruction. Replacing the numbers with these codes, we can turn machine code into assembly language which is also incomprehensible - except to assembly programmers. Hopefully, the SSMC code described in this text is just a bit less incomprehensible.
Moving on to other types of data than instructions, it is clear that we would often want to store text in a computer. If we want to store letters (characters) in computer memory, we also encode them by assigning a number to each letter. Maybe 'a' is 1, 'b' is 2 etc. Things get a bit harder when it comes to numbers with decimal places. How do we store a number such as 0.012 in a computer? the solution is simply to use exponential notation. Somewhat simplified, instead of 0.012, we store . This is called floating point number representation because we raise 10 to some power (in this case -3) which determines where the point (or comma) is placed. This system works well, and if we know that this encoding is used, we only need to store the numbers 12 and -3. The downside is that floating point numbers cannot represent any possible real or even rational number. To make matters worse, floating point numbers become less and less precise the further they are from zero.
Hopefully, it is now a little less unclear how a computer works. However, this text has only discussed computers on a very abstract level. We have not delved into the electronics that go into making a computer or the history of computers. Arguably, we need to know neither electronics nor the history of computers to program them, and the aim of this text is simply to provide a mental model of a computer for people who are in the process of learning computer programming. Nevertheless, some readers might be curious about the history of computers, electronics, or both, and we provide a few pointers to further reading in the following.
Making a machine that can perform basic arithmetic is difficult, but it does not require modern technology. The two great mathematicians Pascal and later Leibniz both made their own mechanical calculators, and there are many other examples, notably Charles Babbage's somewhat ill fated Difference Engine. More recently, the small Curta calculator was popular up until the middle of the 20th Century. It is also not the case that you have to use either mechanics or electronics for performing computation. Say you have two vials of fluid. Simply pouring the contents of both into a measurement beaker will give you the sum of the fluid volumes contained in the vials. Thus, using fluid we can perform addition very easily. This may sound silly, but in the early 20th Century Russian scientists developed a machine for integration based on fluid which was apparently in active use until the eighties.
However, allowing the machine to change tracks is something else. Before the 20th century, it seems that only Charles Babbage had even conceived of a machine that would be able to do that, but his Analytical Engine was never realized. Probably, the conditional goto (track changing) is difficult to do without electronics. However, the electrical relay provided a path, and in 1941 the german engineer Konrad Zuse created the Z3 which was the first true electronic computer. Actually, it did not have conditional goto but it was in theory possible to work around that. The successor, Z4, became the first commercially sold computer when it was delivered to the ETH in Zürich. To get a deeper understanding of how we can build a computer from simple electronics, Charles Petzold's book [1] is warmly recommended.
Konrad Zuse worked in Germany, but electronic computers were also being developed in the USA during the Second World War. Just like the German machine, the American computers were used to aid the war effort. The Hungarian mathematician, and by all accounts genius, John von Neumann had been one of the early users of these machines, and in 1945 he synthesized his understanding of the principles in the "First Draft of a Report on the EDVAC." Most "first draft reports" are not published, but when von Neumann's collaborator Herman Goldstine received the report he sent it to everyone who might be interested, and thus the principles of a modern computer became available to all who cared. These principles also became impossible to patent which made some people very unhappy. The unusual life of John von Neumann and his many contributions to science and math are discussed in Bhattacharya's book [2].
Grace Hopper is also an important figure in the history of computing. She worked in Howard Aiken's lab at Harvard as a programmer of the early Mark 1 computer which was electromechanical like Zuse's machine. Her contribution is mostly in recognizing how high level programming languages would make computer programming vastly more accessible to many people. Ultimately, her efforts led to the Cobol programming language whose success was so great that it is still in use despite being arguably outdated. Beyer's book [3] presents a very readable account of Hopper's life and work.
Finally, in his far ranging book, Roger Penrose describes (among many other things) the ideas of Alan Turing regarding computability in an accessible yet comprehensive format [4]. Turing proposed a very simple theoretical machine in order to shed light on the problem of what is computable in theory. Turing machines are very different from actual computers, but one way of showing that the SSMC can compute anything (that humans know how to compute) would be by showing that it can simulate a Turing machine.
Petzold, Charles. "Code: The hidden language of computer hardware and software." Microsoft Press, 2000.
Bhattacharya, Ananyo. "The Man from the Future: The Visionary Life of John von Neumann." Allen Lane, 2021.
Beyer, Kurt. "W. Grace Hopper and the invention of the information age." MIT Press, 2012.
Penrose, Roger. "The emperor's new mind: Concerning Computers, Minds and The Laws of Physics." Oxford University Press, 1989.