Programming complexity: Difference between revisions

Revision as of 06:51, 2 September 2009

Latest revision as of 15:37, 21 June 2025

(44 intermediate revisions by 37 users not shown)

Line 1:

{{Short description|Attribute of a software system}}

{{Mergeto|Software metric|discuss=Talk:Software metric|date=June 2008}}

{{Distinguish|Computational complexity theory}}'''Programming complexity''' (or '''software complexity''') is a term that includes software properties that affect internal interactions. Several commentators distinguish between the terms "complex" and "complicated". Complicated implies being difficult to understand, but ultimately knowable. Complex, by contrast, describes the interactions between entities. As the number of entities increases, the number of interactions between them increases exponentially, making it impossible to know and understand them all. Similarly, higher levels of complexity in software increase the risk of unintentionally interfering with interactions, thus increasing the risk of introducing defects when changing the software. In more extreme cases, it can make modifying the software virtually impossible.

'''Programming Complexity''', which is often also referred to as '''Software Complexity''' is a term that encompasses numerous properties of a piece of software, all of which affect internal interactions. According to several commentators, including [http://www.astroprojects.com/morespace/johnnie/ Jonnie Moore], there is a distinction between the terms complex and complicated; complicated implies being difficult to understand but with time and effort, ultimately knowable. Complex, on the other hand, describes the interactions between a number of entities. As the number of entities increases, the number of interactions between them would increase exponentially and it would get to a point where it would be impossible to know and understand all of them. Similarly, higher levels of complexity in software increase the risk of unintentionally interfering with interactions and so increases the chance of introducing defects when making changes. In more extreme cases, it can make modifying the software virtually impossible. The idea of linking software complexity to thesoftware maintainability of the software has been explored extensively by [[Meir M. Lehman|Professor Manny Lehman]], who developed his [[Lehman's_laws_of_software_evolutions laws of software evolution|Laws of Software Evolution]] from his research. He and his co-Authorauthor [[Les Belady]] explored numerous possible [[Software_metrics|Softwaresoftware Metricsmetrics]] in their oft cited book<ref>MM Lehmam LA Belady; Program Evolution - Processes of Software Change 1985</ref>, that could be used to measure the state of the software, eventually reaching the conclusionconcluding that the only practical solution would beis to use one that uses deterministic complexity models.<ref>MM Lehmam LA Belady; Program Evolution - Processes of Software Change 1985</ref>

==Types==

Many measures of software complexity have been proposed, many of these although giving a good representation of complexity, do not lend themselves to easy measurement. Some of the more commonly used metrics are

The complexity of an existing program determines the complexity of changing the program. Problem complexity can be divided into two categories:<ref>[https://academia.edu.documents.s3.amazonaws.com/1811257/SHSM2011.pdf In software engineering, a problem can be divided into its accidental and essential complexity [1<nowiki>]</nowiki>.]</ref>

#'''Accidental complexity''' relates to difficulties a programmer faces due to the software engineering tools. Selecting a better tool set or a higher-level programming language may reduce it. Accidental complexity often results from not using the ___domain to frame the form of the solution.{{Citation needed|date=September 2015}} [[Domain-driven design]] can help minimize accidental complexity.

#'''Essential complexity''' is caused by the characteristics of the problem to be solved and cannot be reduced.

==Measures==

* [[cyclomatic complexity|McCabes cyclomatic complexity metric]]

ManySeveral measures of software complexity have been proposed,. manyMany of these, although givingyielding a good representation of complexity, do not lend themselves to easy measurement. Some of the more commonly used metrics are

* [[cyclomatic complexity|McCabesMcCabe's cyclomatic complexity metric]]

* [[Halstead complexity measures|Halstead's software science metrics]]

* Henry and Kafura introduced "Software Structure Metrics Based on Information Flow" in 1981,<ref>Henry, S.; Kafura, D. IEEE Transactions on Software Engineering Volume SE-7, Issue 5, Sept. 1981 Page(s): 510 - 518</ref> which measures complexity as a function of "fan -in" and "fan -out". They define fan-in of a procedure as the number of local flows into that procedure plus the number of data structures from which that procedure retrieves information. Fan-out is defined as the number of local flows out of that procedure plus the number of data structures that the procedure updates. Local flows relate to data passed to, and from procedures that call or are called by, the procedure in question. Henry and Kafura?'s complexity value is defined as "the square of procedure length multiplied by the square of fan-in multiplied by fan-out." (Length ×(fan-in × fan-out)²).

* Chidamber and Kemerer introduced "A Metrics Suite for Object -Oriented Design" in 1994,<ref name=":0">Chidamber, S.R.; Kemerer, C.F. IEEE Transactions on Software Engineering Volume 20, Issue 6, Jun 1994 Page(s):476 - 493</ref> was introduced by Chidamber and Kemerer in 1994 focusing, as the title suggests on metrics specifically for object -oriented code. They introduce six OO complexity metrics;: (1) weighted methods per class,; (2) coupling between object classes,; (3) response for a class,; (4) number of children,; (5) depth of inheritance tree; and (6) lack of cohesion of methods.

There are severalSeveral other metrics thatcan canbe useused to measure programming complexity:

* Elements of Software Science published in 1976 by Maurice Halstead and often referred to as Halstead's software science metrics. He introduced a family of metrics, for program length, programming effort and to estimate the intelligence content. All of them are generated from analysis of the combinations of the unique and total operators and operands of the program.

* branchingBranching complexity (Sneed Metric)

* dataData access complexity (Card Metric)

* dataData complexity (Chapin Metric)

* dataData flow complexity (Elshof Metric)

* decisionalDecisional complexity (McClure Metric)

*Path Complexity (Bang Metric)

[[Law of conservation of complexity|Tesler's Law]] is an [[adage]] in [[human–computer interaction]] stating that every [[Application software|application]] has an inherent amount of complexity that cannot be removed or hidden.

* Henry and Kafura introduced Software Structure Metrics Based on Information Flow in 1981<ref>Henry, S.; Kafura, D. IEEE Transactions on Software Engineering Volume SE-7, Issue 5, Sept. 1981 Page(s): 510 - 518</ref> which measures complexity as a function of fan in and fan out. They define fan-in of a procedure as the number of local flows into that procedure plus the number of data structures from which that procedure retrieves information. Fan-out is defined as the number of local flows out of that procedure plus the number of data structures that the procedure updates. Local flows relate to data passed to and from procedures that call or are called by, the procedure in question. Henry and Kafura?s complexity value is defined as "the square of procedure length multiplied by fan-in multiplied by fan-out."

==Chidamber and Kemerer Metrics==

* A Metrics Suite for Object Oriented Design<ref>Chidamber, S.R.; Kemerer, C.F. IEEE Transactions on Software Engineering Volume 20, Issue 6, Jun 1994 Page(s):476 - 493</ref> was introduced by Chidamber and Kemerer in 1994 focusing, as the title suggests on metrics specifically for object oriented code. They introduce six OO complexity metrics; weighted methods per class, coupling between object classes, response for a class, number of children, depth of inheritance tree and lack of cohesion of methods

{{Prose|date=August 2017}}

Chidamber and Kemerer<ref name=":0" /> proposed a set of programing complexity metrics widely used in measurements and academic articles: weighted methods per class, coupling between object classes, response for a class, number of children, depth of inheritance tree, and lack of cohesion of methods, described below:

* Weighted methods per class ("WMC")

** <math>WMC = \sum_{i=1}^nc_i</math>

** n is the number of methods on the class

** <math>c_i</math> is the complexity of the method

* Coupling between object classes ("CBO")

** number of other class which is coupled (using or being used)

* Response for a class ("RFC")

** <math>RFC = |RS|</math> where

** <math>RS = \{M\}\cup_{all\ i} \{R_i\}</math>

** <math>R_i</math> is set of methods called by method i

** <math>M</math> is the set of methods in the class

* Number of children ("NOC")

** sum of all classes that inherit this class or a descendant of it

* Depth of inheritance tree ("DIT")

** maximum depth of the inheritance tree for this class

* Lack of cohesion of methods ("LCOM")

** Measures the intersection of the attributes used in common by the class methods

** <math>LCOM = \begin{cases} |P| - |Q|, & \text{if } |P| > |Q|

\\0, & \text{otherwise } \end{cases}</math>

** Where <math>P = \{ (I_i,I_j)|I_i\cap I_j = \emptyset\}</math>

** And <math>Q = \{(I_i, I_j)|I_i \cap I_j \neq \emptyset\}</math>

** With <math>I_i</math> is the set of attributes (instance variables) accessed (read from or written to) by the <math>i</math>-th method of the class

==See also==

There are several other metrics that can use to measure programming complexity:

*[[Programming paradigm]]

* data complexity (Chapin Metric)

*[[Software crisis]]

* data flow complexity (Elshof Metric)

* data access complexity (Card Metric)

* decisional complexity (McClure Metric)

* branching complexity (Sneed Metric)

==References==

{{Reflist}}

==See also==

*[[Software crisis]] (and subsequent [[programming paradigm]] solutions)

*[[Software metric]]s - quantitative measure of some property of a program.

{{comp-sci-stub}}

[[Category:Software metrics]]

[[Category:Complex systems theory]]