Teorema di Böhm-Jacopini

Il teorema di Böhm-Jacopini, enunciato nel 1966^[1] dagli informatici Corrado Böhm e Giuseppe Jacopini, è un teorema di informatica teorica il quale afferma che qualunque algoritmo può essere implementato in fase di programmazione (in diagramma di flusso, pseudocodice o codice sorgente) utilizzando tre sole strutture dette strutture di controllo: la sequenza, la selezione e l'iterazione, da applicare in modo gerarchico alla composizione di istruzioni elementari (per esempio, istruzioni eseguibili con il modello di base della macchina di Turing).

Storia

Il lavoro che enuncia questo risultato venne svolto dai due autori presso l'Istituto per le applicazioni del calcolo, di cui erano entrambi ricercatori, nell'ambito di una collaborazione con l'International Computing Center dell'UNESCO, che aveva sede presso lo stesso istituto. Il ruolo dei due autori è specificato nell'introduzione dell'articolo.^[2]

Strutture

Sequenza

La sequenza o blocco è la normale elencazione di istruzioni perché vengano eseguite una di seguito all'altra nell'ordine in cui sono state scritte dal programmatore.

Selezione (o condizionale)

La selezione è la scelta fra due percorsi da seguire alternativamente, 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 della programmazione vengono normalmente usati costrutti selettivi come if (a > 10) nei quali l'espressione tra parentesi è un'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 (istruzioni come: IF(numero)100,200,300) 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.

Ciclo (o iterazione)

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. Anche tutti questi costrutti si possono ridurre ad un costrutto base.

Dimostrazione del teorema

La dimostrazione del teorema di Böhm e Jacopini procede per induzione strutturale del diagramma di flusso.^[3] Avendo impiegato l'accoppiamento di pattern nei grafici, la dimostrazione di Böhm e Jacopini non fu molto utile come algoritmo di trasformazione dei programmi, ma aprì la porta a ricerche aggiuntive in questa direzione.^[4]

Conseguenze

Questo teorema ha un interesse anche 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.

Note

^ C. Bohm, e G. Jacopini, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules (PDF), in Communications of the ACM, vol. 9, n. 5, maggio 1966, pp. 366–371, DOI:10.1145/355592.365646. URL consultato il 5 agosto 2015.
^ In this paper, flow diagrams are introduced by the ostensive method; this is done to avoid definitions which certainly would not be of much use. In the first part (written by G. Jacopini), methods of normalization of diagrams are studied, which allow them to be decomposed into base diagrams of three types (first result) or of two types (second result). In the second part of the paper (by C. Böhm), some results of a previous paper are reported and the results of the first part of this paper are then used to prove that every Turing machine is reducible into, or in a determined sense is equivalent to, a program written in a language which admits as formation rules only composition and iteration.
^ David Harel, On Folk Theorems (PDF), in Communications of the ACM, vol. 23, n. 7, 1980, pp. 379–389, DOI:10.1145/358886.358892.
^ Z. Ammarguellat, A control-flow normalization algorithm and its complexity, in IEEE Transactions on Software Engineering, vol. 18, n. 3, 1992, pp. 237–251, DOI:10.1109/32.126773.