Archivi delle etichette: closure

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.

A proposito di Fibonacci…

Sommario

La semplice funzione per generare la serie di Fibonacci può essere scritta in Go sfruttando le closure.

Fibonacci

Ne abbiamo parlato nel post precedente, ma la sequenza di Fibonacci ha ancora qualcosa da farci scoprire, almeno dal punto di vista del linguaggio di programmazione Go.

Avevano scritto la funzione che calcola l’ennesimo numero della serie a partire dalla definizione della serie: il numero successivo è la somma dei due numeri precedenti. Il codice è quindi il seguente:

package main

// ennesimo numero della serie di Fibonacci
func fibonacci(n int) int {
    var a, b int = 0, 1
    for i := 0; i < n-1; i++ {
        a, b = b, a+b
    }
    return a
}

func main() {
    for i := 1; i < 10; i++ {
        print(fibonacci(i), " ")
    }
    println()
}

Funzioni di prima classe

Quando le funzioni sono tipi di prima classe possono essere trattate come valori, dunque possono essere assegnate a variabili e restituite da una funzione.
Questa prerogativa dei linguaggi funzionali è presente in Lua ed anche in Go (quello che diremo vale indifferentemente per i due linguaggi). Per fare un esempio in Go, assegnamo una funzione ad una variabile per il calcolo della somma degli argomenti interi (ricordo che per provare il codice possiamo utilizzare il comodo servizio web Playground:

package main

func main() {
    add := func(a, b int) int {
        return a + b
    }
    println(add(4,5))
}

Assegnare una funzione ad una variabile significa creare una funzione anonima (senza nome) ma, rispetto alla definizione diretta, cambia solamente la semantica/sintassi del linguaggio ma non il risultato che è esattamente equivalente.

Un esempio con una funzione factory è il seguente dove rispetto ad un simbolo passato come argomento, una funzione restituisce la funzione dell’operazione corrispondente:

package main

func operation(op string) func(int, int) int {
    switch op {
    case "+":
        return func(a, b int) int {
            return a + b
        }
    case "-":
        return func(a, b int) int {
            return a - b
        }
    case "*":
        return func(a, b int) int {
            return a * b
        }
    case "/":
        return func(a, b int) int {
            return a / b
        }
    default:
        return nil
    }
}

func main() {
    add := operation("+")
    println(add(4, 5))
    molt := operation("*")
    println(molt(4, 5))
}

Closure

Quando una funzione di prima classe ha accesso alle variabili locali, le variabili che appartengono allo stesso scopo della funzione, viene chiamata closure.

Tornando a Fibonacci, poiché sono necessari due valori iniziali di innesco della serie, possiamo esprimerli con variabili locali di una closure:

package main

// fibonacci is a function that returns
// a function that returns an int
func fibonacci() func() int {
    a, b := 1, 0
    return func() int {
        a, b = b, a + b
        return a
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        println(f())
    }
}

Le variabili a e b interne alla funzione fibonacci() sono variabili che possono essere lette e scritte dalla funzione anonima, verificando il concetto di funzione closure.
A questo punto possiamo anche creare funzioni di Fibonacci a piacere definendo di volta in volta i primi due numeri della sequenza:

package main

// fibonacci is a function that returns
// a function that returns an int
func fibonacci(n1, n2 int) func() int {
    return func() int {
        n1, n2 = n2, n1 + n2
        return n1
    }
}

func main() {
    f1 := fibonacci(1, 0)
    for i := 0; i < 10; i++ {
        println(f1())
    }
    println()
    f2 := fibonacci(50, 17)
    for i := 0; i < 10; i++ {
        println(f2())
    }
}

Ed in Lua?

-- Lua version : - )
 
-- fibonacci is a function that returns
-- a function that returns an int
function fibonacci(n1, n2)
    return function()
        n1, n2 = n2, n1 + n2
        return n1
        end
end
 
f1 = fibonacci(1, 0)
for i=1,10 do
    print(f1())
end

print()
f2 = fibonacci(50, 17)
for i=1,10 do
    print(f2())
end

Insomma possiamo dire che i progettisti del Go hanno studiato in modo approfondito anche Lua e Python. O no? 🙂

Alla prossima…
Un saluto.
R.