- un numero finito di operazioni, o meglio funzioni, da applicare ai dati per trasformarli;

- la distinzione tra un numero finito di "stati di computazione " nel programma e la capacità di saltare da uno all'altro tramite l'istruzione "goto" (vai a ..);

- una "struttura di controllo" capace di distinguere la situazione del momento e agire di conseguenza (cioè applicare operazioni e salti), che non è altro che la if .. then .. (se .. allora ..).

     Se noi abbiamo delle operazioni e le applichiamo una di seguito all'altra sempre nello stesso modo inventiamo solo un altro tipo di operazione. Quello che rende gli algoritmi capaci di fare molto di più di questo è che ad ogni passo possono scegliere, a seconda dello stato in cui sono giunti, come eseguire l'operazione presente e quale passo eseguire dopo.

     La situazione è ben rappresentata da un grafico in cui ci siano un numero finito di "nodi", rappresentanti gli stati di computazione, e da ognuno di essi escano delle frecce verso alcuni altri nodi. Il progredire del calcolo può essere visualizzato così: si parte dal nodo iniziale, eseguendo le operazioni lì specificate, e si passa al nodo successivo seguendo una delle frecce, quella corrispondente alla situazione in cui ci si trova; qui giunti si ripete, eseguendo le operazioni del nodo e scegliendo il successivo; e così via finché si trova l'istruzione di termine del calcolo.

     L'aspetto grafico della computazione sarà il cosiddetto "piatto di spaghetti", con un groviglio di linee tra un punto e l'altro. Quando l'arte della programmazione muoveva i primi passi i programmatori consideravano dimostrazione di bravura programmare con il minor numero di istruzioni possibili, e questo faceva sì che si tendesse a riutilizzare pezzi di codice semplicemente saltando al loro inizio. Ne risultavano complicati collegamenti tra le varie parti del programma, non facilmente intelleggibili a chi non lo avesse scritto.

     Il problema è che così facendo il programma risulta difficilmente comprensibile anche al suo estensore, specie quando è grande o quando questo gli pone mano dopo una lunga pausa. Inoltre, pur se questo modo di lavorare è ancora praticabile da un singolo programmatore, diventa del tutto inconcepibile per un lavoro di gruppo, quando è necessario che il codice sia facilmente capito anche da persone che non lo hanno scritto.

     Si è arrivati dunque, verso la fine degli anni sessanta, a cambiare completamente la visione di cosa sia un programma ben scritto, e a non considerare più la capacità di districarsi in mezzo ad aggrovigliate matasse di goto come principale caratteristica del buon programmatore.

     Lo schema che alla fine è emerso, detto "programmazione strutturata", si propone di dare l'aspetto di un flusso ordinato tra un inizio ed una fine a programmi che di per sé sarebbero intricati. Il modello è il "programma sequenziale", nel quale si applicano le varie operazioni una di seguito all'altra, in modo ordinato, senza alternative possibili. Abbiamo detto però che la semplice sequenza non può esprimere tutta la potenza degli algoritmi poiché questa è essenzialmente contenuta nella capacità di scegliere tra due alternative. Come si possono dunque conciliare queste due esigenze?

     L'idea è semplicissima: basta imitare il linguaggio naturale. Il goto è concepibile solo per una macchina i cui "pensieri" hanno dei ben determinati indirizzi, mentre in un linguaggio naturale un algoritmo è già espresso in una forma strutturata che corrisponde allo "svolgimento temporale" di una particolare computazione, quello cioè che si chiama un "processo". In un linguaggio naturale le costruzioni utilizzate sono "fai questo ... , dopo fai quello ... ", "se ... fai questo ... altrimenti fai quello ... ", "finché ... fai così ... " oppure "ripeti 5 volte questo ... ", che sono proprio le costruzioni di "controllo del flusso", sequenza, alternativa e ciclo, che saranno al centro di questa discussione.

     Possiamo dire che i linguaggi vicini alla macchina, come i programmi di Turing, i linguaggi Assembler o i più vecchi linguaggi di alto livello tendono naturalmente ad avere una struttura "a ragnatela spaziale", creata dai goto, mentre i linguaggi naturali e quelli di più alto livello tra i linguaggi di programmazione hanno una struttura temporale data dal "seguire lo svolgimento del processo". Questo fatto è visibile nel Fortran, che come primo linguaggio di livello superiore a quello della macchina ha ancora strutture di controllo molto primitive, specie nelle prime versioni. La tendenza ad imitare il linguaggio naturale è iniziata con Algol (1960), linguaggio che era appunto noto per la sua verbosità e che ha dato in eredità le sue strutture di controllo a quasi tutti i suoi successori. Non si può però dire che abbia inventato niente di straordinario, semplicemente perché queste strutture sono solo l'espressione, in inglese, delle frasi viste sopra, "if ... then ... else ... " ecc. .

     L'utilizzo delle forme di controllo di flusso "alla Algol", cioè l'alternativa, nella quale il flusso si divide in due rami per poi riunirsi, e il ciclo, in cui il flusso gira in tondo come in un gorgo, poneva il problema se tutti i programmi potessero essere scritti solo con essi, evitando l'ormai famigerato goto. La cosa è evidente per un programma pensato fin dall'inizio in termini naturali, lo è molto meno se si richiede di riscrivere in forma strutturata un programma pieno di salti tra un punto e l'altro.

     La cosa fu comunque risolta teoricamente nel 1966 dal teorema di Jacopini-Böhm: ogni programma di Turing può essere espresso con sequenze, alternative o cicli di blocchi di istruzioni. Il seguito sarà dedicato a chiarire i termini della questione, spesso non esposti accuratamente, soprattutto riguardo al fondamentale concetto di blocco.

     Esprimeremo i concetti in un quasi-C (misto a Basic e Pascal), non perché il C sia espressione di programmazione strutturata, cosa non vera in quanto, come molti altri linguaggi, mantiene l'istruzione goto, ma perché dispone di un simbolo, la parentesi graffa, che rende facilmente visibile il concetto, fondamentale per la comprensione del teorema, di blocco di istruzioni. Le caratteristiche dei vari termini quindi non si riferiscono al C reale.

     Il blocco di istruzioni è un sottoprogramma, cioè un insieme di istruzioni in sé completo, che non ha bisogno di far riferimento ad altro. E' importante notare che questo implica che il blocco ha un'unica uscita, la fine del blocco, e tutti i processi che eseguono istruzioni del blocco terminano qui. Se infatti ci fossero delle "uscite laterali" tramite delle istruzioni di salto, queste dovrebbero far riferimento ai nomi (etichette) dei punti di programma a cui saltare, per cui il sottoprogramma non sarebbe più autonomo, facendo riferimento a queste etichette. Inoltre si vuole che il blocco sia "opaco", nel senso che si possa utilizzare la sua capacità di elaborazione complessiva senza però vederne e poterne usare le singole parti (è un blocco, in fin dei conti!). Dall'esterno non si può quindi saltare ad una particolare sua istruzione che sia diversa dal semplice inizio del blocco. Queste due caratteristiche fanno sì che i processi esecutivi, attraversando un blocco, trovino un'unica entrata (l'inizio del blocco), un'unica uscita (la fine del blocco) e nessuna "uscita laterale".

     Questa, anche se di solito poco sottolineata, è la caratteristica principale della programmazione strutturata, perché prima di parlare del controllo del flusso (canali che si dividono o uniscono) bisogna sottolineare le caratteristiche di "impermeabilità" del tubo che porta questo flusso, che sono appunto una sola entrata, una sola uscita e niente perdite laterali.

     Dal punto di vista simbolico le parentesi del C sono il modo migliore di descrivere i blocchi:

   { ..... }

     L'inizio di un blocco corrisponde al simbolo "{", la fine al simbolo "}", e i blocchi possono essere annidati uno dentro l'altro come sono i livelli di parentesi in matematica.

     Un blocco può essere trattato (e pensato) a tutti gli effetti come una singola istruzione, e quindi la combinazione più semplice è la sequenza di blocchi:

   { B₁ } { B₂ } ..... { B_N }

     Graficamente:

     Vediamo invece come si esprimono alternative e cicli usando i blocchi. Prima di iniziare bisogna far notare che queste istruzioni condizionali si legano ad un particolare blocco, e quindi formano con esso un nuovo blocco che si dovrebbe indicare con due parentesi. Questo però renderebbe la notazione pesante, per cui è meglio pensare alle parole chiave, introdotte in sovrabbondanza rispetto al vero C (if, then, else, do, while, until, loop, ecc.), come a collanti tra le varie parti. Nel seguito per chiarezza si userà distinguere tramite colori blocchi di questo tipo, cioè non delimitati da parentesi. In alcuni casi le parentesi si rendono comunque necessarie. Per l'alternativa l'espressione (quasi C) è:

   if (A) then { B₁ } else { B₂ }

     Qui si ha la valutazione di una condizione, A; se questa è vera si esegue il primo blocco altrimenti si esegue il secondo. E' da notare che i termini "then" ed "else" non sono necessari per la costruzione, servono solo per chiarezza linguistica.

     Rispetto alle tipiche rappresentazioni grafiche dei diagrammi di flusso, qui adottiamo per le istruzioni decisionali dei cerchi invece dei soliti rombi. Questi ultimi sono usati perché sono sottointese due possibili risposte alternative, sì o no, corrispondenti a due vertici del rombo. Qui però pensiamo nel modo più generale, con scelta non tra due sole possibilità, ma tra quante si vuole (multibranch), per cui usiamo dei cerchi.

     Nello sforzo di essere minimali si può notare che la prima parte delle costruzione è già sufficiente scrivendo, in quasi C, senza "then" ma con un "do":

   if (A) do { B }

     Questa, che potremmo chiamare "esecuzione opzionale" perché si limita ad eseguire il blocco seguente, B, se è vera la condizione A, può infatti esprimere l'alternativa completa nel seguente modo:

   if (A) do { B } if (not A) do { B }

dove "not A" è la condizione opposta ad A, e B rappresenta due volte lo stesso blocco. A stretto rigore bisogna però prima "congelare" la condizione iniziale:

   {A₁ = A} if (A₁) do { B } if (not A₁) do { B }

cioè osservare il valore della condizione A all'inizio, scrivendolo in una nuova variabile A₁ che non sia modificata nel passaggio intermedio. La valutazione di condizioni come la if ( ... ) infatti hanno l'importante caratteristica di non modificare nessuna variabile (osservano solo la situazione), cosa che però non è garantita da un semplice blocco di istruzioni.

     Riguardo ai cicli, il più facile da descrivere è quello che richiede di eseguire un certo numero N di volte un blocco di istruzioni. Esprimendoci in questo caso quasi alla Pascal (con però un "do" in più) perché la costruzione C è poco trasparente:

   for i=1 to N do { ..... }

     Questo tipo di ciclo però è facilmente esprimibile usando quello generale, che valuta una condizione per l'esecuzione. Di questo tipo di ciclo ci sono due forme (la prima è scritta con un "do" in più rispetto al C):

   while (A) do { B }

oppure:

   do { B } while (A)

     Nel secondo si esegue il blocco una prima volta, ed alla fine si valuta la condizione e, nel caso sia vera, si ripete finché la condizione non diventi falsa. Nel primo invece la condizione viene valutata all'inizio, quindi il blocco potrebbe anche non essere mai eseguito, se la condizione è subito falsa. Oltre a queste due forme si trovano costruzioni equivalenti che usano la condizione in modo opposto, cioè se è vera non eseguono il ciclo. Abbiamo così la costruzione del Pascal:

   repeat { ..... } until (A)

e le costruzioni Basic:

do until (A) { ..... } loop	che è:	do while (not A) { ..... } loop
do { ..... } loop until (A)	che è:	do { ..... } loop while (not A)

     Queste comunque implicano solo il cambio di condizione, da "A" a "not A", nelle costruzioni precedenti e non sono quindi nulla di nuovo.

     L'importante è che i due tipi di cicli while sono equivalenti e possono esprimere il ciclo for. Per questo infatti basta scrivere:

   {i = 1} while (i = < N) do { ..... i = i + 1}

in cui si mette una istruzione di inizializzazione, i = 1, si aggiunge alla fine del blocco l'istruzione di incremento, i = i +1, con i = < N come condizione di ripetizione.

     Per gli altri due, "do ... while" può essere espresso con "while ... do" semplicemente ripetendo il blocco una prima volta, prima del ciclo, cioè:

   do { B } while (A)       che è:       { B } while (A) do { B }

     A rigore invece il "while ... do", che può avere zero esecuzioni, non può essere espresso con il "do ... while" che di esecuzioni ne fa almeno una. Se però si utilizza anche la "if ... do" questo è possibile, pur se contorto:

   while (A) do { B }       che è:       (A) do { do { B } while (A) }

     Riassumendo quindi il contenuto del teorema di Jacopini-Böhm si può dire che ogni programma di Turing può essere espresso organizzandolo in blocchi uno contenuto nell'altro, oppure in sequenza uno di seguito all'altro, con eventuali blocchi alternativi (if ... then ... else ...) o blocchi da ripetere in ciclo (while ... do ...).

     Graficamente si hanno dei flussi che scendono dall'alto verso il basso, con i blocchi rappresentati da rettangoli e le istruzioni di decisione da cerchi. I blocchi sono organizzati in "piani", e le frecce passano da un piano a quello inferiore, suddividendosi all'uscita delle istruzioni di decisione: l'unica eccezione è che una freccia può risalire di un piano per rieseguire un blocco, nel qual caso si ha una ripetizione ciclica. All'interno di un blocco tutta questa struttura può ripetersi rispetto a dei sottoblocchi.

     Si può dare una rappresentazione più simmetrica, anche se non di uso pratico, del teorema introducendo due costruzioni di salto all'inizio dei blocchi seguente o precedente, nel seguente modo:

1) istruzione "ometti-se", che chiamiamo "skip-if":

   skip-if (A) { B }          che è:       if (not A) do { B }

