Structured program theorem: Difference between revisions

Revision as of 13:48, 25 April 2020

Revision as of 07:29, 1 May 2020

Line 62:

In 1973, [[S. Rao Kosaraju]] proved that it's possible to avoid adding additional variables in structured programming, as long as arbitrary-depth, multi-level breaks from loops are allowed.<ref name="kozen"/><ref>KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup.

Theory of Computing, (May 1973), 240-252; also in{{cite Jjournal | doi = 10.1016/S0022-0000(74)80043-7 | volume=9 | title=Analysis of structured programs | year=1974 | journal=Journal of Computer and System Sciences, 9,| pages=232–255 | last1 = Kosaraju | first1 = S. Rao}} cited by {{cite journal

3 (December 1974), {{doi| 10.1016/S0022-0000(74)80043-7}} cited by {{cite journal

| author = [[Donald Knuth]]

| title = Structured Programming with go to Statements

Line 81 ⟶ 80:

# branching into a decision (i.e. into an if "branch")

# branching out of a decision

McCabe actually found that these four graphs are not independent when appearing as subgraphs, meaning that a necessary and sufficient condition for a program to be non-structured is for its CFG to have as subgraph one of any subset of three of these four graphs. He also found that if a non-structured program contains one of these four sub-graphs, it must contain another distinct one from the set of four. This latter result helps explain how the control flow of non-structured program becomes entangled in what is popularly called "[[spaghetti code]]". McCabe also devised a numerical measure that, given an arbitrary program, quantifies how far off it is from the ideal of being a structured program; McCabe called his measure [[essential complexity (numerical measure of "structuredness")|essential complexity]].<ref name="McCabe">The original paper is {{cite journal |author=Thomas J. McCabe |date=December 1976 |journal=IEEE Transactions on Software Engineering |issue=4 |pages=315–318 |title=A Complexity Measure|url=https://books.google.com/books?id=vtNWAAAAMAAJ&pg=PA3 |doi=10.1109/tse.1976.233837 |volume=SE-2}} For a secondary exposition see {{cite book|author=Paul C. Jorgensen|title=Software Testing: A Craftsman's Approach, Second Edition|url=https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150|year=2002|publisher=CRC Press|isbn=978-0-8493-0809-3|pages=150–153|edition=2nd}}</ref>

McCabe's characterization of the [[forbidden graph]]s for structured programming can be considered incomplete, at least if the Dijkstra's D structures are considered the building blocks.<ref>{{cite journal | doi = 10.1093/comjnl/26.3.270 | title=Flowchart Schemata and the Problem of Nomenclature | journal=The Computer Journal | date=1983 | volume=26 | issue=3 | pages=270–276 | first=M. H. | last=Williams| doi-access=free }}</ref>{{rp|274–275}}{{clarify|date=July 2014}}