{Go back to William's hexagon?}

Draft Created: 5/26/98; 11/7/03; 3/26/06; 4/29/07
This REFERENCE is only a skeleton of what it is intended to be.
FIBs & SAQs must be added.

       In the1960's it was mathematically proven that any programmable problem can be solved using only three logic control structures, sequence, selection, and repetition (iteration or recursion), that govern the flow of execution of any algorithm or program.   These along with modularization structures (procedures or functions) for "tasks" became the constructs (building blocks) of "structured programming", a strategy, developed in the 1970s, that facilitated the development of modular "programs" that were easy to develop, debug, and modify.  Previous programming languages, that did not have these structured programming constructs, relied on "branch" instructions and the infamous GOTO instruction to control the flow of program execution.  The GOTO instruction is a low level (equivalent to machine language) construct, that could jump to any specified line in a program).  This was a powerful construct, but it allowed (and some say encouraged) undisciplined software development that promoted "buggy" software. (Note that the branch instruction is a selection construct of low-level (machine rather than human oriented) languages, i.e. not a structured programming construct.)   Flowcharts, language-independent diagrams developed to illustrate the logic of algorithms, were oriented towards branch-based GOTO programming; the arrows of the flowcharts represented the GOTO statements.  Structured programming, on the other hand, is "GOTO-less programming" based on structured control constructs (selection and repetition) rather than branch constructs.   Consequently, during the rise of the structured programing paradigm, flowcharts fell out of fashion; they were replaced by pseudocode (concise, English-like statements that indicated the flow of the program logic).  However, "A picture IS worth a thousand words.", so the methodology of flowcharting was adapted to the format of structured programming.  Several versions of structured flowcharting appeared, but, unfortunately, none became a standard.  The structured flowcharting proposed by G. W. Williams, the Editor of Byte Magazine, in the March, 1981 issue (no online archive) most effectively illustrates the logic and format of structured program code.  Structured Algorithm Charts (SACs), presented below, are extensions of Williams ideas.  A comparison of the results of representing an algorithm using old-fashoned flowcharts to a representation using SACs is given here. 

Note that the SAC examples below (as well as in "my" references) are all "structured programming" examples that need to be modified if transferred to an OO environment; in particular, I/O would not be part of the operation/method algorithms in an OO architecture!

SAQ1: What is the (a) similarity and (b) difference between a "construct" and a "control structure"?

The goals of this learning module are:

1. to present the elements of SAC diagrams,
2. to illustrate the constructs of structured algorithms using SACs,
3. to illustrate the various ways the constructs of sturctured algorithms can be organized to achieve fundamental logic constructs, and
   
4. to illustrate classic" algorithmic problem solving examples in order to improve "problem solving skills" and "task automation skills".
   

1. SAC FORMAT
2. RULES FOR CONSTRUCTING A SAC
3. SAC REPRESENTATION OF THE FUNDAMENTAL INPUT-PROCESS-OUTPUT SEQUENCE
4. SAC REPRESENTATION OF SELECTION CONSTRUCTS
5. SAC REPRESENTATION OF REPETITION CONSTRUCTS
6. SAC REPRESENTATION OF CLASSIC ALGORITHMS:
1. Basic Input-Process-Output algorithm
2. Sequential Selections
3. Nested Selections
4. Complex Nested Selections (Triangle Classification)
5. Indefinite Iteration, Accumulation, and Counting
6. Definite Iteration
7. Nested Iterations
8. Simple Search Algorithm
9. Modularization and Top-Down Algorithm Design (IGNORE this because it illustrates the pre object-oriented technique of modularizing in software development, and is therefore virtually irrelevant in OOSD.).

    In order to be a completely general tool for developing or illlustrating structured algorithms that are clear, precise, and concise, a SAC must emphasize human-oriented logic (distinct selection and repetition constructs) rather than machine-oriented logic (branch construct used for both selection and repetition) of old-fashioned flowcharts.  The following rules reflect this principle.  (See Table SAC-1 for a reference to the symbols mentioned.)

1. SAC RULES:
1. A SAC must clearly distinguish the three fundamental control structures as well as invoke operations (of the same class or, implementing the dependency relationship, of other classes).
1. The three constol structures of structured programming include the following.
1. The sequence is represented by a simple vertical line connecting constructs (elements of of a SAC) in a top-down sequence.
2. Selection is represented by the traditional diamond; however, unlike traditional flowcharting, the lines connecting the possible selected constructs flow only from left to right and then, if necessary, top down.  (This restriction insures that all SAC diagrams are top down or left right; thus the developer can begin prototyping a SAC at the upper left corner of a "scratch pad", knowing that no logic construct will ever go up or to the left.)  See section 4 for the case/switch, if, and if-then-else forms of selection.
3. Repetition is represented by the only "new" symbol, the hexagon.  (It is new in that it was not present in older "goto oriented flowcharts"; the diamond was used in original flowcharts because iteration (looping) was viewed as a selection construct, i.e. the flow of control branched upwards to repeat a sequence of instructions or it branched downward to the instructions following the "loop".)  Like the lines of the selection construct, the lines of repition flow left right, top down.   See section 5.
2. A block of instructions is represented by by a rectangle or parallelogram with a descriptive name that explains the result of the instructions.  This implements "abstraction", i.e. the replacement of detailed instructions with a meaningful name.
1. The rectangle is the most general of the SAC constructs; it represents a process, that could contain any self-contained algorithm, i.e. its own SAC.
2. The parallelogram represents a process that serves as input/output.
3. A SAC must clearly represent operation invocations (or OO messages), i.e. transfer of control to operations which must return control, after the operation is completed, to the instruction following the invocation.  Such "calls" or messages are represented by adding double sides to the rectangle,  parallelogram, or hexagon (recursive operations) that represents a complete algorithm (possibly represented by a "subSAC").
2. A SAC should have a top-down flow of execution, containing only blocks or operation invocations, that is modified only by selection or repetition constructs.   Each selection or repetition construct interrupts the top-down (sequential) flow with a left-to-right line that links to a process or new (indented) top-down sequence.  (Most of the following examples show selection or repetition constructs with a single process but SAC EXAMPLES 7, 8, and 9 illustrate new, indented top-down sequences.)  The top-down, left-right format has two distinct advantages (not available in standard flowcharting).
1. SAC development space may be efficiently used.  Since all SACs are developed in a top-down, left-right order, the developer can draft a new SAC by starting the SAC in the upper left corner of a page, without worrying about the algorithm development ever requiring upward or right-left flows of control, that often occur in traditional flowcharting.
2. A SAC mirrors the indentation convention of structured code. Every time a SAC control structure has a line to the right, the corresponding code will be indented one level.  This also makes it easy to develop a SAC from existing code.
3. An optimum number of construct symbols should be used.  There should be enough different symbols to distinguish fundamentally different consturcts (control structures, processing, input/output, beginning/end symbols (including arguments and return values), and documentation).  On the other hand, too many symbols would defeat the purpose of representing the logic of an algorithm clearly, precisely, and concisely.  Therefore, the several possible varieties of the following general constructs will each be represented by a single symbol.
1. Iteration constructs (loop, while, do-while/repeat-until, for, etc.) are all representeed by a right pointed hexagon{Go back to Williams hexagon?}; they are distinguished by their names.
2. Selection constructs (if-then, if-then-else, or switch/case constructs) are all represented by a diamond; they are distinguished by their names.
3. Input/output constructs (input or output) are represented by parallelograms; they are distinguished by their names.
4. Processes and operation invocations are represented by rectangles; they are distinguished by their names.
5. Beginning and end symbols are represented by ovals; they are distinguished by their names.

TABLE SAC-1: SAC SYMBOLS

Beginnin or end of a SAC or subSAC.  The beginning symbol contains the algorithm name; the end symbol contains END for a program or Main method and RETURN(with output parameters, if needed) for a subSAC. Documentation, I/0 parameters, or declarations     Input or output statements       Statement or block of statements     Operation invocations (messages) in OOSD; module invocations (e.g. procedure or function calls) in structured programming.  May or may not have a subSAC.   Selection: (1) An "If" construct has a single line extending to the right linking to another construct.  (2) An "If-then-else"  has two lines, extending to the right, linking to other constructs.  (3) "Switch"/"case" constructs have multiple lines, extending to the right, linking to other constructs.   Repetition: (1) iteration (Loop, while, repeat-until (do-while), for, etc.); (2) recursion is represented by a double sided, left pointing hexagon, above.

2. RULES FOR CONSTRUCTING A SAC:

1. The flow of control should always be top-down (sequence) or left-right (initiation of selection or iteration); no arrows are used.
2. Only symbols from TABLE SAC-1 are used.
3. Operation invocations (messages to objects) are represented by the operation name, inclosed within a double sided symbols, e.g. rectangles (representing                        ()) parallelograms (representing                        ()), or right pointed pentagons (representing                        ()), e.g.

   or  or

Modules may refer to separate "subSACs" located elsewhere, which show the details of the module referenced by the name written within the symbol.  One should distinguish between modules which have separate subSacs (refresented by solid sided symbols, e.g.  ) and those which are purely descriptive, that is they do not have separate subSACs (e.g.  ).  If a language provides modules (methods, functions, or procedures) that allow parameter passing, these symbols represent "calls" to the subprogram named in the parallelogram or rectangle (e.g.   calls a subSAC method  that switches the values of parameters A and B).

4. There is only one entrance and one exit for each SAC construct.  Premature exits from a loop or operation are acceptable, but there is only one exit "point", the end of the construct.
5. The labelling of constructs is language dependent.  The language used in this presentation is English with a syntax based on Pascal-like languages, e.g. Pascal, Modula, Ada, etc.

1. Virtually all "programs" will first input "data", then process it, and output it as "information".

INPUT AND OUTPUT SACS

2. OO I/O....reflect that attributes are encapsulated with associated operations within classes; therefore, input/output is disassociated from processing.

4. SAC REPRESENTATION OF SELECTION CONSTRUCTS:

This section illustrates the format and use of SAC selection constructs by discussing the simplest possible examples of fundamental selection categories.  It reviews the main concepts in selection control structures and the basic techniques used to employ selection correctly and efficiently.  The presentation is via example, the classification of a grade into three categories.  Note that the classification into three categories is the simplest selection task that still illustrates all the main features of selection.  Also note that the following is completely language independent.

THE TASK: Design an algorithm component (portion of a SAC) that, depending on the value of the score, S, classifies the grade, G, into three categories: G is "High" if S = 9 or 10, "Medium" if S = 6-8, or "Low" if S =0-5.

4.1 Nested If Implementation of THE TASK (the most efficient way to classify three mutually exclusive items):

1. Fill in the constructs, below, to make the control structure, categorize the grade G as shown.






2. The real advantage of the SAC approach to algorithm development is that leaving the construct specification details blank allows us to think our way through the logic of a task, without getting "bogged down" with the details.  In this case, specifiying the categores while leaving the selection conditions blank helps quickly generate the most efficient selection conditions necessary to fulfill the task.  Note that the SAC actually guides us to the solution.  This graphically illustrates that the SAC technique is a "power tool" for logical thinking and a key to algorithm development.

4.2 Switch (case) Implementation of THE TASK (three mutually exclusive categories):

1. The following selection symbol represents a switch (languages using ANSI standard C terminology) or case ( Pascal-like languages, e.g. Modula and Ada).  Fill in the case construct and label the branches so that this control structure is equivalent to that in section 3.1, above.

4.3 Sequential Implementation of THE TASK (three mutually exclusive categories -  inefficient ):

1. Fill in the blanks in the following SAC to make the logic equivalent to the previous implementations of THE TASK.






2. An important question now arises: Is the sequential if implementation of classification as "good" as the nested if implementation?  To answer this, consider two cases.
1. Assume that your if statements in the sequential implementation were the same as those in the nested if implementation, i.e. the first if had s >= 8 as its condition and the second had the condition S >= 6.
1. Do a trace for a complete set of test data, e.g. for values of 9, 7, and 3.
2. Hopefully you detected the logic error characteristic of such sequential selections.  Note that the logic works for two of the ghree values but not the third.  ( This should emphasize the importance of doing a trace of any logic construct with a complete set of test data!) thus the sequential if implementation of mutually exclusive classification is not only more inefficient than the nested if implementation, it is more dangerous because it is easy to overlook subtle bugs!
3. The sequential if algorithm can be made to work.  If you haven't alreay done so, change the conditions to make the logic correct.  ( Hint: use compound conditions.)
2. Even if the sequential if implementation does work it is essentially less efficient that the nested if implementation for mutually exclusive categories like those in this example.

SAQ 11: Why, for classification of mutually exclusive items, is the sequential if implementation necessarily less efficient than the nested if implementation?
SAQ 12: Why do we use an if-the and an if-the-else instead of two if-then-elses in the sequential if implemenation of this example.
SAQ 13: Incorporate error traps, equivalent to those in the previous implementations.  Does this help you answer the first SAQ under section 4.1?  It should!)

