Una macchina che scrive programmi: la nascita dei compilatori

Filadelfia, primavera del 1952. Lavori per Remington Rand, e il tuo computer è un UNIVAC I: cinquemila valvole, una stanza intera, memoria a linee di ritardo al mercurio. Programmarlo vuol dire scrivere a mano, su fogli quadrettati, una sequenza di istruzioni in codice macchina, ciascuna con il suo indirizzo di memoria. Se a metà del lavoro ti accorgi che serve un'istruzione in più, devi spostare tutte quelle successive e correggere ogni indirizzo che le richiama. A mano. Con la gomma.

Sulla scrivania tieni un quaderno pieno di pezzi di codice che riusi sempre: il calcolo del seno, la radice quadrata, la stampa di un numero. Quando ti servono, li ricopi nel programma nuovo e ricalcoli gli indirizzi. Ogni copia è un'occasione per sbagliare una cifra, e il computer non ti dirà dove.

Nello stesso edificio lavora Grace Hopper, matematica, ufficiale della riserva della Marina, che arriva dal gruppo del computer Mark I di Harvard. Ha un'idea che ai tuoi colleghi sembra quasi offensiva: se il lavoro di copiare le subroutine e sistemare gli indirizzi è meccanico, perché non lo fa la macchina?

A-0: il computer che si scrive i programmi

Il sistema che Hopper costruisce tra il 1951 e il 1952 si chiama A-0. Le subroutine vengono conservate su nastro magnetico, ciascuna con un numero di riferimento. Tu scrivi un programma che dice, in sostanza, «prendi la subroutine 12 con questi argomenti, poi la 7, poi la 31», e A-0 va a cercarle sul nastro, le mette in fila, sistema gli indirizzi e produce il programma completo in codice macchina. A maggio del 1952 Hopper lo presenta a un convegno dell'ACM a Pittsburgh, in un articolo intitolato The Education of a Computer.

Oggi gli storici discutono se A-0 sia davvero un compilatore: assomiglia di più a quello che chiameremmo un linker, che collega pezzi di codice già scritti. Ma l'idea di fondo è quella che conta: un programma che produce altri programmi. E la reazione dei colleghi è quella che conta di più. L'opinione diffusa è che un computer sappia fare i conti, non scrivere programmi. Ci vorranno un paio d'anni perché l'idea venga presa sul serio.

Hopper non si ferma. Il suo gruppo prosegue con A-2 e poi con FLOW-MATIC, un linguaggio per applicazioni commerciali che usa parole inglesi al posto dei simboli matematici. Quando nel 1959 un comitato di aziende e del governo americano progetta il COBOL, FLOW-MATIC è uno dei modelli principali.

Una falena nel registro

A pranzo, qualcuno racconta di nuovo la storia della falena, e tu decidi di verificarla. Il 9 settembre 1947, alle 15:45, gli operatori del Mark II di Harvard trovarono una falena incastrata nel relè 70 del pannello F. La attaccarono con lo scotch nel registro delle operazioni, con una nota: First actual case of bug being found, «primo caso effettivo di bug trovato».

Due dettagli che si perdono sempre nel racconto. Il primo: la parola bug per indicare un difetto esisteva già da decenni tra gli ingegneri (la usava anche Edison), e la battuta della nota sta proprio in quel «effettivo». Il secondo: secondo lo Smithsonian, che oggi conserva il registro, probabilmente non era il quaderno di Hopper, né fu lei a trovare l'insetto. Lei però faceva parte del gruppo e ha raccontato quella storia per tutta la vita, rendendola famosa.

Nel frattempo, a Zurigo e a Manchester

Non sei l'unica persona al mondo ad avere questo problema, e non lo è nemmeno Hopper. A Manchester, nel 1952, Alick Glennie scrive per il computer Mark 1 un sistema chiamato Autocode, che traduce una notazione più leggibile nel codice macchina, famoso per essere incomprensibile. Molti lo considerano il primo linguaggio compilato. Glennie però non lo distribuisce, e quasi nessun altro lo userà: Donald Knuth, anni dopo, definirà Glennie «l'eroe dimenticato» di questa storia.

E a Zurigo, alla fine del 1951, un giovane matematico milanese di nome Corrado Böhm discute al Politecnico federale una tesi di dottorato in cui fa una cosa che nessuno aveva fatto: definisce un linguaggio di programmazione, una macchina astratta, e un compilatore per quel linguaggio scritto nel linguaggio stesso. È la prima descrizione di un compilatore capace di compilare se stesso, un'idea che tornerà più avanti in questa storia. Böhm diventerà poi uno dei padri dell'informatica teorica italiana: il teorema di Böhm-Jacopini, del 1966, dimostra che qualunque programma si può scrivere usando solo sequenza, scelta e ripetizione, ed è la base teorica della programmazione strutturata.

