Archivi delle etichette: FSM

Macchine a stati finiti e pattern matching (parte 2)

fsm_img

Nell’articolo precedente vi ho fatto ricordare dell’Amiga, vi ho rivelato che aveva le sue espressioni regolari per fare pattern matching, vi ho indotto a (ri)leggere tre articoli di questo blog, e… (questo non lo sapete, ma) prima di pubblicarlo ho tagliato un paio di lunghi paragrafi che discettavano un po’ di linguaggi, metalinguaggi e divagazioni annesse e (s)connesse. Ora forse si capiscono meglio certe affermazioni che ho lasciato e che non si adattano benissimo al testo pubblicato; però vanno sempre bene come “scuse” anticipate per il futuro.

Dimenticavo: avevo anche detto che avremmo affrontato la prima fase: “fare” una macchina a stati finiti (FSM). Mi sono seduto e ho buttato giù un po’ di codice che ora rivediamo assieme. Lo trovate nel mio “parco giochi” su github, precisamente qui.

Le classi necessarie al gioco vivono nel namespace mFSM: visto che ho usato nomi molto poco particolari come State, Connection, Rule… non è una brutta idea metterli in un namespace ad hoc.

Introduzione

L’idea guida alla base è come viene di solito rappresentata una FSM; qualcosa come

FSM
FSM

Ogni stato è un cerchio con un “nome” (un’etichetta) e poi degli archi in uscita e in entrata. La freccia che non ha un’origine indica lo stato iniziale della macchina. Su ogni arco è indicato l’“evento” (nel nostro caso, la ricezione di un carattere) che fa passare la macchina dallo stato da cui esce l’arco allo stato in cui tale arco è entrante (insomma, nella direzione della freccia). Lo stato “a doppio cerchio” è uno stato “finale”: se la macchina, terminato il suo lavoro, si trova in uno di questi stati finali (accepting states, «stati che accettano [l’input e lo riconoscono come facente parte del linguaggio]»), significa che la stringa processata è una stringa corretta del linguaggio.

La macchina dirà allora: io, Macchina, accetto te come legittima stringa

Vi siete già imbattuti in questa roba:

soluzione

Sarebbe bello poter dire: lo stato S1 è uno stato finale, la macchina passa dallo stato S1 a S2 quando riceve uno 0, ma resta sullo stato S1 quando riceve 1, ecc.

In effetti basterebbe poter descrivere il graf(ic)o così: lo stato S1 va a S2 tramite l’arco 0, va a sé stesso tramite l’arco 1; lo stato S2 va a S1 tramite l’arco 0, va a sé stesso tramite l’arco 1; infine, lo stato S1 è uno stato finale accettabile.

Stati

Quindi per noi lo stato è un cerchio singolo o doppio con un’etichetta inscritta. Questi elementi fanno parte della sua identità e sono “passivi” e “statici”. Farne una classe è semplice

class State
{
public:
    State(const std::string& name, bool final=false);
    bool accept() const;
    const std::string& name() const;
    void setFinal(bool final=true);
protected:
    std::string name_;
    bool final_;
};

La maggior parte degli stati non sono final, da cui il default sul costruttore; ci sono due getter (per il nome e final) e un setter, nel caso volessimo cambiare final dopo aver creato l’istanza. (Se creiamo noi gli stati, serve a poco; ma vedrete dopo che la creazione degli stati può essere fatta implicitamente da un’altra classe).

Uno stato ha anche degli archi uscenti; potremmo farne uno stato consapevole del fatto che, quando riceve un certo messaggio, può dover passare il cerino ad un altro stato. Dal punto di vista della macchina nel suo insieme, lo stato con il cerino è quello in cui si trova la macchina (lo stato corrente). Con questa metafora posso dire che gli archi descrivono la “dinamica”, e ogni stato conosce la parte che gli compete, cioè i suoi archi che vanno (se valgono certe condizioni) verso un altro stato.

La classe AwareState, derivata da State1, aggiunge due cose: un metodo per stabilire un arco (onRule) e uno per iterare sugli archi. Quest’ultimo metodo è usato dal “supervisore”, cioè dal codice che fa girare la macchina: lo stato è sì “consapevole” delle sue relazioni regolate, ma non è lui a tenere traccia di chi ha il cerino e a decidere cosa farne se la regola si rivela valida o no.

