| dbpprop:abstract
|
- The structured program theorem is a result in programming language theory. It states that every computable function can be implemented in a programming language that combines subprograms in only three specific ways. These three control structures are Executing one subprogram, and then another subprogram (sequence) Executing one of two subprograms according to the value of a boolean variable (selection) Executing a subprogram until a boolean variable is true (iteration) Computer scientists usually credit the theorem to a 1966 paper by Corrado Böhm and Giuseppe Jacopini. However, David Harel traced its origins to the 1946 description of the von Neumann architecture and Stephen Kleene's normal form theorem. The Böhm-Jacopini proof describes how to construct a structured flow chart from an arbitrary chart, using the bits in an extra integer variable to keep track of information that the original program represents by the program location. This construction was based on Böhm's programming language P′′. 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, "Go To Statement Considered Harmful," followed in 1968. Subsequent proofs of the theorem addressed practical shortcomings of the Böhm-Jacopini proof with constructions that maintained or improved the clarity of the original program. In the 1980s IBM researcher Harlan Mills oversaw the development of the COBOL Structuring Facility, which applied a structuring algorithm to COBOL code. Mills's transformation involved the following steps for each procedure. Identify the basic blocks in the procedure. Assign a unique label to each block's entry path, and label each block's exit paths with the labels of the entry paths they connect to. Use 0 for return from the procedure and 1 for the procedure's entry path. Break the procedure into its basic blocks. For each block that is the destination of only one exit path, reconnect that block to that exit path. Declare a new variable in the procedure (called L for reference). On each remaining unconnected exit path, add a statement that sets L to the label value on that path. Combine the resulting programs into a selection statement that executes the program with the entry path label indicated by L Construct a loop that executes this selection statement as long as L is not 0. Construct a sequence that initializes L to 1 and executes the loop. Note that this construction can be improved by converting some cases of the selection statement into subprocedures.
- El teorema del programa estructurat és un resultat de la teoria de llenguatges de programació. Aquest teorema estableix que tota funció computable pot ser implementada per un llenguatge de programació que combini subrutines de només 3 tipus. Aquestes 3 formes també anomenades estructures de control són: Executar una subrutina i després un altre (estructures de seqüència) Executar una subrutina seleccionada d'entre 2 rutines possibles depenent d'un valor boolea (estructures de selecció com IF-THEN-ELSE) Executar una subrutina durant el temps que una variable booleana sigui certa (estructures d'iteració, cicle o bucle) Aquest teorema demostra que la instrucció GOTO no és estrictament necessària i que per a tot programa existeix un programa equivalent que no utilitza aquesta instrucció. El experts en computació acrediten aquest teorema a un article escrit per Corrado Böhm i Giuseppe Jacopini. Tot i això, David Harel va rastrejar els orígens d'aquest teorema fins arribar a la descripció de 1946 de la arquitectura de Von Neumann i el teorema formal de Kleene.
- El teorema del programa estructurado es un resultado en la teoría de lenguajes de programación. Establece que toda función computable puede ser implementada en un lenguaje de programación que combine subrutinas en únicamente tres formas. Esas tres formas son: Ejecutar una subrutina y luego otra subrutina (secuencia) Ejecutar una de dos subrutinas, dependiendo del valor de una variable booleana (selección o IF-THEN-ELSE) Ejecutar una subrutina mientras una variable booleana sea 'verdadera' (iteración, ciclo o bucle) Este teorema demuestra que la instrucción GOTO no es estrictamente necesaria y para todo programa existe un programa equivalente que no hace uso de dicha instrucción. Los científicos de la computación usualmente acreditan el teorema a un artículo de 1966 escrito por Corrado Böhm y Giuseppe Jacopini. Sin embargo, David Harel rastreó sus orígenes hasta la descripción de 1946 de la arquitectura de von Neumann y el teorema de la forma normal de Kleene. La demostración de Böhm-Jacopini describe cómo construir diagramas de flujo estructurados a partir de cualquier digrama de flujo, usando los bits de una variable entera extra para dar seguimiento a la información que el programa original representa mediante puntos de entrada en el código. Esta construcción estuvo basada en el lenguaje de programación P′′ de Böhm. La demostración de Böhm-Jacopini no esclareció la cuestión sobre cuándo convendría usar programación estructurada para el desarrollo de software, en parte porque la construcción ofuscaba el código del programa en lugar de mejorarlo. Por otro lado, fue el punto de partida para iniciar el debate. Edsger Dijkstra escribió una importante carta titulada "La sentencia Go To considerada dañina" en el año 1968. Demostraciones posteriores agregaron aproximaciones más prácticas a la demostración de Böhm-Jacopini, que mantenían o mejoraban la claridad del programa original.
- Il teorema di Böhm-Jacopini, enunciato nel 1966 dagli informatici Corrado Böhm e Giuseppe Jacopini, afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione ed il ciclo, da applicare ricorsivamente alla composizione di istruzioni elementari (ad es. di istruzioni eseguibili con il modello di base della macchina di Turing). La sequenza è la normale elencazione di istruzioni perché vengano eseguite una di seguito all'altra nell'ordine in cui sono state scritte dal programmatore. La selezione è la scelta fra due percorsi da seguire successivamente, che dipende da una condizione che può essere vera o falsa. Nei linguaggi di programmazione questa struttura viene definita, di solito, con l'uso di parole chiave come if ... then ... else. La condizione può essere una semplice variabile informatica booleana, cioè una variabile che può avere i soli valori "vero" e "falso". Nella pratica delle programmazione vengono normalmente usati costrutti selettivi come if (a > 10) nei quali l'espressione tra parentesi è una espressione booleana. Questo costrutto però si può considerare un'abbreviazione di una sequenza di assegnazioni preliminari conclusa da una selezione su una semplice variabile booleana. Nella pratica sono utilizzate anche selezioni a più di due vie, come quella implicita nell'operatore ?: del linguaggio C, lo storico IF a tre vie del FORTRAN 2 e i vari selettori a più vie come un'antica forma di GOTO del Fortran 2 e i costrutti come quello del C basato su switch e case. Anche tutti questi costrutti si possono ridurre senza difficoltà alla selezione dicotomica di base. Il ciclo, detto anche iterazione, è un blocco di istruzioni che vengono ripetutamente eseguite fino a che una certa condizione cambia di stato. Nella pratica si utilizzano diversi tipi di ciclo: quelli con la clausola sulla condizione in testa, quelli con la clausola in coda, quelli con la clausola in mezzo e quelli che prevedono lo scorrimento di una sequenza enumerativa (strettamente numerica o meno). Per l'implementazione si usano parole chiave come: while ... do, do ... until, for ... do, o similari. Anche tutti questi costrutti si possono ridurre ad un costrutto base. Questo teorema ha un interesse soprattutto teorico, in quanto, i linguaggi di programmazione tendono a dotarsi di più tipi di istruzioni di larga portata per evitare che i programmatori debbano occuparsi di istruzioni di portata molto minuta e quindi dispersive per quanto attiene alla padronanza delle finalità dell'algoritmo (esistono però linguaggi minimalisti, come Brainfuck, che si attengono alla lettera al teorema). Il suo valore va visto nella sua capacità di fornire indicazioni generali per le attività di progettazione di nuovi linguaggi e di strategie di programmazione. In effetti esso ha contribuito alla critica dell'uso sconsiderato delle istruzioni go to e alla definizione delle linee guida della programmazione strutturata che si sono avuti intorno al 1970.
|
![[RDF Data]](/statics/sw-cube.png)
