Addio a Tony Hoare: il creatore di Quicksort lascia un’eredità enorme

La scomparsa di Tony Hoare chiude una stagione decisiva della storia dell’informatica e riporta al centro un fatto spesso trascurato: molte delle idee che regolano ancora oggi il software moderno nascono in un arco di tempo sorprendentemente ristretto, tra la fine degli anni Cinquanta e gli anni Settanta. Hoare ricevette il Turing Award nel 1980 per il contributo dato alla definizione e alla progettazione dei linguaggi di programmazione, ma la sua impronta si estende ben oltre il celebre Quicksort.

Dentro il suo lavoro convivono algoritmi, semantica formale, concorrenza, strutturazione dei sistemi operativi e una lezione intellettuale rara: riconoscere apertamente i limiti delle proprie invenzioni. È anche per questo che, accanto al cordoglio, la morte di Hoare ha riacceso una discussione tecnica, attualissima, sul rapporto tra espressività dei linguaggi, assenza di valore e sicurezza del codice.

Perché ridurre Hoare a Quicksort e null significa raccontarlo male

Dopo la notizia della morte di Hoeare, tante testate hanno riproposto due etichette facili: inventore di Quicksort e “padre del null” (le cose non stanno nemmeno in questi termini!)

Sono formule immediate, ma semplificano troppo. Quicksort non è soltanto un algoritmo di ordinamento noto a chiunque abbia studiato informatica di base. È il risultato di un’intuizione elegante sul partizionamento dei dati: scegliere un pivot, separare gli elementi minori e maggiori, poi ricorrere sugli insiemi ottenuti fino a esaurire il problema.

Nel caso medio il costo computazionale – cioè la quantità di operazioni necessarie per completare l’algoritmo – cresce con una complessità pari a O(n log n), dove n rappresenta il numero di elementi da ordinare. Nel caso peggiore, invece, le prestazioni possono peggiorare fino a O(n²) se la scelta del pivot (l’elemento utilizzato come riferimento per dividere l’insieme dei dati in due gruppi) genera partizioni molto sbilanciate, cioè sottogruppi di dimensioni molto diverse.

La sua lunga diffusione non dipende soltanto dalla buona velocità media, ma anche dal ridotto utilizzo di memoria e dalla chiarezza della struttura concettuale su cui si basa l’algoritmo.

Non inventò null bensì la null reference: cosa significa

Per quanto riguarda il concetto di null, Hoare non inventò l’idea astratta null, né i puntatori nulli nel loro significato più vicino all’hardware e al basso livello. Il suo contributo fu più specifico dal punto di vista tecnico: introdusse la null reference (cioè un riferimento che non punta ad alcun oggetto) come valore valido all’interno del sistema di riferimenti del linguaggio ALGOL W, con lo scopo di rappresentare esplicitamente l’assenza di un oggetto.

Si tratta di un aspetto fondamentale. In un linguaggio in cui i riferimenti sono elementi tipizzati, verificati e gestiti dal compilatore, un riferimento che non punta a nulla non nasce automaticamente dal funzionamento della macchina: è il linguaggio stesso che deve scegliere di permetterlo e definire con precisione il suo significato e il suo comportamento.

L’eleganza di Quicksort e il motivo per cui resiste ancora

Nello studio pubblicato nel 1962, Hoare descrive un metodo di ordinamento pensato per la memoria ad accesso casuale (RAM), rapido, parsimonioso e relativamente semplice da programmare.

Il cuore dell’algoritmo è la partizione in place: invece di costruire strutture ausiliarie grandi quanto l’input, l’array è riorganizzato scambiando elementi attorno a un valore guida. La versione classica usa indici che avanzano dai due estremi verso il centro, individuano inversioni e le correggono tramite scambio. Da lì partono due sottoproblemi indipendenti.

Il valore dell’idea non è mai stato legato a una sola implementazione considerata “definitiva”. In pratica, Quicksort risulta efficiente quando la scelta del pivot riduce la possibilità di partizioni molto sbilanciate, quando si controlla la profondità della ricorsione (il processo con cui l’algoritmo richiama sé stesso su sottoinsiemi dei dati) e quando, per segmenti molto piccoli dell’array, si passa a metodi più semplici e veloci.

