Introducing Control Structures

Computers are dumb! It is just that simple. Over the years that computers have been around, we have tried a bunch of different ways to express our desires to these dumb computers. Some of the ways we have tried made things easy for the people involved, some made things harder. Let’s skip to the easy way.

Designing Programs

First of all, what is a program, anyway? The simplest definition is just a detailed list of specific instructions that a particular computer can follow to perform some task. Phew! That definition raises a number of questions right away! Like:

• What instructions does the computer understand?
• How do I get this list into the computer?
• Why do we care what computer the list is for?
• How do we get data into and out of the computer?

And the biggest one of all:

• How to I solve my problem in the first place?

We will address all of this as we proceed. For now, rather than get too deep into computer programming right away, let’s focus on the problem solving part first.

Analyzing the problem we want to solve

How do we create a program - or even a simple list of instructions some computer could understand?

We should have a clear definition of just what our program is to do. We also need to know what resources we will needed to solve the problem, and what results we expect to obtain.

Hmmm, let me think about that for a moment! If I figure out what resources I need to provide to my computer, then figure out what to do to those resources to solve my problem, then figure out how to get my results out, I am done! Cool!

Three simple steps to success! What could be easier?

Breaking a big problem into smaller problems

In the old days of computer programming, any problem was broken down very quickly into these three major blocks:

• Input the raw data needed by the program
• Perform some computational processing on that data
• Deliver output products in the form of reports

Today, exactly how to do the initial breakdown of functions is more difficult. Especially when the program will include extensive interaction with a human operator and the outputs are more complex that simple printed reports.

The most important skill needed in the early part of problem solving is an ability to see the problem clearly enough to identify places where the big problem can be broken up into smaller pieces. This process, known as decomposition, is one of the ways humans have learned to deal with complexity. The whole is just too complex, so break it down into a series of smaller, less complex, parts and glue those parts together. If the first decomposition still leaves us with parts that are too complex, break them down as well. Continue until each part can be clearly constructed.

A key characteristic of a good problem solution is a clear identification of exactly what input data is needed for each piece, and what output is to be produced. The design should identify the processing that is to be performed, but that processing is often not completely understood until after you have worked on the problem for a while.

You should have noticed something important here. At the top of this entire problem solving process, we tried to identify all the information we need to have available to solve our problem, then identify what is to happen in a process, then identify the results we want to get out. While we design a solution, we can focus on the transformation of data from input stuff to output stuff and not worry about exactly how that transformation takes place. We can think of this transformation process as a kind of black box that does magic.

In the decomposition process, we break up a big magic box into a series of smaller magic boxes, and what comes out of one box flows into another box later. Seen this way, it seem like all we need to do is to work out how data flows through the entire system undergoing small transformations along the way, until we get the final output we want.

The problem is that there are a gazillion different ways to build any solution; some work well, and some do not. Your job is to first find at least one way that works, then see if you can make it better.

So, how do we decompose a problem?

Spaghetti Code

When computer programming first took off as a professional activity, there was little guidance in how to perform decomposition. So, programmers just started with the first step they could think of. They usually followed their data as it moved through a series of processing stages until it was ready for output. Along the way, as they thought up something that needed attention, they would hook additional process boxes into the system in ways that were not well thought out at all!

The problem with this approach was they often still forgot fundamental things that needed to be included. So, they would go back into their scheme and patch in new blocks of code to take care of the missing elements. As they patched in new process steps, they would need to perform tests to see if this new process was to be performed, or skipped. Where the program code was to be picked up after a test depended on the result of that test. What came out of all this patching was a solution process that was jumping all over the place , from point to point - not a nice linear sequence of steps at all! Over time, the flow of the program became very confused - and the term Spaghetti Code became a popular way to describe these solutions schemes.

Many people studied this strange situation, and one famous computer scientist, Edsger W. Dijkstra, published a paper titled Go To Statement Considered Harmful (Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148). Dijkstra’s analysis determined that the programming languages of the day gave too much power to the programmer to do whatever they wanted, whenever they wanted. Specifically, he pointed to the uncontrolled use of a jumping statement in most languages that let a programmer jump from one spot in the code to another with few constraints. The result was clearly a mess.

