Teorema del programma strutturato

Teorema del programma strutturato Rappresentazione grafica dei tre modelli di base del teorema del programma strutturato — sequenza, selezione, e ripetizione — usando i diagrammi NS (blu) e diagrammi di flusso (verde).

Il teorema del programma strutturato, chiamato anche teorema di Böhm-Jacopini,[1][2] è un risultato della teoria del linguaggio di programmazione. Afferma che una classe di grafici di flusso di controllo (storicamente chiamati diagrammi di flusso in questo contesto) può calcolare qualsiasi funzione calcolabile se combina i sottoprogrammi solo in tre modi specifici (strutture di controllo). These are Executing one subprogram, e poi un altro sottoprogramma (sequenza) Esecuzione di uno dei due sottoprogrammi in base al valore di un'espressione booleana (selezione) Esecuzione ripetuta di un sottoprogramma fintanto che un'espressione booleana è vera (iterazione) Il grafico strutturato soggetto a questi vincoli può tuttavia utilizzare variabili aggiuntive sotto forma di bit (memorizzato in una variabile intera aggiuntiva nella prova originale) al fine di tenere traccia delle informazioni che il programma originale rappresenta dalla posizione del programma. La costruzione era basata sul linguaggio di programmazione di Böhm P′′.

Il teorema costituisce la base della programmazione strutturata, un paradigma di programmazione che evita i comandi goto e utilizza esclusivamente subroutine, sequenze, selezione e iterazione.

Contenuti 1 Origine e varianti 1.1 Ciclo singolo, versione popolare del teorema 1.2 La dimostrazione di Böhm e Jacopini 2 Implicazioni e perfezionamenti 3 Applicazione a Cobol 4 Guarda anche 5 Riferimenti 6 Further reading Origin and variants The theorem is typically credited[3]:381  ad a 1966 paper by Corrado Böhm and Giuseppe Jacopini.[4] David Harel ha scritto 1980 che il giornale Böhm–Jacopini godette "popolarità universale",[3]:381  in particolare con i fautori della programmazione strutturata. Harel lo ha anche notato "per il suo stile piuttosto tecnico [il 1966 Carta Boehm-Jacopini] è apparentemente più spesso citato che letto in dettaglio"[3]:381  e, dopo aver esaminato un gran numero di articoli pubblicati fino a 1980, Harel ha sostenuto che il contenuto della dimostrazione di Böhm-Jacopini era solitamente travisato come un teorema popolare che contiene essenzialmente un risultato più semplice, un risultato che a sua volta può essere ricondotto all'inizio della moderna teoria dell'informatica negli articoli di von Neumann e Kleene.[3]: 383  Harel also writes that the more generic name was proposed by H.D. Mulini come "Il teorema della struttura" nei primi anni '70.[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 (caselle del diagramma di flusso) nel programma originale non strutturato. Harel fece risalire l'origine di questo teorema popolare a due documenti che segnarono l'inizio dell'informatica. Uno è il 1946 descrizione dell'architettura di von Neumann, che spiega come funziona un contatore di programma in termini di un ciclo while. Harel osserva che il singolo ciclo utilizzato dalla versione popolare del teorema di programmazione strutturata fornisce fondamentalmente solo la semantica operativa per l'esecuzione di un diagramma di flusso su un computer di von Neumann.[3]:383  Un altro, fonte ancora più antica che Harel ha tracciato la versione popolare del teorema è il teorema della forma normale di Stephen Kleene da 1936.[3]: 383  Donald Knuth criticized this form of the proof, che risulta in uno pseudocodice come quello qui sotto, sottolineando che la struttura del programma originale è completamente persa in questa trasformazione.[5]:274  Allo stesso modo, Bruce Ian Mills ha scritto di questo approccio che "Lo spirito della struttura a blocchi è uno stile, non una lingua. Simulando una macchina di Von Neumann, possiamo produrre il comportamento di qualsiasi codice spaghetti entro i confini di un linguaggio strutturato a blocchi. Questo non impedisce che siano spaghetti."[6] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := numero del passo successivo risultante del passo 1 dal diagramma di flusso (0 se nessun successore) end if if p = 2 then perform step 2 from the flowchart p := numero del passo successivo risultante del passo 2 dal diagramma di flusso (0 se nessun successore) finisci se ...