Però lo stato deve fornire gli elementi affinché il “supervisore” possa decidere, e lo fa senza esporre i dettagli sul come mantiene le connessioni2: il chiamante invoca il metodo overConnectionsDo fornendo come argomento una funzione che riceve una regola (Rule) e lo stato di destinazione. Il “supervisore” applica la regola sull’input (di cui lo stato non è aware) che sta elaborando e decide se mantenere lo stato corrente o passare a quello di destinazione.

Non è un design entusiasmante… però ci permette di buttare in pentola una cosa del C++11: l’header functional ci dà std::function<...> tramite il quale è facile specificare il “prototipo” della funzione che ci aspettiamo come argomento… e che potrà essere — e sarà — una closure

bool AwareState::overConnectionsDo(
        std::function<bool(const Rule*,
                       const std::string& stateName)> action) const
{
    for (auto& c : connections_) {
        if (action(c.rule, c.destState)) {
            return true;
        }
    }
    return false;
}

Usando altre due comodità del C++11 (ovvero auto e il for each che ci permette di iterare sugli elementi di una classe itarabile) passiamo in rassegna le “connessioni”; se l’action ritorna vero, usciamo a nostra volta con vero; altrimenti proseguiamo con la “connessione” successiva. Se per nessuna delle connessioni l’action ha restituito true, allora ritorniamo al chiamante con false. (Nel codice ho messo una versione alternativa di cui parlo alla fine.)

Praticamente ci aspettiamo che il chiamante usi action per segnalarci quando ha trovato una regola soddisfacente (solo il chiamante sa qual è l’input!) Se abbiamo più regole che danno true, la nostra FSM è malfatta. Non c’è nessun controllo nel codice per impedire ciò: sta a chi la costruisce non creare situazioni strane.

L’ordine delle regole va considerato arbitrario, cioè non dobbiamo far affidamento su un ordine preciso di controllo per fare magari qualche trucchetto strano. Nella specifica implementazione le regole ordinate in base alla dimensione dell’insieme di caratteri che possono soddisfarla. Quindi any, che è l’unica regola che acchiappa tutto (dunque 256 codici…), starà sempre in fondo.

AwareState& AwareState::onRule(const Rule* rule, const AwareState* dest)
{
    Connection con{rule, dest->name()};
    connections_.push_front(con);
    connections_.sort([](const Connection& a, const Connection& b)->bool {
            return a.rule->size() < b.rule->size();
        });
    return *this;
}

L’ordinamento è fatto passando una funzione anonima (di fatto una lambda function) al metodo sort gentilmente offerto da list, che è la classe di connections_.

Per capire qual è il problema che l’ordinamento risolve, consideriamo le regole a, any, ~b controllate in quest’ordine. Non hanno molto senso: se l’input è a (1) prendiamo la prima; in tutti gli altri casi si applica any (256) e mai ~b (255). Se l’ordine fosse a, ~b, any, l’input a verrebbe catturato dalla prima, c dalla seconda e b, infine, dalla terza. I numeri tra parentesi contano i caratteri per i quali la regola è valida (un ottetto ha 256 possibili valori).

Connection

AwareState mantiene le connessioni tramite una lista (list) in cui mettiamo le coppie 〈regola, nome dello stato di destinazione〉 (struttura Connection). Ho usato il nome invece del puntatore (passato in onRule) perché c’era un meccanismo che distruggeva e ricreava gli stati e in questo modo si evitavano puntatori ballerini (dangling pointer). Naturalmente i nomi vanno risolti, e questo è a carico della classe FSM che mantiene un’anagrafe di stati e regole.

Le regole (Rule)

Un arco parte da uno stato (che è quello che lo mantiene, nella lista connections_ di AwareState) e finisce in un altro (Connection.destState) “tramite” una regola, modellata dalla classe Rule. Con “tramite” intendo dire che c’è (o ci dovrebbe essere…) una relazione tra l’avvenuta o mancata transizione e la validità dell’input rispetto alla regola in questione (e dirò anche, in alternativa, che la regola è valida per quell’input).

La regola è espressa tramite una stringa e si applica a un singolo carattere in input (passato come int). Quando dico carattere intendo in realtà byte: il codice non gestisce stringhe in codifiche multibyte. Il metodo satisfiedBy ritorna vero se il carattere soddisfa la regola, falso altrimenti.

