Capitolo II
L’UNESCO e le sue iniziative per l’informatica
John W. Backus e l’idea di un nuovo metalinguaggio formale per l’informatica
SOMMARIO
§ 2.1 - Le iniziative dell’UNESCO per l’informatica
§ 2.4 - La lettera di Donald Knuth per ribattezzare la BNF: Backus Normal Form vs. Backus Naur Form
§ 2.1 - Le iniziative dell’UNESCO per l’informatica
Ulteriore elemento “probatorio”[54] di questo entusiastico fermento iniziale legato ad ALGOL troviamo il grande interesse che l’UNESCO, (l’Organizzazione delle Nazioni Unite per l'Educazione, la Scienza e la Cultura) cominciò a dedicare a quello che non era un semplice fatto tecnologico, bensì ad un nuovo fenomeno culturale da assimilare nella sua interezza e trasformare in una nuova disciplina scientifica e, per molti versi, umanistica: l’informatica.
I primi passi che mosse l’UNESCO rispetto ad ALGOL, e alla nascente informatica, furono:
- La prima ICIP, International Conference Information Processing, che si tenne a Parigi dal 15 al 20 giugno del 1959 nel nuovo complesso UNESCO a Place de Fontenoy (vedi notizie su Appendice al Capitolo II) ora considerata come il primo congresso dell’IFIP, di cui sotto. Tra i vari relatori anche J. W. Backus che presentò ufficialmente la sua notazione BNF.
- La International Federation of Information Processing Societies (IFIPS) ha come fondatore un nome di eccellenza: Isaac L. Auerbach, ingegnere e informatico statunitense. Nata nel 1960 come organizzazione globale per ricercatori e professionisti IT per condurre ricerche, sviluppare standard e promuovere la condivisione delle informazioni. Il suo gruppo, WG 2.1, dal marzo 1959 all'agosto 1988, ha curato i 52 numeri del Bollettino ALGOL
-----------------------------
[54] Per consultare altri materiali relativi a quel periodo storico visitare le APPENDICI ai capitoli di questo sito
§ 2.2 - La nascita della BNF
Come abbiamo visto in precedenza, nell’ambito dei lavori della Conferenza ICIP di Parigi del giugno ’59, John Backus presentò la sua notazione in un documento intitolato:
“The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference”[55]
in cui illustrava la formulazione del suo metalinguaggio formale applicato alla strutturazione del nascente Linguaggio Algebrico Internazionale.
Era la prima stesura del suo reference language,[56] quella notazione poi così ampiamente utilizzata per la descrizione degli algoritmi nelle varie pubblicazioni successive, lasciando le specifiche per l’input/output alle realizzazioni effettive.
È mio pensiero che Backus, da buon matematico, avesse deciso di realizzare la sua notazione per dipanare qualunque equivoco espositivo tra i partecipanti al progetto, riflettendo sulle molteplici cause che avrebbero potuto generare incomprensioni tra i formulatori del nuovo linguaggio:
- La differente estrazione culturale in termini di lingua, formazione, provenienza, esperienze, ambiti operativi, ecc.
- Le diverse aspettative interne agli USA di ACM, da una parte e di SHARE, DUO e USE dall’altra.
A rafforzare la mia convinzione è la notizia di un malinteso che fece accogliere con favore una delibera sull’IAL approvata durante l'undicesima riunione di SHARE.[57]
L’equivoco fu originato da una lettura imprecisa del contenuto e del contesto della delibera dovuto al linguaggio impiegato che era intenzionalmente ambiguo.
Ad aumentare la comicità del fatto è che nel corso degli anni certa storiografia ha spesso interpretato quella delibera come una piena adesione di SHARE ad ALGOL come linguaggio di programmazione universale! Sic.
Invece ora sappiamo bene che in realtà SHARE aveva a stento raggiunto un fragile accordo interno sulla convenienza di mantenere la molteplicità dei linguaggi di programmazione.
-----------------------------
[55] Il documento è consultabile liberamente al seguente link: https://www.softwarepreservation.org/projects/ALGOL/paper/Backus-ICIP-1959.pdf
[56] Verbatim Transcript of the SHARE 11th Meeting, September 9-12, 1958, Appendix C-17, p. 1. SHARE Inc. Records (CBI 21), box 3, folder 17.
[57] Ibidem.
§ 2.3 - Avvertenze sulla traduzione de: “The syntax and semantics of the proposed International Algebraic Language” di John Backus
Per ragioni di spazio e di grafica ho ritenuto opportuno rimandare il visitatore ad una copia sfogliabile on line della traduzione del documento di presentazione della BNF in cui sono riportati, oltre alla spiegazione sull'uso, tutti i simboli che l’informatico statunitense ritenne opportuno impiegare per descrivere ALGOL in vari ambiti di pubblicazione.
Ho pensato di rendere disponibile agli interessati il documento da me tradotto, avvalendomi di Google Traduttore, attraverso due file in formato docx e PDF liberamente scaricabili da Google Drive i cui link sono a fine paragrafo
Mi preme precisare che per non alterare i simboli ideati da Backus nel suo testo ho ritenuto opportuno effettuare una serie di catture video lì dove comparivano segni grafici non presenti nel set di font Times New Roman con cui è stato redatto il testo. Va da sé che il lettore/studioso/appassionato più zelante potrà riprodurre, se necessario, sicuramente con font vettoriali come il Cambria Math ciò che io mi sono limitato a copiare.
Il lettore noterà che la numerazione associata alla descrizione dei vari passi della notazione risulta alquanto discontinua; a tal proposito mi preme precisare che mi sono limitato a copiare verbatim il testo originale così come riportato nel documento di cui al seguente link:
limitandomi a disporre lo scritto su di una sola colonna anziché su due.
Per la traduzione ho utilizzato una struttura tabellare che mi ha consentito di spostare, nella colonna di sinistra, i capoversi delle descrizioni in modo tale da agevolare la consultazione del documento tradotto.
consultazione online e DOWNLOAD TRADUZIONE DOCUMENTO ICIP DI JOHN W. BACKUS SULLA BNF
- Scarica DOCX da Google Drive (Word) 44,1 MB
- Scarica il PDF da Google Drive 1,9 MB
§ 2.4 - La lettera di Donald Knuth per ribattezzare la BNF: Backus Normal Form vs. Backus Naur Form
È una beautiful mind a scrivere, nel 1964, una lettera all'editore del Communications of the ACM per proporre un cambio di nome alla notazione di Backus che, all’epoca, era comunemente chiamata Backus Normal Form; si trattava di un giovanissimo matematico: Donald Knuth, all’epoca alle prese col suo dottorato di ricerca presso il California Institute of Technology, dove successivamente lavorò come associato.
Dopo aver ricevuto l'incarico di scrivere un libro sui compilatori, si dedicò alla scrittura di quella che si sarebbe estesa a un'opera in più volumi, destinata a divenire un classico dell'algoritmica, The Art of Computer Programming.
Ho deciso di tradurre e riportare la lettera di Knuth a conclusione di questo lungo capitolo sulla storia iniziale di ALGOL e della BNF per fornire un quadro abbastanza completo al lettore su quelle vicende così lontane ma, al contempo, tanto ricche di passione per la nascente scienza informatica.
Caro editore:
Negli ultimi anni è diventata consuetudine fare riferimento alla sintassi presentata alla maniera dell'ALGOL 60 riportata come "Backus Normal Form".
Non sono sicuro di dove abbia avuto origine questa terminologia; personalmente ricordo di averlo letto per la prima volta in un articolo di indagine di S. Gorn [1].
Molti di noi che lavorano sul campo non si sono mai preoccupati del nome Backus Normal Form perché non è una "forma normale" nel senso convenzionale.
Una forma normale di solito si riferisce a una sorta di rappresentazione speciale che non è necessariamente una forma canonica; ad esempio, non è difficile trasformare qualsiasi sintassi “Backus Normal” Form in modo che tutte le definizioni tranne la definizione di <vuoto> abbiano una delle tre forme:
(i) <A> ::= <B> | <C>
(ii) <A> :: = <B> <C>
(iii) <A> ::= a.
(Si può dire che una sintassi in cui tutte le definizioni hanno una tale forma sia in "Floyd Normal Form" poiché questo punto è stato sollevato per la prima volta in una nota da Robert W. Floyd [2]. Ma mi affretto a ritirare tale termine da un ulteriore uso poiché senza dubbio molte persone hanno utilizzato indipendentemente questo semplice fatto nel proprio lavoro, e il punto è solo incidentale rispetto alle considerazioni principali della nota di Floyd.).
Molte persone si sono opposte al termine Backus Normal Form perché è solo un nuovo nome per un vecchio concetto in linguistica: un tipo equivalente di sintassi è stato utilizzato sotto vari altri nomi (grammatica Chomsky di tipo 2, grammatica della struttura delle fasi semplice, grammatica libera dal contesto, ecc.).
C'è ancora una ragione per distinguere tra questi, tuttavia, poiché i linguisti presentano la sintassi sotto forma di produzioni mentre la versione Backus ha una forma completamente diversa. (È un modello per una sintassi, non un modello normale.)
Le cinque cose principali che distinguono la forma di Backus dalla forma di produzione sono:
i) I simboli non terminali si distinguono dalle lettere terminali racchiudendoli tra parentesi speciali.
ii) Tutte le alternative per una definizione sono raggruppate insieme (cioè, in un sistema di produzione "A → BC, A → d, A → C" verrebbero scritte tutte invece di "<A> :: = <B> <C> | d | <C>)").
iii) Il simbolo ":: =" è usato per separare sinistra da destra.
iv) Il simbolo "|" è utilizzato per separare le alternative.
v) I nomi completi che indicano il significato delle stringhe in fase di definizione sono usati per i simboli non terminali.
Di questi cinque elementi, (iii) è chiaramente irrilevante e il simbolo peculiare ":: =" può essere sostituito da qualsiasi cosa desiderata; "→" è forse meglio, per corrispondere alle produzioni più strettamente.
Ma (i), (ii), (iv), (v) sono entrambi importanti per il potere esplicativo di una sintassi. È abbastanza difficile sondare il significato di un linguaggio definito dalle produzioni, rispetto alla documentazione fornita da una sintassi che incorpora (i), (ii), (iv), (v). (D'altra parte, è molto più facile fare manipolazioni teoriche usando sistemi di produzione ed evitando sistematicamente (i), (ii), (iv), (v).)
Per questo motivo, la forma di Backus merita un nome distintivo speciale. In realtà, tuttavia, solo (i) e (ii) furono realmente usati da John Backus quando propose la sua notazione; (iii), (iv), (v) sono dovuti a Peter Naur che ha incorporato queste modifiche durante la stesura del rapporto ALGOL 60. Le aggiunte di Naur (in particolare (v)) sono piuttosto importanti.
Inoltre, se non fosse stato per il lavoro di Naur nel riconoscere il potenziale delle idee di Backus e nel renderle popolari con il comitato ALGOL, il lavoro di Backus sarebbe andato praticamente perso e gran parte della conoscenza che abbiamo oggi di linguaggi e compilatori non sarebbe stata acquisita.
Pertanto propongo che d'ora in poi si dica sempre "Backus Naur Form" invece di “Backus Normal Form”, quando ci si riferisce a tale sintassi. Questa terminologia ha diversi vantaggi:
- Dà il giusto credito sia a Backus che a Naur;
- Conserva l'abbreviazione "BNF" usata spesso;
- Non chiama una Forma Normale una Forma.
Dico Backus Naur Form da circa due mesi ormai e ne sono ancora abbastanza soddisfatto, quindi penso che forse anche tutti gli altri apprezzeranno questo termine.
------------------------------------------
Note
- GORN, S. Specification languages for mechanical languages and their processors -- a baker's dozen. Comm. ACM 4 (Dec. 1961), 532-542.
- FLOYD, R. W. Note on mathematical induction in phrase structure grammars. Inform. Contr. 4 (1961), 353-358.
DONALD E. KNUTH
California Institute of Technology
Pasadena, California
consultazione online e DOWNLOAD TRADUZIONE lettera di donald knuth a cacm
- Scarica DOCX da Google Drive (Word) 544kB
- Scarica il PDF da Google Drive 614KB
Condividi questa pagina sul tuo Social preferito