Satz über strukturierte Programme

Theorem des strukturierten Programms Grafische Darstellung der drei Grundmuster des Theorems des strukturierten Programms — Sequenz, Auswahl, und Wiederholung – unter Verwendung von NS-Diagrammen (blau) und Flussdiagramme (grün).

Der Satz über strukturierte Programme, auch Satz von Böhm-Jacopini genannt,[1][2] ist ein Ergebnis der Programmiersprachentheorie. Es besagt, dass eine Klasse von Kontrollflussgraphen (in diesem Zusammenhang historisch Flussdiagramme genannt) kann jede berechenbare Funktion berechnen, wenn es Unterprogramme auf nur drei spezifische Arten kombiniert (Kontrollstrukturen). These are Executing one subprogram, und dann ein weiteres Unterprogramm (Reihenfolge) Ausführen eines von zwei Unterprogrammen gemäß dem Wert eines booleschen Ausdrucks (Auswahl) Wiederholtes Ausführen eines Unterprogramms, solange ein boolescher Ausdruck wahr ist (Wiederholung) Das diesen Beschränkungen unterliegende Struktogramm kann jedoch zusätzliche Variablen in Form von Bits verwenden (in einer zusätzlichen Integer-Variablen im Originalbeweis gespeichert) um Informationen zu verfolgen, die das Originalprogramm durch den Programmort darstellt. Die Konstruktion basierte auf Böhms Programmiersprache P′′.

Das Theorem bildet die Grundlage der strukturierten Programmierung, ein Programmierparadigma, das auf goto-Befehle verzichtet und ausschließlich Subroutinen verwendet, Sequenzen, Auswahl und Iteration.

Inhalt 1 Herkunft und Varianten 1.1 Single-while-Schleife, Volksversion des Theorems 1.2 Beweis von Böhm und Jacobini 2 Implikationen und Verfeinerungen 3 Bewerbung bei Cobol 4 Siehe auch 5 Verweise 6 Further reading Origin and variants The theorem is typically credited[3]:381  bis a 1966 Aufsatz von Corrado Böhm und Giuseppe Jacopini.[4] David Harel schrieb sich ein 1980 die das Böhm-Jacopini-Papier genoss "universelle Popularität",[3]:381  insbesondere bei Befürwortern der strukturierten Programmierung. Harel bemerkte das auch "aufgrund seines eher technischen Stils [das 1966 Böhm–Jacopini paper] wird offenbar öfter zitiert als ausführlich gelesen"[3]:381  und, nach Überprüfung einer großen Anzahl von Artikeln, die bis veröffentlicht wurden 1980, Harel argumentierte, dass der Inhalt des Böhm-Jacopini-Beweises normalerweise als Volkssatz falsch dargestellt wurde, der im Wesentlichen ein einfacheres Ergebnis enthält, ein Ergebnis, das selbst auf die Anfänge der modernen Computertheorie in den Arbeiten von von Neumann und Kleene zurückgeführt werden kann.[3]: 383  Harel also writes that the more generic name was proposed by H.D. Mühlen als "Der Struktursatz" in den frühen 1970er Jahren.[3]: 381  Single-while-loop, folk version of the theorem This version of the theorem replaces all the original program's control flow with a single global while loop that simulates a program counter going over all possible labels (Flussdiagramm-Boxen) im ursprünglichen nicht strukturierten Programm. Harel führte den Ursprung dieses Volkstheorems auf zwei Veröffentlichungen zurück, die den Beginn des Rechnens markierten. Einer ist der 1946 Beschreibung der von Neumann-Architektur, was erklärt, wie ein Programmzähler in Form einer While-Schleife arbeitet. Harel merkt an, dass die von der Volksversion des Theorems der strukturierten Programmierung verwendete Einzelschleife im Grunde nur eine operative Semantik für die Ausführung eines Flussdiagramms auf einem von Neumann-Computer bereitstellt.[3]:383  Ein anderer, Eine noch ältere Quelle, aus der Harel die Volksversion des Satzes zurückverfolgt hat, ist Stephen Kleenes Normalformsatz 1936.[3]: 383  Donald Knuth criticized this form of the proof, was zu Pseudocode wie dem folgenden führt, indem er darauf hinweist, dass die Struktur des ursprünglichen Programms bei dieser Transformation vollständig verloren geht.[5]:274  Ähnlich, Bruce Ian Mills schrieb über diesen Ansatz, dass "Der Geist der Blockstruktur ist ein Stil, keine Sprache. Durch die Simulation einer Von-Neumann-Maschine, Wir können das Verhalten eines beliebigen Spaghetti-Codes innerhalb der Grenzen einer blockstrukturierten Sprache erzeugen. Das hindert es nicht daran, Spaghetti zu sein."[6] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := resultierende Folgeschrittnummer des Schrittes 1 aus dem Flussdiagramm (0 wenn kein Nachfolger) end if if p = 2 then perform step 2 from the flowchart p := resultierende Folgeschrittnummer des Schrittes 2 aus dem Flussdiagramm (0 wenn kein Nachfolger) Ende wenn ...

