Nella progettazione di un programma non basta creare uno o più algoritmi per risolvere problemi di natura computazionale, come il calcolo, la ricerca o l’ordinamento,. La maggior parte delle applicazioni, in particolar modo le applicazioni interattive grafiche, i videogiochi o i server sono software che non solo svolgono calcoli, ma mantengono memoria delle interazioni e della storia dell’attività svolta, ed hanno un comportamento condizionato non solo dall’input dell’utente ma anche da questa memoria.

Pensiamo a Gmail: l’applicazione memorizza il login dell’utente, l’elenco delle mail lette e non lette, ed in base alle interazioni (accesso utente, nuova mail ricevuta, invio mail) si comporta di conseguenza. Oppure pensiamo ad un player video: esso permette interattivamente di andare in play, in pausa, in stop, ricordare l’ultima posizione del video che stiamo vedendo, andare avanti ed indietro da questa posizione, ecc.

L’applicazione è quindi un ecosistema complesso fatto di procedure, memoria, interazione, gestione errori, ed altre attività che ne determinano tutta la sua attività. E’ necessario quindi andare oltre l’algoritmo creare un modello ad alto livello che descriva questo sistemo, ovvero l’intero ciclo di vita dell’applicazione, come l’avvio, l’inizializzazione, l’interazione con l’utente, la memoria che mantiene sui dati, le condizioni di errore, e l’uscita.

Uno dei modelli più diffusi ed importanti per descrivere il funzionamento delle applicazioni reali è il modello matematico detto SFA, ovvero automa a stati finiti (o macchina a stati finiti). In questo modello l’applicazione si trova, in ogni istante, in uno stato ben definito tra un insieme finito di stati possibili. Il sistema passa da uno stato all’altro con una transizione in risposta a determinati eventi o input. Esistono molti modelli di automi a stati finiti, noi prenderemo quello con transizioni deterministiche, ovvero da un determinato stato A con un determinato evento E si può transitare sempre e solo allo stato B.

Vediamo un esempio di questo modello, la macchinetta del caffè.

Come si può vedere l’automa permette di organizzare il flusso di stati e transizioni e determinare quindi il modo in cui progettare l’applicazione. Ad esempio questo modello ci dice in modo rigoroso che il resto viene controllato ed emesso DOPO l’erogazione del caffè (un altro modello potrebbe prevedere l’erogazione di caffè dopo l’emissione del resto). Non va tuttavia confuso con un diagramma di flusso: esso non si occupa di capire come la macchinetta del caffè capisce che il denaro è in eccesso, ma solo quando e cosa fare se succede.

La macchina a stati finiti è un sistema semplice e potente per descrivere ecosistemi anche complessi e semplificare il lavoro del programmatore.

Modelli di Moore e di Mealy

E’ possibile rappresentare lo stesso comportamento di una applicazione con due modelli distinti.

L’automa di Moore è un modello lo stato è determinato esclusivamente da stati e transizioni.: un automa passa dallo stato S1 allo stato S2 con la transizione T1, e passa da S1 a S3 con la transizione T2, e così via. Il modello della macchina del caffè visto sopra è un modello di Moore: la macchina eroga il caffè dallo stato denaro inserito e raggiunge lo stato di caffè erogato.

L’automa di Mealy è un modello che invece introduce il concetto di output. La transizione non è solamente una azione che si svolge tra due stati, ma contiene al suo interno sia l’azione che l’output. Successivamente lo stato finale viene calcolato in base a entrambi (azione ed output). In altri termini esistono tre entità: Stato, Azione, Uscita, dove l’uscita è una conseguenza dell’Azione, e lo Stato è una conseguenza sia dell’Azione che dello Stato precedente.

Vediamo un primo esempio proprio con la macchina del caffè:

Come si vede ogni transizione è data da una coppia:

• l’azione svolta
• l’output generato

Lo stato invece è semplicemente il punto di partenza della prossima operazione.

Nel modello di Moore lo Stato accorpa sia l’uscita che lo stato di partenza della prossima transizione, e pertanto per avere due modelli con lo stesso comportamento occorrono più Stati distinti, ciascuno che mostra una singola coppia di Output/Stato di partenza.

Vediamo un altro esempio. Poniamo di dover progettare un player video, che prevede il play, la pausa, lo stop, e l’avanti e indietro veloce. Vediamo come viene rappresentato nei due modelli.

Moore:

Mealy:

Come si può vedere la differenza tra i due modelli si può riassumere nel fatto che il modello di Moore è molto rigoroso e definisce Stato qualsiasi Output distinto, il prezzo da pagare è un aumento degli stati e delle transizioni possibili. Nel modello di Mealy gli Stati sono ridotti, perché le Transizioni contengono sia l’azione che l’output.

Moore si usa quando:

• quando si desidera un modello rigoroso, che intende dare “rango” di Stato agli output. E’ il modello che si usa per definire ad esempio i sistemi dove la sicurezza è un fattore critico. Pensiamo al sistema di un ascensore: in Moore lo stop di un ascensore e l’apertura delle porte sono due Stati distinti, mentre in Mealy possono essere gestiti come un output e uno Stato.
• quando si desidera definire in modo rigoroso una UI: ogni schermata ed ogni output è uno Stato, e da esso derivano delle conseguenze.

In generale Moore è adatto a sistemi sincroni, cioè dove output e stato avvengono nello stesso momento (vedi ascensore o UI). Offre però modelli con più Stati e più Transizioni, più complesso da sviluppare.

Mealy è invece adatto quando:

• nella definizione della comunicazione tra sistemi: l’emissione di output di comunicazione avviene prima della transizione di Stato. Si pensi al player che va avanti velocemente (output) finché si tiene premuto il tasto FF e poi torna allo Stato play.
• nei sistemi basati su eventi: l’emissione dell’evento causa una reazione immediata, successivamente viene modificato lo Stato del sistema. E’ il caso della pressione del pulsante su una schermata web: il pulsante risulta visibilmente premuto, prima che si transiti allo Stato successivo.

In generale Mealy è adatto a sistemi asincroni, cioè dove output e stato possono avvenire in momenti distinti (vedi click del pulsante). Offre un modello con meno Stati e meno Transizioni, più semplice da sviluppare.

E’ comunque sempre possibile passare da un modello all’altro, a seconda del bisogno. E’ compito del programmatore scegliere il trade-off corretto in base alle esigenze del problema.

Tabelle di stato

E’ possibile rappresentare un automa a stati finiti anche con una tabella. Ad esempio:

	PLAY	PLAY	PAUSA	STOP
STOP	Play / Avvia flusso
PLAY	FF / Avanti veloce	FR / Indietro veloce	Pausa / Immagine ferma	Stop / Spegni flusso
PAUSA	Play / Riattiva flusso			Stop / Spegni flusso

Questo modello è utile per avere una rappresentazione analitica in fase di analisi, al fine di vedere se tutti i collegamenti sono evidenziati.

Esempi applicativi

Stati di processo

TCP Handshake

Ecommerce

Login/Registrazione di un sito

Conclusioni

Gli automi a stati finiti sono un modello matematico che consente di progettare una applicazione ad alto livello, identificando in modo chiaro sia gli Stati dell’applicazione, sia le transizioni tra gli stessi.

Vi sono due rappresentazioni:

• di Moore, che identifica gli stati con gli output del software, ed effettua le transizioni in base al solo stato di partenza: si usa per schemi rigorosi, in ambito di sicurezza e in ambienti sincroni;
• di Mealy, che inserisce gli output nella transizione, e gli stati identificano solo punti di partenza: si usa per schemi con meno stati, ed in ambienti asincroni.