Surprisingly, many programmers took notice of this paper, and programming languages went through a re-engineering period that lead to a revolution in programming and design - structured programming.

What is a structure?

As simple as it seems, a structure is just a block of processing that has a single point where you enter it, with a clearly defined set of data items in hand, and a single point where you leave it, with a different clearly defined set of data items in hand. We usually draw a structure as a simple box with a line going in the top and a line exiting the bottom:

We sometimes call this box a process box.

By itself, this is not very useful. The power of structured programming comes from the use of three very simple variations to this simple box.

Sequence

If we glue several of these simple process boxes together in order, we have a Sequence of actions. Viewed as a whole, there is still a single point of entry and a single point of exit - even for the entire group of boxes. So, we could draw a single box around all the smaller boxes.

Bingo - I see a decomposition here!

The single big box is our original problem, and the sequence of steps is a decomposition of that problem into smaller, hopefully easier to understand, sub-problems.

Decision

Not very many problems can be solved with just a simple sequence of steps. Most will involve making a decision at various points in the flow of processing. Based on the results of each decision, we will perform different kinds of processing. It was probably this single activity that was most abused in unstructured programming.

Today, we only allow decisions to be made in the following structured way:

The diamond represents a question of some sort - one that has only a true or false answer. We allow the flow of the program to branch out of the diamond two ways - one way if the answer is true and the other if it is false. Each path goes to a single process box where the processing for that answer will be performed. We require that the flow rejoin after each of these possible processes so we still have a single point of exit for the structure. (We may allow the process box for the false answer to be missing - in which case we simply pass through the box with no magic happening, but we never allow the process box for the true answer to be missing.)

Constraining the program flow this way seems like it might cause problems, but it turns out not to be in real life - we just have to think a bit harder.

Loops

Finally, there is often a need to perform one action a number of times in a program. For instance, you need to process all the time cards for all employees in your company to figure out the monthly payroll. Loops are easy to set up in a computer, we just jump back to a previous point in the program and do it all over. We really need a way to stop this process or we get stuck in what programmers call an infinite loop - one that never stops. (Some programs need such a loop, most do not!)

Here is one variation of a loop. Can you think up another?

In the case of the loop, the question we place in the diamond is not really a question. It is an expression we can evaluate to see if it is true or false. Something like this:

• I have not run out of data to process

This statement is clearly true or false whenever we check it. That leads to a true or false condition that controls which way we branch out of the diamond.

Using the structures

Now for the real trick in structured programming. We are seeking to decompose big problems into easier to work sub-problems. We can take any of these three fundamental structured forms and place it inside any process box you find in your diagram. Since each structured form has more boxes inside it, you can continue installing other structured forms as needed to clearly define how your processing should proceed.

Cool!

Note

If you think about what we have just said, you will see that programming is actually very simple. The trick is to train your brain to only use these structures and make sure you do not generate any of that nasty spaghetti code. Seriously, if you find yourself having problems getting your programs to work - make sure you are using the structures as we have explained here. If not, do not be afraid to junk what you have and rethink the problem and how you have designed the code. There is a lot of proof out there that says 80 percent of your time should be spent thinking and ony 20 percent coding!

It helps to have a tool of some kind to use these diagrams in this way, but many programmers use just pencil and paper - lots of paper - to do the job. When you decompose a process box, put a number in it - go to another piece of paper, put that number on it and show what goes inside. You end up with a lot of paper, but by taping it to the wall, you can see how it all fits together. (I have seem teams fill up all the walls in a room this way!) Today, there are powerful programs like Microsoft Visio that can be used to build diagrams using these structures. Oddly enough such a diagram is called a Flow Chart.

Is this too confining?

After a lot of study, scientists have proved that anything that can be done on a computer can be done using just these three basic structured forms. So the answer is clearly NO - it is not too confining. Most modern programming languages have constructs that map cleanly to each of these fundamental forms. Most languages add to this simple set to make programming a bit easier, but each addition still conforms to the single entry - single exit principle.

