Changing Path

A straight line program is a useful tool and can solve many problems.  Its primary drawback is that its behaviour is rigid or static.  A straight line program is good at doing one thing only and it will never deviate from that one path.  It is important in many problems to be more adaptive and responsive to the changes in the problem as the input is explored or for differing inputs.

For example when you log onto this web page or another using a password the program that checks your password must decide if that password is correct or not (by checking it against the one stored in the database of passwords).  If it is correct it will mark your activity on the website as belonging to your account.  This helps it make other decisions, like what content to display or what actions to allow you to perform.  A website that does not allow anonymous comments would allow you to comment if you were logged into your account.  If you were not logged on it would present you with a different screen – an error screen – asking you to log in or sign up.

These decisions are very common place in programs as we want our programs to be able to do many different things.  These decision points constitute branches in our straight line program much like a fork in the road.  When a branch is encountered there is always at least two possible paths for the programs execution to follow, but only one will be executed and the other ignored in this run.  Which branch will be executed will be determined by checking a condition (password correct/incorrect, account logged in/out).

If-Then-Else

The simplest branch statement in most programming languages is the if-statement.  The if statement characterizes the simplest choice – the binary choice (that is, the choice with two possible outcomes).  The if-statement has three parts: the condition, the then-body (if-body), and the else-body.

Condition

The condition is an expression that must have a truth value.  Specifically the statement must be something that can be true or not (we call these assertions).   Whether or not the condition is true then determines what is done next.  Here are some example assertions that might make good conditions:

Password entered is the same as password in database.

This can be true or false and so it is an assertion.  If it is true we want to do one thing (allow access) and if it is false we want to do a second thing (ask to re-enter/deny access).

Today is Sunday.

This assertion can clearly be true or not.  Such an assertion might be used to display different material on a webpage depending on the day of the week (say today’s broadcast schedule).

Some user is logged in more than once.

This is again a clear assertion, but this one might be harder to determine if it is true or not.  We might need to write a program just to decide this assertion.  We might want to know this if we wish to allow users to only log on once at any given time.

1 = 1

This is a bizarre assertion.  It says that the number 1 is equal to the number 1 which we all know is always true.  This assertion is sometimes used in place of another assertion if we want to force the program to take only one branch.  However, if this is so we have just forced the program back to a rigid state like that of a straight line program.

Then-Body

The then-body of the if-statement contains the operations the program is to carry out if the condition is true.  The then-body itself is potentially a complete program itself.  At the simplest it is a single operation, or a straight line program.  However, it could include all manner of complex control including other branches, loops, or even running entirely different programs.

Occasionally we might leave the then-body empty.  This would constitute a program with zero instructions and we would want to do this in a case where we will ignore one half of the branch but do something important in the other half (in this case the else-body).

Else-Body

The else-body parallels the then-body in many ways, except that it contains the operations to be executed if the condition is false.  Like the then body the else body can range from an empty program to a complete program with branches, loops, etc.

After the else-body the program continues as normal.  This means that regardless of which branch we entered the branches merge again into one path after the if-statement.  This is certainly the most common form of branch, but in some rare cases there are no operations after the branch and the branches split forever (the program ends after the branch).

Nested Branches

If-statements are necessarily a two way branch, but by using more than one if-statement in combination (not one after another) we can create more branches.  Consider the following piece of pseudo-code (pretend program code):

if “Today is Friday” then
   if “Today is the 13th” then
      Scary!
   else
      Party!
else
   I wish it was Friday!

This nested if-statement expressed my feelings about what day it is.  Notice that it captures three possible branches.  If today is Friday the 13th then being superstitious I am scared of unlucky encounters.   In the second case if today is Friday but not the 13th then I am happy the weekend has come – time to party!  In the third case I long for Friday to come again.  Using two if-statements we can make three branches.

Notice we added the nested if-statement to the then-body of this example.  We could have added a nested if-statement to the else-body instead creating three different branches, or we could have added one to the else-body as well creating four total branches.

if “Today is Friday” then
   if “Today is the 13th” then
      Scary!
   else
      Party!
else
   if “Today is Saturday” then
      More party!
   else
      I wish it was Friday!

