music

OSdata.com

control structures

summary

    Control structures are used to control the flow of a program.

free computer programming text book project table of contents If you like the idea of this project, then please donate some money. more information on donating

control structures

    Control structures are used to control the flow of a program.

    Control structures and data structures are the stuff that programs are made of.

    This is an informal discussion that will serve as background so that the reader will understand the context of the next few chapters.

    In modern computer programming (called structured programming there are three basic control structures:

1. sequence
2. choice or decision
3. loop or repetition

sequence

    A sequnce is a series of steps. Classic examples include, calculations, manipulations of data, and running subroutines or functions.

    One very important note is that in structured programming, a sequence must have only one entry point and only one exit point. While structured programming does allow the use of three different control structures, a group or block of program commands must always have exactly one entry and exactly one exit.

    A common example of a sequence is finding an average of several numbers. The following example assumes exactly five total numbers being added.

    1.a. set the running subtotal to zero (an example of initialization)
    1.b. set the count of numbers to zero (an example of initialization)
    2.a. add the first number to the running subtotal
    2.b. add one to the count of numbers (an example of incrementing)
    3.a. add the second number to the running subtotal
    3.b. again increment (add one to) the count of numbers
    4.a. add the third number to the running subtotal
    4.b. increment (add one to) the count of numbers
    5.a. add the fourth number to the running subtotal
    5.b. increment the count of numbers
    6.a. add the fifth number to the running subtotal
    6.b. increment the count of numbers
    7. divide the running subtotal by the count of numbers

    The following shows the example with actual numbers:

step	next number	running subtotal	count of numbers
1a	N/A	0	-
1b	N/A	0	0
2a	6	0+6=6	0
2b	-	6	0+1=1
3a	2	6+2=8	1
3b	-	8	1+1=2
4a	5	8+5=13	2
4b	-	13	2+1=3
5a	9	13+9=22	3
5b	-	22	3+1=4
6a	3	22+3=25	4
6b	-	25	4+1=5
25 / 5 = 5		the average is 5

    The most simple or elementary steps of a sequence or things like the simple computations in the example above or other basic computer operations. other examples would be making a copy of a piece of data (if this was a formal discussion, I’d call it a piece of datum), a single logical operation (AND, OR, NOT, etc, if you recognize those), a rotation or shift, a single text substittion, concatenating text, or the deletion, insertion, or modification of a piece of data into a data base, list, tree, or other data structure.

    If the programming language allows combining several operations into a single instructure, the instruction is often viewed as a signle sequential step. For example, the following computation includes two multiplications, an exponentiation, an addition, and a subtraction, but is viewed collectively as a single sequential step (note that because this is an informal discussion, none of these examples are intended to be from any actual programming language):

x = 3a² + 2b - c
or
x := 3*a**2 + 2*b - c;

    In computer programming, sequential steps can be many things other than arithmetic cmputations.

    The grouping of a sequence of steps (as well as a grouping with any combination of the three basic control structures) is often referred to as a block of code. The block of code may be either a concept or may be an actual programming structure in the programming language. A block of code as a single group can be viewed as a sequential step, even if the block internally contains other control structures.

    A much more powerful version of a sequential step is a subroutine or function. Note that in some programming languages there is no disticntion between a subroutine and a function, while in other programming languages there is a strong difference between the two. We won’t get into those details here.

    The basic idea of a function is similar to the basic idea of a function in algebra. A function takes a value (or sometimes more than one value) as an input and produces a single answer or value as a result. Common examples include trignometric functions, such as sine, cosine, and tangent, which might appear as follows:

x = cos(a) + sin(b) + tan(c)

    While almost all modern computers have a single hardware instruction for trignometric functions, most functions have to be written by a programmer, whether they are built-in (supplied by the compiler) or user defined (written by the programmer).

    An example of a function that would have several internal (hidden) steps, as well as more than one input value, would be finding the greatest common denominator (see example below). Even though there are several steps hidden inside the function, the function is treated as a single sequential step.

x := gcd(a,b);

    A subroutine is also a set of instructions that are hidden away and treated as one group and therefore a single sequential step. For languages that distinguish between subroutines and functions, a subroutine normally doesn’t return a result, while a function normally does return a result.

    A subroutine can be used twhen the same piece of coding will appear in many different places in a prgram. Rather than writing it out each time individually, the subroutine would be written once and a call to the subroutine would be inserted everywhere you would have otherwise had to write it out repeatedly. This can make the program much easier to maintain, because it is much easier to fix, change, or update one subroutine than to search a giant program listing for every place the same little piece of coding appears.

    A subroutine can also be used to assist in creating a top-down structured program, increasing readability.

    The use of subroutines as single sequential steps allow for decomposing a complex program from top-down, a basic method in modern structured programming. Consider the following example:

    Initialize;
    OpenDataFiles;
    ReadDataFromFiles;
    CloseFiles;
    PerformCalculations;
    SortData;
    PrepareReport;
    PrintReport;
    Finish;

    Even a non-programmer could probably figure out what is going on and maybe even give useful feedback on important steps that might be missing. By hiding all the details of each major step, it is easier for the programmer to visualize the structure of the program, making it more likely that the programmer will create a bug-free program that other programmers can easily modify for changing circumstances for years or decades into the future.

    Using the idea of functional decomposition, the programmer might also use this same approach of a sequence of subroutines at lower levels. For example, consider the subroutine PrepareReport, which might be:

    Initialize;
    PrepareReportHeader;
    PrepareMainSection;
    PrepareExceptionSection;
    PrepareReportFooter;
    Finish;

    Obviously each of these sequential steps is its own subroutine with its own hidden steps.

    Another important concept is the utility. There are some functions or subroutines that are so commonly used that they are considered to be utility routines or utlity function. The built-in functions of a programming language are a good example. A group of programmers will often share a library of commonly used utility functions and subroutines.

choice or decision

    A decision is the act of making a choice. The two most commonly encountered decisions are the IF-THEN-ELSE and the CASE or SWITCH. An IF-THEN-ELSE is a straightforward decision between two different chocies. A CASE or SWITCH is picking an option between a long list of choices.

    The IF-THEN structure is pretty straght forward. Your program tests to see if something is true. If the test is true, then your program does something (usually a sequence, although it can be any combination of the three control structures).

    For example, if you are tall enough, then you may go on the amusement park ride (which also implies that if you are not tall enough, then you can’t)..

    The thing being tested in an IF is called the condition.

    The two most common tests are for the condition to be TRUE or for the condition to be FALSE. Sometimes it is easier to write a program with a negative test (testing for a FALSE condition) rather than a positive test (testing for a TRUE condition). Sometimes it makes the program easier to read and understand (and therefore easier and less expensive to maintain over years or decades) for the test to be for a FALSE condition.

    While the basic control structure is testing for TRUE or FALSE, the test condition often can be for things slightly more complex conceptually, such as equality (are two thing sexactly equal), inequality (greater than or less than), length, time, emptiness, fullness, completion, incompletion, etc.

    Note also that we can have a simple test (only one condition is tested) or a compound test (multiple conditions are tested). Compound tests have potential problems in different programming languages, which will be discussed in detail when we get to the appropriate section.

    The THEN part is what is done if the condition passes (I’d say if the condition is true but you might have been testing for the condition to be false). The THEN part can be a single sequential step, a block (or group) of sequential steps, a block or group of any combination ot the three control structures, or a function or subroutine.

    After the test is completed and the action possibly taken, the program continues on to the next item in the sequence of steps. This is an important feature of structured programming: exactly one entry and exactly one exit. It is a disaster for maintenance if the program can start wandering all over the place.

    Using our average example, we might be interested in testing for zero divide before performing a division. Both elementary algebra and computer hardware reject any attempt to divide by zero (and the computer hardware can reject your attempt by freezing or otherwise crashing).

    In our sequence example for finding an average, we never actually stated where the numbers to be averaged came from. They just were there when we needed them. What would happen if we never received the input numbers? When we attempted to do the division of the subtotal by the count, the count could have still been zero. The program crashes.

    We could place a test for the count being zero just before we attempt to divide:

    IF count NOT EQUAL zero (0)
        THEN average = subtotal / count;

    This avoids the program crashing.

    We could also place a test for the existence of the numbers, somewhere near the start of the sequence (as one of the initialization steps). We would then place the entire rest of the block of sequential steps into the THEN portion, skipping the entire process if we don’t actually have our five input numbers. This approach would not only avoid a divide by zero crash, but also avoid wasting a bunch of computation time on something that is going to fail anyway.

    The IF-THEN-ELSE structure gives two different paths, which must combine back together at the end to maintain structured programming.

    To use our average example, we could text for the count not being zero. If the count is not zero, we perform the THEN portion (single sequential step, block of code, subroutine, etc.), which in this example would be the division step. If the count is zero, then we would perform the ELSE portion (single sequential step, block of code, subroutine, etc.).

    In this case, we could report that there is an error, so that the reader will know why he or she didn’t receive an answer for the average.

    IF count NOT EQUAL zero (0)
        THEN average = subtotal / count
    ELSE
        REPORT an ERROR;

    I previsously mentionedcompund testing (testing for more than one condition at a time). Another variation is the nested test. In the nested IF, we make a test and then in either the THEN or the ELSE part (or both), we follow up with an additional test. The nesting can be continued to as many levels as needed.

    As an example, say we were searching through a list of people for either a blue-eyed man or a brown-eyed woman. At the top level fo the IF-THEN-ELSE we would test for man or woman. Then we would nest additional testing. If the THEN part was for the condition of the person being a woman, the nested test would be for brown eyes, and in the ELSE part (the person is a man, assuming only two choices) we would test for blue eyes.

    IF person is a WOMAN
        THEN IF person has brown eyes
            THEN successful match (woman with brown eyes)
            ELSE unsuccessful match (woman without brown eyes)
        ELSE (must be a MAN) IF person has blue eyes
            THEN successful match (man with blue eyes)
            ELSE unsuccessful match (man without blue eyes)

    Nested IFs can become very complicated and difficult to read and prone to mismatch errors. This will be discussed more in the appropriate section.

    The other important decision structure is the CASE structure. Technically there is no need for a case structure, because all case structures can be written as a NESTED IF structure instead. Because readability is vital for successful long term maintenance of a prorgam, most modern langauges have a CASE structure (sometimes called a SWITCH structure).

    In the basic CASE structure, we have one test and many possibilities. Each possibility is matched with a single sequential step, block of structured code, or subroutine. Normally only one of the choices is performed.

    An example using a test for eye color:

    CASE of eye color:
        BLUE EYES:     do the blue eyes block of code
        BROWN EYES:    do the brown eyes block of code
        GREEN EYES:    do the green eyes block of code
        GRAY EYES:     do the gray eyes block of code
        OTHERWISE:     do special exception block of code

    Notice the existence of the OTHERWISE choice. This covers the exception cases where you had unexpected results.

    Without getting into messy details now, note that some programming languages allow a fall through. For example, we might have wanted to do one extra step for blue eyes than we did for brown eyes, but that otherwise the two choices shared the same steps. We could have the one extra step occur in the blue eyes case, then fall through to the brown eyes and do all of the brown eyes steps. If the CASE determined that there were brown eyes, it would skip the extra blue eyes step and only do the brown eyes steps. I hope I didn’t just confuse you. If that doesn’t make sense, don’t worry about it for now.

loop or repetition

    A loop or repetition is the act of repeating an action or actions. A lot of the power of computers is being able to do repetitive choices over and over (sometimes millions or more times).

    This is one of the most important and powerful features of a computer — the ability to repeatedly do something over and over in really large numbers of repetitions.

    The most basic loop or repetition structure is known as the DO LOOP. This is also called the FOR LOOP. Another name for this is the Iterative DO.

    In the DO LOOP, you instruct the computer exactly how many times you want it to repeat a particular task and it does it exactly that many times (assuming no crashes or bugs).

    Please remember that the examples in this informal discussion are not from any actual programming language. These are designed to illustrate the basic principles.

    Using our average example from above, you will notice that after the first (initialization) steps (1.a and 1.b.) and before the last (final computation) step (7), that each of the pairs of steps are exactly the same. Instead of writing out each and every step, we could describe the two basic steps and put them into a DO LOOP:

    Initialize;
    BEGIN
        Subtotal := 0;
    END;
    DO five times;
    BEGIN
        Add the next number to the Subtotal;
    END;
    Finish;
    BEGIN
        Answer is Subtotal divided by 5;
    END;

    In most programming languages there is some variation of a loop count variable. The number of times to loop is established by setting the initial value of the loop count variable and setting the limit for the the number of times to repeat the DO LOOP.

    Initialize;
    BEGIN
        Subtotal := 0;
        IF there are no numbers available to average
            THEN REPORT an ERROR and STOP;
    END;
    DO Count := 1 TO 5;
    BEGIN
        Add the next number to the Subtotal;
    END;
    Finish;
    BEGIN
        Answer is Subtotal divided by Count;
    END;

    You may notice that we started the count at one rather than zero. We did this to have the DO LOOP perform exactly five repetitions with the count of numbers matching the standard counting numbers.

    You may also notice that we used the Count outside of the actual DO LOOP. Note that in many prgramming languages you can not actually use the loop count variable outside the loop (although you can usuually use it inside the DO LOOP). A common work-around is to create an extra copy of the count variable that we can use outside the DO LOOP:

    Initialize;
    BEGIN
        Subtotal := 0;
        NumberCount := 0;
        IF there are no numbers available to average
            THEN REPORT an ERROR and STOP;
    END;
    DO LoopCount := 1 TO 5;
    BEGIN
        Add the next number to the Subtotal;
        Increment (add one to) the NumberCount;
    END;
    Finish;
    BEGIN
        Answer is the Subtotal divided by the NumberCount;
    END;

    The loop count variable is considered to have a start value and a finish value. The loop count variable is often called the control variable. The starting value for the control variable is often called the initial value. The finishing value for the control variable is often called the limit value.

    Some programming languages will allow greater flexibility in how the loop count variable is used. Many programming languages give the choice of counting up or counting down. Computers are really good at counting down to zero. This shouldn’t matter much with modern computers (where the ability to easily read and understand someone else’s program is far more important than a nanosecond saved somewhere), but you will certainly encounter this when working on old programs from back in the days when this time difference was important.

    Most prgramming languages allow the initial value and limit value to be variables. This allows the flexibility of the program deciding these values while it is running rather thaan the programmer having to know the values in advance when the program is written. This is known as the difference between run time and compile time.

    Some programming languuages allow the step to be something other than a step up or down by one (increment and decrement). An example might be a loop that only works on odd or even numbers (the initial value might be one (1) for odd numbers and either zero (0) or two (2) for even numbers).

    In the following example, the loop would be performed a total of 10 times and each time through the loop the count would be a multiple of ten (for some reason we need multiples of ten in the work we are doing).

DO COUNT := 10 to 100 STEP UP BY 10;

    If the programming language allows for steps other than increment, the size of the step is known as the step value or the modification value. There is also the possibility that the step value can be a variable and determined at run time.

    Some programming languages allow a lot more variations, such as counting from 1 to 99 by steps of 1 and then coutning from 100 to 1,000 by steps of 100., or even more complicated versions. Because this is an informal discussion, I won’t get into those complexities here, but I wanted you to know that they can exist.

    The next important repetition or loop structure is the DO WHILE loop.

    Historically the first looping structure available was the iterative do loop. The DO WHILE loop was the form of loop used in the original proof of the concept of structured programming.

    In the DO WHILE loop there is a condition test and the loop is repeated over and over again as long as the condition remains true.

    We can use the DO WHILE loop to add flexibility to our average example. So far we have always had to have exactly five numbers to average. Using this method, we would need to write a whole new program for a list of six numbers to average and another program for a list of ten numbers to average. This would get ridicously out of hand in a hurry.

    By using a DO WHILE loop, we can write one program for any size list of numbers to average:

    Initialize;
    BEGIN
        Subtotal := 0;
        Count := 0;
        IF there are no numbers available to average
            THEN REPORT an ERROR and STOP;
    END;
    DO WHILE there are still numbers available;
    BEGIN
        Add the next number to the Subtotal;
        Increment (add one to) the Count;
    END;
    Finish;
    BEGIN
        IF count NOT EQUAL zero (0)
            THEN average := subtotal / count;
        ELSE
            Report ERROR;
    END;

    An important note regarding the DO WHILE loop (and loops in general) is that the loop needs to come to an end some time. If the loop never ends it is called an infinite loop and is one of the reasons that a program or computer freezes. The computer hasn’t actually stopped working (which is implied by the word freeze). Rather the program is stuck in a loop that it will never finish (until you turn the computer off, reboot, stop the program, etc.).

    It is important to check for and avoid inifinite loops. Make sure that any loop you write will eventually come to an end.

    The third major repetition or loop structure is the DO UNTIL loop.

    In the DO UNTIL loop there is a condition test and the loop is repeated over and over again until the condition becomes true.

    The DO UNTIL is actually not an appropriate choice for our avaerage example, but it will work and you are already familiar with this example.

    Initialize;
    BEGIN
        Subtotal := 0;
        Count := 0;
        IF there are no numbers available to average
            THEN REPORT an ERROR and STOP;
    END;
    DO UNTIL there are no more numbers available;
    BEGIN
        Add the next number to the Subtotal;
        Increment (add one to) the Count;
    END;
    Finish;
    BEGIN
        IF count NOT EQUAL zero (0)
            THEN average := subtotal / count;
        ELSE
            Report ERROR;
    END;

    As with the the DO WHILE loop, it is vitally important to make sure that your DO UNTIL loop will eventually end and avoid putting your program into an infinite loop.

    The Iterative DO LOOP is perfomed the exact number of times the programmer specified.

    The DO WHILE loop is perfomed zero or more times.

    The DO UNTIL loop is perfomed at least once.

    The key difference between the DO WHILE loop and the DO UNTIL loop is that the condition test comes at the beginning of the DO WHILE loop and the condition test comes at the end of the DO UNTIL loop.

    The DO WHILE loop might never be performed (if the test condition fails before the first attempt to loop).

    The DO UNTIL loop will always be performed at least once (because the condition test occurs after the first pass of the loop).

    Just as it was possible to have nested IF structures, it is also possible to have nested loop structures, placing one or more loops inside another loop. See the following example:

    DO OutsideCount := 1 TO 100 STEP UP BY 1;
    BEGIN outer loop
        DO InsideCount := 1 TO 1000 STEP UP BY 1;
        BEGIN inner loop
            some sequence of steps
        END inner loop;
    END outer loop;
    STOP PROGRAM.

    It is possible to nest the loops more than two deep. Notice that we use indentation to make it clear to the reader which loop (inner or outer) we are talking about. Your computer doesn’t need the indentation, but anyone trying to read and modify your program a few years later (even you) will really appreciate the indentation.

    It is possible to have the inner and outer loops be different kinds, such as an Iterative DO LOOP inside a DO WHILE LOOP.

JOVIAL

    The following material is from the unclassified Computer Programming Manual for the JOVIAL (J73) Language, RADC-TR-81-143, Final Technical Report of June 1981.

    A full complement of language constructs permits looping,
    branching, conditional execution, procedure or function calls,
    and assignment of values to data elements.

    Chapter 1 INTRODUCTION, page 1

    1.1.6 Flow of Control

    For structured flow of control, JOVIAL has an if-statement, a
    case-statement, and a loop-statement with an optional exit-
    statement.  Examples of these statements follow.

    Chapter 1 Introduction, page 10

other

   “Common sense also leads us to the recognition of the characteristics of programs that makes the programs maintainable. Above all, we look for programs that exhibit logical simplicity — failing that, at least clarity. The earmarks of simplicity and clarity include modularity (true functional modularity, not arbitrary segmentation) and a hierarchical control structure, restrictions on each module’s access to data, structured data forms, the use of structured control forms, and generous and accurate annotation.
   “Much has been said of the technical members of this set in earlier pages. Of good annotation, there are several features that must be included. First, the header information of each procedure should provide a concise statement of the procedure’s external specifications, including a description of input and output data. Each section of the procedure should be introduced by comments identifying the section’s relation to the external characteristics. Finally, comments within each section should relate groups of statements to the program’s documented description. This last is automatically achieved by using design language statements as source code comments.” —Robert Dunn. Software Defect Removal. McGraw-Hill, 1984, pg. 308

---

free music player coding example

    Coding example: I am making heavily documented and explained open source code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).

    View music player in action: www.musicinpublic.com/.

    Create your own copy from the original source code/ (presented for learning programming).