CONTENTS

Part II
Two real programmes – and why programming is difficult!

Two real programmes

Now, what does it mean to say that a programme consists of steps executed one after the other, in order to calculate a function? As a reminder: We distinguish between what a function describes and how that is calculated: To a human it is intuitively clear how to understand the character sequences f(x,y)=x+y and g(x)=x2  and what they mean, namely “sum of x and y” and “x squared”. To a machine, though, we have to tell how to calculate this. One way to calculate the square function is x*x. We must then also tell the machine how multiplication works, which in turn consists of individual steps.

So, let’s take a really quick look at what a programme looks like to calculate our square and sum functions. Let us start with the sum function. The inputs are the two summands x and y; the output is supposed to be their sum. Let’s assume for the moment that we are using a simple programming language that cannot handle the addition of arbitrary numbers, but can handle the simpler addition of 1 and subtraction of 1. We will now try to calculate arbitrary sums using these two simple functions.

Let us observe that x+y is the same as 1+x+(y-1). Thus, we added a one to the left and subtracted a one from the right. They cancel each other out. In turn, 1+x+(y-1) is the same as 1+1+x+(y-1-1), and so on. For example, 3+2 is the same as (1+3)+(2-1), which is 4+1, and that is the same as (1+4)+(1-1), which is 5+0. Hence, our final result is 5.

We can thus calculate arbitrary sums by adding and subtracting 1, by subtracting 1 from the second summand (which is y) and at the same time adding 1 to the first summand, which is x. We do this exactly y-times: So, we subtract a 1 from y y-times until the result is zero, and add a one to x y-times.

The original values of x and y are handled in the memory, which we introduced above. In our programme we can read and overwrite the corresponding values (for this, computer scientists say store and even more precisely store in x or store in y). Our programme then looks like this.

“Sum” programme
Input: two numbers x and y
Output: Sum x plus y
Repeat as long as y is not 0:

1. add 1 to x and store the result 1+x in x
2.subtract 1 from y and store the result y-1 in y

Output x

As real code, this looks as follows. while (condition) is the repeat statement that is executed as long as the condition in the parenthesis is true. ≠ is the inequality. We use the left arrow ← to describe the process of storing; so x ← x+1 says that the value of x+1 is written to the location in memory designated for x. output prints the result on the screen. The curly braces are for grouping purposes only.

sum(x, y) {

while (y≠0) {

x ← x+1;
y ← y-1;

}
output x;

}

A computer now runs the programme as follows. Let us take the example of the inputs x=3 and y=2.

  1. Because y≠0, in the first step x becomes 3+1=4 and y becomes 2-1=1.
  2. y is still non-zero, so x now becomes 4+1=5 and y becomes 1-1=0.
  3. Now y≠0 is no longer valid, no further repetition takes place.
  4. The result is the last value of x, namely 5.

This is perhaps a bit unintuitive, but actually quite logical. Please note that here we have solved the more difficult problem “calculate any sum” with the help of two simpler operations, namely the addition and subtraction of 1. This is a core idea of programming: We solve a difficult problem using simpler steps.

Now let’s play the same game for the square function. This time we assume that our programming language offers only the subtraction of 1 and additionally the addition of numbers. We have just programmed the latter ourselves, so we can simply use this programme.

Multiplying x by x is the same as adding x-times the number x: 3*3 is 3+3+3 and 4*4 is 4+4+4+4. To describe multiplication with the general addition and subtraction of 1, we use a trick like above again: x*x is the same as x+(x-1)*x. And that is the same as x+x+(x-1-1)*x. Ah! That in turn is the same as x+x+(x-1-1)*x. And so on until the value in the parenthesis is zero. So now we have defined the square function using two simpler functions, namely the subtraction of 1 and the general addition.

