Content deleted Content added
Line 15:
'''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-->
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.<ref name="mccabe76"/>{{rp|317}} (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.<ref name="mccabe76"/>{{rp|318}} 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.<ref name="mccabe76"/>{{rp|317}} Thus
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.<ref name="WattFindlay2004">{{cite book|author1=David Anthony Watt|author2=William Findlay|title=Programming language design concepts|year=2004|publisher=John Wiley & Sons|isbn=978-0-470-85320-7|pages=228}}</ref>
| |||