Théorème du programme structuré

Théorème du programme structuré Représentation graphique des trois modèles de base du théorème du programme structuré — séquence, sélection, et répétition — à l'aide de diagrammes NS (bleu) et organigrammes (vert).

Le théorème du programme structuré, également appelé théorème de Böhm-Jacopini,[1][2] est un résultat de la théorie des langages de programmation. Il stipule qu'une classe de graphes de flux de contrôle (historiquement appelés organigrammes dans ce contexte) peut calculer n'importe quelle fonction calculable si elle combine des sous-programmes de trois manières spécifiques seulement (Structures de contrôle). These are Executing one subprogram, puis un autre sous-programme (séquence) Exécution d'un des deux sous-programmes selon la valeur d'une expression booléenne (sélection) Exécution répétée d'un sous-programme tant qu'une expression booléenne est vraie (itération) Le graphe structuré soumis à ces contraintes peut cependant utiliser des variables supplémentaires sous forme de bits (stocké dans une variable entière supplémentaire dans la preuve originale) afin de garder une trace des informations que le programme original représente par l'emplacement du programme. La construction était basée sur le langage de programmation P′′ de Böhm.

Le théorème constitue la base de la programmation structurée, un paradigme de programmation qui évite les commandes goto et utilise exclusivement des sous-programmes, séquences, sélection et itération.

