Proving Turing completeness, i.e. proving that a language can compute anything, is often difficult. In the previous chapter we discovered that you had to prove that the language in question could be used to implement a Universal Turing Machine. With a programming language that has the three forms of flow of control you still need to prove that you can implement a Universal Turing Machine, but usually the ability to use a conditional and a loop are enough to indicate that a language can do the job. Without these forms of control the language is unlikely to be Turing-complete. With them all you really need to prove is that you can implement something that mimics reading a paper tape.

Nesting

Programs are built using three forms of flow of control – default, conditional and looping, the flow of control atoms. You can put these together one after another as if the flow of control was a model railway set. You can have a loop followed by a conditional, followed by a loop and so on.

There is another way of combining the flow of control atoms – you can nest one inside the other. For example, you can have a loop that repeats something that needs a conditional:

While condition 
    instruction
    If condition Then instruction
    instruction

This makes the flow of control more varied that you might imagine. 

A particularly common nesting is of loops. You can nest one loop inside another to obtain a repeat of a repeat. For example, if you nest a five times repeat inside a 10 time repeat loop the inner loop will be repeated 10 times making a total of 50 repeats:

repeat 10
 repeat 5
   instruction

Why would you want to do this?

It is always possible to replace a set of nested loops by a single loop that repeats the same total number of times, but sometimes the logic of the situation is best expressed as a repeat of a repeat. Usually the inner repeat does some job to completion and the outer loop repeats the inner job together with some initialization or processing.

For example, if the inner loop is

repeat 20 stir coffee

the outer loop might be

repeat 5
	get new cup of coffee
  	repeat 20 stir coffee

You can see that the inner loop stirs a single coffee and the outer loop repeats it 5 times to complete the stirring of five coffees. Nesting loops is usually about repeating two actions in this way – getting the coffee five times and stirring each coffee 20 times.

Now?

It is difficult to put ourselves back in the position of the early programmers trying to do something on a regular basis that was once a rare occupation. The Goto incident is an example of the move away from the way programs are created to a more abstract view. In this case feelings were running high as programmers were being told that the way that they had been programming was very wrong and it was implied that they were damaged beyond recovery by the experience. 

This may sound extreme, but in many cases it was true. It was difficult to see how obviously correct the Goto-less approach was because the people that needed to be persuaded were unable to see how to program using it. They saw it as an unnecessary straitjacket and confirmation bias made it possible to aggressively reject it.

It took a long time for programmers to see the error of their ways and retrain themselves to think in terms of the structured programming primitives. Even today you will still find new questions being asked on forums “What IS so bad about the Goto”, usually with a rider that the questioner wouldn’t dream of using a Goto or that they are asking for a “friend”.

Today there really is no dissent from the party line and all of the major programming language support structured Goto-less programming. What is perhaps strange is that many still have instruction labels and a Goto instruction often hidden in the documentation with big warning signs that something terrible will happen to any programmer who dares to use them!

Is there a better way than structured programming?

Probably not. 

Summary

• Initially the only way to modify the flow of control was to use the Goto or an equivalent which transferred control to another instruction.

• Line numbers were the first way to locate a particular instruction, but these change if the list of instructions is modified.

• Line number were replaced by the idea of labels which can be numbers or meaningful titles.

• The problem with the Goto is that it gives you no guidance in how to use it. Early programmers just used to change the flow of control as seemed useful at the time. The result was that the flow of control graph was often a tangled mess – hence the term ”spaghetti programming”

• Edsger Dijkstra decided to put things right with an attack on the Goto in a famous academic paper – The GOTO considered harmful.

• Dijkstra formulated an alternative to the Goto in the form of structured programming which provided a way to construct a conditional and a loop without the use of the Goto.

• Despite the fact that you could do anything with structure programming that you could do with the Goto and the flow of control graph was easier to keep simple using them programmers were resistant to the change.

• Today few programmers would argue with Dijkstra’s ideas and many use them without even being aware that there once was a much worse way of doing things.routines.

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info