Editing Structured programming (section)

==History==

===Theoretical foundation===
The [[structured program theorem]] provides the theoretical basis of structured programming. It states that three ways of combining programs&mdash;sequencing, selection, and iteration&mdash;are sufficient to express any [[computable function]]. This observation did not originate with the structured programming movement; these structures are sufficient to describe the [[instruction cycle]] of a [[central processing unit]], as well as the operation of a [[Turing machine]]. Therefore, a processor is always executing a "structured program" in this sense, even if the instructions it reads from memory are not part of a structured program. However, authors usually credit the result to a 1966 paper by Böhm and Jacopini, possibly because [[Edsger W. Dijkstra|Dijkstra]] cited this paper himself.{{sfn|Dijkstra|1968}} The structured program theorem does not address how to write and analyze a usefully structured program. These issues were addressed during the late 1960s and early 1970s, with major contributions by [[Edsger W. Dijkstra|Dijkstra]], [[Robert W. Floyd]], [[Tony Hoare]], [[Ole-Johan Dahl]], and [[David Gries]].

===Debate===
[[P. J. Plauger]], an [[early adopter]] of structured programming, described his reaction to the structured program theorem:

{{quote|Us converts waved this interesting bit of news under the noses of the unreconstructed assembly-language programmers who kept trotting forth twisty bits of logic and saying, 'I betcha can't structure this.' Neither the proof by Böhm and Jacopini nor our repeated successes at writing structured code brought them around one day sooner than they were ready to convince themselves.<ref>{{cite book
|last = Plauger
|first = P. J.
|author-link = P. J. Plauger
|title = Programming on Purpose, Essays on Software Design
|url = https://archive.org/details/programmingonpur0000plau
|url-access = registration
|date = February 12, 1993
|publisher = Prentice-Hall
|edition = 1st
|isbn = 978-0-13-721374-0
|page = [https://archive.org/details/programmingonpur0000plau/page/25 25]
}}</ref>}}

[[Donald Knuth]] accepted the principle that programs must be written with provability in mind, but he disagreed with abolishing the GOTO statement, and {{as of|2018|lc=true}} has continued to use it in his programs.<ref>{{Cite AV media|title=DLS • Donald Knuth • All Questions Answered |url=https://www.youtube.com/watch?t=2610&v=XWR5Y3Wf8Fo|website=YouTube |publisher=University of Waterloo |access-date=24 July 2022 |language=en |date=15 Nov 2018|minutes=48}}</ref> In his 1974 paper, "Structured Programming with Goto Statements",<ref>{{cite journal |author=Donald E. Knuth |title=Structured programming with go to statements|journal=Computing Surveys|volume=6|issue=4|pages=261–301|date=December 1974 |doi=10.1145/356635.356640|s2cid=207630080|url=http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf |archive-url= https://web.archive.org/web/20131023061601/http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf |archive-date=2013-10-23 |url-status=dead}}</ref> he gave examples where he believed that a direct jump leads to clearer and more efficient code without sacrificing provability. Knuth proposed a looser structural constraint: It should be possible to draw a program's [[flow chart]] with all forward branches on the left, all backward branches on the right, and no branches crossing each other. Many of those knowledgeable in [[compiler]]s and [[graph theory]] have advocated allowing only [[reducible flow graphs]].{{definition|date=April 2012}}{{Who|date=May 2011}}

Structured programming theorists gained a major ally in the 1970s after [[IBM]] researcher [[Harlan Mills]] applied his interpretation of structured programming theory to the development of an indexing system for ''[[The New York Times]]'' research file. The project was a great engineering success, and managers at other companies cited it in support of adopting structured programming, although Dijkstra criticized the ways that Mills's interpretation differed from the published work.{{refn| In EWD1308, {{cite web
|url=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html 
|title=What led to "Notes on Structured Programming"}}, dated 10 June 2001, Dijkstra writes, "Apparently, IBM did not like the popularity of my text; it stole the term "Structured Programming" and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of the goto statement."}}

As late as 1987 it was still possible to raise the question of structured programming in a computer science journal. Frank Rubin did so in that year with an open letter titled "'GOTO Considered Harmful' Considered Harmful".<ref>{{cite journal |author=Frank Rubin |date=March 1987 |title="GOTO Considered Harmful" Considered Harmful |journal=Communications of the ACM |volume=30 |issue=3 |pages=195–196 |s2cid=6853038 |doi=10.1145/214748.315722 |url=http://www.ecn.purdue.edu/ParaMount/papers/rubin87goto.pdf |archive-url=https://web.archive.org/web/20090320002214/http://www.ecn.purdue.edu/ParaMount/papers/rubin87goto.pdf |archive-date=2009-03-20}}</ref> Numerous objections followed, including a response from Dijkstra that sharply criticized both Rubin and the concessions other writers made when responding to him.

===Outcome===
By the end of the 20th century, nearly all computer scientists were convinced that it is useful to learn and apply the concepts of structured programming. High-level programming languages that originally lacked programming structures, such as [[FORTRAN]], [[COBOL]], and [[BASIC]], now have them.