Contenu 1 Origine et variantes 1.1 Boucle while unique, version folklorique du théorème 1.2 Preuve de Böhm et Jacopini 2 Implications et raffinements 3 Application à Cobol 4 Voir également 5 Références 6 Further reading Origin and variants The theorem is typically credited[3]:381  à un 1966 article de Corrado Böhm et Giuseppe Jacopini.[4] David Harel a écrit dans 1980 que le papier Böhm-Jacopini a apprécié "popularité universelle",[3]:381  notamment avec les tenants de la programmation structurée. Harel a également noté que "en raison de son style plutôt technique [la 1966 Papier Boehm-Jacopini] est apparemment plus souvent cité que lu en détail"[3]:381  et, après avoir examiné un grand nombre d'articles publiés jusqu'à 1980, Harel a fait valoir que le contenu de la preuve de Böhm-Jacopini était généralement déformé comme un théorème populaire qui contient essentiellement un résultat plus simple, un résultat qui lui-même peut être attribué à la création de la théorie informatique moderne dans les articles de von Neumann et Kleene.[3]: 383  Harel also writes that the more generic name was proposed by H.D. Moulins comme "Le théorème de structure" au début des années 1970.[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 (boîtes d'organigramme) dans le programme original non structuré. Harel a retracé l'origine de ce théorème populaire à deux articles marquant le début de l'informatique. L'un est le 1946 description de l'architecture von Neumann, qui explique le fonctionnement d'un compteur de programme en termes de boucle while. Harel note que la boucle unique utilisée par la version populaire du théorème de programmation structurée ne fournit essentiellement qu'une sémantique opérationnelle pour l'exécution d'un organigramme sur un ordinateur von Neumann.[3]:383  Un autre, une source encore plus ancienne que Harel a retracée la version folklorique du théorème est le théorème de forme normale de Stephen Kleene de 1936.[3]: 383  Donald Knuth criticized this form of the proof, qui se traduit par un pseudocode comme celui ci-dessous, en soulignant que la structure du programme original est complètement perdue dans cette transformation.[5]:274  De même, Bruce Ian Mills a écrit à propos de cette approche que "L'esprit de la structure en blocs est un style, pas une langue. En simulant une machine Von Neumann, nous pouvons produire le comportement de n'importe quel code spaghetti dans les limites d'un langage structuré en blocs. Cela ne l'empêche pas d'être des spaghettis."[6] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := numéro d'étape successeur résultant de l'étape 1 à partir de l'organigramme (0 si pas de successeur) end if if p = 2 then perform step 2 from the flowchart p := numéro d'étape successeur résultant de l'étape 2 à partir de l'organigramme (0 si pas de successeur) fin si ...

if p = n then perform step n from the flowchart p := numéro d'étape successeur résultant de l'étape n de l'organigramme (0 si pas de successeur) end if end while Böhm and Jacopini's proof This section needs expansion. Vous pouvez aider en y ajoutant. (Juillet 2014) La preuve dans l'article de Böhm et Jacopini procède par induction sur la structure de l'organigramme.[3]:381  Parce qu'il a utilisé le pattern matching dans les graphes, la preuve de Böhm et Jacopini n'était pas vraiment pratique comme algorithme de transformation de programme, et a ainsi ouvert la porte à des recherches supplémentaires dans ce sens.[7] Implications and refinements The Böhm–Jacopini proof did not settle the question of whether to adopt structured programming for software development, en partie parce que la construction était plus susceptible d'obscurcir un programme que de l'améliorer. Au contraire, cela a marqué le début du débat. La célèbre lettre d'Edsger Dijkstra, "Aller à la déclaration considérée comme nuisible," suivi dans 1968.[8] Certains universitaires ont adopté une approche puriste du résultat de Böhm-Jacopini et ont fait valoir que même des instructions comme la pause et le retour du milieu des boucles sont une mauvaise pratique car elles ne sont pas nécessaires dans la preuve de Böhm-Jacopini., et donc ils ont préconisé que toutes les boucles aient un seul point de sortie. Cette approche puriste est incarnée dans le langage de programmation Pascal (conçu en 1968-1969), qui jusqu'au milieu des années 1990 était l'outil préféré pour enseigner les cours d'initiation à la programmation dans le milieu universitaire.[9] Edward Yourdon note que dans les années 1970, il y avait même une opposition philosophique à la transformation de programmes non structurés en programmes structurés par des moyens automatisés., basé sur l'argument selon lequel il fallait penser à la manière d'une programmation structurée dès le départ. Le contrepoint pragmatique était que de telles transformations profitaient à un grand nombre de programmes existants.[10] Parmi les premières propositions de transformation automatisée figurait un 1971 article d'Edward Ashcroft et Zohar Manna.[11] L'application directe du théorème de Böhm – Jacopini peut entraîner l'introduction de variables locales supplémentaires dans le graphique structuré, et peut également entraîner une duplication de code.[12] Ce dernier problème est appelé le problème de la boucle et demie dans ce contexte.[13] Pascal est concerné par ces deux problèmes et selon des études empiriques citées par Eric S. Robert, les étudiants programmeurs avaient des difficultés à formuler des solutions correctes en Pascal pour plusieurs problèmes simples, comprenant l'écriture d'une fonction pour rechercher un élément dans un tableau. UN 1980 une étude d'Henry Shapiro citée par Roberts a révélé que l'utilisation uniquement des structures de contrôle fournies par Pascal, la solution correcte a été donnée par seulement 20% des sujets, alors qu'aucun sujet n'a écrit de code incorrect pour ce problème s'il était autorisé à écrire un retour à partir du milieu d'une boucle.[9] Dans 1973, S. Rao Kosaraju a prouvé qu'il est possible d'éviter d'ajouter des variables supplémentaires dans la programmation structurée, tant que la profondeur arbitraire, les ruptures à plusieurs niveaux des boucles sont autorisées.[1][14] Par ailleurs, Kosaraju a prouvé qu'il existe une hiérarchie stricte des programmes, aujourd'hui appelée la hiérarchie Kosaraju, en ce que pour tout entier n, il existe un programme contenant une rupture multi-niveaux de profondeur n qui ne peut pas être réécrit comme un programme avec des ruptures multi-niveaux de profondeur inférieure à n (sans introduire de variables supplémentaires).[1] Kosaraju cite la construction de rupture à plusieurs niveaux du langage de programmation BLISS. Les pauses à plusieurs niveaux, sous la forme d'un mot-clé d'étiquette de congé ont en fait été introduits dans la version BLISS-11 de cette langue; le BLISS original n'avait que des pauses à un seul niveau. La famille de langages BLISS n'a pas fourni de goto sans restriction. Le langage de programmation Java suivra plus tard cette approche également.[15]: 960–965  A simpler result from Kosaraju's paper is that a program is reducible to a structured program (sans ajouter de variables) si et seulement si elle ne contient pas de boucle avec deux sorties distinctes. La réductibilité a été définie par Kosaraju, en gros, en calculant la même fonction et en utilisant le même "actions primitives" et prédicats comme le programme original, mais éventuellement en utilisant différentes structures de flux de contrôle. (Il s'agit d'une notion de réductibilité plus étroite que celle utilisée par Böhm-Jacopini.) Inspiré par ce résultat, dans la section VI de son article très cité qui a introduit la notion de complexité cyclomatique, Thomas J. McCabe a décrit un analogue du théorème de Kuratowski pour les graphes de flux de contrôle (CFG) de programmes non structurés, c'est-à-dire, les sous-graphes minimaux qui rendent le CFG d'un programme non structuré. Ces sous-graphes ont une très bonne description en langage naturel. Elles sont: sortie d'une boucle (autre que du test de cycle de boucle) branchement dans une boucle branchement dans une décision (c'est à dire. dans un si "bifurquer") branching out of a decision McCabe actually found that these four graphs are not independent when appearing as subgraphs, ce qui signifie qu'une condition nécessaire et suffisante pour qu'un programme soit non structuré est que son CFG ait comme sous-graphe l'un de n'importe quel sous-ensemble de trois de ces quatre graphes. Il a également constaté que si un programme non structuré contient l'un de ces quatre sous-graphes, il doit en contenir un autre distinct de l'ensemble des quatre. Ce dernier résultat permet d'expliquer comment le flux de contrôle d'un programme non structuré s'emmêle dans ce qu'on appelle communément "code des spaghettis". McCabe a également conçu une mesure numérique qui, étant donné un programme arbitraire, quantifie à quel point il est éloigné de l'idéal d'être un programme structuré; McCabe a qualifié sa mesure de complexité essentielle.[16] La caractérisation de McCabe des graphes interdits pour la programmation structurée peut être considérée comme incomplète, du moins si les structures D de Dijkstra sont considérées comme les blocs de construction.[17]:274–275[clarification nécessaire] Jusqu'à 1990 il y avait pas mal de méthodes proposées pour éliminer les gotos des programmes existants, tout en préservant l'essentiel de leur structure. Les différentes approches de ce problème ont également proposé plusieurs notions d'équivalence, qui sont plus strictes que la simple équivalence de Turing, afin d'éviter une sortie comme le théorème populaire discuté ci-dessus. La rigueur de la notion d'équivalence choisie dicte l'ensemble minimal de structures de flux de contrôle nécessaires. La 1988 L'article JACM de Lyle Ramshaw examine le domaine jusqu'à ce point, ainsi que de proposer sa propre méthode.[18] L'algorithme de Ramshaw a été utilisé par exemple dans certains décompilateurs Java car le code de la machine virtuelle Java a des instructions de branchement avec des cibles exprimées sous forme de décalages, mais le langage Java de haut niveau n'a que des instructions break et continue à plusieurs niveaux.[19][20][21] Il s'évanouit (1992) a proposé une méthode de transformation qui revient à appliquer la sortie unique.[7] Application to Cobol This section needs additional citations for verification. Aidez-nous à améliorer cet article en ajoutant des citations à des sources fiables. Le matériel non sourcé peut être contesté et supprimé. (Août 2013) (Découvrez comment et quand supprimer ce modèle de message) Dans les années 1980, le chercheur d'IBM Harlan Mills a supervisé le développement de l'installation de structuration COBOL, qui a appliqué un algorithme de structuration au code COBOL. La transformation de Mills impliquait les étapes suivantes pour chaque procédure.

Identifier les blocs de base de la procédure. Attribuez une étiquette unique au chemin d'entrée de chaque bloc, et étiquetez les chemins de sortie de chaque bloc avec les étiquettes des chemins d'entrée auxquels ils se connectent. Utilisation 0 pour le retour de la procédure et 1 pour le chemin d'entrée de la procédure. Décomposer la procédure en ses blocs de base. Pour chaque bloc qui est la destination d'un seul chemin de sortie, reconnectez ce bloc à ce chemin de sortie. Déclarer une nouvelle variable dans la procédure (appelé L pour référence). Sur chaque chemin de sortie non connecté restant, ajouter une instruction qui définit L à la valeur de l'étiquette sur ce chemin. Combinez les programmes résultants dans une instruction de sélection qui exécute le programme avec l'étiquette de chemin d'entrée indiquée par L Construisez une boucle qui exécute cette instruction de sélection tant que L n'est pas 0. Construire une séquence qui initialise L à 1 et exécute la boucle.

Notez que cette construction peut être améliorée en convertissant certains cas de l'instruction de sélection en sous-procédures.

Voir aussi Programmation structurée Complétude de Turing Références ^ Aller à: a b c Dexter Kozen et Wei-Lung Dustin Tseng (2008). Le théorème de Böhm-Jacopini est faux, propositionnellement (PDF). MPC 2008. Notes de cours en informatique. Volume. 5133. pp. 177–192. CiteSeerX 10.1.1.218.9241. est ce que je:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. ^ "CSE 111, Tomber 2004, THÉORÈME DE BOEHM-JACOPINI". Cse.buffalo.edu. 2004-11-22. Récupéré 2013-08-24. ^ Sauter à: a b c d e f g h Harel, David (1980). "Sur les théorèmes populaires" (PDF). Communications de l'ACM. 23 (7): 379–389. est ce que je:10.1145/358886.358892. S2CID 16300625. ^ Bohm, Corrado; Giuseppe Jacopini (Peut 1966). "Diagrammes de flux, Machines de Turing et langages avec seulement deux règles de formation". Communications de l'ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. est ce que je:10.1145/355592.365646. S2CID 10236439. ^ Donald Knuth (1974). "Programmation structurée avec go to Statements". Enquêtes informatiques. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. est ce que je:10.1145/356635.356640. S2CID 207630080. ^ Bruce Ian Mills (2005). Introduction théorique à la programmation. Springer. p. 279. ISBN 978-1-84628-263-8. ^ Sauter à: a b Ammarguellat, Z. (1992). "Un algorithme de normalisation de flux de contrôle et sa complexité". Transactions IEEE sur le génie logiciel. 18 (3): 237–251. est ce que je:10.1109/32.126773. ^ Dijkstra, Edger (1968). "Aller à la déclaration considérée comme nuisible". Communications de l'ACM. 11 (3): 147–148. est ce que je:10.1145/362929.362947. S2CID 17469809. Archivé de l'original sur 2007-07-03. ^ Sauter à: un b Roberts, E. [1995] "Sorties de boucle et programmation structurée: Rouvrir le débat," Bulletin ACM SIGCSE, (27)1: 268–272. ^ E. N. Votredon (1979). Classiques en génie logiciel. Presse Yourdon. pp. 49–50. ISBN 978-0-917072-14-7. ^ Ashcroft, Edouard; Manne du Zohar (1971). "La traduction des programmes aller aux programmes 'while'". Actes du Congrès IFIP. Le papier, qui est difficile à obtenir dans les actes originaux de la conférence en raison de leur diffusion limitée, a été republié dans Yourdon's 1979 livre pp. 51-65 ^ David Anthony Watt; Guillaume Findlay (2004). Concepts de conception de langage de programmation. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7. ^ Kenneth C. fort; Kenneth A.. Lambert (2011). Langages de programmation: Principes et pratiques (3 éd.). Apprentissage Cengage. pp. 422–423. ISBN 978-1-111-52941-3. ^ BASKET-BALL, S. RAO. "Analyse de programmes structurés," Proc. Cinquième sirop ACM annuel. Théorie de l'informatique, (Peut 1973), 240-252; aussi Kosaraju, S. Rao (1974). "Analyse de programmes structurés". Journal des sciences informatiques et des systèmes. 9 (3): 232–255. est ce que je:10.1016/S0022-0000(74)80043-7. cité par Donald Knuth (1974). "Programmation structurée avec go to Statements". Enquêtes informatiques. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. est ce que je:10.1145/356635.356640. S2CID 207630080. ^ Brender, Ronald F.. (2002). "Le langage de programmation BLISS: Une histoire" (PDF). Logiciel: Pratique et expérience. 32 (10): 955–981. est ce que je:10.1002/spe.470. S2CID 45466625. ^ Le papier original est Thomas J. McCabe (Décembre 1976). "Une mesure de complexité". Transactions IEEE sur le génie logiciel. SE-2 (4): 315–318. est ce que je:10.1109/ces.1976.233837. S2CID 9116234. Pour une exposition secondaire voir Paul C. Jorgensen (2002). Test de logiciel: L'approche d'un artisan, Deuxième édition (2sd éd.). Presse du CRC. pp. 150–153. ISBN 978-0-8493-0809-3. ^ Williams, M. H. (1983). "Schémas d'organigramme et problème de nomenclature". Le journal informatique. 26 (3): 270–276. est ce que je:10.1093/comjnl/26.3.270. ^ Ramshaw, L. (1988). "Éliminer les rendez-vous tout en préservant la structure du programme". Journal de l'ACM. 35 (4): 893–920. est ce que je:10.1145/48014.48021. S2CID 31001665. ^ Godfrey Nolan (2004). Décompiler Java. dépêche toi. p. 142. ISBN 978-1-4302-0739-9. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[URL nue PDF] ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[URL nue PDF] Further reading Material not yet covered above: DeMillo, Richard A.. (1980). "Compromis espace-temps dans la programmation structurée: Un théorème d'incorporation combinatoire amélioré". Journal de l'ACM. 27 (1): 123–127. est ce que je:10.1145/322169.322180. S2CID 15669719. Devienne, Philippe (1994). "Une clause de corne binaire suffit". Piles 94. Notes de cours en informatique. Volume. 775. pp. 19–32. CiteSeerX 10.1.1.14.537. est ce que je:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0. Catégories: Théorie des langages de programmationModèles de calculThéorèmes de la théorie de la complexité computationnelle