Content deleted Content added
has a "d" in there |
|||
Line 12:
year=1996}}</ref>
== Measure of the "
'''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 structure]]s, 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.<ref name="mccabe76">{{cite journal| last=McCabe| date=December 1976| journal=IEEE Transactions on Software Engineering| pages=308–320| title=A Complexity Measure|format=}}</ref>{{rp|317}}<ref>http://www.mccabe.com/pdf/mccabe-nist235r.pdf</ref>{{rp|80}}<!-- note that the original paper has an error in the final formula for ev, but this is corrected the technical report-->
Line 21:
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.<Ref name="K">{{cite journal|title=Analysis of structured programs|author=S. Rao Kosaraju|journal=J. Computer and System Sciences|volume=9|number=3|date=December 1974|doi=10.1016/S0022-0000(74)80043-7}}</ref>{{rp|236}} 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, the latter 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 exits 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 a 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 breaks with depth less than ''n'', again without introducing additional variables.<Ref name="K"/><Ref>For more modern treatment of the same results see: Kozen, [http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf The Böhm–Jacopini Theorem is False, Propositionally]</ref>
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 in terms of their control flow graphs.<ref name="mccabe76"/>{{rp|315}} He proceeds by first identifying the control flow graphs corresponding to the smallest non-structured programs (these include branching into a loop, branching out of a loop, and their if-then-else counterparts) which he uses to formulate a theorem analogous to [[Kuratowski's theorem]], and thereafter he introduces his notion of essential complexity in order to give a scale answer ("measure of the
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.
| |||