Ricordi

 

 

Il teorema di Böhm

di Gianfranco Accattino

 

“Sono stato a trovare mio zio, il fratello di mia madre. Si chiama Corrado Böhm e si occupa di informatica”. Bastarono queste parole, buttate lì anni fa da David Terracini durante una chiacchierata, a farmi rizzare le antenne. Chiesi subito di precisare: “Ma non è mica quello del teorema di Böhm-Jacopini?”. Al sì di David, mi misi in piedi sull’attenti, mentalmente, forse anche fisicamente.

Per me, pensionato con esperienza informatica, Corrado Böhm era uno di quei nomi consegnati alla storia, per i quali è sorprendente apprendere che sono ancora in vita. Poiché, purtroppo, il 23 ottobre scorso Corrado Böhm ci ha lasciati, per entrare definitivamente nella storia dell’informatica, sono lieto di ricordarlo con queste righe, naturalmente su invito di David.

Corrado Böhm nacque a Milano nel 1923. Dal 1942 visse in Svizzera, prima a Losanna (dove si diplomò in ingegneria elettronica nel 1946) poi a Zurigo, come assistente di ricerca nella Scuola Politecnica Federale (ETH, Eidgenössische Technische Hochschule). Nel 1951 tornò in Italia. Dopo un breve periodo di lavoro all’Olivetti nel 1953, divenne ricercatore presso l'Istituto per le Applicazioni del Calcolo del CNR a Roma. Ottenne il dottorato in matematica nel 1954 con una tesi sottoposta all’ETH di Zurigo, in cui, quattro anni prima della pubblicazione del Fortran, si definivano i concetti di linguaggio e di compilatore. Negli anni ’60 Corrado Böhm continuò la sua attività in IAC (orientandosi dalla matematica verso l’informatica) mentre insegnava all’Università di Roma, avendo fra i suoi studenti Giuseppe Jacopini, poi suo collaboratore all’IAC.

Nel 1968 divenne professore di ruolo, prima a Modena, poi a Torino (dove creò nel 1970 il primo istituto di Scienze dell’Informazione) e infine ancora alla “Sapienza” di Roma.

La produzione scientifica di Corrado Böhm è sterminata. Mi limiterò a ricordare, per la sua importanza nello sviluppo delle tecniche di programmazione, il celeberrimo teorema di Böhm-Jacopini, enunciato nel 1966, quando Böhm e Jacopini erano ricercatori presso l'IAC.

Il teorema venne descritto e dimostrato in un articolo del maggio 1966 su “Communications of the ACM” dal titolo “Flow Diagrams, Turing Machines and Languages With Only Two Formation Rules”. Gli appassionati possono trovare il testo originale, nella sua rigorosa formulazione scientifica, in http://www.cs.unibo.it/~martini/PP/bohm-jac.pdf

Ma del teorema esiste anche una enunciazione accessibile a tutti, compresi i pensionati privi di esperienza informatica: “Qualunque algoritmo può essere implementato combinando ogni insieme di istruzioni secondo tre sole regole: sequenza, selezione, ripetizione ciclica”.

Algoritmo. Questa parola è entrata nel linguaggio comune, anche in forme retorico-allarmistiche (gli algoritmi condizionano la nostra vita!). Si tratta di un termine in uso da secoli, la cui etimologia è legata al nome del matematico persiano Al-Khwarizmi. Da “algoritmo” trasse il nome il linguaggio di programmazione Algol del 1958.

Dato uno stato iniziale, un algoritmo è una sequenza di istruzioni logiche e aritmetiche che dà risposta a una domanda.

Esempietto: dato un elenco di persone, dire per ognuna se è maggiorenne o minorenne.

Algoritmo:

1.    Scrivi “Elenco delle persone”

2.    Determina l’anno attuale

3.    Ripeti finché ci sono dati da leggere

3.1.  Leggi nome-cognome

3.2.  Scrivi nome-cognome

3.3.  Scrivi “nato nel”

3.4.  Leggi anno di nascita

3.5.  Scrivi anno di nascita

3.6.  Scrivi “è m”

3.7.  Se (anno di nascita < anno attuale - 18) allora Scrivi “aggi” altrimenti Scrivi “in”

3.8.  Scrivi “orenne.” e vai a capo

4.    Scrivi “Fine elenco delle persone”

 

In questo pur banale esempio sono riconoscibili le tre regole di Böhm-Jacopini: la sequenza di istruzioni, la ripetizione ciclica da 3.1 a 3.8, nella quale il punto 3.7 (cuore dell’algoritmo) è la selezione in base alla quale si dà la risposta alla domanda.

Le tre regole (sequenza, selezione, ripetizione) sono simbolicamente rappresentate nei linguaggi di programmazione da forme come begin … end - if … then … else … endif - repeat oppure while oppure for.

Ciò che è importante è che non è mai necessario trasferire il punto corrente del calcolo a un altro punto mediante l’istruzione goto. L’elaborazione fluisce naturalmente, in un’unica sequenza.