We can continue nesting statements to get as many branches as we like.  Much decision making in computer programs is carried out by nested branch statements like this.  Some programming languages will allow you to use a general purpose switch statement to handle multiple cases like this, but these statements offer mostly a cosmetic improvement as they work similarly to nested if-statements.  We’ll look closer at these in the language specific topics.

Loops

A large part of programming is repeating yourself.  A single operation might appear in many different places in your program – possibly one after another.  Other times an entire block of operations might be repeated more than once.  When we must repeat an operation or sequence of operations one after another we have convenient structures called loops to help us.

There are several kinds of commonly used loop structures.  Which loop structure you use is a function of the programming language you are working in and the purpose the loop in intended to fulfill.  We can consider most loops as variants of a general loop structure.  That is, we can usually get away with using only one kind of loop structure but since each structure lends itself to different uses we find all in practice.

Each loop structure will have a loop-body, a short program that is to be repeated in the loop, and a stopping condition that determines the number of times the loop is repeated.  Some loop structures will also make use of additional variables to maintain the loop called counters.

The simplest use of a loop is to repeat an operation (or collection of operations) a fixed (and known) number of times.  Thus a simple loop (or just loop) has a loop-body consisting of the operations to be repeated and a stopping condition determining the number of repetitions usually through a number or a variable with a number as its value.

Recall to move the man out of the maze we had to repeat the operation move forward some number of times determined by the specific maze. For instance perhaps this program would get our man out of the maze:

move forward
move forward
move forward
move forward
move forward

This simple program takes five lines but we can imagine a similar program that has one thousand steps. The cost to the programmer to type out one thousand operations, or even to efficiently copy and past the one thousand lines, would be very great in time. So we save typing and time using a loop.

do 5 times
   move forward

In this case 5 is chosen to be the number of repetitions and this program will have the same output as the one above (the man will move forward five times). If we wanted we could use a variable to make this program more dynamic.

set count to 5
loop count times
   move forward

This program also loops 5 times but uses the variable count to control the loop. By changing the value of count in this program we can alter the number of repetitions the loop makes.

Exercise

While Loops

As I mentioned above all loops have a similar general structure.  Relying on this I will start by presenting one of the common loop structures called the while loop.   A while loop combines the branching power of an if-statement with a loop structure.  We will consider the while loop as consisting of three primary parts: initialization, loop condition, and the loop-body.  The loop will also use an auxiliary variable (a variable not used in other parts of the program) as a counter.  In our examples I’ll call this variable count.

Here I have taken our simple loop above and translated it as a while loop with a counter variable.

set count to 1
while count is less than 6 do
   move forward
   set count to count + 1

The variable count is initialized to 1 before the loop begins. The while loop occurs next along with a condition. This condition operates like the condition of an if-statement. If the condition is true, that is if count is less than 6, then the loop-body is executed (the next two indented statements). If the condition is false then the loop is exited to the next line in the program (there is none in this example). The only difference in a while loop is that after the loop-body is executed the condition is tested again. If the test is still true the loop body is entered for another execution, after each a new check will be made. In this way the loop will be executed while the condition is true.

This means that we must ensure that the condition at some point becomes false, otherwise the loop will iterate forever, this is called an infinite loop and is rarely desirable. In our loop-body we have added the line set count to count + 1 which increments the variable count by 1. In each subsequent check of the condition the variable count is greater than the last, meaning eventually it will no longer be less than 6. Indeed after five iterations the value of count will be 6 and the loop will be exited.  Again if we wish to avoid an infinite loop when using a while loop we must include some statements in the loop-body that alter the condition so at some future point it might become false.

Exercise

For Loops

A for loop is a convenient short hand for this standard while loop structure.  The for loop builds the auxiliary variable, the variable initialization, the loop condition, and even the variable update into one statement.

for count from 1 to 5 do
   move forward

The variable count is initialized as part of the for loop and the loop states it will be initialized to 1 and end when it is 5. The update operation in this example is left implicit but is assumed to be increment (add one). In both writing pseudo-code and in writing in various languages the for loop is a convenient way to construct a loop.

for count from 5 down to 1 do
   move forward

In this example the implicit update operation is decrement (minus one). We indicate this using down to. Other more sophisticated initialization and update methods exist when looping and many languages allow for the for loop to operate as a general loop structure. Rarely are loop structures needed other than the while loop or the for loop.

Square

Triangle

House