Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
|||
Line 83:
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}} 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}}
Up to 1990 there were quite a few proposed methods for eliminating gotos from existing programs, while preserving most of their structure. The various approaches to this problem also proposed several notions of equivalence, which are stricter than simply Turing equivalence, in order to avoid output like the folk theorem discussed above. The strictness of the chosen notion of equivalence dictates the minimal set of control flow structures needed. The 1988 [[JACM]] paper by Lyle Ramshaw surveys the field up to that point, as well proposing its own method.<ref>{{Cite journal | doi = 10.1145/48014.48021| title = Eliminating go to's while preserving program structure| journal = Journal of the ACM| volume = 35| issue = 4| pages = 893–920| year = 1988| last1 = Ramshaw | first1 = L. }}</ref> Ramshaw's algorithm was used for example in some Java [[decompiler]]s because the [[Java virtual machine]] code has branch instructions with targets expressed as offsets, but the high-level Java language only has multi-level <code>break</code> and <code>continue</code> statements.<ref name="Nolan2004">{{cite book|author=Godfrey Nolan|title=Decompiling Java|year=2004|publisher=Apress|isbn=978-1-4302-0739-9|page=142}}</ref><ref>https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf</ref><ref>http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf</ref> Ammarguellat (1992) proposed a transformation method that goes back to enforcing single-exit.<ref name="amma92">{{cite journal | doi = 10.1109/32.126773 | title=A control-flow normalization algorithm and its complexity | journal=IEEE Transactions on Software Engineering | date=1992 | volume=18 | issue=3 | pages=237–251 | first=Z. | last=Ammarguellat}}</ref>
| |||