State diagram: le origini, gli automa a stati finiti
Un automa a stati finiti è un modello formale utile in tutte le circostanze in cui si abbia la necessità di studiare un sistema che possiede un numero finito di configurazioni e che, in funzione di uno stimolo esterno, transiti da una configurazione ad un’altra.
L’esempio classico utilizzato per illustrare le peculiarità del formalismo degli automi a stati finiti è costituito dagli “Analizzatori lessicali”.
Quando un compilatore analizza il codice sorgente fornitogli in input per verificarne la correttezza e realizzarne la traduzione, tipicamente, la prima operazione che compie è l’estrazione degli elementi sintattici del linguaggio (i famosi token): identificatori, parole chiavi, costanti, operatori, delimitatori.
In sostanza, si esegue quella che viene definita analisi lessicale; la procedura software che la realizza è pertanto, denominata analizzatore lessicale o più comunemente scanner.
Si consideri l’esempio dell’automa a stati finiti utilizzato per analizzare la sintassi degli identificatori di un linguaggio di programmazione qualsiasi, definita successivamente per mezzo della Forma Normale di Backus (Backus Normal Form BNF, bei tempi, eh!?).

<identificatore> ::= <lettera>/<sottolin.> {<lettera>/<cifra>/<sottolin.>}n
<lettera> ::= A/B/…/Z/a/b/…/z
<cifra> ::= 0/1/…/9
<sottolin.> ::= _

Figura 1. Diagramma a stati di un analizzatore sintattico di identificatori

Il diagramma riportato in figura 1 è stato introdotto sia per mostrare l’immediatezza degli state diagram, sia per iniziare a introdurre gli elementi che lo costituiscono.
Si potrebbe proseguire con la presente digressione considerando il rapporto che esiste tra gli automi a stati finiti e le grammatiche regolari tanto care agli studenti di IT, ma ciò esula dagli obiettivi del presente articolo.
I diagrammi degli stati sono utilizzati per analizzare l’intero ciclo di vita di una parte del sistema, che può essere un intero sotto sistema o più semplicemente un oggetto.
Gli state diagram mostrano gli stati in cui un oggetto può transitare e gli eventi che ne condizionano il comportamento nel tempo, ossia gli eventi che generano il passaggio da uno stato al successivo. Eventi tipici sono: la ricezione di messaggi, l’insorgenza di condizioni di errore, il verificarsi di specifiche situazioni, lo scadere di un determinato lasso di tempo a disposizione, ecc.
Lo stato di un oggetto è una condizione o situazione che si verifica durante il ciclo di vita dell’oggetto stesso. Ogni stato è caratterizzato dal soddisfacimento di precise condizioni, dall’esecuzione di determinate azioni e/o semplicemente dall’attesa del verificarsi di opportuni eventi.
Gli state chart diagrammi sono molto utili per mostrare il comportamento dinamico di oggetti particolarmente complessi o dei quali si sappia con certezza il dominio dei relativi stati.
Spesso vengono associati alla documentazione delle singole classi (in Rational Rose non esiste alternativa), e in tal caso sono caratterizzati dal possedere un livello di astrazione molto basso.
In condizioni di run time, tutti gli oggetti possiedono uno stato, il quale è il risultato di tutte le attività eseguite fino a quel dato istante dall’oggetto stesso.
Lo stato di un oggetto è costituito dai valori associati ai relativi attributi e dai legami instaurati con altri oggetti, che, in ultima analisi rientrano nel primo caso, in quanto si tratta di particolari valori di tipo “puntatore” (indirizzo di blocchi di memoria) associati ad opportuni attributi. (Si spera che nessun lettore obietti che “In Java i puntatori non esistono!”).
Alcune classi prevedono un attributo di stato vero e proprio.
Contrariamente a quanto alcuni sarebbero portati a pensare, la transazione da uno stato ad un altro non avviene spontaneamente, o per intercessione di qualche PIO oggetto, bensì un oggetto transita in un nuovo stato al verificarsi di opportuni eventi.
Per esempio una e-mail transita dallo stato “Unsent Message” a quello di “Sent” a seguito di un invio esplicito richiesto dall’utente ed eseguito senza errori dal client di posta.
Ancora, un preventivo non appena redatto si trova in uno stato di “attesa responso”. A fronte di una conferma da parte del cliente transita nello stato di “accettato”, mentre, nel caso in cui ciò non avvenga e trascorso un lasso di tempo maggiore del periodo di validità concordato, il preventivo transita nello stato di “rifiutato”.
 
 

