Structured program theorem: Difference between revisions

Revision as of 21:32, 16 August 2023

Revision as of 00:37, 24 August 2023

Line 1:

{{short description|Control-flow graphs with 3 types of control structures can compute any computable function}}

The '''structured program theorem''', also called the '''Böhm–Jacopini theorem''',<ref name="kozen">{{cite book|url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |title=The Böhm–Jacopini Theorem Is False, Propositionally|author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|title=Mathematics of Program Construction |chapter=The Böhm–Jacopini Theorem is False, Propositionally |doi=10.1007/978-3-540-70594-9_11|journal=MPC 2008|volume=5133|pages=177–192|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-70593-2|citeseerx=10.1.1.218.9241}}</ref><ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html |title=CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM |publisher=Cse.buffalo.edu |date=2004-11-22 |access-date=2013-08-24}}</ref> is a result in [[programming language theory]]. It states that a class of [[control-flow graph]]s (historically called [[flowchart]]s in this context) can compute any [[computable function]] if it combines subprograms in only three specific ways ([[control structure]]s). These are

#Executing one subprogram, and then another subprogram (sequence)

#Executing one of two subprograms according to the value of a [[Boolean data type|boolean]] expression (selection)

Line 53:

== Implications and refinements ==

The Böhm–Jacopini proof did not settle the question of whether to adopt [[structured programming]] for software development, partly because the construction was more likely to obscure a program than to improve it. On the contrary, it signalled the beginning of the debate. [[Edsger Dijkstra]]'s famous letter, "'''[[Considered Harmful|Go To Statement Considered Harmful]]'''<!--boldface per WP:R#PLA-->," followed in 1968.<ref>{{cite journal|last=Dijkstra|first=Edsger|author-link=Edsger W. Dijkstra|year=1968|title=Go To Statement Considered Harmful|journal=Communications of the ACM|volume=11|issue=3|pages=147–148|doi=10.1145/362929.362947|s2cid=17469809 |url=http://www.acm.org/classics/oct95/|url-status=dead|archive-url=https://web.archive.org/web/20070703050443/http://www.acm.org/classics/oct95/|archive-date=2007-07-03|doi-access=free}}</ref>

Some academics took a purist approach to the Böhm–Jacopini result and argued that even instructions like <code>break</code> and <code>return</code> from the middle of loops are bad practice as they are not needed in the Böhm–Jacopini proof, and thus they advocated that all loops should have a single exit point. This purist approach is embodied in the [[Pascal (programming language)|Pascal programming language]] (designed in 1968–1969), which up to the mid-1990s was the preferred tool for teaching introductory programming classes in academia.<ref name="roberts">Roberts, E. [1995] "[http://cs.stanford.edu/people/eroberts/papers/SIGCSE-1995/LoopExits.pdf Loop Exits and Structured Programming: Reopening the Debate]," ACM SIGCSE Bulletin, (27)1: 268–272.</ref>