Content deleted Content added
unfloat image and move down, since it is almost my whole screen width |
→Origin and variants: added reference to von Neumann |
||
Line 9:
The theorem forms the basis of [[structured programming]], a programming paradigm which eschews [[Goto|goto commands]] and exclusively uses subroutines, sequences, selection and iteration.[[File:Structured program patterns.png|Graphical representation of the three basic patterns of the structured program theorem — sequence, selection, and repetition — using [[Nassi–Shneiderman diagram|NS diagrams]] (blue) and [[flow chart]]s (green).|center|frame]]
== Origin and variants ==
The theorem is typically credited<ref name="Harel"/>{{rp|381}} to a 1966 paper by [[Corrado Böhm]] and [[Giuseppe Jacopini]].<ref>{{cite journal|last=Bohm|first=Corrado|author2=Giuseppe Jacopini |date=May 1966|title=Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules|journal=[[Communications of the ACM]]|volume=9|issue=5|pages=366–371|doi=10.1145/355592.365646|citeseerx=10.1.1.119.9119|s2cid=10236439 }}</ref> [[David Harel]] wrote in 1980 that the Böhm–Jacopini paper enjoyed "universal popularity",<ref name="Harel"/>{{rp|381}} particularly with proponents of structured programming. Harel also noted that "due to its rather technical style [the 1966 Böhm–Jacopini paper] is apparently more often cited than read in detail"<ref name="Harel"/>{{rp|381}} and, after reviewing a large number of papers published up to 1980, Harel argued that the contents of the Böhm–Jacopini proof were usually misrepresented as a [[Mathematical folklore|folk theorem]] that essentially contains a simpler result, a result which itself can be traced to the inception of modern computing theory in the papers of [[John von Neumann|von Neumann]]<ref>{{Citation|last1= Burks|first1= Arthur W.|last2= Goldstine|first2= Herman|last3= von Neumann|first3= John|author-link= Arthur W. Burks|author2-link= Herman Goldstine|author3-link = John von Neumann|title= Preliminary discussion of the Logical Design of an Electronic Computing Instrument|publisher= Institute for Advanced Study|___location= Princeton, NJ|year= 1947}}</ref> and [[Stephen Cole Kleene|Kleene]].<ref name="Harel"/>{{rp|383}}
Harel also writes that the more generic name was proposed by [[Harlan Mills|H.D. Mills]] as "The Structure Theorem" in the early 1970s.<ref name="Harel">{{cite journal|last=Harel|first=David|author-link=David Harel|year=1980|title=On Folk Theorems|journal=Communications of the ACM|volume=23|issue=7|pages=379–389|doi=10.1145/358886.358892|s2cid=16300625 |url=http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/OnFolkTheorems.pdf}}</ref>{{rp|381}}
| |||