Figura 2 State diagram del ciclo di vita di un preventivo.

Dall’esempio di figura 2, si può notare che il diagramma degli stati coinvolge due prospettive di dinamicità, per così dire, esterna ed interna. La prima è una vera e propria interazione, ossia viene descritto il comportamento esterno dell’oggetto e la sua interazione con la restante parte del sistema, realizzata per mezzo di scambio esplicito di messaggi. Per esempio, si consideri ancora il diagramma di figura 2, quando un preventivo transita nello stato accettato, automaticamente si esegue la funzione “genera una commessa”, ossia viene inviato un messaggio ad un opportuno oggetto che provvederà ad avviare un nuovo flow.
La dinamicità “interna” è invece rappresentata dal cambiamento di stato, descritto per esempio, dall’attribuzione di nuovi valori agli attributi dell’oggetto.
 
 
 

Gli elementi
Gli state diagram hanno un solo punto di inizio (stato iniziale) e possono disporre di diversi punti di arrivo (stati finali), i primi indicano il punto di partenza e sono rappresentati per mezzo di un cerchio pieno, i secondi (detti “occhi di bue” ,“bull’s eye”) indicano la fine dell’esecuzione della macchina a stati e sono rappresentati per mezzo di due circonferenze concentriche di cui la più interna è piena. (Vedere figura 2)
Chiaramente, non si tratta di stati veri e propri: non hanno le feature tipiche degli altri e pertanto vengono denominati pseudostati.
I rimanenti stati sono realizzati graficamente per mezzo di rettangoli con gli angoli arrotondati. I vari elementi sono connessi tra di loro per mezzo di frecce corredate da un’etichetta che ne indica l’evento che ha generato la transizione.
Ogni stato può essere costituito da tre sezioni: il nome, le variabili di stato e le attività, di cui solo la prima (il nome) è obbligatoria. Nel caso di stati concorrenti è prevista un’ulteriore sezione dedicata agli stati annidati.
 
 

Figura 3 Rappresentazione di uno stato

Per quanto concerne le prime due sezioni c’è ben poco da dire, mentre per ciò che riguarda le attività va evidenziato che esistono tre eventi standard: entry, do, exit.
Il primo è utilizzato per esprimere un’azione da compiere non appena si entra nello stato che la contiene, ed è utile per inizializzare il valore degli attributi, per inviare dei messaggi di notifica, ecc.. L’evento exit è l’opposto del precedente, ossia permette di specificare azioni da compiere all’uscita dello stato, utile anch’esso per l’invio di messaggi di notifica. Infine l’evento do è utilizzato per evidenziare azioni che si compiono mentre l’oggetto permane nello stato.
In tabella 1 sono riportati le tipologie di azioni più frequenti.
 

Nella rappresentazione grafica dello stato di login riportato in figura 4, si può notare che oltre alla presenza delle attività standard, sono presenti anche delle transizioni interne (help, clear). Si tratta di eventi che si verificano all’interno dello stato e che devono essere gestiti senza causare l’uscita dallo stato stesso. Questi stati non vanno confusi con le auto transizioni (self transition), in quanto in questo caso vi è un effettiva transizione: si esce dallo stato per poi rientrarvici, e quindi vengono eseguite le eventuali azioni connesse con gli eventi entry e exit. 
 
 

Figura 4. Esempio stato login

Una transizione è una relazione tra due stati; indica che un oggetto nel primo stato, eseguendo determinate azioni, passa (“fire”) al secondo in seguito al verificarsi di uno specifico evento o di una determinata condizione.
Una transizione è composta da cinque parti:

1. stato di partenza;
2. evento trigger: evento che può provocare la transizione di stato, in accordo con le condizioni di guardia;
3. condizione di guardia: espressione booleana che abilita o inibisce la transizione di stato avviata da un determinato evento (viene scritta tra parentesi quadre dopo l’evento trigger);
4. azione: computazione atomica (non interrompibile dal verificarsi di ulteriori eventi) eseguibile (invocazione, creazione o distruzione di oggetti, ricezione o invio degnali);
5. stato di arrivo

Nel caso in cui si esamini una macchina a stati concorrenti, in tal caso una transazioni può disporre di diversi stati di partenza e arrivo.
 
 
 
 