if p = n then perform step n from the flowchart p := numero del passaggio successivo risultante del passaggio n dal diagramma di flusso (0 se nessun successore) end if end while Böhm and Jacopini's proof This section needs expansion. Puoi contribuire aggiungendo ad esso. (Luglio 2014) La dimostrazione nell'articolo di Böhm e Jacopini procede per induzione sulla struttura del diagramma di flusso.[3]:381  Perché utilizzava il pattern matching nei grafici, la dimostrazione di Böhm e Jacopini non era realmente pratica come algoritmo di trasformazione del programma, e ha così aperto la porta per ulteriori ricerche in questa direzione.[7] Implications and refinements The Böhm–Jacopini proof did not settle the question of whether to adopt structured programming for software development, in parte perché la costruzione aveva più probabilità di oscurare un programma che di migliorarlo. Anzi, segnò l'inizio del dibattito. La famosa lettera di Edsger Dijkstra, "Vai alla dichiarazione considerata dannosa," seguito 1968.[8] Alcuni accademici hanno adottato un approccio purista al risultato di Böhm–Jacopini e hanno sostenuto che anche istruzioni come pausa e ritorno dal centro dei cicli sono una cattiva pratica in quanto non sono necessarie nella dimostrazione di Böhm–Jacopini, e quindi hanno sostenuto che tutti i loop dovrebbero avere un unico punto di uscita. Questo approccio purista è incarnato nel linguaggio di programmazione Pascal (progettato nel 1968-1969), che fino alla metà degli anni '90 era lo strumento preferito per l'insegnamento delle classi introduttive di programmazione nel mondo accademico.[9] Edward Yourdon osserva che negli anni '70 c'era persino un'opposizione filosofica alla trasformazione di programmi non strutturati in programmi strutturati con mezzi automatizzati, sulla base dell'argomento che si doveva pensare in modo strutturato fin dall'inizio. Il contrappunto pragmatico era che tali trasformazioni hanno giovato a un ampio corpus di programmi esistenti.[10] Tra le prime proposte per una trasformazione automatizzata c'era a 1971 articolo di Edward Ashcroft e Zohar Manna.[11] L'applicazione diretta del teorema di Böhm-Jacopini può comportare l'introduzione di ulteriori variabili locali nel grafico strutturato, e può anche comportare la duplicazione del codice.[12] Quest'ultimo problema è chiamato il problema del ciclo e mezzo in questo contesto.[13] Pascal è affetto da entrambi questi problemi e secondo gli studi empirici citati da Eric S. Roberts, i programmatori studenti hanno avuto difficoltà a formulare soluzioni corrette in Pascal per diversi problemi semplici, inclusa la scrittura di una funzione per la ricerca di un elemento in un array. UN 1980 lo studio di Henry Shapiro citato da Roberts ha scoperto che utilizzando solo le strutture di controllo fornite da Pascal, la soluzione corretta è stata data da only 20% dei soggetti, mentre nessun soggetto ha scritto codice errato per questo problema se è stato autorizzato a scrivere un ritorno dal mezzo di un ciclo.[9] In 1973, S. Rao Kosaraju ha dimostrato che è possibile evitare di aggiungere ulteriori variabili nella programmazione strutturata, purché di profondità arbitraria, sono consentite interruzioni a più livelli dai loop.[1][14] Inoltre, Kosaraju ha dimostrato che esiste una rigida gerarchia di programmi, al giorno d'oggi chiamato la gerarchia Kosaraju, in quanto per ogni intero n, esiste un programma contenente un'interruzione multilivello di profondità n che non può essere riscritta come programma con interruzioni multilivello di profondità inferiore a n (senza introdurre variabili aggiuntive).[1] Kosaraju cita il costrutto break multi-level al linguaggio di programmazione BLISS. Le interruzioni a più livelli, nella forma una parola chiave etichetta di congedo è stata effettivamente introdotta nella versione BLISS-11 di quella lingua; il BLISS originale aveva solo interruzioni di un livello. La famiglia di lingue BLISS non ha fornito un goto illimitato. Anche il linguaggio di programmazione Java avrebbe seguito questo approccio.[15]: 960–965  A simpler result from Kosaraju's paper is that a program is reducible to a structured program (senza aggiungere variabili) se e solo se non contiene un ciclo con due uscite distinte. La riducibilità è stata definita da Kosaraju, parlando in modo approssimativo, come calcolare la stessa funzione e utilizzarla "azioni primitive" e predicati come il programma originale, ma possibilmente utilizzando diverse strutture di flusso di controllo. (Questa è una nozione di riducibilità più ristretta di quella usata da Böhm–Jacopini.) Ispirato da questo risultato, nella sezione VI del suo citato articolo che introduceva la nozione di complessità ciclomatica, Thomas J. McCabe ha descritto un analogo del teorema di Kuratowski per i grafici del flusso di controllo (CFG) di programmi non strutturati, vale a dire, i sottografi minimi che rendono non strutturato il CFG di un programma. Questi sottografi hanno un'ottima descrizione in linguaggio naturale. Sono: diramarsi da un ciclo (diverso dal ciclo di prova del ciclo) diramazione in un ciclo diramazione in una decisione (cioè. in un se "ramo") branching out of a decision McCabe actually found that these four graphs are not independent when appearing as subgraphs, il che significa che una condizione necessaria e sufficiente affinché un programma non sia strutturato è che il suo CFG abbia come sottografo uno di qualsiasi sottoinsieme di tre di questi quattro grafici. Ha anche scoperto che se un programma non strutturato contiene uno di questi quattro sottografici, deve contenere un altro distinto dall'insieme di quattro. Quest'ultimo risultato aiuta a spiegare come il flusso di controllo del programma non strutturato si impigli in ciò che viene comunemente chiamato "codice spaghetti". McCabe ha anche ideato una misura numerica che, dato un programma arbitrario, quantifica quanto è lontano dall'ideale di essere un programma strutturato; McCabe ha chiamato la sua misura complessità essenziale.[16] La caratterizzazione di McCabe dei grafi proibiti per la programmazione strutturata può essere considerata incompleta, almeno se le strutture D di Dijkstra sono considerate gli elementi costitutivi.[17]:274–275[chiarimenti necessari] Fino a 1990 c'erano alcuni metodi proposti per eliminare i goto dai programmi esistenti, preservando la maggior parte della loro struttura. I vari approcci a questo problema proponevano anche diverse nozioni di equivalenza, che sono più severi della semplice equivalenza di Turing, al fine di evitare output come il teorema popolare discusso sopra. Il rigore della nozione di equivalenza prescelta determina l'insieme minimo di strutture di flusso di controllo necessarie. Il 1988 Il documento JACM di Lyle Ramshaw esamina il campo fino a quel momento, oltre a proporre il proprio metodo.[18] L'algoritmo di Ramshaw è stato utilizzato ad esempio in alcuni decompilatori Java perché il codice della macchina virtuale Java ha istruzioni branch con target espressi come offset, ma il linguaggio Java di alto livello ha solo istruzioni break e continue a più livelli.[19][20][21] Sviene (1992) proposto un metodo di trasformazione che torna a far rispettare l'uscita singola.[7] Application to Cobol This section needs additional citations for verification. Aiutaci a migliorare questo articolo aggiungendo citazioni a fonti affidabili. Il materiale non fornito può essere contestato e rimosso. (agosto 2013) (Scopri come e quando rimuovere questo messaggio modello) Negli anni '80 il ricercatore IBM Harlan Mills ha supervisionato lo sviluppo della COBOL Structuring Facility, che ha applicato un algoritmo di strutturazione al codice COBOL. La trasformazione di Mills ha comportato i seguenti passaggi per ciascuna procedura.