5. SAC REPRESENTATION OF REPETITION CONSTRUCTS:

1. Repetition in Algorithms has two special cases, iteration (looping) and recursion.





 
1. Iteration is the primary repetition control construct of imperative programming languages but recursive procedures and functions are avaiable in structured programming languages and recursive methods are avaiable in all OOPL.
2. Recursion is the primary repetition construct of declarative programming languages, which seldom have iteration constructs.
2. Iteration Categories:
1. Indefinite Loops repeat a block of instructions as long as a looping condition is true, i.e. something has to be true for the repetition to continue; when this condition changes to false the loop is exited.
1. the Loop construct is the most general iteration construct.  There is no looping condition associated with the loop itself; selection constructs  within the loop body are used to exit the loop.





 
2. the While  construct:

SAC for a Generic While Loop	SAQ: Equivalent using a Loop

3. the Repeat until construct (do while in languages based on C):




SAC for a Generic Repeat-Until Loop	SAQ: Equivalent using a Loop

2. A Definite loop is one where the number of repetitions can be determined at the beginning of a loop construct.
1. The for loop is a count-controlled definite loop.  The labelling convention used below is based on Pascal-like languages, e.g. Modula, Ada, etc.

SAC for a Generic For Loop	SAQ: Equivalent using a Loop

1. the repeat loop is the simplest type of loop, e.g. the loop body of a repeat 4 would be executed exactly four times.

SAQ 14: What is the (a) similarity and (b) difference between (1) iteration and recursion,  (2) loop, while loop, and repeat loop, and (3) indefinite loop and definite loop?
SAQ 15: A repeat loop can be simulated using a while loop.  How?
SAQ 16: What looping cases can not be done using a while or repeat loop?

6. SAC REPRESENTATION OF CLASSIC ALGORITHMS