if p = n then perform step n from the flowchart p := resultierende Folgeschrittnummer von Schritt n aus dem Flussdiagramm (0 wenn kein Nachfolger) end if end while Böhm and Jacopini's proof This section needs expansion. Sie können helfen, indem Sie etwas hinzufügen. (Juli 2014) Der Beweis in der Arbeit von Böhm und Jacopini erfolgt durch Induktion über die Struktur des Flussdiagramms.[3]:381  Weil es Mustervergleiche in Graphen verwendet, der Beweis von Böhm und Jacopini war als Programmtransformationsalgorithmus nicht wirklich praktikabel, und damit die Tür für weitere Forschungen in dieser Richtung geöffnet.[7] Implications and refinements The Böhm–Jacopini proof did not settle the question of whether to adopt structured programming for software development, zum Teil, weil die Konstruktion eher ein Programm verschleierte als es verbesserte. Andererseits, es signalisierte den Beginn der Debatte. Edsger Dijkstras berühmter Brief, "Gehen Sie zu der als schädlich eingestuften Aussage," folgte hinein 1968.[8] Einige Akademiker haben das Böhm-Jacopini-Ergebnis puristisch angegangen und argumentiert, dass sogar Anweisungen wie break und return aus der Mitte der Schleifen eine schlechte Praxis sind, da sie im Böhm-Jacopini-Beweis nicht benötigt werden, und so befürworteten sie, dass alle Schleifen einen einzigen Austrittspunkt haben sollten. Dieser puristische Ansatz ist in der Programmiersprache Pascal verkörpert (Entwurf 1968–1969), das bis Mitte der 1990er Jahre das bevorzugte Instrument für den Unterricht von einführenden Programmierkursen in der Wissenschaft war.[9] Edward Yourdon stellt fest, dass es in den 1970er Jahren sogar philosophischen Widerstand gegen die Umwandlung unstrukturierter Programme in strukturierte Programme mit automatisierten Mitteln gab, basierend auf dem Argument, dass man von Anfang an in strukturierter Programmierung denken müsse. Der pragmatische Kontrapunkt war, dass solche Transformationen einer großen Anzahl bestehender Programme zugute kamen.[10] Zu den ersten Vorschlägen für eine automatisierte Transformation gehörte a 1971 Papier von Edward Ashcroft und Zohar Manna.[11] Die direkte Anwendung des Böhm-Jacopini-Theorems kann dazu führen, dass zusätzliche lokale Variablen in das Struktogramm eingeführt werden, und kann auch zu einer gewissen Codeduplizierung führen.[12] Letzteres Problem wird in diesem Zusammenhang als Anderthalbschleifenproblem bezeichnet.[13] Pascal ist von diesen beiden Problemen betroffen und nach empirischen Studien, zitiert von Eric S. Roberts, Programmierstudenten hatten Schwierigkeiten, in Pascal richtige Lösungen für einige einfache Probleme zu formulieren, einschließlich des Schreibens einer Funktion zum Suchen eines Elements in einem Array. EIN 1980 Eine von Roberts zitierte Studie von Henry Shapiro ergab, dass nur die von Pascal bereitgestellten Kontrollstrukturen verwendet werden, die richtige Lösung wurde nur von gegeben 20% der Fächer, während kein Subjekt einen falschen Code für dieses Problem geschrieben hat, wenn es erlaubt ist, eine Rückkehr aus der Mitte einer Schleife zu schreiben.[9] Im 1973, S. Rao Kosaraju hat bewiesen, dass es möglich ist, das Hinzufügen zusätzlicher Variablen in der strukturierten Programmierung zu vermeiden, solange beliebige Tiefe, mehrstufige Unterbrechungen von Schleifen sind erlaubt.[1][14] Außerdem, Kosaraju bewies, dass es eine strenge Programmhierarchie gibt, heutzutage Kosaraju-Hierarchie genannt, darin für jede ganze Zahl n, Es gibt ein Programm, das einen mehrstufigen Umbruch der Tiefe n enthält, das nicht als Programm mit mehrstufigen Umbrüchen der Tiefe kleiner als n umgeschrieben werden kann (ohne zusätzliche Variablen einzuführen).[1] Kosaraju zitiert das mehrstufige Break-Konstrukt der Programmiersprache BLISS. Die mehrstufigen Pausen, in Form eines Leave-Label-Schlüsselworts wurden tatsächlich in der BLISS-11-Version dieser Sprache eingeführt; Das ursprüngliche BLISS hatte nur einstufige Unterbrechungen. Die BLISS-Sprachfamilie bot kein uneingeschränktes goto. Diesem Ansatz folgte später auch die Programmiersprache Java.[15]: 960–965  A simpler result from Kosaraju's paper is that a program is reducible to a structured program (ohne Variablen hinzuzufügen) genau dann, wenn es keine Schleife mit zwei unterschiedlichen Ausgängen enthält. Reduzierbarkeit wurde von Kosaraju definiert, grob gesagt, als dieselbe Funktion zu berechnen und dieselbe zu verwenden "primitive Handlungen" und Prädikate als ursprüngliches Programm, aber möglicherweise unter Verwendung unterschiedlicher Kontrollflussstrukturen. (Dies ist ein engerer Begriff der Reduzierbarkeit als der von Böhm-Jacopini verwendete.) Inspiriert von diesem Ergebnis, in Abschnitt VI seines vielzitierten Artikels, der den Begriff der zyklomatischen Komplexität einführte, Thomas J. McCabe beschrieb ein Analogon von Kuratowskis Theorem für die Kontrollflussgraphen (CFG) von nicht strukturierten Programmen, Was ist zu sagen, die minimalen Untergraphen, die die CFG eines Programms unstrukturiert machen. Diese Teilgraphen haben eine sehr gute Beschreibung in natürlicher Sprache. Sie sind: Verzweigung aus einer Schleife (außer aus dem Schleifenzyklustest) Verzweigung in eine Schleife Verzweigung in eine Entscheidung (d.h. in ein wenn "Zweig") branching out of a decision McCabe actually found that these four graphs are not independent when appearing as subgraphs, was bedeutet, dass eine notwendige und hinreichende Bedingung dafür, dass ein Programm nicht strukturiert ist, darin besteht, dass sein CFG als Teilgraph einen von einer beliebigen Teilmenge von drei dieser vier Graphen hat. Er fand auch heraus, dass, wenn ein nicht strukturiertes Programm einen dieser vier Untergraphen enthält, es muss eine andere unterschiedliche aus der Menge der vier enthalten. Dieses letztgenannte Ergebnis hilft zu erklären, wie der Kontrollfluss eines nicht strukturierten Programms mit dem verstrickt wird, was im Volksmund genannt wird "Spaghetti-Code". McCabe entwickelte auch ein numerisches Maß dafür, ein beliebiges Programm gegeben, quantifiziert, wie weit es vom Ideal eines strukturierten Programms entfernt ist; McCabe nannte sein Maß essentielle Komplexität.[16] McCabes Charakterisierung der verbotenen Graphen für die strukturierte Programmierung kann als unvollständig angesehen werden, zumindest wenn man die D-Strukturen von Dijkstra als Bausteine ​​betrachtet.[17]:274–275[Klärung nötig] Bis zu 1990 Es gab einige vorgeschlagene Methoden zum Entfernen von Gotos aus bestehenden Programmen, unter Beibehaltung des größten Teils ihrer Struktur. Die verschiedenen Herangehensweisen an dieses Problem schlugen auch mehrere Äquivalenzbegriffe vor, die strenger sind als die einfache Turing-Äquivalenz, um eine Ausgabe wie das oben diskutierte Volkstheorem zu vermeiden. Die Strenge des gewählten Begriffs der Äquivalenz diktiert den minimalen Satz von benötigten Kontrollflussstrukturen. Das 1988 Das JACM-Papier von Lyle Ramshaw untersucht das Feld bis zu diesem Punkt, und schlägt auch eine eigene Methode vor.[18] Der Algorithmus von Ramshaw wurde beispielsweise in einigen Java-Decompilern verwendet, da der Code der virtuellen Java-Maschine Verzweigungsbefehle mit Zielen aufweist, die als Offsets ausgedrückt sind, aber die Hochsprache Java hat nur Break- und Continue-Anweisungen auf mehreren Ebenen.[19][20][21] Er fällt in Ohnmacht (1992) schlug eine Transformationsmethode vor, die auf die Durchsetzung von Single-Exit zurückgeht.[7] Application to Cobol This section needs additional citations for verification. Bitte helfen Sie mit, diesen Artikel zu verbessern, indem Sie zuverlässige Quellen zitieren. Nicht bezogenes Material kann angefochten und entfernt werden. (August 2013) (Erfahren Sie, wie und wann Sie diese Vorlagennachricht entfernen können) In den 1980er Jahren leitete der IBM-Forscher Harlan Mills die Entwicklung der COBOL-Strukturierungsanlage, die einen Strukturierungsalgorithmus auf COBOL-Code anwandten. Die Transformation von Mills umfasste die folgenden Schritte für jedes Verfahren.