Dal codice per satisfiedBy si capisce che le regole sono pochine: match esatto, qualunque carattere e infine match con tutto tranne un carattere specifico. Possiamo espanderle a piacere anche con l’intento di semplificare la macchina3.

Cosa accade se la regola è soddisfatta dipende dalla funzione action passata a overConnectionsDo. Il metodo viene invocato da FSM::feed.

Le regole possono venir usate più volte da diversi stati: la regola che accetta la a è sempre la stessa, sia che la usi lo stato X sia che la usi lo stato Y. Questo fatto viene sfruttato dalla classe FSM, che ha un magazzino di regole.

FSM

La classe FSM mette insieme un po’ tutte le altre classi, usandole in modo opportuno. È la classe che “rappresenta” la macchina a stati finiti ed è contemporaneamente la classe che la fa “girare”.

Per costruire la nostra macchina usiamo principalmente connect, che crea implicitamente gli stati di cui non conosce il nome; tuttavia crea stati non-final di default, per cui gli stati final vanno creati esplicitamente a parte.

m.state("S1", true);
m.connect("S1", "S2", "0");
m.connect("S1", "S1", "1");
m.connect("S2", "S1", "0");
m.connect("S2", "S2", "1");
m.first("S1");

L’ultima riga definisce lo stato di partenza; in questo caso non serviva perché il primo stato creato è anche quello di partenza.

La macchina m così creata è quella dell’esempio di wikipedia e serve per vedere se un numero ha un numero pari di 0.

Come usiamo questa macchina? Abbiamo due modalità principali.

Una è quella passo-passo: le diamo in pasto dei caratteri (tramite il metodo feed) e lei si comporta di conseguenza, cambiando il suo stato (oppure no…). Quando abbiamo finito possiamo sapere se la macchina è in uno stato final usando il metodo accepted(). Se vogliamo riusare la macchina per un’altra sequenza, dobbiamo riportarla allo stato iniziale (metodo rewind).

L’altra modalità prevede di far girare la macchina su una stringa (run). Questo metodo parte sempre dallo stato iniziale, ma al termine lascia la macchina nello stato dove l’input l’ha condotta; perciò dovete chiamare rewind se dopo un run volete usare feed con la macchina nello stato iniziale.

Il metodo run ha due modi diversi di funzionamento: uno strict, in cui l’assenza di una regola che gestisca l’input interrompe il processamento e restituisce false (però la macchina potrebbe essere ferma su uno stato final… sta al chiamante decidere che fare…); un altro in cui ogni carattere per il quale non c’è una regola lascia la macchina indifferente (si passa al carattere successivo rimanendo nello stesso stato). Il default è la versione “rilassata”; si può cambiare chiamando il metodo strict(true).

Il metodo feed è un po’ il cuore dell’esecuzione. Dopo un breve preambolo per assicurarsi che ci sia uno stato iniziale e quello corrente, abbiamo una bella closure passata al metodo overConnectionsDo dello stato corrente.

    const AwareState* next_current = current_;
    bool matched = current_->overConnectionsDo(
        [c,&next_current,this](const Rule* r, const std::string& s)->bool {
            if (r->satisfiedBy(c)) {
                if (this->states_.count(s) > 0) {
                    next_current = states_[s];
                }
                return true;
            }
            return false;
        });
    current_ = next_current;    

Se andate a vedere il codice di overConnectionsDo, vedete che è un ciclo sulle “connessioni”, cioè sulle coppie 〈regola, stato destinazione〉. È quello che la funzione riceve in ingresso (r e s). Oltre agli argomenti, la funzione “cattura” c, next_current e this. Poiché abbiamo bisogno di cambiare next_current, lo catturiamo per riferimento (this è un puntatore e quindi automaticamente con this->states_ facciamo riferimento all’istanza e non ad una sua copia).

Se il carattere c soddisfa la regola che lo stato ci ha passato, allora il prossimo stato sarà quello specificato da s, posto che esista. Alla fine della giostra matched sarà vero se c soddisfa almeno una delle regole r, e sarà falso altrimenti (se nessuna regola è stata soddisfatta).

Verifichiamo!

Il codice testFSM.cpp crea alcune FSM e le mette alla prova. In particolare ho creato la FSM corrispondente al pattern #?.info… Il pattern non richiede che dopo .info non ci sia altra roba. Sapete modificare la FSM in modo che la stringa da verificare debba finire esattamente con .info? (Con le RE ciò equivale a .*\.info$4).

