Essential complexity: Difference between revisions

Essential complexity has been defined in various ways by various people. One definition is as an antonym to accidental complexity. Another definition is a number attempting to measure how close (or far) a given program is from being a structured program.

Antonym to accidental complexity

Essential complexity refers to a situation where all reasonable solutions to a problem must be complicated (and possibly confusing) because the "simple" solutions would not adequately solve the problem. It stands in contrast to accidental complexity, which arises purely from mismatches in the particular choice of tools and methods applied in the solution.

This term has been used since, at least, the mid-1980s. Turing Award winner Fred Brooks has used this term and its antonym of accidental complexity since the mid-1980s. He has also updated his views in 1995 for an anniversary edition of Mythical Man-Month, chapter 17 "'No Silver Bullet' Refired".

Measure of the "structureness" of a program

Essential complexity is also a numeric measure defined by McCabe in his highly cited, 1976 paper better known for introducing cyclomatic complexity. McCabe, defined essential complexity as the cyclomatic complexity of the reduced control flow graph after iteratively replacing (reducing) all structured programming control structures, i.e. those having a single entry point and a single exit point (for example if-then-else and while loops) with placeholder single statements.

McCabe's reduction process is intended to simulate the conceptual replacement of control structures (and actual statements they contain) with subroutine calls, hence the requirement for the control structures to have a single entry and a single exit point. (Nowadays a process like this would fall under the umbrella term of refactoring.) All structured programs evidently have an essential complexity of 1 as defined by McCabe because they can all be iteratively reduced to a single call to a top-level subroutine. As McCabe explains in his paper, his essential complexity metric was designed to provide a measure of how far off this ideal (of being completely structured) a given program was. Thus higher essential complexity numbers, which can only be obtained for non-structured programs, indicate that they are further away from the structured programming ideal.

To avoid confusion between various notions of reducibility to structured programs, it's important to note that McCabe's paper briefly discusses and then operates in the context of a 1973 paper by S. Rao Kosaraju, which gave a refinement (or alternative view) of the structured program theorem. The seminal 1966 paper of Böhm and Jacopini showed that all programs can be [re]written using only structured programming constructs, (aka the D structures: sequence, if-then-else, and while-loop), however, in transforming a random program into a structured program additional variables may need to be introduced (and used in the tests) and some code may be duplicated.

In their paper, Böhm and Jacopini conjectured, but did not prove that it was necessary to introduce such additional variables for certain kinds of non-structured programs in order to transform them into structured programs. An example of program (that we now know) does require such additional variables is a loop with two conditional exits inside it. In order to address the conjecture of Böhm and Jacopini, Kosaraju defined a more restrictive notion of program reduction than the Turing equivalence used by Böhm and Jacopini. Essentially, Kosaraju's notion of reduction imposes, besides the obvious requirement that the two programs must compute the same value (or not finish) given the same inputs, that the two programs must use the same primitive actions and predicates, understood as expressions used in the conditionals. Because of these restrictions, Kosaraju's reduction does not allow the introduction of additional variables; assigning to these variables would create new primitive actions and testing their values would change the predicates used in the conditionals. Using this more restrictive notion of reduction, Kosaraju proved Böhm and Jacopini's conjecture, namely that a loop with two exists cannot be transformed into a structured program without introducing additional variables, but went further and proved that programs containing multi-level breaks (from loops) form an hierarchy, such that one can always find a program with multi-level breaks of depth n that cannot be reduced to a program of multi-level depth less than n, again without introducing additional variables.

McCabe notes in his paper that in view of Kosaraju's results, he intended to find a way to capture the essential properties of non-structured programs. He proceeds by first identifying the control flow graphs corresponding to the smallest non-structured programs, which he uses to formulate a theorem analogous to Kuratowski's theorem, and thereafter introduces his notion of essential complexity in order to give a scale answer ("measure of the structureness of a program" in his words) rather than a yes/no answer to the question of whether a program's control flow graph is structured or not. Finally, the notion of reduction used by McCabe to shrink the CFG is not the same as Kosaraju's notion of reducing flowcharts. The reduction defined on the CFG not know or care about the program's inputs, it is simply a graph transformation.

For example, the following C program fragment has an essential complexity of 1, because the inner if statement and the for can be reduced, i.e. it is a structured program.

   for(i=0;i<3;i++) {
      if(a[i] == 0) b[i] += 2;
   }

The following C program fragment has an essential complexity of four; its CFG is irreducible. The program finds the first row of z which is all zero and puts that index in i; if there is none, it puts -1 in i.

  for(i=0;i<m;i++) {
    for(j=0;j<n;j++) {
      if(z[i][j] != 0)
        goto non_zero;
    }
    goto found;
non_zero:
  }
  i = -1;
found:

The idea of CFG reducibility by successive collapses of sub-graphs (ultimately to a single node for well-behaved CFGs) is also used in modern compiler optimization. The areas of the CFG that cannot be reduced to "nice" programs, technically called natural loops (which have a rather involved definition that we elide in this article) are called improper regions, and these regions end up having a relatively simple definition: multiple-entry strongly connected components of the CFG. (Multiple exits do not cause problems to modern compilers. Thus the simplest improper region is a loop with two entry points.) Improper regions cause additional difficulties in optimizing code.

See also

• History of software engineering
• Software prototyping (one of the main strategies against essential complexity in "No Silver Bullet")
• Decision-to-decision path
• Occam's Razor
• No silver bullet
• Cyclomatic complexity

Further reading

For the first sense of the term:

• Brooks, Fred P. (1986). "No Silver Bullet - Essence and Accident in Software Engineering". Proceedings of the IFIP Tenth World Computing Conference: 1069–1076.
• Brooks, Fred P. (April 1987). "No Silver Bullet - Essence and Accidents of Software Engineering". IEEE Computer. 20 (4): 10–19. {{cite journal}}: Unknown parameter |authormask= ignored (|author-mask= suggested) (help)

• Brooks, Fred P. (1995). "Chap. 17". 'No Silver Bullet' Refired (Anniversary Edition with four new chapters ed.). Addison-Wesley. ISBN 0-201-83595-9. {{cite book}}: |work= ignored (help); Unknown parameter |authormask= ignored (|author-mask= suggested) (help)