Per questo motivo, nel corso dei decenni sono state sviluppate diverse varianti: strategie come il median-of-three, che sceglie il pivot come mediana tra tre elementi per ottenere divisioni più equilibrate; l’uso della randomizzazione per evitare casi sfavorevoli; l’integrazione con insertion sort, particolarmente efficiente su insiemi ridotti; approcci “introspective”, che monitorano il comportamento dell’algoritmo e passano a heapsort (algoritmo di ordinamento iterativo proposto da J. W. J. Williams nel 1964) se la situazione diventa sfavorevole.

Al di là delle molteplici evoluzioni, il principio di fondo resta lo stesso: Hoare ha definito una struttura algoritmica di base che ancora oggi orienta la progettazione delle routine di ordinamento ad alte prestazioni.

Il miliardo di dollari perso sul null non era soltanto una battuta

La frase con cui Hoare definì il null il suo “billion-dollar mistake” è diventata proverbiale perché unisce onestà tecnica e precisione storica.

Nel suo racconto, l’errore non consisteva nell’aver immaginato l’assenza di valore come concetto, ma nell’aver introdotto una scorciatoia troppo comoda in un sistema che voleva essere sicuro.

Se ogni riferimento di un certo tipo può contenere implicitamente anche null, il tipo smette di dire tutta la verità sul valore che rappresenta. Da lì nasce una lunga catena di controlli mancati, dereferenziazioni errate, eccezioni a runtime, crash, superfici di attacco e difetti logici difficili da riprodurre.

Il problema resta attuale perché non si risolve semplicemente invitando a “controllare l’uso dei null”. Nei linguaggi di programmazione in cui la nullabilità è implicita – cioè dove una variabile o un riferimento possono contenere anche il valore null – l’interfaccia di una funzione (la sua definizione pubblica, composta da parametri e valore di ritorno) non chiarisce se chi la utilizza debba aspettarsi un valore valido oppure la possibile assenza di dati.

Il compilatore, che è il programma incaricato di verificare e trasformare il codice sorgente in codice eseguibile, riconosce semplicemente la presenza di un riferimento, ma non può imporre allo sviluppatore di distinguere in modo rigoroso tra un valore presente e uno assente.

Dal punto di vista della progettazione del software, il vero problema nasce qui: un’informazione fondamentale non è codificata nel sistema dei tipi (il meccanismo con cui il linguaggio descrive e controlla la natura dei dati), ma rimane affidata alla memoria del programmatore, ai commenti nel codice o alle convenzioni informali adottate dal team.

Da ALGOL W a Kotlin, Swift, C# e Rust: come i linguaggi hanno corretto la rotta

La discussione tecnica nata attorno al lascito di Hoare converge quasi sempre sulla stessa osservazione: l’assenza di valore serve, ma va resa esplicita.

I linguaggi di programmazione moderni affrontano il problema dei valori assenti (cioè la possibilità che una variabile non contenga alcun dato valido) con approcci diversi, ma spesso concettualmente simili.

In Kotlin, ad esempio, il sistema di tipi – il meccanismo che definisce quali valori una variabile può contenere – applica controlli statici durante la compilazione: ciò significa che il compilatore analizza il codice prima dell’esecuzione e impedisce di accedere direttamente a un riferimento che potrebbe essere nullo.

Per usare quel valore è necessario impiegare una safe call (un accesso sicuro che esegue l’operazione solo se il valore esiste), effettuare un controllo esplicito o utilizzare altre tecniche che permettono al compilatore di verificare che il valore non sia nullo.

In Swift il problema è gestito tramite gli Optional, un tipo speciale che rappresenta esplicitamente la possibilità che un valore sia presente oppure assente. Tecnicamente il linguaggio li implementa vagliando due casi: uno che contiene il valore e uno che indica la sua assenza. L’incertezza sulla presenza del dato diventa parte esplicita del significato del codice, anziché un dettaglio nascosto.

Anche C#, a partire dalla versione C# 8, ha introdotto le nullable reference types per affrontare una difficoltà storica del linguaggio senza rompere la compatibilità con il codice esistente.

In questo caso il runtime, cioè il sistema che esegue il programma, non cambia il modo in cui i riferimenti funzionano in memoria. Il compilatore aggiunge invece annotazioni e analisi statica del flusso del programma.