1954: il sacerdozio e FORTRAN

Due anni dopo cambi lavoro e passi in IBM, sul nuovo 704. Lì incontri il gruppo di John Backus, che sta lavorando a un sistema per tradurre formule matematiche in codice macchina: FORmula TRANslation, FORTRAN. Il 10 novembre 1954 il gruppo completa un rapporto preliminare con una frase che ti fa ridere: FORTRAN, c'è scritto, dovrebbe «eliminare virtualmente la scrittura del codice e il debugging».

Non sei l'unica persona a ridere. I programmatori dell'epoca sono, nelle parole che Backus userà anni dopo, un «sacerdozio»: gente orgogliosa di saper aggirare le stranezze dell'hardware e di far stare un programma in poche migliaia di parole di memoria. I sistemi di «programmazione automatica» visti fino a quel momento producevano codice da cinque a dieci volte più lento di quello scritto a mano. E il tempo macchina costava moltissimo: nessuno avrebbe accettato di sprecarlo.

Backus lo sa, e prende una decisione che segnerà la storia dei compilatori: l'obiettivo principale non è il linguaggio, è l'efficienza del codice prodotto. FORTRAN deve generare programmi veloci quasi quanto quelli scritti dai migliori programmatori, altrimenti nessuno lo userà. Il gruppo passa la maggior parte del tempo sull'ottimizzazione: come allocare i registri, come trasformare i cicli, come evitare di ricalcolare due volte la stessa espressione.

Ad aprile del 1957 FORTRAN comincia a essere distribuito ai clienti del 704. Tu provi a confrontare il suo codice con il tuo, istruzione per istruzione, convinto di batterlo. In molti casi non ci riesci. Il codice e il debugging non sono spariti, come prometteva il rapporto: si sono spostati di un piano più in alto. Ma un programma che ti costava settimane ora ti costa giorni.

Cosa fa un compilatore, in trenta righe

Settant'anni dopo, un compilatore moderno fa ancora le stesse quattro cose che faceva FORTRAN. Si possono vedere in miniatura con un piccolo compilatore in Python, per un linguaggio che conosce solo assegnamenti e operazioni aritmetiche:

import re

def tokenize(src):                     # 1. analisi lessicale: testo → parole
    return re.findall(r"\d+|[a-z]+|[-+*/()=]", src)

def parse(tokens):                     # 2. analisi sintattica: parole → albero
    pos = 0
    def peek():
        return tokens[pos] if pos < len(tokens) else None
    def take():
        nonlocal pos
        pos += 1
        return tokens[pos - 1]
    def expr():                        # somme e differenze
        node = term()
        while peek() in ("+", "-"):
            node = (take(), node, term())
        return node
    def term():                        # prodotti e divisioni legano più forte
        node = factor()
        while peek() in ("*", "/"):
            node = (take(), node, factor())
        return node
    def factor():                      # numero, variabile o parentesi
        t = take()
        if t == "(":
            node = expr(); take()
            return node
        return int(t) if t.isdigit() else t
    target = take(); take()            # "y" "="
    return ("=", target, expr())

