The Essence Of Loops
The Essence Of Loops
Written by Mike James   
Thursday, 27 November 2014
Article Index
The Essence Of Loops
Single Exit Loops
Complex Loops and Problems

Loops are an essential part of any program and becoming a programmer is mostly a matter of mastering the idea of controlled repetition. It is sad that most programmers only know the forms of loops provided by one or at most two languages because they have a life and structure that doesn't depend on language. 

There are only three types of flow of control in any program - the default sequential, the conditional and the loop. The sequential moves the program on from one instruction to the next in a given order. The conditional makes a choice about which instruction comes next based on some condition. The loop simply repeats one or more instruction some number of times. 

The loop is something that takes time for a beginning programmer to fully appreciate. As many of us rarely stray outside of a given language even experienced programmers may not fully appreciate the abstract concept and form of the general loop. Let's take detailed and language independent look at the whole idea of repeating instructions. 

If you would like a "too long didn't read"summary then skip to the end.

 Loop

Loop

 More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language

 

Loops That Never End

Back in dark days of programming loops were formed using the jump or goto instruction that transferred control to a labeled instruction somewhere in the program. Conditionals also use the jump or goto to transfer control to different parts of the program. The big difference is that the loop transfers control backwards to an earlier part of the program whereas a condtional usually jumps forward.

The effect of jumping back in the program text is that instructions that have been obeyed are excuted again and hence a loop is formed. 

For example:

label: instruction1
       instruction2
       instruction3
      goto label

is the jump or goto way of forming the granddaddy of all loops the infinite loop. In the early days of assembler and unstructured languages this was the only way to form a loop. 

 

At this point you may be thinking "goto" - that's harmful isn't it? 

Well yes the goto has a bad reputation but not because of forming loops. A goto used in the way indicated above is ok - its a structured use of the goto and hence easy to understand. The use of the goto is bad when it is used to jump all over the code in an "unstructured" way.

To stop programmers from writing unstructured code languages introduced none-jumpy ways of writing a loop. This got rid of the goto and the temptation to use it poorly but it also obscured the mechanism of the loop and made it slightly harder for the beginner to learn to program. 

For example many languages use the "Loop - EndLoop" type of syntax:

Loop:
       instruction1
       instruction2
       instruction3
EndLoop

You can see the general idea - the list of instructions between the Loop and EndLoop statements are repeated - in this case forever. 

loop1

A loop is called a loop because it … loops

 

You can see how the Loop-EndLoop syntax hides the jump back to the start, but it is still there in the generated machine code. 

There are lots of variations on how you can write a jumpless loop. Some languages end all control structures by writing the starting word backwards:

Loop: 
       instruction1
       instruction2
       instruction3
Pool

some just use End and some, like Java, C++, C# and so on make use of curly brackets to group the repeated list of instructions:

Loop { 
      instruction1
      instruction2
      instruction3
}

It is important not to get too focused on the syntax of the way loops are written.

Focus instead on the underlying idea. 

Loops That End

Infinite loops are sometimes taught as something you should avoid but in many situations the entire structure of a program is organized around an infinite loop that keeps the whole thing running.

However all good things come to an end and so do most loops. 

It is only when we start to consider how loops come to an end do the really interesting variations come to the surface. You could say that this is where the family tree of loops starts to develop. 

There is one big split in all loop classification - conditional loops and enumeration loops. 

If you are going to repeat a block of code then there are two possibilities:

  • you might what to repeat the block until some condition is satisfied - a conditional loop e.g. repeat until A<0

or

  • you might want to repeat the block a given number of times - an enumeration loop e.g. repeat 5 times.  

You might want to object and say that the enumeration loop is just a special conditional loop and you would be 100% correct. The only sort of loop you need is a conditional loop - a language with default flow of control, conditionals and conditional loops is Turing complete, that is you can use it to write any program that can be written. 

So repeat 5 times can be written as repeat until count>5 where we assume that count it incremented each time through the loop. 

The essential difference between a conditional loop and an enumeration loop is that the number of repeats is explicitly known before the loop begins. With a true conditional loop you don't explicitly know how many repeats you are going to get before it starts. 

As the conditional loop covers just about every type of loop it makes sense to look at it first and then specialise to the enumeration loop.

The Conditional Loop

Conditional loop are just infinite loops with a condition that has to be satisfied for them to terminate. 

How do they differ?

The major way that conditional loops differ is in the location and number of their exit points.

An exit point from a loop is simply an instruction that can bring the loop to an end and continue with the rest of the program. 

For example, a loop with two exit points:

Loop: 
       instruction1
 If condition1 Then Exit Loop
       instruction2
 If condition2 Then Exit Loop
       instruction3
EndLoop

While and Until Exits

You can also write exit points in two forms - While and Until exits. 

The natural way to write an exit point is to write the condition needed to stop the loop i.e. the loop continues until the condition is true:

Until cond1 => If cond1 Then Exit Loop

This says that the loop continues until condition1 is satisfied. 

A while condition is has to be true for the loop to continue i.e. the loop continues while the condition is true. Obviously a while exit point's condition is just the logical not of the corresponding until exit point's condition and this allows while exit points to be written as:

While cond1 =>If cond1 Then null Else Exit Loop

or more usually as

If Not cond1 Then Exit Loop

Obviously there isn't anything deep in either specifying the condition for the loop to stop or the condition for the loop to continue but sometimes one is more natural than the other as we will see. 


loops



Last Updated ( Thursday, 27 November 2014 )
 
 

   
Banner
Banner
RSS feed of all content
I Programmer - full contents
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.