Identifizieren Sie die grundlegenden Blöcke in dem Verfahren. Weisen Sie dem Eingangspfad jedes Blocks eine eindeutige Bezeichnung zu, und beschriften Sie die Austrittspfade jedes Blocks mit den Beschriftungen der Eintrittspfade, mit denen sie verbunden sind. Verwenden 0 für die Rückkehr aus dem Verfahren und 1 für den Eintrittspfad der Prozedur. Unterteilen Sie das Verfahren in seine grundlegenden Blöcke. Für jeden Block, der das Ziel von nur einem Ausgangspfad ist, Verbinden Sie diesen Block wieder mit diesem Ausgangspfad. Deklarieren Sie eine neue Variable in der Prozedur (als Referenz L genannt). Auf jedem verbleibenden unverbundenen Ausgangspfad, fügen Sie eine Anweisung hinzu, die L auf den Labelwert auf diesem Pfad setzt. Kombinieren Sie die resultierenden Programme zu einer Auswahlanweisung, die das Programm mit der durch L angegebenen Eintragspfadkennung ausführt. Konstruieren Sie eine Schleife, die diese Auswahlanweisung ausführt, solange L dies nicht tut 0. Konstruieren Sie eine Sequenz, die L mit initialisiert 1 und führt die Schleife aus.