che, se è vera A, salta all'inizio del blocco successivo.

2) istruzione "ripeti-se", che chiamiamo "repeat-if":

   { B } repeat-if (A)       che è:       do { B } while (A)

che, se è vera A, salta all'inizio del blocco precedente (B).

     In questo caso si deve pensare ad una sequenza di blocchi:

   ... { B_-1 } { B₀ } { B₊₁ } ...

con le istruzioni skip-if o repeat-if davanti ad un blocco, in questo caso il blocco B₀:

   ... { B_-1 } istruzione-salto { B₀ } { B₊₁ } ...

     Si hanno i casi:

1) niente istruzione	>>	sequenza:	viene eseguito B0;
2) istruzione skip-if	>>	omissione:	viene eseguito B+1;
2) istruzione skip-if	>>	ripetizione:	viene eseguito B-1.

     Per distinguere anche graficamente questo tipo di rappresentazione, disponiamo i blocchi in orizzontale:

Sequenza:

Salto:

Ripetizione:

     Si vede quindi che si ha una notevole simmetria, e il teorema di Jacopini-Böhm può essere riespresso dicendo che un programma "if ... goto ..." può essere organizzato in blocchi contenuti gerarchicamente uno nell'altro oppure messi in sequenza con possibilità di salti condizionali di ± 1 posizioni, cioè rispettivamente con omissioni o ripetizioni condizionali.

     In questa formulazione si vede che i salti "qualsiasi" permessi dalle "if ... goto ..." vengono regolamentati. Intanto si ha una struttura sequenziale di istruzioni, come quella tipica dell'Assembler o della numerazione presente nelle prime versioni di Fortran e Basic; queste istruzioni sono riunite in blocchi che sono contenuti uno nell'altro o uno di seguito all'altro (in ogni caso non possono intersecarsi); le istruzioni di salto possono saltare in modo molto limitato, cioè solo all'inizio del blocco successivo o precedente (non servono quindi nemmeno etichette del target); quindi, visto che i blocchi non si intersecano, le "traiettorie" dei salti non si possono incrociare, e quindi non si ha il groviglio tipico del "piatto di spaghetti".

     Dal punto di vista "visuale" c'è qualcosa da dire sul significato delle tre costruzioni della "if", la "if ... goto ...", la "if ... do ..." e la "if ... then ... else ...". Nella prima la "if" è semplicemente una istruzione condizionale e l'informazione di salto è tutta contenuta nel "goto". Questa è l'istruzione dei programmi non strutturati, come quelli di Turing. La seconda, da chiamare "esecuzione opzionale", presuppone un ordinamento sequenziale dei blocchi, come quello di cui abbiamo appena parlato, perché fa esplicito riferimento al "blocco successivo". La terza, nominata "alternativa" e usata in tutti i linguaggi superiori oltre che nella formulazione originale del teorema di Jacopini-Böhm, fa riferimento all'immagine del "diagramma di flusso" o "diagramma a blocchi", e l'abbiamo vista più sopra. In questi il flusso esecutivo si divide in due, senza alcuna idea di salto, segue paritariamente le due alternative e si torna a riunire. Dal punto di vista logico non ha nemmeno importanza che le alternative siano due, come si vede dalle istruzioni "multibranch" che si trovano in C (switch), Pascal (case of) e anche Basic (select case). Per descrivere questa struttura si può dire che si ha un ordinamento "discendente" (dall'inizio alla fine) con dei punti di diramazione del flusso che si riunisce tutto in un punto "nuovo", cioè non già attraversato in precedenza. Il ciclo ha anche in questa rappresentazione lo stesso significato di ritorno all'inizio del blocco appena eseguito. Questi diagrammi di flusso hanno in sé più chiarezza della struttura sequenziale con omissioni e ripetizioni.

     Riguardo ai goto che permangono in molti linguaggi, bisogna dire che esiste un loro uso particolare che non contravviene alla strutturazione del programma, cioè non distrugge la chiarezza espositiva. Questo è il caso in cui il goto è usato per uscire dai cicli annidati, allo stesso modo delle istruzioni tipo "break" ed "exit" per un singolo ciclo. Questo uso residuale "buono" del goto può essere del tutto sostituito, come in Java, da un "break etichettato" per uscire da cicli annidati a più livelli.

     Per terminare, un accenno alle idee alla base della dimostrazione del teorema. Sostanzialmente si tratta di replicare il codice invece che riutilizzarlo "saltando indietro". Inoltre si eliminano i salti "a valle" costringendo l'alternativa che salta a seguire il flusso normale, senza però subire le computazioni di questo. Questa cosa si può fare introducendo delle variabili booleane ausiliarie con valori diversi per il flusso normale e quello "saltante", e testando prima di ogni esecuzione il loro valore, omettendo l'esecuzione nel caso del flusso saltante. Si vede quindi che il programma strutturato sarà più lungo, ripetitivo e, potremmo dire, ridondante dell'originale. Questo è il prezzo da pagare alla chiarezza e all'ordine, e non è troppo alto considerati i vantaggi che porta con sé.