Building Flow Charts

For a long time, building flow charts was a big part of thinking through problems - not just computer problems. Paper and pencil worked well then, and it works well today - if you have no other way. However, many people are not that good at drawing pictures, and anyway, as you decompose one block into others, you end up redrawing the darned things over and over. So, can we come up with another way to do decomposition using tools we already have, and that do not require graphical skills?

Pseudo-Code

Suppose we invent a simple, English-like shorthand notation that can be used to do the same job that drawing diagrams does. Wouldn’t that be just as good?

Since we do not need to worry about asking a computer to read our notation, we can be very informal in what we invent. Here is a simple scheme:

• Use simple, numbered, English sentences to describe a process

• A sequence is just a series of sentences to be followed in order

• We will use the word IF to start a sentence where we are going to ask a question

  • Place the question inside parentheses on the same line as the IF.
  • For the processing we do if the answer is true, start that sentence with the word THEN, and indent that sentence a few spaces
  • For the processing we do if the answer is ‘’false’‘, start that sentence with the word ELSE and indent that sentence so it is even with the previous sentence (which must be there!)
  • Mark the end point where these two sub-processes rejoin with a single line containing the work ENDIF lined up with the matching IF.

• Use the word WHILE followed by a question in parentheses on a sentence where you want to start a looping structure.

  • Indent the sentence describing the process you do inside the loop
  • Place an ENDWHILE on a line by itself to mark the end of the loop. Line up this word with the WHILE above.

What goes inside this is just English - short and clear. This is called Pseudo Code because it is almost code, but not quite.

Here is a simple example - a pseudo code description for driving up Congress Ave.

1. Start the car and start driving
2. WHILE (I have not run into the Capitol)
    2.1 Drive to next intersection
    2.2 IF (the traffic light is green)
        2.2.T THEN Continue driving
        2.2.F ELSE Stop at the intersection until it is green
        ENDIF
   ENDWHILE
3. Stop before the guards yell at you!

Study this a while and make sure you see how it works. You are free to use any description of what you want to happen you like. The only requirement is that you use indentation to show where actions are part of a structure. Notice that I used outline-style numbering to number the sentences inside the structures, and even invented my own numbering scheme for the decision structure.

Note

See anything wrong with the pseudo-code above. Is every line a simple application of one of the structures? How about 2.2.F? What kind of structure is that? Well, for now, this will do. However, we will need to get a bit more clear about what we want to happen here before this is a good description of the steps we want to follow!

You might notice, also, that if we are neat in writing our sentences, we do not even need to number the lines. We can see where each structure is by studying the indent level of the sentences. However, if your sentences get long, it is helpful to use the numbers to clearly define where each sentence begins.

When you practice writing pseudo code, use any text editor and be neat! Your skills as a programmer will be judged (not just inside this class) by other programmer on how easy it is to read your work. Someone will have to fix any problems in your work, or may just want to study how you did something - and they expect to be able to see what is going on easily!

We will use pseudo code a lot as we learn how to build our solutions.

Are you hungry for more?

Let’s Bake a Cake!

What’s that you say, this is a programming course? Well sure it is. But we need to begin at the beginning – with a problem or task to work on.

We also need be able to analyze that problem or task in enough detail to be able to tell the computer exactly what we want it to do for us. So, let’s consider a simple problem - baking a cake, actually, let’s bake two cakes!

Is this silly? Maybe so - but maybe not!

The problem statement

We are going to start detailing the process of baking two cakes. To make things a bit more interesting, assume that you are going to write up the instructions and hand them to someone who has no idea how to bake a cake! (Do such people exist? Who knows?)

Doing some research

Since we are all experts in the kitchen, we could just start writing down what we need to do, right? I do not know about you, but if I tried that I might get a cake, but it might be a brick instead. We could Google and find out what to do, but I chose to go to a real authority on the process. I scanned the back of a cake mix box in my pantry! With due credit to Duncan Hines, here is an image of the back of my cake box:

Breaking the problem down

