Ingegneria del software: teorema di Bohm-Jacopini
Il teorema di Bohm-Jacopini, enunciato nel 1966 dagli informatici Corrado Bohm e Giuseppe Jacopini, afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione ed il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari (ad es. di istruzioni eseguibili con il modello di base della macchina di Turing).
Strutture valide
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 (un es.: 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.
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.
Conseguenze del teorema di Bohm-Jacopini
Il teorema di Bohm-Jacopini 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.
