Essential complexity: Difference between revisions

Revision as of 10:56, 24 July 2014

Revision as of 06:42, 1 August 2014

Line 1:

{{About-distinguish2|the numerical measure of a program's "structuredness" defined by McCabe|the notion antonymic to accidental complexity used by Brooks in [[No Silver Bullet]] and subsequent works.}}

{{split|date=July 2014}}

'''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 programming|structured 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 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 in the technical report-->

== Antonym to accidental complexity ==

{{mergeto|No Silver Bullet|section=yes|date=July 2014}}

'''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.{{cn|date=July 2014}} 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".<ref name="Brooks, Proc. IFIP" >[[#Brooks, Proc. IFIP|Brooks, Proc. IFIP]]</ref><ref>Brooks, IEEE Computer</ref><ref>Brooks, Mythical Man-Month, Silver Bullet Refired</ref>

<ref name="nist_web">{{cite web|

url=http://hissa.nist.gov/HHRFdata/Artifacts/ITLdoc/235/chaptera.htm|

title=Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric Chapter 10: Essential Complexity|

author=McCabe, Watson|

year=1996}}</ref>

== Measure of the "structuredness" 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 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 greater than 1 essential complexity numbers, which can only be obtained for non-structured programs, indicate that they are further away from the structured programming ideal.<ref name="mccabe76"/>{{rp|317}}

Line 51 ⟶ 38:

==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]]

== References ==

{{reflist}}

==Further reading==

For the first sense of the term:

* {{cite journal

|title=No Silver Bullet - Essence and Accident in Software Engineering

|last=Brooks |first=Fred P.

|authorlink=Fred Brooks

|journal=Proceedings of the IFIP Tenth World Computing Conference

|pages=1069–1076

|year=1986

|ref=Brooks, Proc. IFIP

}}

* {{cite journal

|title=No Silver Bullet - Essence and Accidents of Software Engineering

|last=Brooks |first=Fred P.

|authorlink=Fred Brooks

|authormask=1

|journal=[[Computer (magazine)|IEEE Computer]]

|volume=20 |issue=4

|date=April 1987

|pages=10–19

|ref=Brooks, IEEE Computer

}}

* {{cite book

|work=The Mythical Man Month

|edition=Anniversary Edition with four new chapters

|chapter=Chap. 17

|title='No Silver Bullet' Refired

|last=Brooks |first=Fred P.

|authorlink=Fred Brooks

|authormask=1

|publisher=Addison-Wesley

|year=1995

|isbn=0-201-83595-9

|ref=Brooks, Mythical Man-Month, Silver Bullet Refired

}}

{{DEFAULTSORT:Essential Complexity}}