8 Measuring internal product attributes: structure

8.2 Control-flow structure, sequencing and nesting

There are just two legitimate operations we can use to build new flowgraphs from old: sequencing and nesting.

We denote the sequence of two programs A and B as A;B. Then F(A;B) = F(A);F(B), where F(A);F(B) means that the stop node of F(A) is merged with the start node of F(B) to become an ordinary node, see Figure 8.4. This is called sequencing.

Consider the program P: if b then x else y. Assume that we construct a new program from this by substituting a program A instead of x. We could write this as "P with A substituted for x".

Then F(P with A substituted for x) means the flowgraph where 1) the start node of F(A) is merged with the node x, and 2) the arc(s) to the stop node of F(A) and its stop node are replacing the out-going arc from x and its end node, see Figures 8.5 and 8.6.

This is called nesting. For nesting x must be a procedure node.

By reversing the operations of nesting and sequencing we arrive at some flowgraphs that cannot be decomposed non-trivially by sequencing or nesting. These flowgraphs are called prime flowgraphs.

All the flowgraphs in Figures 8.2 and 8.3 are prime flowgraphs (note P_n is special).

8.2 Control-flow structure, structuredness

Depending of our prime flowgraphs S, we say that a family of graphs are S-structured, if it satifies the following recursive rules:

1. Each member of S is S-structured
2. If F and F' are S-structured, then so are F;F' and F(F') (whenever nesting of F' on F is defined.
3. No flowgraph is an S-structured graph unless it can be shown to be generated by a finite application of the above steps.

Graphs with S^D = {P₁, D₀, D₂} are often called the structured graphs. A larger useful class is the one with S = {P₁, D₀, D₁, D₂, D₃, D₄, C_n (for all n), L₂}.