In this case we have to remember an intermediate result, which we store as z in each case. At the beginning we set z to the value 0. Now let’s look at example of computing 3²:

  1. This is the same as 3*3, which is the same as 3+(3-1)*3. The left part of the sum is our intermediate result.
  2. So we add this left 3 to z, which is originally 0, and store the result 3+0 in z.
  3. Then we continue: z+2*3 is the same as z+3+(2-1)*3, so z+3+1*3.
  4. We add the left 3 to the intermediate result z and write the value z=3+3=6 into memory for z.
  5. z+1*3 is then the same as z+3+(1-1)*3, which is the same as z+3+0*3.
  6. We add the left 3 to the intermediate result z, which now stores the value z=6+3=9.
  7. 0*3 is 0, so we can stop.
  8. The intermediate result z has changed in each step, and its last value is 9. Exactly what we set out to compute!

Because we have to add the value of x to the intermediate result z in each step, we cannot change x in each step as in the case of the sum. Instead, we need a second intermediate result v which stores the value of x, x-1, x-2, …, 0 in succession.

“Square” programme
Input: a number x
Output: x squared, i.e. x*x
Store 0 in intermediate result z
Store x in intermediate result v
Repeat as long as v is not 0:

  1. add x to z and store the result z+x in z
  2. subtract 1 from v and store the result v-1 in v

Output z

As code:

square(x){

z ← 0;
v ← x;
while (v≠0) {

z ← z+x;
v ← v-1;

}
output z;

}

Let us simulate the computer running the programme for the input x=3.

  1. First, z is set to 0 and v is set to the value of x, i.e. 3.
  2. Because 3≠0, z is set to 0+3=3 and v is set to 3-1=2.
  3. Because 2≠0, we repeat: z becomes 3+3=6 and v becomes 2-1=1.
  4. Again, 1≠0, so we repeat the steps again: z becomes 6+3=9 and v becomes 1-1=0.
  5. Now the repetition terminates, because 0≠0 is not valid, and z=9 is output.

That’s how simple programmes work. E-mail clients, search engines, control units in cars and in bakeries are programmed the same way.

In case you are wondering: We have deliberately injected a small bug into our programmes that we will find afterwards.

Libraries and reuse

If our programming language does not know the addition symbol +, we can simply replace it with our sum programme above (change in blue) and derive a new programme square2:

square2(x) {

z ← 0;
v ← x;
while (v≠0) {

z ← sum(z,x);

v ← v-1;

}
output z;

}

The use of previously created programmes in a new programme is a tremendously powerful principle that was discovered only in the Sixties. It is so powerful because, on the one hand, it allows us to break problems down into smaller problems, solve them independently and then put the solutions together. In this way, it helps us organise our programming work, among other things.

On the other hand, this principle also allows functionality once created to be made available to other programmers. Computer scientists call such programme packages libraries, which are made available to others for use in their own programmes. We compared them to baking books above. Perhaps you have heard of the Java programming language, or a language called Python? These languages are used by a great many programmers around the world in part because they provide huge libraries for all sorts of functionalities, including sending data to the Internet, using machine learning, or analysing natural language text. Programmers then do not have to create these functionalities themselves, but can benefit directly from the work of others by reusing the corresponding programmes.

If you have paid close attention, you will notice that we have introduced two concepts for the same idea. Above we said that programming languages differ in how they express “certain concepts” or “technical steps”, and that some languages are more suitable for talking about “window”, “button” and “mouse pointer”, and others about “distance to the car ahead.” Here we are now saying that “certain concepts” are captured in programmes, that is, solutions are programmed for problems that are then available in libraries for reuse. Your observation is correct. This is indeed the same idea in two different forms: Recurring constructs should be as easy to use as possible. The underlying principle is what computer scientists call abstraction.

Almost there: processor and machine language

Perhaps by now you have developed a suspicion that somehow we have tricked you. This is because we have programmed our functions on the basis of other, simpler functions. Strictly speaking, this does indeed merely shift the problem. To calculate an arbitrary sum, we have nonchalantly taken for granted the simpler operations of “plus 1” and “minus 1”. In the square programme we could just save ourselves, because we had programmed the addition ourselves earlier. But we still needed the “minus 1” operation there.