Beachten Sie, dass diese Konstruktion verbessert werden kann, indem einige Fälle der Auswahlanweisung in Unterprozeduren umgewandelt werden.

Siehe auch Strukturierte Programmierung. Der Vollständigkeit halber Referenzen ^ Nach oben springen: a b c Dexter Kozen und Wei-Lung Dustin Tseng (2008). Der Satz von Böhm-Jacopini ist falsch, Propositional (Pdf). MPC 2008. Vorlesungsunterlagen in Informatik. Vol. 5133. pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. ^ "CSE 111, Herbst 2004, BÖHM-JACOPINI-SATZ". Cse.buffalo.edu. 2004-11-22. Abgerufen 2013-08-24. ^ Nach oben springen: a b c d e f g h Harel, David (1980). "Über Volkssätze" (Pdf). Mitteilungen der ACM. 23 (7): 379–389. doi:10.1145/358886.358892. S2CID 16300625. ^ Böhm, Corrado; Giuseppe Jacobini (Kann 1966). "Flussdiagramme, Turingmaschinen und Sprachen mit nur zwei Bildungsregeln". Mitteilungen der ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439. ^ Donald Knuth (1974). "Strukturierte Programmierung mit go to Statements". Computing-Umfragen. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Bruce Ian Mühlen (2005). Theoretische Einführung in die Programmierung. Springer. p. 279. ISBN 978-1-84628-263-8. ^ Nach oben springen: a b Ammarguelat, Z. (1992). "Ein Kontrollfluss-Normalisierungsalgorithmus und seine Komplexität". IEEE-Transaktionen zur Softwaretechnik. 18 (3): 237–251. doi:10.1109/32.126773. ^ Dijkstra, Edger (1968). "Gehen Sie zu der als schädlich eingestuften Aussage". Mitteilungen der ACM. 11 (3): 147–148. doi:10.1145/362929.362947. S2CID 17469809. Ab dem Original archiviert 2007-07-03. ^ Nach oben springen: ein b Roberts, E. [1995] "Schleifenausgänge und strukturierte Programmierung: Wiedereröffnung der Debatte," ACM SIGCSE-Bulletin, (27)1: 268–272. ^E. N. Yourdon (1979). Klassiker der Softwaretechnik. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7. ^ Aschcroft, Eduard; Zohar Manna (1971). "Die Übersetzung von Gehe zu Programmen in 'Während'-Programme". Tagungsband des IFIP-Kongresses. Das Papier, die aufgrund ihrer begrenzten Verbreitung im Original-Konferenzband nur schwer erhältlich sind, wurde in Yourdon's neu veröffentlicht 1979 Buch pp. 51-65 ^ David Anthony Watt; Wilhelm Findlay (2004). Designkonzepte für Programmiersprachen. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7. ^ Kenneth C. Laut; Kenneth A. Lambert (2011). Programmiersprachen: Prinzipien und Praktiken (3 ed.). Cengage-Lernen. pp. 422–423. ISBN 978-1-111-52941-3. ^ BASKETBALL, S. RAO. "Analyse strukturierter Programme," Proz. Fünfter jährlicher ACM-Sirup. Theorie der Informatik, (Kann 1973), 240-252; auch Kosaraju, S. Rao (1974). "Analyse strukturierter Programme". Zeitschrift für Computer- und Systemwissenschaften. 9 (3): 232–255. doi:10.1016/S0022-0000(74)80043-7. zitiert von Donald Knuth (1974). "Strukturierte Programmierung mit go to Statements". Computing-Umfragen. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Brender, Roland F. (2002). "Die Programmiersprache BLISS: eine Geschichte" (Pdf). Software: Praxis und Erfahrung. 32 (10): 955–981. doi:10.1002/sp.470. S2CID 45466625. ^ Das Originalpapier ist Thomas J. McCabe (Dezember 1976). "Ein Komplexitätsmaß". IEEE-Transaktionen zur Softwaretechnik. SE-2 (4): 315–318. doi:10.1109/diese.1976.233837. S2CID 9116234. Für eine sekundäre Darstellung siehe Paul C. Jörgensen (2002). Softwaretest: Der Ansatz eines Handwerkers, Zweite Ausgabe (2und Aufl.). CRC-Presse. pp. 150–153. ISBN 978-0-8493-0809-3. ^ Williams, M. H. (1983). "Flussdiagrammschemata und das Problem der Nomenklatur". Das Computerjournal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270. ^ Ramscha, L. (1988). "Go to's werden eliminiert, während die Programmstruktur erhalten bleibt". Zeitschrift der ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665. ^ Godfrey Nolan (2004). Java dekompilieren. sich beeilen. p. 142. ISBN 978-1-4302-0739-9. ^https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[bloße URL-PDF] ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[bloße URL-PDF] Further reading Material not yet covered above: DeMillo, Richard A. (1980). "Raum-Zeit-Kompromisse in der strukturierten Programmierung: Ein verbesserter kombinatorischer Einbettungssatz". Zeitschrift der ACM. 27 (1): 123–127. doi:10.1145/322169.322180. S2CID 15669719. Werden, Philipp (1994). "Eine binäre Hornklausel ist genug". Stapel 94. Vorlesungsunterlagen in Informatik. Vol. 775. pp. 19–32. CiteSeerX 10.1.1.14.537. doi:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0. Kategorien: ProgrammiersprachentheorieModelle der BerechnungTheoreme in der Berechnungskomplexitätstheorie