def fold(n):                           # 3. ottimizzazione: calcola subito le costanti
    if not isinstance(n, tuple):
        return n
    op, a, b = n[0], fold(n[1]), fold(n[2])
    if op != "=" and isinstance(a, int) and isinstance(b, int):
        return {"+": a + b, "-": a - b, "*": a * b, "/": a // b}[op]
    return (op, a, b)

def gen(n, out):                       # 4. generazione del codice (macchina a pila)
    if isinstance(n, int):
        out.append(f"PUSH  {n}")
    elif isinstance(n, str):
        out.append(f"LOAD  {n}")
    elif n[0] == "=":
        gen(n[2], out); out.append(f"STORE {n[1]}")
    else:
        gen(n[1], out); gen(n[2], out)
        out.append({"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}[n[0]])
    return out

ast = parse(tokenize("y = a * (2 + 3) + b"))
print("\n".join(gen(fold(ast), [])))

Il risultato, passo per passo:

# token
['y', '=', 'a', '*', '(', '2', '+', '3', ')', '+', 'b']
# albero sintattico: la moltiplicazione sta "sotto" la somma
('=', 'y', ('+', ('*', 'a', ('+', 2, 3)), 'b'))
# dopo l'ottimizzazione: 2 + 3 è diventato 5
('=', 'y', ('+', ('*', 'a', 5), 'b'))
# codice generato
LOAD  a
PUSH  5
MUL
LOAD  b
ADD
STORE y

Il cuore del lavoro è il passaggio dal testo all'albero: è lì che il compilatore «capisce» che la moltiplicazione va fatta prima della somma, cosa che un programmatore del 1952 doveva ricordarsi da solo, istruzione per istruzione. Nel 1960, per descrivere la grammatica di ALGOL, Backus e Peter Naur introdurranno una notazione formale per scrivere regole come quelle di expr, term e factor: la Backus-Naur Form, che si usa ancora oggi nelle specifiche di quasi ogni linguaggio.

L'eredità di Backus: l'ottimizzatore

La scelta di Backus di puntare tutto sull'efficienza si vede ancora oggi in ogni compilatore. Prendi una funzione C banale:

int f(int x) { return x*8 + x*2; }

Compilata con gcc senza ottimizzazioni (-O0), diventa una traduzione quasi letterale, con il valore che passa per lo stack:

f:  push  rbp
    mov   rbp, rsp
    mov   DWORD PTR -4[rbp], edi
    mov   edx, DWORD PTR -4[rbp]
    mov   eax, edx
    sal   eax, 2
    add   eax, edx
    add   eax, eax
    pop   rbp
    ret

Con -O2 resta questo:

f:  lea   eax, [rdi+rdi*4]    ; eax = x*5
    add   eax, eax            ; eax = x*10
    ret

Il compilatore ha capito che x*8 + x*2 è x*10, e che una moltiplicazione per dieci si fa più in fretta con un'istruzione di indirizzamento (lea, che calcola x + x*4) e un raddoppio. Nessuna moltiplicazione, nessun accesso alla memoria. È esattamente il genere di trucco che il «sacerdozio» del 1954 era convinto che una macchina non avrebbe mai saputo trovare.

L'uovo e la gallina

C'è una domanda che prima o poi viene a chiunque studi i compilatori: il compilatore C è scritto in C. Chi ha compilato il primo? La risposta si chiama bootstrapping, e l'aveva già descritta Böhm nel 1951: si scrive una prima versione minima in un linguaggio più semplice (o in codice macchina), la si usa per compilare una versione scritta nel linguaggio stesso, e da lì il compilatore compila le sue versioni successive. Puoi vedere l'ultimo anello della catena su un qualsiasi sistema Linux, leggendo chi ha compilato il tuo compilatore:

$ readelf -p .comment $(command -v gcc)
String dump of section '.comment':
  [     0]  GCC: (Alpine 13.2.1_git20240309) 13.2.1 20240309

gcc compilato da gcc, che a sua volta era stato compilato da un gcc precedente, e così via all'indietro, per decenni. Ed è proprio qui che, nel 1984, Ken Thompson ha messo il dito nella piaga. Nel testo della lezione per il Premio Turing, ricevuto con Dennis Ritchie per Unix, intitolato Reflections on Trusting Trust, Thompson descrive un attacco in tre passi:

1. modificare il compilatore perché, quando compila il programma di login, ci inserisca una backdoor;
2. modificarlo anche perché, quando compila se stesso, inserisca nel nuovo compilatore entrambe queste modifiche;
3. compilare il compilatore modificato, e poi rimettere al loro posto i sorgenti originali e puliti.

Da quel momento la backdoor non esiste in nessun sorgente, eppure si riproduce a ogni ricompilazione, perché vive solo nel binario del compilatore. La conclusione di Thompson è che non ci si può fidare di codice che non si è scritto interamente da sé, compilatore compreso. Leggere i sorgenti non basta.

Per vent'anni sembrava un problema senza soluzione. Nel 2005 David A. Wheeler ha proposto un metodo chiamato diverse double-compiling, poi sviluppato nella sua tesi di dottorato del 2009: si ricompila il sorgente del compilatore sospetto con un secondo compilatore indipendente, poi lo si ricompila con il risultato, e si confronta il binario finale bit per bit con quello originale. Se coincidono, il binario corrisponde davvero al suo sorgente. E nel 2023 il progetto GNU Guix ha completato un full-source bootstrap: l'intera distribuzione, oltre ventiduemila pacchetti, si costruisce a partire da un programma iniziale di 357 byte, abbastanza piccolo da poter essere letto e verificato da una persona. Il quaderno con i codici esadecimali, insomma, è tornato. Solo che stavolta serve a fidarsi, non a lavorare.

Lunedì 15 settembre 2025

Settantatré anni dopo il tuo primo programma sull'UNIVAC, il gcc più recente è il 15.2, rilasciato l'8 agosto. Il Dott. Brambilla passa davanti alla tua scrivania con il telefono in mano: ha appena letto che con l'intelligenza artificiale «non servirà più scrivere codice», e vuole sapere quanto si risparmia.

Gli mostri la frase del rapporto FORTRAN del 1954: should virtually eliminate coding and debugging. Brambilla la legge due volte, annuisce soddisfatto e chiede quando è uscito questo FORTRAN.

«Nel 1957», gli rispondi.

Ci pensa un attimo. «E allora perché ti pago ancora?»