Archivi delle etichette: espressioni regolari

Macchine a stati finiti e il pattern matching amighista (parte 1)

amirex

Sono un Amighista, lo confesso. L’Amiga era un computer molto serio, a dispetto di ciò che tanti credono dal momento che il suo successo commerciale era dovuto principalmente ad alcune capacità che lo rendevano assai appetibile nel mondo ludico. Oltre all’hardware custom (che oggi fa sorridere ma all’epoca era incredibile…) c’era un sistema operativo straordinario.

Non voglio parlarvi dell’AmigaOS in generale: mi aggancio ad alcuni vecchi articoli di questo blog che parlano di regular expression e macchine a stati finiti, e con il pretesto cerco di implementare il pattern matching usando le regex nella variante messa a disposizione dall’Amiga tramite la libreria di sistema dos.library.

Sull’Amiga si parlava proprio di pattern matching: vedete per esempio la sezione 7-31 del manuale Using the System Software v2.05, che potete trovare su archive.org in vari formati tra cui DJVU.

Rileggere questi post (o leggerli se non li avete mai letti) non vi farà male:

Spero che le mie scarse capacità didattiche e la mia prolissità non vi ammorbino troppo. Se notate errori di varia natura (che non siano frutto di necessarie semplificazioni) o avete suggerimenti, li ascolterò… tempo permettendo.

Questo articolo è solo di apertura e non c’è veramente carne al fuoco.

Pattern matching su Amiga

Pare che ci siano circa 7000 linguaggi nel mondo, ma quelli che siamo in grado di elencare e di cui sappiamo l’esistenza sono una misera frazione.

Le regular expression più note sono in pratica tre e sembrano varianti/estensioni di una base comune: POSIX semplici, estese e PCRE (Perl Compatible Regular Expression).

Ma un tempo c’era pure l’Amiga e anche lì c’era l’esigenza di avere delle regular expression per fare del pattern matching (chiaro, no?) Un uso caratteristico era nei file requester1.

Un file requester della libreria di sistema asl.library
Un file requester della libreria di sistema asl.library

Il file requester nell’immagine è dell’AmigaOS4, ma comunque c’era pure nelle versioni precedenti (fornito allora come “ora” dalla libreria di sistema asl.library), anche se magari meno gratificante esteticamente; per i più esigenti c’erano altre possibilità fornite da toolkit come MUI o ReAction.2

Il punto comunque è che in questi file requester tipicamente si metteva di default il pattern per nascondere i file .info, che sono dei file del Workbench (il “desktop” e l’explorer o il finder dell’Amiga) contenenti l’icona ed eventualmente alcune metainformazioni associate. Niente che di solito l’utente voglia vedere quando richiede l’elenco dei file contenuti in una cartella, che su Amiga si chiamava drawer (cassetto) o directory (schedario).

Per questi scopi il glob è più popolare, è un po’ più alla portata di tutti (mentre moltissimi utenti non sanno nulla delle regular expression): se una finestra di dialogo di un programma di grafica ci chiede di scegliere un file, molto probabilmente applicherà diversi “glob”, uno per ogni formato che capisce: *.jpg, *.png ecc.3

Il pattern (Amiga) per nascondere i .info è, come potete vedere dall’immagine, ~(#?.info): il pattern #?.info selezionerebbe tutti i file terminanti in .info. Il ~ nega e le parentesi raggruppano, sicché ~(#?.info) seleziona tutti i file che non soddisfano il pattern #?.info, cioè che non terminano con .info.

Avrete intuito (forse) che #?, espresso nella lingua delle regular expression più note, è .*. Su Amiga ? significa “qualunque carattere”, dunque equivale al punto, e # è il quantificatore (ciò che segue compare 0 o più volte), dunque equivale all’asterisco. Notiamo anche che l’ordine è invertito: su Amiga diciamo prima quante volte compare ciò che segue, mentre nelle RE il quantificatore viene dopo.

Il problema che ci poniamo non è la traduzione tra sintassi diverse di RE o pattern “equivalenti”: vogliamo costruire una macchina a stati finiti per matchare una stringa a partire dai pattern in stile Amiga.

Notate una cosa: una volta che abbiamo la nostra macchina a stati finiti, ci possiamo disinteressare delle sue origini, cioè da dove siamo partiti per generarla: siamo partiti da #?.info? O da .*\.info? O da *.info? O l’abbiamo scritta a mano?

Ora potete studiarvi il pattern matching dell’Amiga, se proprio volete…

Nella prossima puntata

Per incuriosirvi… (spero di avere il tempo e la voglia: che non diventi del vaporware, insomma!)

Il problema può essere decomposto in due parti. La prima è poter definire programmaticamente una macchina a stati finiti, ed è quello che volevo provare a fare nella prossima puntata. Fatto ciò, dovremo risolvere l’altro problema: generare la macchina a partire dal pattern4.

L’idea che voglio seguire per la FSM è questa: definire gli stati e poi “unirli” tra di loro, specificando in quale circostanza (ovvero in seguito a quale “evento”) si passa da uno stato all’altro — l’esempio terrà sempre a mente l’uso specifico delle espressioni regolari e affini, sicché gli “eventi” sono in realtà i caratteri letti dall’input. Potremo poi dare in pasto alla macchina a stati così definita la stringa da controllare.

Una volta che abbiamo questi mattoncini, dovremo implementare un algoritmo che ci consenta di generare la macchina a stati a partire dal pattern: tornerà in gioco il pattern matching Amiga, tanto per prendere le distanze dalle RE note, troppo famose… e anche perché sennò che ne ho parlato a fare?

Due cosette che è bene tenere a mente:

  • non ho alcuna pretesa di rigore formale teorico (non ne sarei nemmeno capace) — se avete rimostranze sulla terminologia, suggerimenti per evitare fraintendimenti con il mondo accademico e/o settoriale, o perle di saggezza in generale, elargitele, ma tenete a mente che semplificare e comunicare alle volte significa mentire consapevolmente…;
  • alcuni aspetti (anche pratici) non saranno curati, per questioni di tempo e proporzioni — insomma, non vi aspettate del codice perfetto, con un design ben pensato, ecc… tuttavia, se mi fate notare o se noterò da me erroracci e/o antipattern vergognosi, proverò a trovare il tempo di coprire le tracce correggerle.

Dubitate, pensate, esplorate, non vi fermate, ricominciate.

Qui metterò il link alla prossima puntata non appena avrò avuto il tempo di scriverla:


  1. «I requester sono delle sottofinestre temporanee usate per confermare azioni o selezionare opzioni» (tradotto da ASL Library, About Requesters. Sono insomma delle finestre modali.

  2. Nelle versioni più recenti del sistema (ma prima di AmigaOS4), Amiga aveva introdotto il BOOPSIBasic Object Oriented Programming System for Intuition — negli “ingranaggi” di Intuition (appunto). Questo facilitò la nascita di toolkit che si integravano bene con Intuition, sia dal punto di vista dell’utente quanto del programmatore (che comunque, come al solito, ha vita sempre un po’ più difficile…) Potete pensare a BOOPSI come alle fondamenta per la costruzione delle classi di oggetti dell’interfaccia.

  3. Seguendo l’incauta consuetudine secondo la quale ciò che viene dopo l’ultimo punto del nome di un file sia sufficiente ad identificarne il formato.

  4. Cfr. Thompson’s construction algorithm e, per esempio, questa risposta su StackOverflow.