As you look over this image, you should start to see several key things. First, we have to collect a bunch of stuff (tools, ingredients, etc.) to do the job. Next we have to manipulate those tools and ingredients in just the right way to get a cake.

But wait, then we have to do the whole thing over again to get two cakes! Yikes!

The ingredients

At the top of the image we see that we are to collect the following ingredients:

• 1 and 1/3 Cups of water
• 1/3 Cup Vegetable Oil
• 3 large eggs

Oh yeah - I almost forgot!

• A box of cake mix.

The tools

What else do we need to do the job?

Study the entire image and see what you can come up with. Here is my list.

• An Oven (with temperature control)
• A metal or glass or dark or coated cake pan
• Shortening (isn’t that an ingredient?)
• Flour (another ingredient?)
• Large bowl
• Blender
• Timer
• Toothpick (!)
• Wire rack
• Frosting (another ingredient?)

That is a lot of stuff!

Is this list complete? Are there any problems with what we have written down yet?

Well, I did not remember that I have two cakes to bake, so I may need to modify this list a bit. What else needs to be modified?

• All ingredients must be doubled since we consume them for each cake.
• I might need additional tools to clean up the primary tools before I build the second cake.

The reason I am distinguishing between ingredients and tools is that I do not need two sets of tools, but I do need two sets of ingredients!

The sequence of steps

The image on the box has three steps. But we would see a few more if we look closely. Here is the sequence of actions we need to take to get the cake built!

1. Fire up the oven
2. If the cake pan is metal or glass, set the temperature to 350
3. If the cake pan is dark or coated, set the temperature to 325
4. Grease the pan sides and bottom with shortening
5. Flour the pan lightly
6. Pour cake mix into bowl
7. Pour water into bowl
8. Pour oil into bowl
9. Place eggs into bowl
10. Place bowl under blender
11. Start blender
12. Set blender speed to low
13. Set timer to 30 seconds
14. Start timer
15. Wait for timer alarm
16. Adjust blender speed to medium
17. Set timer to two minutes
18. Start timer
19. Wait for timer alarm
20. Stop blender
21. Pour mix from bowl into cake pan
22. Place cake pan into oven
23. Set timer according to cake pan size from chart
24. If cake pan is dark or coated increase timer time by 3-5 minutes
25. Wait for timer alarm
26. Remove cake pan from oven
27. Place pan on wire rack
28. Set timer for 15 minutes
29. Start timer
30. Wait for timer alarm
31. Frost cake

Oh phooey -

Do everything again (do we need to clean up first?)

Wow! Three simple steps on the cake mix box turned into 31 steps when we wrote down what we think is a complete list of things to do. A professional cook would blast through all of this without batting an eye.

Is this complete enough to work?

Once we think we know what we want to do, we need to step back and look things over. Maybe we can do a better job. Maybe we missed something. We need to make sure we are confident that our steps will really do the job!

Do you have any problems with what we have written down? I surely do!

• Steps 1-3: Pretty hard to mess these up as long as you can tell what kind of pan you have.
• Step 4: Hmmm! How much shortening do I need to use? About a half a pound should be right, right?
• Step 5: Same problem here. How much flour do I need to use? A 5 pound bag should be about right!
• Steps 6-8: Pretty clear here.
• Step 9: I do not think just placing the eggs in the mix is right, do you?
• Step 10: This one is fine
• Steps 11-20: We are doing some time sensitive stuff here, this needs more study!
• Steps 21-22: Nothing wrong here.
• Steps 23-25: This is pretty complex. And I forgot a step, right?
• Steps 28-30: More time sensitive stuff, but easier here.
• Step 31: I need help here. What do I do to do this? (Google it?)

Help is on the way!

What would you do to all of this if you had a helper who could do part of the work for you? Can you see any part of the sequence above that you could carve off and hand over to to your new helper?

Here is a mantra I have heard some programmers mutter:

I am lazy! I do not want to do the same job twice! I will build a simple tool that someone else can use to do that job over and over! I will teach the computer to do that job, then I will relax!

We obviously have a way to go to finish this off. But this should get you thinking about how to approach a problem for now.