Il lavoro di Böhm-Jacopini dimostrava la non-necessità del goto, ma fu seguito a distanza di due anni da un altrettanto famoso articolo del matematico olandese Edsger W. Dijkstra (altra figura storica dell’informatica) pubblicato con il significativo (ed esplosivo!) titolo “Go-to statement considered harmful”.

Gli appassionati lo troveranno in http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF

Si accese una vivace polemica sulla programmazione senza goto (goto-less programming), intesa come base per una “programmazione strutturata” (concetto elaborato dallo stesso Dijkstra), ossia una programmazione come disciplina scientifica basata sul rigore matematico.

Ispirati a questo concetto nacquero nuovi linguaggi in alternativa ai predominanti Fortran e Cobol: Pascal (sviluppato da Niklaus Wirth, non a caso all’ETH di Zurigo), PL/1, Ada.

Di quella polemica, sviluppatasi a cavallo tra gli anni ’60 e ’70, ho dei ricordi precisi. Ero invaso da un senso di colpa ogni volta che introducevo un GOTO nei miei programmini in Fortran (il Fortran divenne “strutturato” solo nel 1977). Mi consolava l’opinione di uno dei pochi fautori del GOTO: “Perché mai dovrei rinunciare a una istruzione così semplice, esplicita e diretta che può essere capita anche dal mio cane?”.

Dopo cinquant’anni, polemiche come queste ci fanno sorridere. La programmazione strutturata è un concetto acquisito. Il goto è stato relegato a strumento da usare in eccezionali condizioni di emergenza, esattamente come si accetta che da un treno si esca di norma passando per una porta e solo eccezionalmente attraverso una finestra spaccandone il vetro.

Come accade in ogni campo, sta ai profeti produrre concetti nuovi e anti-intuitivi destinati nei tempi successivi a diventare opinione comune. Corrado Böhm ha svolto, con tanti altri, questo ruolo profetico.

Torniamo alla programmazione strutturata, che è rigore matematico ma soprattutto eleganza formale. Ed è anche un modo per costruire programmi facilmente mantenibili ed espandibili. Questo è un aspetto fondamentale per quanto riguarda i costi di produzione e manutenzione del software.

Riprendiamo l’esempietto di cui sopra.

I lettori più attenti si saranno accorti che la soluzione proposta è un po’ sbrigativa, basandosi solo sull’anno di nascita, e considerando quindi maggiorenni anche persone che, al momento in cui si esegue il programma, maggiorenni non sono. Questo criterio sbrigativo può anche essere valido, dipende dal contesto in cui si applica. Se ci trovassimo in un contesto in cui la condizione di maggiore età deve essere determinata con maggior rigore (esistono casi limite in cui si deve tenere conto anche del minuto di nascita!) occorre raffinare l’algoritmo.

Altro punto critico: le lettrici più attente si saranno accorte che il programma scrive sempre “nato”, anche per le femmine. Argomento scottante, in questi tempi di sindache e assessore. Anche qui occorre intervenire.

L’algoritmo originale e rudimentale può essere raffinato fino ai massimi livelli pur mantenendo inalterate le tre regole di Böhm-Jacopini: sequenza, ripetizione, selezione.

Nel primo caso (determinazione rigorosa della maggiore età) occorrerà modificare l’istruzione di selezione 3.7 introducendo dopo “altrimenti” una nuova sequenza Determina-Leggi-Scrivi-Se relativa al mese di nascita. Ma non basta: questa nuova sequenza può essere migliorata inanellando una nuova sequenza relativa al giorno, e poi anche all’ora, al minuto. Ne nasce una struttura di if - then - elseif logicamente coerente ed efficiente, in una parola elegante. L’efficienza consiste nel fatto che, per esempio, non si deve sprecare tempo di elaborazione per acquisire il giorno di nascita quando, ai fini del nostro problema, basta sapere l’anno. In generale, ogni istruzione viene eseguita solo se e quando serve.

L’eleganza è anche fisicamente evidente leggendo il programma opportunamente indentato (termine nuovo, la cui spiegazione lascio ai lettori interessati …).

Nel secondo caso (questione di genere), dopo 3.2 occorre aggiungere (in sequenza) “Leggi genere” mentre la successiva istruzione puntuale “Scrivi” diventa una sequenza che ha al suo interno un’istruzione di selezione:

  • Scrivi “nat”

  • Se genere=M Scrivi “o” altrimenti Scrivi “a”

  • Scrivi “nel”

Mi resta il rimpianto di non aver mai avuto la possibilità, attraverso David, di incontrare Corrado Böhm. Ma forse è meglio così. Sarei rimasto irrigidito e ammutolito dal timore di fare domande inutili o affermazioni banali. Così come inutile e banale egli forse giudicherebbe questo mio ricordo, se gli fosse possibile leggerlo. Ma non gli è possibile, e questo è il vero rimpianto, per me e per tutti noi.

 

Gianfranco Accattino

 

Corrado  Böhm

 

 

Share |