Un'eredità indiretta: le grammatiche di Chomsky e la semantica operazionale
Il titolo di questo post contiene una piccola provocazione. Se si apre un manuale di semantica dei linguaggi di programmazione, il nome di Noam Chomsky compare quasi sempre nel capitolo sulla sintassi e quasi mai in quello sulla semantica. Chomsky non ha mai scritto una regola di transizione, non ha mai definito un interprete, e per tutta la sua carriera ha guardato con un certo sospetto alla parola stessa "semantica", almeno nell'accezione referenziale che le davano i logici. Eppure la semantica operazionale, così come la conosciamo oggi, sarebbe difficile da immaginare senza gli strumenti che lui ha messo in circolazione negli anni Cinquanta. Il suo contributo è indiretto, ma non per questo marginale: è il contributo di chi ha fornito il linguaggio in cui un'altra disciplina avrebbe poi formulato le proprie domande.
Un nome che non compare nelle bibliografie
Conviene partire da ciò che la semantica operazionale è. Dare la semantica operazionale di un linguaggio significa descrivere il significato di un programma attraverso il modo in cui viene eseguito: quali passi compie una macchina, reale o astratta, quando lo valuta. Le tappe storiche sono note. John McCarthy, all'inizio degli anni Sessanta, definisce LISP attraverso una funzione che valuta le espressioni del linguaggio stesso. Peter Landin, nel 1964, descrive la valutazione delle espressioni con la macchina SECD. Alla fine del decennio, il laboratorio IBM di Vienna costruisce un formalismo, la Vienna Definition Language, per specificare il comportamento di PL/I. Nel 1981 Gordon Plotkin, ad Aarhus, scrive le note A Structural Approach to Operational Semantics, che trasformano un insieme di pratiche eterogenee in un metodo. Pochi anni dopo Gilles Kahn propone la cosiddetta semantica naturale.
In questa genealogia Chomsky non c'è. Per trovarlo bisogna guardare non ai contenuti ma alla forma: alla struttura delle regole, al modo in cui sono indicizzate sulla sintassi, all'idea stessa che un linguaggio possa essere descritto da un insieme finito di regole di riscrittura capace di generare un insieme infinito di oggetti.
Grammatiche come sistemi di riscrittura
Nel 1956, con l'articolo Three Models for the Description of Language, e l'anno dopo con Syntactic Structures, Chomsky propone di trattare una lingua naturale come un oggetto formale: un insieme, in generale infinito, di frasi, generato da un dispositivo finito. Quel dispositivo è una grammatica, cioè un sistema di regole della forma "sostituisci questo con quest'altro". L'idea non era del tutto nuova: i sistemi di riscrittura di Axel Thue e i sistemi canonici di Emil Post appartenevano alla logica matematica da decenni. La novità stava nell'applicarli al linguaggio e nel classificarli.
Nel 1959, in On Certain Formal Properties of Grammars, Chomsky ordina le grammatiche in una gerarchia secondo le restrizioni imposte alla forma delle regole. Al vertice ci sono le grammatiche senza restrizioni, equivalenti per potere espressivo alle macchine di Turing; poi quelle dipendenti dal contesto, quelle libere dal contesto, infine quelle regolari. A ogni livello corrisponde una classe di automi: macchine di Turing, automi lineari limitati, automi a pila, automi a stati finiti. Con Marcel-Paul Schützenberger, nel 1963, lavora alla teoria algebrica dei linguaggi liberi dal contesto.
Questa corrispondenza tra grammatiche e macchine è il primo punto di contatto con la semantica operazionale. Dice, in sostanza, che generare e calcolare sono due facce della stessa medaglia: una sequenza di riscritture e una sequenza di passi di una macchina sono, a un certo livello di astrazione, lo stesso tipo di oggetto. Una derivazione grammaticale è una successione di configurazioni legate da una relazione di transizione. È esattamente la struttura che, vent'anni dopo, Plotkin userà per descrivere l'esecuzione di un programma.
Dalla gerarchia al BNF
Il canale attraverso cui le idee chomskiane entrano nell'informatica è, prima ancora che la semantica, la sintassi dei linguaggi di programmazione. Nel 1959 John Backus presenta una notazione per descrivere la sintassi del linguaggio che sarebbe diventato ALGOL; Peter Naur la adotta e la perfeziona nel rapporto su ALGOL 60. Nasce così quella che chiamiamo Backus-Naur Form. Backus stesso ha in seguito indicato come fonte principale i sistemi di produzione di Post, più che il lavoro di Chomsky, ma l'equivalenza tra BNF e grammatiche libere dal contesto fu riconosciuta molto presto, e con essa l'intero apparato teorico che Chomsky e i suoi colleghi stavano costruendo: le proprietà di chiusura, i problemi di decidibilità, il legame con gli automi a pila che sarebbe diventato la base del parsing.
Da quel momento in poi, definire un linguaggio di programmazione significa cominciare da una grammatica. E qui sta il punto decisivo per la semantica: se la sintassi è data da una grammatica, allora ogni programma ha una struttura ad albero, un albero di derivazione, e il significato può essere definito per induzione su quella struttura. La semantica strutturale di Plotkin si chiama così proprio perché le sue regole seguono la forma delle produzioni grammaticali. Una regola per l'espressione e1 + e2 dice come procedere a partire dalle sue sottoespressioni, esattamente come la produzione grammaticale dice da quali parti quell'espressione è composta.
Sintassi astratta e struttura profonda
Nel 1962-1963 McCarthy introduce una distinzione destinata a durare: quella tra sintassi concreta e sintassi astratta. La sintassi concreta riguarda le stringhe di caratteri, le parentesi, le precedenze degli operatori; la sintassi astratta riguarda la struttura logica del programma, ciò che rimane una volta tolti i dettagli di superficie. La semantica operazionale lavora quasi sempre sulla sintassi astratta.
È difficile non notare la somiglianza con un'altra distinzione, quella che Chomsky formalizza in Aspects of the Theory of Syntax nel 1965: la distinzione tra struttura profonda e struttura superficiale. Anche qui c'è un livello in cui le relazioni essenziali sono esplicite e un livello in cui la frase si presenta nella sua forma pronunciabile, collegati da un insieme di trasformazioni. Bisogna essere onesti: non c'è una linea di influenza documentata da Chomsky a McCarthy su questo punto, e le motivazioni erano diverse. Ma il parallelismo è istruttivo, perché mostra che negli stessi anni linguistica e informatica arrivavano alla stessa intuizione: il significato non si attacca alla superficie delle stringhe, ma a una struttura soggiacente che va ricostruita.
Le regole di Plotkin
Si guardi una tipica regola di semantica operazionale a piccoli passi, scritta in notazione lineare:
e1 → e1'
-----------------
e1 + e2 → e1' + e2
La regola dice: se l'espressione e1 può fare un passo diventando e1', allora anche e1 + e2 può fare un passo, diventando e1' + e2. Una sola regola, applicata ricorsivamente, governa infinite situazioni. Il meccanismo è lo stesso di una grammatica generativa: un insieme finito di schemi che, istanziati e combinati, producono un insieme infinito di fatti. In una grammatica i fatti sono "questa stringa appartiene al linguaggio"; nella semantica operazionale sono "questo programma, in questo stato, evolve in quest'altro".
C'è di più. La relazione di transizione → è una relazione su configurazioni, e la sua chiusura riflessiva e transitiva descrive le esecuzioni complete, così come la chiusura della relazione di derivazione diretta descrive le derivazioni complete di una grammatica. Il vocabolario dei sistemi formali che Chomsky aveva reso familiare a un'intera generazione di informatici, fatto di simboli, regole, derivazioni e chiusure, è lo stesso in cui Plotkin scrive le sue note.
Contesti di valutazione: dove la grammatica diventa semantica
Il punto in cui l'eredità chomskiana diventa più visibile è forse la semantica a riduzione, sviluppata da Matthias Felleisen e dai suoi collaboratori tra la fine degli anni Ottanta e l'inizio dei Novanta. Invece di scrivere una regola di congruenza per ogni costrutto, come nell'esempio precedente, si definisce una grammatica dei contesti di valutazione:
E ::= [] | E + e | v + E
Questa produzione dice dove, all'interno di un'espressione, può avvenire il prossimo passo di calcolo: il "buco" [] indica la posizione della sottoespressione da ridurre. Le regole di riduzione vere e proprie si applicano solo a ciò che sta nel buco, e il contesto si occupa del resto. L'ordine di valutazione, prima l'operando sinistro e poi il destro, non è descritto da una regola semantica ma da una grammatica.
In questo caso non si tratta più di un'analogia. Una grammatica libera dal contesto, esattamente del tipo che Chomsky aveva classificato, diventa parte integrante della definizione del significato. La strategia di esecuzione di un linguaggio è codificata nella forma delle sue produzioni. È il luogo in cui la vecchia separazione tra sintassi e semantica, che Chomsky aveva difeso con tanta energia, si assottiglia fino quasi a scomparire.
Competenza ed esecuzione
C'è però un aspetto che separa nettamente il pensiero di Chomsky dalla semantica operazionale, e che vale la pena sottolineare. Chomsky ha sempre insistito sul fatto che una grammatica generativa non è un modello di come il parlante produce o comprende le frasi. "Generare", nel suo lessico, significa caratterizzare in modo esplicito un insieme, non descrivere un processo che si svolge nel tempo. La distinzione tra competenza ed esecuzione, competence e performance, serve proprio a tenere separate le due cose: la grammatica descrive ciò che il parlante sa, non ciò che fa.
La semantica operazionale va nella direzione opposta. Il suo oggetto è precisamente il processo, la successione dei passi, ciò che avviene quando il programma gira. In questo senso si potrebbe dire che la semantica operazionale ha preso in prestito da Chomsky la forma delle regole e ne ha rovesciato l'interpretazione: dove lui vedeva una caratterizzazione statica, essa vede una dinamica. Le derivazioni, che per il linguista erano un dispositivo di prova dell'appartenenza di una frase alla lingua, diventano per l'informatico la traccia di un'esecuzione.
È un rovesciamento fecondo. Mostra che lo stesso apparato formale può sostenere due filosofie diverse del significato: una, quella chomskiana, che colloca il linguaggio nella mente come sistema di conoscenza; l'altra, quella operazionale, che lo colloca nel comportamento di una macchina. Il fatto che entrambe possano essere scritte con le stesse frecce e le stesse barre orizzontali dice qualcosa sulla generalità degli strumenti che Chomsky aveva contribuito a diffondere.
Un'eredità di forma
Ridotto all'essenziale, il contributo di Chomsky alla semantica operazionale è questo: ha reso naturale pensare un linguaggio come un oggetto matematico generato da regole finite, ha legato quelle regole alle macchine che le riconoscono, e ha fornito alla nascente informatica la grammatica come punto di partenza obbligato di ogni definizione linguistica. Tutto ciò che la semantica operazionale ha costruito dopo, dalla macchina SECD alle note di Plotkin fino ai contesti di valutazione, si appoggia su questo terreno.
Non è il tipo di contributo che si misura in citazioni dirette. È piuttosto il contributo di chi cambia il modo in cui una comunità formula i problemi, al punto che le soluzioni successive sembrano ovvie e il loro debito invisibile. Nella storia delle idee succede spesso: le eredità più profonde sono quelle che smettono di essere riconosciute come tali, perché sono diventate semplicemente il modo in cui si pensa.