Elementi “avanzati”
L’utilizzo degli elementi introdotti in precedenza, detti “base”, permette di modellare un gran numero di meccanismi.
Talune volte però, è necessario ricorrere a elementi più sofisticati (appunto avanzati) al fine di rendere i diagrammi più chiari ed eleganti.
Per esempio, al fine di agevolare il processo di rappresentazione di modelli complessi è possibile visualizzare eventuali stati interni (annidati) che costituiscono stati più generali, detti compositi per distinguerli da quelli semplici che non prevedono la presenza di stati annidati. Il ricorso a tale feature va comunque ben ponderato, in quanto spesso risulta più chiaro realizzare appositi state chart diagram di dettaglio.
Il digramma riportato in figura 5 illustra la modellazione di un ipotetico fax (esempio sempre molto originale). Al fine di evidenziare il comportamento degli stati di trasmissione e ricezione (stati compositi), sono stati evidenziati i relativi stati annidati (nested state).
 
 

Figura 5a  Statechart di un ipotetico invio di fax

Figura 5b  Statechart di un ipotetico invio di fax

Quando una transizione entra in uno stato composito viene eseguito lo stato iniziale interno. Talune volte però è preferibile che l’oggetto abbia memoria dell’ultimo sottostato attivo prima dell’ultima uscita dallo stato composito stesso. Si consideri la gestione di situazioni anomale di un oggetto che si occupi dell’installazione di un determinato prodotto SW (figura 6). Si prenda in esame la situazione in cui l’oggetto richieda di collegarsi ad un sito Internet per registrare e quindi terminare l’installazione e che l’utente non abbia ancora provveduto ad instaurare la connessione stessa. In tali circostanze, l’oggetto dovrebbe abbandonare il suo stato composito (installa), gestire l’errore e, nel caso in cui l’utente ripristini una situazione corretta (instaurazione della connessione Internet), proseguire senza dover necessariamente ricominciare l’intero processo. Per risolvere situazioni di questo tipo, si ricorre ad un pseudostato denominato hystory state, disegnato per mezzo di un cerchio con un carattere “H” maiuscolo posto al suo interno. Pertanto, quando si introduce uno stato “memoria”, l’entrata nello stato composito che lo contempla non genera necessariamente l’esecuzione dello stato iniziale, bensì la selezione dello stato da cui iniziare dipende dall’ultimo stato annidato eseguito prima dell’abbono dello stato composito. Ovviamente il sottostato iniziale viene sempre eseguito la prima volta che si entra nello stato composito.
 
 

Figura 6  Esempio di utilizzo dell’History state.

Nei diagrammi presentati fin qui i vari sottostati sono stati impostati in modo tale che la relativa esecuzione avvenisse in modo sequenziale, spesso però occorre modellare tali stati al fine di rendere la relativa esecuzione concorrente, in tal caso si parla di sottostati concorrenti. Ciò consente di rappresentare più (sotto)macchine a stati in esecuzione parallela nello stesso stato che le contiene.
Sebbene sia possibile utilizzare tale tecnica, spesso risulta più opportuno partizionare lo stato attraverso più oggetti attivi, ciascuno demandato a modellare il comportamento di una sottomacchina a stati. Esistono però delle situazioni in cui non sia possibile procedere in tale decomposizione o comunque non risulti conveniente. Ciò si verifica quando non esiste alcuna interazione, o comunque essa risulti del tutto marginale, tra i comportamenti delle varie macchine a stati. 
 
 

Figura 7 Esempio di stato composito costituito da sottostati concorrenti.

In figura 7 è riportato un esempio di uno stato composito costituito da due macchine a stati sequenziali, denominate rispettivamente “testing” e “commanding”, separate da una linee tratteggiata.
La transizione che genera il passaggio dallo stato di “idle” a quello di “Maintenance” è a tutti gli effetti un “fork”, in quanto determina la generazione di più processi (in questo caso due) in esecuzione parallela. Analogamente, la transizione in uscita dallo stato corrisponde ad un “join”.
Nel caso in cui una delle sotto macchine a stati raggiunga il relativo stato finale, deve comunque rimanere in attesa affinché anche gli altri raggiungano il medesimo stato nella propria sequenza.

 
Conclusioni
Questo articolo è dedicato all’illustrazione delle macchine a stati e specificatamente agli statechart diagram, utilizzate nello Unified Modeling Language per modellare determinate proiezioni dell’aspetto dinamico di un sistema. In particolare, in funzione dell’aspetto al quale si vuole conferire maggior risalto, le state machines possono essere rappresentate o attraverso degli activity diagrams o per mezzo degli statechart diagrams. I primi evidenziano l’evoluzione del flusso di controllo in termini di sequenza delle attività svolte, i secondi visualizzano il dominio degli stati di un oggetto e le transazione che determinano il passaggio di stato. Si tratta di due formalismi ben noti nel mondo dell’informatica facilmente riconducibili ai flow chart e agli automi a stati finiti.
La macchine a stati possono essere utilizzate in diverse viste del modello con differenti livelli di astrazione, pertanto è compito del progettista scegliere, di volta in volta, il livello più consono per la fase di progetto a cui appartengono.
 
 
 