Nel caso di Rust l’assenza di valore è rappresentata tramite il tipo Option, che distingue esplicitamente tra Some (valore presente) e None (valore assente).

Hoare logic, monitor e concorrenza: il lascito meno popolare ma più profondo

Concentrare l’attenzione su Quicksort e null rischia di lasciare in ombra la parte forse più influente della sua opera.

Con Hoare logic o Logica di Hoare, formalizzata nel 1969, l’informatico britannico offrì un modo rigoroso per ragionare sulla correttezza dei programmi tramite precondizioni, comando e postcondizioni.

La tripla {P} C {Q} ha cambiato il lessico della verifica del software: non più solo test empirici, ma specifiche che descrivono cosa deve essere vero prima e dopo l’esecuzione. Molta verifica formale moderna, dalle prove di correttezza ai tool per l’analisi statica, continua a fare perno su quella storica quella intuizione.

Un ragionamento analogo riguarda i monitor, introdotti nel 1974 come meccanismo di programmazione per controllare in modo ordinato l’accesso simultaneo a risorse condivise, e il modello CSP (Communicating Sequential Processes), pubblicato nel 1978.

In questi lavori Hoare affronta uno dei problemi più complessi dell’ingegneria del software: la concorrenza, cioè la situazione in cui più processi o thread – unità di esecuzione che operano potenzialmente nello stesso momento – devono cooperare tra loro. In questi scenari non è sufficiente che ogni parte del codice funzioni correttamente se considerata da sola: è necessario disporre di modelli formali che descrivano come i processi si sincronizzano (cioè coordinano i tempi di esecuzione), come comunicano tra loro e come evitare situazioni di interblocco, note come deadlock, in cui più processi restano bloccati in attesa reciproca.

CSP ha esercitato un’influenza duratura perché ha descritto i processi che comunicano come entità matematiche definibili con precisione, rendendo possibile analizzare e verificare formalmente il comportamento dei sistemi concorrenti e favorendo la nascita di linguaggi di programmazione, librerie e tecniche di verifica dedicate a questo tipo di sistemi.

Una figura centrale anche per il modo in cui il software pensa se stesso

La biografia di Hoare aiuta a capire perché la sua eredità non si riduca alla competenza tecnica.

Hoare non arrivò all’informatica da un percorso lineare: Oxford, studi classici e filosofia, poi la statistica, il servizio nella Royal Navy con lo studio del russo, infine il passaggio alla programmazione in un momento in cui la disciplina non aveva ancora confini stabili. Nel 1959, durante un soggiorno alla Moscow State University legato a un progetto di traduzione automatica, ideò proprio il Quicksort, algoritmo che avrebbe pubblicato nel 1962 su The Computer Journal.

Le reazioni dopo la sua morte riflettono proprio l’ampiezza della traiettoria seguita in vita. C’è chi ricorda Hoare per l’algoritmo studiato all’università, chi per la logica di Hoare, chi per CSP, chi per quella frase sul null che ha accompagnato intere generazioni di programmatori.

In tutti i casi emerge lo stesso tratto: la capacità di trasformare problemi concreti in strutture concettuali durevoli. È un’eredità rara, perché non invecchia con il linguaggio o con la piattaforma del momento.

Che cosa resta dell’insegnamento di Hoare

La lezione più utile che Hoare lascia agli sviluppatori software contemporanei non coincide con una singola invenzione. Riguarda il metodo.

Un buon linguaggio non deve solo permettere di scrivere programmi potenti; deve anche rendere difficili gli errori prevedibili.

Un buon algoritmo non deve solo essere veloce; deve essere comprensibile, analizzabile, migliorabile. Una buona teoria non deve allontanarsi dalla pratica; deve offrire strumenti per giudicarla con più rigore.

Per questo la sua scomparsa pesa oltre il valore simbolico. Ricorda che l’informatica migliore nasce quando eleganza e responsabilità procedono insieme.

Quicksort mostra quanto possa essere fertile un’idea semplice ma ben costruita. La vicenda della null reference mostra, con altrettanta chiarezza, quanto una scelta apparentemente minima possa produrre conseguenze enormi se il sistema di tipi non la governa abbastanza bene.

Tra questi due estremi, il nome di Tony Hoare continua a segnare una linea di fondo della disciplina: scrivere software significa progettare possibilità, ma anche delimitare gli errori prima che arrivino in produzione.