Nella progettazione di ua applicazione non è sufficiente creare un algoritmo (o più algoritmi) per risolvere un determinato problema o fornire una certa funzionalità. La maggior parte delle applicazioni, infatti, ed in particolar modo le applicazioni interattive, le applicazioni visuali 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, e mostra all’utente delle interazioni che dipendono dai dati memorizzati in quel momento. Un player video è sempre in una situazione ben precisa: in play, in pausa, in avanti veloce, ecc. e di conseguenza permette di svolgere determinate operazioni in base al suo stato attuale. E si possono fare innumerevoli altri esempi.

Una applicazione è quindi di norma un ecosistema che non solo svolge delle operazioni, anche interattive, ma ha un suo stato interno, che ne determina l’attività e l’interazione con l’esterno. E’ necessario quindi andare oltre l’algoritmo e creare un modello ad alto livello che descriva questo sistema, che descriva cioé 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 è l’automa a stati finiti (SFA), un modello matematico in grado di descrivere tutti gli stati interni della applicazione e le transizioni da uno stato all’altro.

In questo modello l’applicazione si trova sempre in uno stato ben definito tra un insieme finito di stati possibili. Il sistema poi può passare da uno stato all’altro, secondo regole ben definite, tramite una transizione, che può avvenire in base a determinati eventi, input, operazioni di algoritmiche.

In questa lezione studieremo gli SFA deterministici, ovvero quelli per cui a partire da uno stato A se accade un evento E si può transitare sempre e solo allo stato B, ovvero la transizione è prevedibile.

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

Come si può vedere l’automa permette di definire ed organizzare in modo generale 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è, ma potremmo predisporre un altro modello che 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, a seconda del focus che vogliamo dare alla progettazione del software.

L’automa di Moore è un modello in cui lo stato è determinato esclusivamente dallo stato precedente ed una transizione: 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 comprende due informazioni: l’azione di transizione e l’effetto che fa verso il mondo esterno (cioè l’output), oltre ad indicare lo stato successivo. In altri termini esistono tre entità: Stato, Azione, Uscita, dove l’uscita è una conseguenza dell’Azione, mentre lo Stato successivo è una conseguenza sia dell’Azione che dello Stato precedente.

Vediamo una macchina del caffè di Mealy:

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. Il modello di Mealy ci consente invece di separare i due concetti, e quindi possiamo scrivere più transizioni da uno stato A, ognuna con output differenti, ma che arrivano comunque allo stato B.

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, ma ci obbliga a considerare come “stato” quello che talvolta è solo un “output”. Nel modello di Mealy le Transizioni contengono sia l’azione che l’output, e quindi possiamo scrivere meno stati possibili.

Moore si usa:

• quando si desidera un modello rigoroso, che intende dare “valore” 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 occorre definire sistemi di input/output: 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.
• quandi si progettano 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.