If you remember, the situation was quite similar when we were baking a cake. In recipes, many individual steps are presented in a highly simplified way, for example, when it is tacitly assumed that “baking” includes the following proceses: “Open oven door,” “Remove all trays from the oven,” “Close oven door,” “Preheat oven,” “Open oven door,” “Push in cake pan,” “Bake,” “Turn off oven,” “Open oven door,” “Remove cake,” “Close oven door. There, it is assumed that the baker knows which individual steps make up complex steps (and again, what the meaning of “a pinch of salt” is).

So, programmes are written with the help of simple operations. We then write still larger programmes with the help of these simple operations along with other programmes and the libraries we have just mentioned. Building on that, we write still larger programmes and so on. In this sense, we can stack programmes on top of each other.

However, I have not yet explained how to actually compute the results from these simple underlying operations. Furthermore, perhaps you have remembered that we have yet to tell you exactly what a processor really does. Let’s do that now: The processor provides exactly these simple underlying operations just mentioned! It can calculate very simple operations on the hardware like – you guessed it – adding or subtracting one and multiplying by two or dividing by two. It can check if a value is zero, it can select arbitrary locations in a programme as the next step to execute and so on. For these very simple operations executed on the hardware, there is again a separate programming language called machine language. The machine language for Intel processors consists of around 1000 possible simple operations.

Programmes in other programming languages such as Java or Python are ultimately translated into programmes in machine language. This is probably best understood in the sense of a translation from German to English.

You may have heard the word compiler before: compilers do exactly this translation into machine language. The idea is quite similar to the use of the sum programme in the square2 programme in the line z ← sum(z,x). You may also remember our earlier remark about the conceptual similarity between libraries and different programming languages. After all, the use of the word sum represents the lines of code that implement the sum programme. In reality, things work slightly differently, but you can think of it as replacing the word sum in our square2 programme by exactly the lines of code that correspond to the sum programme. In exactly the same way, the repeat statement while, the assignment ←, addition and subtraction of 1 and the output function output stand for small independent programmes in machine language, into which they are actually translated as well.

Amazingly, e-mail clients, bakery controls and all other functions can be translated into this simple machine language. A processor can then execute machine language programmes directly on the hardware. That is, the processor receives input signals in the form of “voltage” and “no voltage,” representing, for example, the addition of 1 to a number 7, and it provides output signals also in the form of “voltage” and “no voltage,” which are then interpreted as the result of the addition. These are the famous binary ones and zeros that we all associate with computers.

That it is possible to represent arbitrary numbers with ones and zeros has been known since the 17th century. It would take us too long to go into any more detail about this here, but we can at least quickly understand the idea. Think of it as follows: We humans use ten digits to represent numbers, namely 0, 1, 2, …, 9. If we want to represent ten, we need more than one digit: 1 and 0, so 10. Eleven is 1 and 1, so 11. Ninety-nine is 9 and 9, so 99. If we want to represent one hundred, we need three digits: 1 and 0 and 0, so 100 and so on. If we have only zeros and ones available, we can use the same principle: Just as we humans cannot represent a ten with only one digit, computers cannot represent a two with only one digit. So, we add a second digit, and 2 is represented as 1 and 0, which is 10. We represent 3 as 1 and 1, which is 11. We need another digit for four, just as we needed another digit for hundred: Four is written as 1 and 0 and 0, so 100, and so on. By the way, the ten is represented as 1010, the hundred as 1100100.

Because the programme steps that are described with machine language are very fine-grained, the corresponding programmes quickly become very large. For this reason alone, they become difficult to understand and maintain. In computers’ early days programmes were actually written directly in machine language. Today, no one actually does this anymore, but instead uses the programming languages that are better understood by humans, which are translated into machine language with the aforementioned compilers for programmes.

Three comments: Condition; three instructions are enough; humanisation

Please allow me to make three comments at the end of this part. I think they are important and even if you are still not clear about everything after your first reading of this section, you will still be able to understand the rest.