Trovate anche la macchina per la grammatica a(ab)n e quella per riconoscere i codici 12A45 o 22B48 (cfr. Macchine a stati 2). Potete aggiungere tutti i test che volete per verificare che si comporti come vi aspettate… Se trovate un bug, sono qui per schiacciarlo… sempre tempo permettendo!

Sul codice

Non ci dovrebbero essere cose particolarmente difficili.

Ho cercato di mettere un minimo di enfasi su ciò che personalmente trovo più interessante nel C++11, ovvero le funzioni che stanno guadagnando il posto di cittadini di prima classe e ci permettono di adottare un po’ del paradigma funzionale. A tal scopo, oltre a functional, ho incluso algorithm per riscrivere il codice di overConnectionsDo usando std::any_of, che restituisce vero se per uno qualunque degli elementi il predicato ritorna vero (qui il predicato è data dalla nostra action, che dobbiamo però wrappare in un’altra closure per “adattare” gli argomenti5).

bool AwareState::overConnectionsDo(
    std::function<bool(const Rule*,
                       const std::string& stateName)> action) const
{
    return std::any_of(connections_.begin(),
                       connections_.end(),
                       [&](decltype(connections_.front()) c) {
                           return action(c.rule, c.destState);
                       });
}

Un’altra cosa che torna comoda è poter demandare al compilatore l’ingrato compito di “capire” il tipo giusto di un dato, visto che lui può dedurlo; alle volte non è solo ingrato, ma anche piuttosto complicato (non è il caso del codice della FSM, ma il discorso è generale). Su questo versante ho usato due novità: auto e decltype, che vedete nel frammento sopra. Sconsiglio l’uso di decltype come l’ho usato io: l’ho fatto solo per farvi vedere che, volendo, si può fare… (a mano avremmo scritto const Connection&).

Infine, tutto vive in due file soltanto, FSM.cpp e FSM.hpp. In teoria sarebbe più carino se avessimo State.cpp, AwareState.cpp, Connection.cpp, Rule.cpp, FSM.cpp e relativi .hpp. Ma viste le dimensioni del tutto, non credo che sia un peccato troppo grande aver fatto un nunico malloppo.

Compilazione

Per divertirvi con i test, la compilazione è

g++ -I src/ -std=c++11 src/FSM.cpp src/testFSM.cpp -o testFSM.cpp

Questo se state nella root del progettino (un livello sopra src). Forse ci aggiungerò un Makefile in futuro.


  1. Poteva esserci anche una sola classe State, che fosse già anche consapevole, visto che State normale non è usata… Potete provare come esercizio ad eliminare State incorporandola direttamente in AwareState (poi potete rinominarla in State). È andata così perché prima è uscita la classe, piuttosto ovvia, State e solo dopo mi sono trovato a dover scegliere come rappresentare le “connessioni” tra i diversi stati. Dalla scelta fatta è nato l’AwareState

  2. Questo perché per progetto le “connessioni” sono informazioni che lo stato tiene con sé, diventando “stato consapevole”, AwareState. Si poteva fare diversamente, forse meglio: una classe che descriveva tutta la FSM: dallo stato Si si va allo stato Sj quando la regola Rn è valida… ecc. Il “supervisore” non avrebbe fatto altro che leggere questa descrizione e agire basandosi su di essa e sull’input. Invece per ciascuno stato l’informazione che serve al “supervisore” è nello stato stesso, per cui c’erano almeno due opzioni: un getter per ottenere la lista degli archi uscenti (connections_), o un metodo che invoca una funzione su ciascuna connessione trovata — ogni “connessione” è una “regola” e uno stato destinazione.

  3. Per esempio: se il carattere è in un elenco (immaginate [0-9]), salta allo stato Sn. Dobbiamo fare un arco per ciascun carattere; se la Rule consentisse il match con un elenco, ci risparmieremmo un po’ di archi.

  4. Invece nel caso dei pattern Amiga è implicito, nel senso che il match è sempre esatto; con le RE è come se scrivessimo sempre ^...$ (dove ... rappresenta il resto della RE); quindi in realtà il pattern che la FSM implementa è #?.info#? e non #?.info.

  5. Si potrebbe usare std::function<bool(const Connection&)> e risparmiarci un livello: il predicato sarebbe direttamente action.

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.