La storia delle regex

La singolare vendetta dei pionieri dell'intelligenza artificiale, che a suo tempo vennero screditati, arriva grazie alle espressioni regolari e solo dopo con le reti neurali

(Alcuni appunti per organizzare le cose che studio partendo dal testo di Buzz Andersen (opens new window) e sulle mie note)

Antefatto

Il 10 marzo 2021 molti utenti Internet russi hanno scoperto all'improvviso di avere problemi ad accedere a buona parte del Web. Kentik, una società di analisi di rete con sede negli Stati Uniti, ha registrato che il traffico di rete verso Rostelecom, la società di telecomunicazioni statale russa, era precipitato riducendosi al 24% del totale. Su Twitter la comunità internazionale degli esperti di sicurezza informatica era impazzita: le speculazioni sulle cause di quello che stava succedendo era diventate sempre più fantasiose.

Alla fine, un artista russo e utente di Twitter di nome Gregory Khodyrev ha capito cosa stava succedendo davvero: qualcuno di Roscomnadzor, l'ente statale russo per la censura di internet, aveva cercato di bloccare il dominio Internet "t.co" (utilizzato dall'abbreviatore di URL di Twitter), e invece aveva di fatto bloccato l'accesso a qualsiasi dominio contenente il frammento di testo "t.co." In pratica, siti come "microsoft.com", "reddit.com" e persino il media statale russo "rt.com" all'improvviso erano diventati inaccessibili perché erano stati bloccati.

Chi ha un minimo di conoscenza tecnica ha già capito cosa è probabilmente successo: un burocrate del Roscomnadzor particolarmente sfortunato, nel tentativo di bloccare Twitter per limitarne l'influenza politica, ha creato una regola di pattern matching sul firewall nazionale russo che era un po' più zelante del voluto. La regola in questione è stata quasi certamente formalizzata usando una notazione notoriamente astrusa chiamata "espressione regolare".

"Alcune persone, di fronte a un problema, pensano: 'So come fare, userò le espressioni regolari'. Queste persone adesso hanno due problemi"