First, the set of all intermediate results at a given time is called the state of a programme. The state is stored in the memory during the programme execution. Each step of the programme execution changes this state, because intermediate results are changed and in our example so too are the values of the variable storing the input. Often there are many such possible states. Their large number makes it difficult to write and understand programmes. So, it is not only the number of steps that makes a programme complex (the software in a car today consists of hundreds of millions of lines of code), but also the number of possible states.

Second, we have explained that programming languages differ, among other things, in how they can succinctly express certain concepts in a particular context: We talked about “windows” and “buttons”, for instance. In our real programmes above, we used three basic concepts just like that, without explaining them further, because they are so natural: (1) storing values or intermediate results in memory – those are the lines with the left arrow; (2) executing one line after the next – that’s signalled by the semicolon at the end of each line; and (3) repetition – the while statement, which we already explained. I still find this really amazing: since the 1960s, it has been known that all functions that are capable of being computed can be programmed using these three facts plus addition and subtraction. All of them!

(Why  the strange interjection with “functions which one can calculate” in the first place? That is crazy enough, but there are also functions which one cannot calculate. This is hardly imaginable! A famous example is a function F, which receives a programme P as input and is to compute for each input programme P whether this programme P will eventually terminate its calculation for each input E, or whether it can happen that the program P runs infinitely long. We will see in a moment how this can be the case for our examples of the square and sum programmes above in the case of the input of negative numbers. Now a function F, which computes for all programmes P and all inputs E whether the calculation will stop at some point, looks like this: F(P)= “yes” if P(E) finishes at some point for all inputs E, and “no” otherwise. There is no programme for such a function! We have known this since the 1930s, but best that we do not dwell on this conundrum any further here!)

Third, you may have noticed that throughout the text we have quite intuitively used words for actions of machines that you would usually attribute more to humans or living things in general: “respond to a stimulus,” “interact,” “communicate,” “recognise,” “compute,” “learn,” and so on. Philosophers have given considerable thought to such “humanisation” of machines. This becomes explosive when it is assumed, or linguistically suggested, that machines can “decide” facts and even be “responsible” or “liable” if necessary. With the exception of responsibility and liability, I find this linguistic humanisation catchy and completely okay. However, I do not want to hide the fact that there are schools of thought in connection with so-called transhumanism that at some point grant machines real intelligence or even emotions or responsibility. For my part, I consider this to be absurd.

Programming precision; errors

Perhaps you, too, have tried a cake recipe that you didn’t quite understand or misunderstood, and then, upon closer inspection of the result, decided that perhaps you would rather throw the cake away than eat it. Sometimes that’s simply your mistake. But sometimes it’s also because recipes aren’t described precisely enough, or because they contain mistakes.

You may have noticed that if the input y for our sum function or the input x for our square function above is a negative number, then the programme will never terminate. This is because a negative number minus one can never add up to zero: As we run the programme, we subtract minus one an infinite number of times. The problem is that we forgot to account for this special case. We were not sufficiently precise. (The error can be fixed in both programmes by replacing the ≠ in the while condition with the greater-than sign >. See for yourself! Now if you look carefully, we forgot something else: We didn’t require the inputs to be integers in the programme. If you enter 4.2 as input, the programme will never finish either. Replacing ≠ with >, though, also fixes this problem).

Lack of precision in this and other ways is a big problem in programming. That’s one of the reasons why programming is not always that easy. In a very funny video clip (Exact Instructions Challenge: This is why my children hate me), the problem is well illustrated by an example: A father asks his young children to write down exactly which steps he should perform in order to make them a peanut butter and jam sandwich. Do try this out with your kids! It quickly turns out to be more difficult than anticipated. For example, the father, intentionally of course, misunderstands the instruction to “spread peanut butter on a toast” to spread the peanut butter on one of the four edges of the bread instead of one of the two larger sides. Or he uses his hands to get jam out of the jar because the children forgot to suggest using a spoon to do it. Or he fails at the very beginning because there was no instruction to open the refrigerator door before removing the jar of jam.