Identificare i blocchi di base nella procedura. Assegna un'etichetta univoca al percorso di ingresso di ogni blocco, ed etichettare i percorsi di uscita di ogni blocco con le etichette dei percorsi di ingresso a cui si connettono. Uso 0 per il ritorno dalla procedura e 1 per il percorso di ingresso della procedura. Suddividi la procedura nei suoi blocchi di base. Per ogni blocco che è la destinazione di un solo percorso di uscita, ricollegare quel blocco a quel percorso di uscita. Dichiarare una nuova variabile nella procedura (chiamato L per riferimento). Su ogni percorso di uscita non connesso rimanente, aggiungi un'istruzione che imposta L al valore dell'etichetta su quel percorso. Combina i programmi risultanti in un'istruzione di selezione che esegua il programma con l'etichetta del percorso di ingresso indicata da L Costruisci un ciclo che esegua questa istruzione di selezione fintanto che L non è 0. Costruisci una sequenza che inizializza L a 1 ed esegue il ciclo.

Si noti che questa costruzione può essere migliorata convertendo alcuni casi dell'istruzione di selezione in sottoprocedure.

Vedi anche Programmazione strutturata Completezza Turing Riferimenti ^ Salta a: a b c Dexter Kozen e Wei-Lung Dustin Tseng (2008). Il teorema di Böhm-Jacopini è falso, In modo propositivo (PDF). MPC 2008. Appunti delle lezioni in Informatica. 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, Autunno 2004, TEOREMA DI BOEHM-JACOPINI". Cse.buffalo.edu. 2004-11-22. Recuperato 2013-08-24. ^ Salta su: a b c d e f g h Harel, Davide (1980). "Sui teoremi popolari" (PDF). Comunicazioni dell'ACM. 23 (7): 379–389. doi:10.1145/358886.358892. S2CID 16300625. ^ Bohm, Corrado; Giuseppe Jacopini (Maggio 1966). "Diagrammi di flusso, Macchine di Turing e linguaggi con solo due regole di formazione". Comunicazioni dell'ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439. ^ Donald Knuth (1974). "Programmazione strutturata con vai a Statements". Indagini informatiche. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Bruce Ian Mills (2005). Introduzione teorica alla programmazione. Springer. p. 279. ISBN 978-1-84628-263-8. ^ Salta su: a b Ammarguellat, Z. (1992). "Un algoritmo di normalizzazione del flusso di controllo e la sua complessità". Transazioni IEEE sull'ingegneria del software. 18 (3): 237–251. doi:10.1109/32.126773. ^ Dijkstra, Edsger (1968). "Vai alla dichiarazione considerata dannosa". Comunicazioni dell'ACM. 11 (3): 147–148. doi:10.1145/362929.362947. S2CID 17469809. Archiviato dall'originale in poi 2007-07-03. ^ Salta su: a b Roberts, e. [1995] "Uscite di loop e programmazione strutturata: Riapertura del dibattito," Bollettino ACM SIGCSE, (27)1: 268–272. ^ E. N. Tuodon (1979). Classici in Ingegneria del Software. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7. ^ Ashcroft, Edoardo; Zohar Manna (1971). "La traduzione di vai ai programmi in programmi 'while'". Atti del Congresso IFIP. La carta, che è difficile da ottenere negli atti del convegno originale a causa della loro distribuzione limitata, è stato ripubblicato in Yourdon's 1979 libro pagg. 51-65 ^ David Anthony Watt; William Findlay (2004). Concetti di progettazione del linguaggio di programmazione. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7. ^ Kenneth C. Forte; Kenneth A. Lambert (2011). Linguaggi di programmazione: Principi e pratiche (3 ed.). Apprendimento Cengage. pp. 422–423. ISBN 978-1-111-52941-3. ^ PALLACANESTRO, S. RAO. "Analisi di programmi strutturati," Proc. Quinto Sciroppo ACM Annuale. Teoria dell'informatica, (Maggio 1973), 240-252; anche Kosaraju, S. Rao (1974). "Analisi di programmi strutturati". Giornale di scienze informatiche e dei sistemi. 9 (3): 232–255. doi:10.1016/S0022-0000(74)80043-7. citato da Donald Knuth (1974). "Programmazione strutturata con vai a Statements". Indagini informatiche. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Brender, Ronald F. (2002). "Il linguaggio di programmazione BLISS: una storia" (PDF). Software: Pratica ed Esperienza. 32 (10): 955–981. doi:10.1002/spe.470. S2CID 45466625. ^ La carta originale è Thomas J. McCabe (Dicembre 1976). "Una misura di complessità". Transazioni IEEE sull'ingegneria del software. SE-2 (4): 315–318. doi:10.1109/questi.1976.233837. S2CID 9116234. Per un'esposizione secondaria vedi Paul C. Jorgensen (2002). Test del software: Un approccio da artigiano, Seconda edizione (2nd ed.). CRC Press. pp. 150–153. ISBN 978-0-8493-0809-3. ^ Williams, M. H. (1983). "Diagrammi di flusso e il problema della nomenclatura". Il giornale informatico. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270. ^ Ramshaw, l. (1988). "Eliminare i go to preservando la struttura del programma". Giornale dell'ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665. ^ Godfrey Nolan (2004). Decompilare Java. fretta. p. 142. ISBN 978-1-4302-0739-9. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[URL nudo PDF] ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[URL nudo PDF] Further reading Material not yet covered above: De Millo, Riccardo A. (1980). "Compromessi spazio-temporali nella programmazione strutturata: Un teorema di incorporamento combinatorio migliorato". Giornale dell'ACM. 27 (1): 123–127. doi:10.1145/322169.322180. S2CID 15669719. Diventare, Filippo (1994). "È sufficiente una clausola di corno binario". Pile 94. Appunti delle lezioni in Informatica. 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. Categorie: Teoria dei linguaggi di programmazioneModelli di calcoloTeoremi nella teoria della complessità computazionale