C'è una vecchia battuta tra programmatori (generalmente attribuita a Jamie Zawinski) che dice: "Alcune persone, di fronte a un problema, pensano: 'So come fare, userò le espressioni regolari'. Quelle persone adesso hanno due problemi". Interrompendo accidentalmente l'accesso a gran parte di Internet per un intero paese (e nel processo attirando l'attenzione imbarazzante sugli sforzi di censura della Russia), il nostro anonimo burocrate sembrerebbe aver dimostrato con una certa abilità la validità di quella battuta.

Perché è interessante?

Un'espressione regolare, o "regex" (in italiano si pronuncia "reghecs"), è una sorta di stenografia algebrica per specificare modelli di testo. Qui di seguito, ad esempio, c'è un'espressione regolare che corrisponde alle parole "sink", "sank" o "sunk".

s[aiu]nk

Le parentesi quadre indicano che "a", "i" o "u" sono corrispondenze accettabili per il secondo carattere della serie.

Ora, per rendere le cose un po' più interessanti, possiamo aggiungere un elemento opzionale:

st?[aiu]nk

Il punto interrogativo rende la "t" opzionale nel nostro pattern (in italiano possiamo tradurlo con "modello") e significa che la nostra espressione può ora corrispondere non solo a "sink", "sank" e "sunk", ma anche a "stink", "stank" e "stunk".

Infine, per espandere drasticamente il numero di "stringhe" di testo che la nostra espressione può abbinare, possiamo aggiungere un punto (che significa "qualsiasi carattere") seguito da un asterisco (che significa "un numero arbitrario di volte").

s.*nk

Ora la nostra regex può corrispondere a "stonk", "slink" o in effetti qualsiasi altra parola che inizia con "s" e termina con "nk".

La maggior parte delle implementazioni delle espressioni regolari supporta anche una funzionalità chiamata "ancore", che specifica che la corrispondenza deve apparire all'inizio o alla fine di una stringa di testo. Per esempio:

^t\.co$

L'espressione qui sopra corrisponde al pattern "t.co", ma solo se la "t" è il primo carattere nella stringa e la "o" è l'ultimo (il backslash davanti al punto serve per escluderne il valore semantico di istruzione e trattarlo come un semplice punto). Senza "^" e "$", al contrario, l'espressione, come ha imparato il nostro anonimo censore russo, corrisponderebbe al pattern indipendentemente da dove appaia nella stringa.

Di cosa parliamo quando ne parliamo

Il concetto di espressione regolare ha una storia sorprendentemente interessante, che risale al periodo di massimo splendore (e forte ottimismo) della ricerca sull'intelligenza artificiale, alla metà del XX secolo.

Il termine stesso è stato creato dal matematico Stephen Kleene. Nel 1943, il neuroscienziato Warren McCulloch e il logico Walter Pitts avevano appena descritto il primo modello matematico di un neurone artificiale, e Kleene, specializzato in teorie computazionali, voleva capire quali tra queste reti di neuroni artificiali potessero in effetti, dal punto di vista almeno teorico, effettuare delle computazioni.

I linguaggi regolari sono linguaggi molto semplici. Le loro grammatiche regolari vengono incapsulate da una notazione algebrica chiamata "espressione regolare"

In un paper del 1951 per la RAND Corporation, Kleene si è messo a riflettere sui tipi di pattern che le reti neurali erano in grado di rilevare applicandoli a dei linguaggi giocattolo molto semplici, i cosiddetti "linguaggi regolari". Ad esempio: data una lingua il cui alfabeto ammette solo le lettere “A” e “B”, esiste una rete neurale in grado di rilevare se una stringa arbitraria di lettere è valida o meno all'interno dell'alfabeto “A/B”? Kleene sviluppò una notazione algebrica per incapsulare queste “grammatiche regolari” (ad esempio, a*b* nel caso del nostro linguaggio “A/B”) e nacque così l'idea di espressione regolare.

L'estate delle AI

Partendo da qui negli anni successivi il lavoro di Kleene è stato ampliato da alcune delle figure più importanti dell'epoca, come il linguista Noam Chomsky e il ricercatore che ha più lasciato il segno sull'intelligenza artificiale, cioè Marvin Minsky. I due hanno formalizzato la relazione tra espressioni regolari, reti neurali e una classe di astrazione computazionale teorica chiamata "macchine a stati finiti" o, almeno da noi, "automi a stati finiti".

Queste scoperte hanno dato la sensazione ai primi pionieri dell'AI di essere sul punto di svelare i misteri fondamentali della mente, e per un po' è sembrato sul serio che la "vera" intelligenza artificiale fosse ormai raggiungibile, praticamente dietro l'angolo. Sfortunatamente, questo inebriante entusiasmo iniziale per l'approccio di Pitts, McCulloch e Lettvin si è presto scontrato con un muro di mattoni.

L'inverno delle AI

Nel 1969 Minksy pubblicò il suo controverso libro Perceptrons (opens new window), che esplorava alcuni importanti limiti delle prime reti neurali, con conseguenze devastanti per la scienza emergente e i suoi pionieri. Come scrive Brian Christian nel libro The Alignment Problem (opens new window), che ricostruisce chiaramente quel che avvenne all'epoca:

È come se una nuvola nera si fosse posata sul settore e tutto fosse crollato: la ricerca, i soldi, le persone. Pitts, McCulloch e Lettvin, che si sono trasferiti tutti e tre al MIT, vennero bruscamente esiliati dopo un malinteso con Norbert Wiener, che era stato come una seconda figura paterna per Pitts e ora non voleva più neanche parlargli. Pitts, alcolizzato e depresso, gettò nel fuoco tutti i suoi appunti e documenti, inclusa una dissertazione inedita sulle reti neurali tridimensionali che il MIT ha cercato disperatamente di salvare per anni. Pitts è morto di cirrosi nel maggio 1969, all'età di 46 anni.

Lo studio delle reti neurali entrò presto in un lungo periodo di inattività poiché molti ricercatori spostarono i loro sforzi dalle teorie "connessioniste" (in cui l'intelligenza emerge da reti massicciamente parallele) a un approccio "simbolista" con un paradigma più familiare (che vuole sviluppare l'intelligenza caricando le macchine con delle grandi quantità di fatti e cercando di insegnare loro le regole della logica). Il ripudio delle reti neurali è stato così completo che sembrava improbabile che le espressioni regolari potessero mai essere conosciute al di fuori dell'informatica più esoterica, se non fosse stato per una coincidenza unica: gli sforzi di Ken Thompson, uno dei creatori del sistema operativo UNIX presso i Bell Labs.

Qualsiasi cosa è testo

Il sistema operativo UNIX è basato su un approccio particolare: "qualsiasi cosa è documento" (in realtà dice "flusso di byte", ma poi questi vengono organizzati in documenti. Infatti, questo approccio definisce molto bene una delle caratteristiche distintive di Unix e dei sistemi operativi da lui derivati: un'ampia gamma di risorse di input/output come documenti, directory, unità di memoria (dischi, ssd), modem, tastiere, stampanti e persino alcune comunicazioni tra processi e di rete sono semplici flussi di byte esposti attraverso il namespace (lo spazio dei nomi) del filesystem. E siccome il contenuto dei documenti è il testo semplice (cioè un flusso di byte codificati come una serie di caratteri Unicode), il vantaggio di questo approccio è che è possibile utilizzare lo stesso insieme di strumenti, utility e API per gestire un'ampia gamma di risorse.

Ad esempio, sui sistemi Unix (ma non su macOS) usando il comando:

cat /proc/cpuinfo

viene stampato il contenuto del documento "cpuinfo" sul terminale, cioè si stampano le informazioni della CPU del proprio computer. Ma non si tratta di un documento "descrittivo" preparato dal produttore del computer al momento dell'installazione del sistema operativo. Invece, il documento "cpuinfo" è virtuale e viene attualizzato si richiesta: viene cioè calcolato al volo da una funzione del kernel e offerto come testo da leggere nel documento quando cat accede al filesystem su cui è montato /proc, che si chiama "procfs".

Tre esempi di "documenti" presenti su Linux: /dev/null, /dev/random, e /dev/zero

Se pensiamo a questi tre solo come documenti, non ne vediamo l'utilità. Invece, se li consideriamo come strumenti, acquistano un significato completamente diverso.

/dev/null è un documento esiste ma che in realtà non esiste. È un buco nero: tutto quello che viene scritto in questo documento semplicemente non c'è, non è mai stato scritto. È il modo per gettare via le cose inutili senza bisogno di utilizzare un comando dedicato. /dev/random è un generatore di numeri casuali: il documento si riempie di numeri creati utilizzando il rumore ambientale attorno al computer, quindi senza uno schema di tipo deterministico che sarebbe potenzialmente riproducibile. Infine, /dev/zero è un documento che si riempie a piacere di una serie costante di zero, senza fine. Perfetto per generare documenti molto grandi ma totalmente inutili. È il lorem ipsum dell'informatica, ma può essere utilizzato anche, ad esempio, per cancellare rapidamente un intero hard disk usando il comando di copia fisica dd e facendogli scrivere ovunque un flusso di zeri.

Thompson, Wall e le regex

All'origine di Unix, nel 1968, Thompson ha iniziato ad applicare le espressioni regolari ai compiti più banali, integrandole nella funzione di ricerca avanzata del suo editor di testo QED. Da lì, le espressioni regolari sono diventate un pilastro di UNIX. Infatti, sono qualcosa di più delle wildcard nelle stringhe di ricerca utilizzate da UNIX: sono dei veri modelli testuali che vengono confrontati con il testo da cercare per trovare delle corrispondenze. La crescente centralità di UNIX le ha quindi rese sempre più importanti, ma il fenomeno è stato amplificato con la maturità dell'Internet commerciale e la nascita di alcuni linguaggi che hanno adottato lo stesso meccanismo. Un linguaggio in particolare ha fatto la differenza.

Ancora oggi Internet è gestita dalla filosofia di Unix: "tutto è un flusso di testo, tutto è documento, il software gestisce flussi di testo perché il testo è una interfaccia universale"

Negli anni '80 Larry Wall ha dato alle regex un'altra spinta, rendendole una delle caratteristiche fondamentali del suo linguaggio di programmazione orientato al testo, il Perl, che è diventato l'indispensabile "nastro adesivo" dello sviluppo web degli anni '90. Quest'ultima mossa ha assicurato alle espressioni regolari un posto permanente nella cassetta degli attrezzi di tutti i sistemisti e gli smanettoni web del pianeta. Ancora oggi Internet è gestito da computer basati sulla filosofia stabilita da UNIX: tutto è un flusso di testo, tutto è documento, gli strumenti software di UNIX fanno una cosa sola e la fanno bene, gli strumenti collaborano con gli altri strumenti, gli strumenti gestiscono flussi di testo perché il testo è una interfaccia universale. In questo sistema le regex hanno un ruolo chiave per chi fa il lavoro di amministratore del back-end del tipo svolto dagli amministratori del firewall russo.

Lieto fine?

Per quanto riguarda McCulloch, Pitts, Kleene e gli altri, alla fine hanno ottenuto la loro vendetta. Gli anni Dieci del nuovo millennio hanno visto una rinascita di interesse per le reti neurali, che a sua volta ha portato all'avvento del "deep learning" e a massicci progressi per quanto riguarda problemi come il riconoscimento facciale, la traduzione automatica e la navigazione autonoma dei veicoli. Quindi, la prossima volta che che ci scervelleremo sulla sintassi imperscrutabile per la ricerca avanzata del nostro editor di testo, motore di ricerca Internet o firewall nazionale, prendiamoci un minuto per pensare ai pionieri dell'intelligenza artificiale, sconfitti e screditati ma che hanno finito per realizzare tutti i loro sogni, dalla corrispondenza delle wildcard alle auto a guida autonoma.

(pubblicato sabato 9 ottobre 2021) (fonte (opens new window))