Bibliografia

[1] The Unified Modeling Language User Guide
Grady Booch, James Rumbaugh, Ivar Jacobson
Addison Wesley
Questo libro vanta il primato di essere stato scritto dai progettisti originali del linguaggio, sebbene sia conosciuto come “Grady’s book”, dal nome del suo primo autore. La mancanza di una sua copia (magari autografata!) può generare giudizi di scarsa professionalità per coloro che operano nel settore della progettazione O.O... Ciò però, costituisce una condizione necessaria, ma non sufficiente, in quanto bisogna, assolutamente, aggiungere una copia del [3] e una del [4]. Sono soldi spesi bene! Forse, il limite del libro, se proprio se ne vuole trovare uno, è quello di essere poco accessibile ad un pubblico non espertissimo di progettazione O.O. Un altro piccolo inconveniente è che, probabilmente, taluni esempi possano sembrare di carattere accademico: poco rispondenti alle problematiche del mondo reale.

[2] UML Toolkit
Hans-Erik Eriksson, Magnus Penker
Wiley
Questo libro si fa particolarmente apprezzare per via del taglio pratico dello stesso. Illustra in modo semplice il linguaggio, attraverso numerosi esempi, limitando le digressioni di carattere teorico. Si suppone infatti, che coloro che si occupano di progettazione O.O. abbiano una certa familiarità con i relativi concetti. Chissà perché si ha la sensazione che non sia sempre così! Naturalmente, studiare libri che illustrano gli aspetti teorici dell’informatica, è sempre qualcosa più che auspicabile. È altresì vero però, che coloro che non hanno tempo da perdere, per la lettura di concetti arcinoti, gradiscono arrivare rapidamente al nocciolo. Ciò spesso equivale a strappare alle nottate lavorative ore preziose per il sonno.

[3] The Unified Modeling Language Reference Manual
Grady Booch, James Rumbaugh, Ivar Jacobson
Addison Wesley
Il commento da riportare per questo libro, noto per come “Rumbaugh’s book”, è sostanzialmente equivalente a quanto riportato per il primo. Esso però offre un livello di difficoltà decisamente inferiore, e pertanto dovrebbe essere più accessibile. Come suggerisce il nome, si tratta di un manuale, per cui ne rispetta la tipica struttura.

[4] Design Patterns: Elements of Reusable Object-Oriented Software
Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, Grady Booch
Addison Wesley.
Si tratta di un ottimo libro che bisogna assolutamente avere se si vuole lavorare nell’ambito della progettazione O.O. . I “pattern” riportati, forniscono un ottimo ausilio al processo di disegno del software. L’utilizzo del libro contribuisce ad aumentare la produttività, fornisce soluzioni chiare, efficienti e molto eleganti. La fase di disegno del software, spesso, si riduce ad individuare e personalizzare i “pattern” che risolvono la problematica specifica. Si è di fronte ad una nuova frontiera della progettazione O.O.: il riutilizzo di parti del progetto. L’unica pecca imputabile, è che i vari diagrammi non sempre rispettano il formalismo UML.

[5] www.omg.org
Si tratta del sito ufficiale del Object Managment Group.

[6] www.mokabyte.it, numero 34 (Ottobre 1999)
UML e lo sviluppo del software.

[7] www.mokabyte.it, numero 35 (Novembre 1999)
Use Case: l’analisi dei requisiti secondo l’U.M.L.

[8] www.mokabyte.it, numero 36 (Dicembre 1999)
Diagrammi delle classi e degli oggetti: proiezione statica della Design View.

[9] www.mokabyte.it, numero 37 (Gennaio 2000)
Proiezione statica della “Design View” parte seconda: esempi “celebri” di diagrammi delle classi..

[10] www.mokabyte.it, numero 38 (Febbraio 2000)
Proiezione dinamica della “Design View” prima parte diagrammi di interazione.