This introductory chapter of my new book on the nature of programming is aimed at programmers and non-programmers alike. In this extract we look at what makes a language "big" enough to do the job.

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops ***NEW!!

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

 <ASIN:1871962722>

<ASIN:B09MDL5J1S>

The existence of little languages suggests that there are big languages and this raises the question. “What do you need to write a program?” The answer has to be a programming language. 

What sort of language would that be? This time there isn't a short simple answer, or is there?

We have made the acquaintance of three programming languages – the language of geometry, the language of arithmetic, and regular expressions. All of these were referred to as "little" languages because they are limited in ways we now need to make clear. We also need to look into what makes a language “big” and exactly what it can compute.

Decisions and Repeats

A program is a list of instructions and the type of instructions in the list depends on the object that the program is working with. In the case of the geometric language, Turtle Graphics, the instructions were all about moving specified distances in specified directions. In the case of the little language of arithmetic, the instructions were all about taking numbers and doing simple arithmetic on them and in the case of regular expressions we defined classes of characters that match.

If the instructions that go into the lists are always different, how can there be anything constant about programming languages?

The answer is that any reasonably capable programming language always has the ability to make decisions and repeat things. For example, in a recipe you might find the instruction: 

"If the sauce is sweet add lemon"

This is a conditional. You don't "add lemon" every time. Instead you compute a condition "is the sauce sweet" and if this true you "add lemon". 

The important point here is that the idea of a conditional is something you find in every programming language, even if it is well hidden. It is a universal of programming. 

Equally, within a recipe you might find an instruction like:

"Repeat the beating of the cream until it is thick"

or:

"Place 5 cherries on the top of the cake"

In each case you are repeating an instruction. 

This repetition of an instruction occurs in every programming language and it too is a universal of programming. Sometimes it is hidden and difficult to see. For example, is "place 5 cherries" a repeat or just one action? For a human things are vague and you can think about instructions in different ways, but you can see that it is "place one cherry" repeated. When it comes to repeats we are likely to bundle the actions up into one composite action and almost not notice that a repeat is involved – we take it for granted.

It is true to say that humans are more used to noticing conditionals than they are repetition, but when you start noticing it you will find it everywhere.

You could say, even at this early stage, that it is the use of conditionals and repeats that makes a programming language so much more than a little language, but the ideas are so much bigger than just this.

The Flow Of Control

What we have observed so far is that there are common ideas in all lists of instructions. Even if the instructions change, the way that we can organize them to get things done stays roughly the same:

• You can obey one instruction after another

• You can obey some instructions only if a condition is true

• You can repeat a block of instructions until a condition is true

What is amazing is that these three options are all there is – there is nothing more sophisticated that can be thrown into this mix. All lists of instructions boil down to these three ways of obeying instructions.

Programmers call the first the default flow of control, the second is a conditional and the third is a loop. In fact they form the three fundamental forms of the flow of control. You can think of the instruction currently being obeyed as the instruction currently in control of what is happening. As you work your way though the instructions, control passes from one instruction to another – this is the flow of control.

As we have already seen there are only three fundamental forms this can take and you can imagine them something like:

The first is the default flow of control. The second is a conditional that skips a set of instructions. The third is a loop where the control passes back to an earlier instruction. These are often called “railway diagrams” because they are essentially the possible routes though a program as if a train was running on tracks on the flow of control. More technically the collection of the possible paths through a program is called its flow of control graph. The shapes also correspond to the movement your finger would make if you traced out on the program the order in which you obey the instructions.

These three forms of control are all you need, but at this point I need to introduce one other form of control – recursion. This is not the place to discuss it because it isn't easy to see what it is about and what makes it different from the other three. I only mention it here to allow for the possibility that you might have heard about it or know about and want to know where it fits in. The simple answer is that you don't actually need it because it can be reduced to some combination of the first three. This may be true, but recursion is still fascinating and of great practical value and you can find out more about it in Chapter 10.