UNIVERSITÀ DEGLI STUDI DI TRIESTE

FACOLTÀ DI INGEGNERIACORSO DI LAUREA SPECIALISTICA IN INGEGNERIA

INFORMATICA

�IMPLEMENTAZIONE IN .NET DI UN FRAMEWORK PERL'ANALISI DI SISTEMI BIOLOGICI BASATO SULLA

PROGRAMMAZIONE CONCORRENTE CON VINCOLI.�

Laureando RelatoreDiego Banovaz prof. Luca Bortolussi

ANNO ACCADEMICO 2009 - 2010

Ringraziamenti

Scrivere i ringraziamenti di questa tesi è un passo importante, nel fare ilquale spero di non dimenticare nessuno.In primis vorrei ringraziare il mio relatore, Luca Bortolussi, per avermi ac-compagnato in questo viaggio verso la follia della durata di sei mesi. In molteoccasioni ha saputo spronarmi o fustigarmi per spingermi ad andare avanticon il lavoro. In particolar modo è a lui che si deve la stesura corretta dell'e-laborato; senza il suo intervento infatti non sempre avrei trovato la forza diriordinare quella che era una matassa intricata di idee `gettate su un foglio'.Voglio ringraziare poi la mia famiglia: mia madre Silvia, in arte Iena, laquale ha saputo insegnarmi con dolcezza e pugno di ferro che cosa signi�chiprendersi un impegno; mio padre Loris, meglio noto come Ba�o, che non hamai lesinato un gesto a�ettuoso o un incoraggiamento. Spero possano trarreda questa occasione almeno una parte dell'entusiasmo e della grati�cazioneche loro hanno sempre saputo darmi.Ringrazio poi mio fratello Daniele, o Menion, per avermi trasmesso innume-revoli passioni e ben pochi sani principi. Devo sicuramente a questa `guerradei venticinque anni' buona parte della mia formazione caratteriale. Azzar-dando che almeno un lettore su due abbia pensato `purtroppo', non possofare altro che far ricadere sul fratello malvagio la colpa.Il mio pensiero va poi ai miei Nonni, Alda, Cornelio, Danira e Giordano pergli insegnamenti che hanno saputo darmi nel corso degli anni e per quantodi buono mi hanno trasmesso.Un grande grazie va a Giordana, per avermi reso (e rendermi) ogni giornopiù felice. Un grazie per essere sempre al mio �anco, nei momenti belli e inquelli brutti.

Fine della pseudo-serietà.Un grazie di proporzioni bibliche va al Sig. Federico Morsut (quel de Gra-do!), per avermi accompagnato in tutto questo percorso di studi e non solo;per esser stato sempre ad ascoltare e sempre disponibile. Unico!Al Dott. Mr.P per l'amicizia di mille mila anni, dalla sabbionaia agli stiva-

i

letti di spritz!A m3kka, per aver implementato una List in Java e per le mille altre stupi-daggini che ci hanno portato a sghignazzare insieme.Al buon lelìn per le mille avventure a�rontate insieme (quando torniamo aNovalia?)A PoL, perchè i motivi da elencare sarebbero troppi.A ZaK, per essere una delle persone migliori che conosco.Grazie a tutti i fenomeni del DMI: dal furlanissimo Ghise, al karate-kid-spartano Alex, alla New Entry Luka, al buon vecchio Peo, al PortaNOT tr3,ad Alice e a tutti quelli che mi odieranno per essermeli dimenticati!Un grazie va anche a tutti i compagni di LAN della Tana: a kapa per ilfalsetto potente, a Spruss per le cene di Bio, a Spino per essere un camper,a Conza per la risata suina, a Defy per i rosik trascendentali, a Max perla fede nel Dark Cocumber, a Iccio per la perdita dell'olfatto, a Jack per itormentoni immancabili, a 0rka per l'Arroganza, a minivap per l'arroganza,a jockey per nominarmi tra le due e le trecento volte a LAN, a Diu per l'usoscorretto di qualunque Zombie a Left, a Kane per essersi beccato con gioiai miei Commando in CnC, a Baz per avermi fornito una scena alla Porky'sche di�cilmente dimenticherò, a Turbo per lo Strip CnC con la corriera disvedesi, a Tora per le sponte in ET, a Fil per la corretta fede nel sacro UTserale, a Sick perchè tutto è un GdR, a Pislner Urquel per l'UT in esecuzioneautomatica, a Angel per i quintali di gamberetti in salsa rosa, a Gandalf perl'utilizzo corretto della parole Bollione, a Pietro per aver involontariamenteassaggiato, a Toom per la risata contagiosa e letale, a Gibo per il wood rivelascritte idiote, a bubez per esser sempre più sfalcià, al Wolf per le Storie delLupo e alla sk0d3 per essere la prova vivente che una donna non può essereforte ad UT, per quanto ci provi.Ai miei cuginetti condividi-pasto/cartoni-inutili del pranzo dalla nonna, An-gelica e Davide (e ovviamente anche a Fede e Roby). A tutta la musica, inparticolar modo agli Opeth.Grazie anche agli Insanity Fair (Jo, Tati, Alf, Mauro) e agli Overtures (Meek,Dani, Luka, Cum, Guitty) per le tournè/viaggi e per le incredibili serate vis-sute insieme.Al Gippo (alias el Bomber) per le innumerevoli volte che mi ha lasciato vince-re a PES adducendo innumerevoli scuse improbabili, alla pazientissima Sarae al suo acerrimo nemico Rudy.A Niha, Maru, m3kka e Diu per la GdR experience in montagna.A butra, per i racconti dei Mig Russi e del cemento per el controllo climatico.A Nebbia, el Folpo, el Guru, Patachini e a tutti i compagni di carretto dellaSagra.Un grazie anche ai Bodri per tutte le Bodrate insieme: Hale, Ophy, Sara,

ii

Vale, Xander, Biz, Ushti, la ragazza di Ushti, Scano, Jessica, Marta, Mono,i ba� di Mono.Come da consuetudine i ringraziamenti son stati scritti 10 minuti prima dimandare in stampa la tesi, quindi saranno sicuramente carichi di mancanzee lacune.

iii

Indice

Ringraziamenti i

Introduzione vii

1 Nozioni Teoriche 11.1 Algebre di Processo . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Operazioni dei processi . . . . . . . . . . . . . . . . . . 11.1.2 CCP: Concurrent Constraint Programming . . . . . . . 4

1.2 Algebre di Processo Stocastiche . . . . . . . . . . . . . . . . . 81.3 sCCP: Stocastic Concurrent Constraint Programming . . . . . 8

1.3.1 Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.2 Constraint Store . . . . . . . . . . . . . . . . . . . . . 91.3.3 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . 101.3.4 Le potenzialità del sCCP . . . . . . . . . . . . . . . . 11

1.4 ITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.4.1 Limitazioni del linguaggio . . . . . . . . . . . . . . . . 131.4.2 Modello ITS . . . . . . . . . . . . . . . . . . . . . . . . 141.4.3 Le Variabili di Stato . . . . . . . . . . . . . . . . . . . 141.4.4 Transizioni . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 ODE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.5.1 Deterministicità del Linguaggio . . . . . . . . . . . . . 161.5.2 La de�nizione di ODE . . . . . . . . . . . . . . . . . . 16

2 Analisi e Progettazione 182.1 Analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.1 Analisi dei Requisiti . . . . . . . . . . . . . . . . . . . 182.1.2 Studio dei Casi d'Uso . . . . . . . . . . . . . . . . . . . 19

2.2 Progettazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2.1 Standardizzazione di Input ed Output . . . . . . . . . 212.2.2 I Macro Moduli . . . . . . . . . . . . . . . . . . . . . . 222.2.3 Il Compilatore . . . . . . . . . . . . . . . . . . . . . . . 23

iv

2.2.4 Runtime Manager . . . . . . . . . . . . . . . . . . . . . 242.2.5 Constraint Store . . . . . . . . . . . . . . . . . . . . . 252.2.6 De�nition Store . . . . . . . . . . . . . . . . . . . . . . 252.2.7 Interfaccia Gra�ca . . . . . . . . . . . . . . . . . . . . 26

3 Interfaccia 293.1 Installazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Il Codice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2.1 Il Codice SourceAM . . . . . . . . . . . . . . . . . . . 303.2.2 Il Codice SourceCS . . . . . . . . . . . . . . . . . . . . 32

3.3 La Simulazione . . . . . . . . . . . . . . . . . . . . . . . . . . 333.3.1 Graphic Simulator . . . . . . . . . . . . . . . . . . . . 333.3.2 Batch Simulator . . . . . . . . . . . . . . . . . . . . . . 35

4 Implementazione 374.1 Dettagli dell'Interfaccia Gra�ca . . . . . . . . . . . . . . . . . 374.2 SCCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2.1 Il Constraint Store . . . . . . . . . . . . . . . . . . . . 384.2.2 De�nition Store . . . . . . . . . . . . . . . . . . . . . . 474.2.3 Runtime Manager . . . . . . . . . . . . . . . . . . . . . 504.2.4 ParserCS . . . . . . . . . . . . . . . . . . . . . . . . . 514.2.5 ParserAM . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3 ITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.3.1 Constraint Store e De�nition Store . . . . . . . . . . . 554.3.2 Runtime Manager . . . . . . . . . . . . . . . . . . . . . 564.3.3 ParserCS e ParserAM . . . . . . . . . . . . . . . . . . 59

4.4 ODE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.4.1 ParserAM e ParserCS . . . . . . . . . . . . . . . . . . 604.4.2 Transition System . . . . . . . . . . . . . . . . . . . . . 60

5 Test 635.1 Esempio #1: client server . . . . . . . . . . . . . . . . . . . . 63

5.1.1 Analisi del problema . . . . . . . . . . . . . . . . . . . 635.1.2 Modello sCCP . . . . . . . . . . . . . . . . . . . . . . . 655.1.3 Analisi delle prestazioni . . . . . . . . . . . . . . . . . 66

5.2 Esempio #2: Lotka-Volterra . . . . . . . . . . . . . . . . . . . 675.2.1 Analisi del Sistema . . . . . . . . . . . . . . . . . . . . 675.2.2 Modello sCCP . . . . . . . . . . . . . . . . . . . . . . . 685.2.3 Analisi delle Prestazioni . . . . . . . . . . . . . . . . . 69

5.3 Esempio #3: Sintesi di Glucosio da Lattosio in E-Coli . . . . . 705.3.1 Analisi del Sistema . . . . . . . . . . . . . . . . . . . . 70

v

5.3.2 Modello sCCP . . . . . . . . . . . . . . . . . . . . . . . 715.3.3 Analisi delle Prestazioni . . . . . . . . . . . . . . . . . 73

5.4 Esempio 4: Numero elevato di Agenti . . . . . . . . . . . . . . 73

6 Conclusioni 75

Bibliogra�a 76

vi

Introduzione

La costruzione di modelli di alcuni aspetti della realtà è sempre stata untassello fondamentale del metodo di indagine scienti�co.Le tecniche di modellizzazione dei giorni nostri permettono di descrivere e ra-gionare su aspetti sempre più complessi del mondo. In questo la matematicae l'informatica hanno un ruolo fondamentale: la prima fornisce una corniceformale entro cui costruire dei modelli, la seconda mette a disposizione po-tenti strumenti computazionali per l'analisi.L'aumento della potenza computazionale e il miglioramento delle tecniche dianalisi non sono tuttavia su�cienti a rendere la modellizzazione matematicapervasiva anche nelle discipline scienti�che storicamente più descrittive (acausa della loro complessità), come la biologia.Costruire modelli formali e analizzarli a calcolatore sono attività complicateche richiedono nozioni approfondite di matematica ed informatica, oltre chenell'ambito speci�co del modello.Per queste ragioni oggigiorno c'è la tendenza a creare degli ambienti di svi-luppo integrato per la creazione ed analisi di modelli, che rendano questaattività accessibile anche a non specialisti. Sull'onda di questa evoluzionesi è deciso di a�rontare l'argomento di questa tesi: creare un ambiente disviluppo per SCCP, un linguaggio per la creazione di modelli ad agenti con-correnti ad evoluzione stocastica.Nel corso del progetto sono stati svolte le fasi di analisi, progettazione erealizzazione dello stesso e sono state portate tutte a termine: il frameworkadesso esiste e rispetta tutte le speci�che preventivate.Lo stesso è composto da un'interfaccia gra�ca che si interfaccia tramite XMLe CSV e tre compilatori diversi che sono stati scritti appositamente per ri-spondere a tre diverse esigenze.Nel primo capitolo tratteremo le nozioni teoriche che sono le fondamenta ne-cessarie per a�rontare il problema: si parlerà infatti di Algebre di Processo,Algebre di Processo Stocastiche e si daranno alcuni tratti sul lavoro svoltodai tre compilatori che sono stati creati.Nel secondo capitolo si a�ronteranno l'Analisi e la Progettazione del fra-

vii

mework: si partirà dalle basi teoriche esposte nel primo capitolo per proget-tare la visione funzionale dei moduli del progetto.Nel terzo capitolo si darà una visione esterna del progetto, si tratterà l'in-stallazione e l'utilizzo delle diverse componenti che formano il progetto.Nel quarto capitolo si guarderà più da vicino al progetto: si analizzeranno leclassi più importanti, si vedranno i punti di forza e di debolezza delle scelteoperate, e si vedranno a livello pratico la di�erenza tra i diversi compilatori.Il quinto capitolo sarà un'analisi prestazionale e funzionale del framework:si studieranno le prestazioni rispetto a diversi programmi SCCP, si confron-teranno le tempistiche e le performance dei diversi compilatori cercando ditrovare dei punti nei quali approfondire gli sforzi per migliorare il frameworkstesso.In�ne, nel sesto capitolo, si trarranno le conclusioni su quanto è stato fatto.L'intero codice è stato scritto dal tesista, eccezzion fatta per alcuni mo-duli di supporto esterno che verranno segnalati per la corretta valutazionedell'operato.

viii

1

1

Capitolo 1

Nozioni Teoriche

In questo capitolo verranno presentate sintetizzate le nozioni teoriche per lacomprensione dei capitoli successivi.Dapprima verranno presentate le algebre di processo come formalismo perla de�nizione di programmi ad agenti concorrenti. In seguito verrà espostoCCP, come esempio di linguaggio concorrente.Nelle sezioni seguenti si scenderà in dettaglio su sCCP e gli argomenti neces-sari per capire le tre semantiche a disposizione del framework.

1.1 Algebre di Processo

Le algebre di processo (in inglese, Process Algebras) sono un linguaggio for-male che permette di descrivere l'evoluzione parallela di più processi con leconseguenti modi�che del sistema stesso. Il formalismo prevede che l'evolu-zione segua tre regole principali:

1. I processi (chiamati anche Agenti) comunicano tra loro tramite mes-saggi (attraverso memoria condivisa)

2. La descrizione dei processi avviene tramite l'utilizzo di semplici primi-tive, composte per formare della azioni più complesse.

3. Viene de�nita un'algebra che imponga delle regole per gli operatori deiprocessi.

1.1.1 Operazioni dei processi

Secondo la teoria, ogni processo è composto dalla concatenazione di più azioniatomiche; nello speci�co queste sono:

1

1. Composizione in parallelo

2. Indicazione del canale per il trasferimento dati

3. Composizione sequenziale delle azioni atomiche

4. Restrizione di dati e comunicazioni

5. Scelta tra più possibili azioni

6. Chiamata ricorsiva ad un processo

7. Azione nulla

Nelle sottosezioni successive verrà spiegato il signi�cato di ognuna di questeoperazioni.

Composizione in Parallelo

Per indicare una composizione in parallelo viene utilizzato l'operatore ′′||′′.Un esempio può essere il seguente:

Agente1||Agente2

La semantica di questa azione è traducibile nell'istanziazione ed esecuzio-ne parallela degli agenti (equivalente a processo) indicati come Agente1 edAgente2. Sebbene possa sembrare limitante il parallelo de�nito in questomodo, basti pensare che uno dei due agenti composto da un altro paralleloper vedere che il numero di Agenti da istanziare in parallelo con una singolaazione è illimitato.

Comunicazione

La comunicazione è un azione atomica che permette a degli agenti di comuni-care tra loro. Si capisce subito come dei processi paralleli privi di possibilitàdi comunicare risultino di scarso interesse e per questo motivo ques'azione ècosì importante; solitamente vi sono due modi per due processi di comunicare:

• Tramite l'ausilio di variabili o aree di memoria condivise;

• Tramite il passaggio diretto di dati;

Il primo punto è autoesplicativo: basta dare libero accesso ad opportune areedi memoria ed il gioco è fatto.Per il secondo punto vanno invece de�niti il canale, il �usso di input e quello

2

di output.Generalmente si indica il �usso di input come x(~v) e il �usso di output comex〈~y〉(supponendo x il nome del canale, v il vettore di dati da ricevere e y il vettoreda spedire)A livello semantico l'elemento di input speci�ca che il processo è in attesa didati in arrivo, mentre l'elemento di output speci�ca che il processo è prontoa inviare sul canale i dati.

Composizione in sequenza

La composizione in sequenza permette di collegare nell'esecuzione un numeroinde�nito di azioni. Vediamo un semplice esempio della composizione delleazioni che abbiamo �n'ora visto.Supponiamo di voler descrivere un agente che attenda un parametro di in-gresso per poi istanziare due agenti (A1 e A3) in parallelo: Questo processopotrebbe venir descritto come:

x(~v).(A1(v)||A3(v))

Focalizzare dati / comunicazioni

Un processo può voler limitare il numero di connessioni che gli altri agentipossono aprire con lui: l'hiding gli permette di nascondere il canale di comu-nicazione (o variabile) ad altri agenti. In pratica l'agente fa il �wrapper� disé stesso e nasconde all'esterno parte dei suoi canali.

Scelta

La scelta permette ad un agente di scegliere in maniera non deterministical'azione da eseguire.L'operatore per la scelta è il +, un'esempio di utilizzo potrebbe essere:

P0 :- P1 + P2;

In questo caso, al momento dell'esecuzione di P0, questi sceglierà quale azioneinvocare.

3

Chiamate Ricorsive

Una chiamata ricorsiva prevede la possibilità di far si che un processo ese-gua sé stesso (o un altro processo), permettendo la costruzione di cicli e diesecuzioni illimitate/in�nite.

Azione nulla

L'azione nulla (indicata in innumerevoli modi, come nil, null, 0) fa terminareil processo che la invoca. Questa capacità viene utilizzata per terminareselettivamente un agente in determinate situazioni (sicchè non rimanga inmemoria ultimata la sua esecuzione).

1.1.2 CCP: Concurrent Constraint Programming

CCP è un linguaggio di programmazione a processi concorrenti basato suivincoli che sta alla base di sCCP. La di�erenza principale tra i due sta nellanon-deterministicità di CCP che si contrappone alla stocasticità di sCCP.Nelle prossime sezioni verranno presentate le componenti che contraddistin-guono il linguaggio.

Constraint Store

Il Constraint Store è la rappresentazione che CCP ha della memoria. In essole variabili non assumono un semplice valore, ma rappresentano un insiemedi valori che la variabile stessa può assumere.Questa de�nizione è più estesa rispetto quella di Von Neumann: permetteinfatti di associare alle variabili insiemi di valori, ma anche insiemi con unsolo elemento e quindi sono evidenti le maggiori potenzialità.È possibile accedere al Constraint Store attraverso due funzioni: Ask e Tell.Ask è una chiamata che pone una domanda al gestore della memoria, nellospeci�co gli chiede la validità di una formula.Tell invece impone un nuovo vincolo al sistema espresso come formula logicaal primo ordine.Si noti come i diversi Tell vadano ad inserire nuovi vincoli, senza in alcunmodo toccare quelli esistenti: questa condizione può portare facilmente al-l'inconsistenza del sistema, ma utilizzata nel modo corretto porta le variabiliad appartenere a dei domini di accettazione sempre più ristretti.È comprensibile allora il nome di questo linguaggio:

• Concurrent: deriva dalla presenza di Agenti in un ambiente conccoren-te;

4

• Constraint: deriva dall'utilizzo di una rappresentazione della memoriaa vincoli come il Constraint Store;

• Programming: indica che si tratta di un linguaggio di programmazione;

Identi�cate le componenti di base, si può procedere alla de�nizione dellagrammatica del linguaggio.

La Grammatica di CCP

Di seguito viene esposto la sintassi del linguaggio nella conveniente forma digrammatica.

Program ::= Declaration.Agente

Declaration ::= ε | Declaration.Declaration | p(x): −Agente

Azioni ::= ask(c) → tell(c)

Scelta ::= Azione.Agente | Scelta+ Scelta

Agente ::= 0 | Agente.Agente | Scelta | Agente ‖ Agente | ∃xAgente | p(x)

Tabella 1.1: La sintassi di CCP.

Programma Programma è il punto di partenza della grammatica, in CCPquesti è costituito dalle dichiarazioni degli agenti e dall'agente iniziale.

Declaration Le dichiarazioni possono essere una, più di una o anche nes-suna; si indicano con la forma:

NomeAgente (~v) : − Agente

Una dichiarazione rappresenta il prototipo di un Agente; contiene le diverseazioni che fanno parte del comportamento del processo stesso e le variabililocali che gli appartengono.

5

Azioni Le azioni che permettono di e�ettuare degli update condizionatidel Constraint Store. L'agente e�ettua gli Ask e i Tell al Constaint Store.Ricordiamo brevemente quali sono le azioni compiute da ask e tell:

• Ask(condizione) permette all'agente di domandare al Constraint Storela validità della condizione;

• Tell(condizione) permette all'agente di aggiungere al Constraint Storeil vincolo espresso in condizione;

Si veda l'esempio quì riportato per capire l'utilizzo delle guardie stesse.

if(x < 5) y = 9;

diventa:

ask(x < 5).tell(y = 9)

Si è deciso, sempre prendendo spunto da un'idea trovata in [1], di adot-tare la seguente scrittura per le guardie:

[ condizione → condizione ]

La semantica scelta impone di interpretare come Ask tutte el condizioneche stanno a destra dell'operatore → , mentre ciò che sta dopo viene inter-pretato come Tell.La condizione prima esposta:

ask(x < 5).tell(y = 9)

diventa:

[ x < 5 → y = 9 ]

Questa forma contratta non impone l'utilizzo di entrambe le azioni (Aske Tell), in quanto basta omettere le condizioni od utilizzare dei vincoli sem-pre veri:

[ true → t = 10 ]

Contratto per comodità in:

6

[ → t = 10]

Scelta La scelta permette di associare più azioni ad un solo agente.La scelta prevede, come si vede in grammatica, la distinzione tra le varieazioni separate da il segno +. Ogni elemento che forma una somma è costi-tuito da una guardia seguita da un'Agente.

Agente1 : − [x > 0 → y >= 0].Agente1()+ [x == 0 → (x <= 10) (y <= 0)].Agente1();

Questo è la de�nizione di un'Agente, operante sulle variabili globali x edy che compie le seguenti azioni:

Se x > 0, impongo un nuovo vincolo per cui y debba essere positiva;Se x == 0, impongo un nuovo vincolo per cui x debba essere minore ugualea 10.

Quando viene chiesto di eseguire ad un agente, questi sà quali sono le guardiesono vere (con Ask true) e quali no: eseguirà solo le azioni corrispondentialle prime.Si noti come in questo particolare esempio l'agente ha sempre e solo una solaazione da eseguire: non è possibile infatti che entrambi le azioni superino leguardie perchè presupporrebbe che nello stesso istante x sia maggiore a 0 eanche uguale a 0. Nel caso più guardie siano attive contemporaneamente, lascelta viene e�ettuata in modo non-deterministico.

Agente L'agente è la parte centrale non solo della grammatica, ma dellinguaggio in generale: formato da azioni e variabili locale è l'elemento sottoosservazione da parte della simulazione. Un'Agente è formalmente compostoda agenti, guardie e scelte che a loro volta vengono composte per ottenere laforma dello stesso da noi voluta. Un esempio di Declaration potrebbe essere:

P (x = 0) : − [true → x >= 0].( P2() || P3() ) + P4();

Questa viene interpretata come:

Declaration -> Scelta tra (Guardia seguita da parallelo e chiamata P4)

7

1.2 Algebre di Processo Stocastiche

Nel corso delle prossime sottosezioni verrà analizzato un ambiente in cui,dato lo stato della memoria e l'indice dell'istruzione non è possibile sapere ilrisultato che questa avrà, ma al massimo si potrà fare delle stime su questovalore.

1.3 sCCP: Stocastic Concurrent Constraint Pro-

gramming

sCCP è un linguaggio per la descrizione di modelli in cui agenti interagisconotra loro e con l'ambiente in modo concorrente; inoltre questa interazione ègovernata da leggi probabilistiche.sCCP è un'estensione stocastica di CCP e da esso eredita le peculiarità fon-damentali: il Constraint Store e gli Agenti. Questo linguaggio prevede lacomunicazione tra agenti come asincrona, ottenuta tramite l'utilizzo di va-riabili globali condivise. sCCP è strutturato in modo da avere tutte le azioniviste prima: scelta non deterministica, composizione in parallelo, chiamataricorsiva e in più la dichiarazione di variabili locali.L'evoluzione temporale di sCCP è profondamente legata alle catene di Mar-kov Tempo Continue, come spiegato in [1]. In questa sezione analizzeremo illinguaggio e ne studieremo le di�erenze con CCP.

1.3.1 Rate

Ad ogni azione interagente con il Constraint Store, viene associato un valore∈ <+ che rappresenta il Rate. Il Rate è il prametro di una distribuzione diprobabilità esponenziale che descrive il tempo che l'azione impiega a venireeseguita. Ad ogni passo si veri�ca una Race Condition tra le diverse azioniattive: verrà eseguita quella che impiega il tempo minore. Questa evoluzionesi può descrivere (dal punto di vista matematico) equivalentemente tramitela scelta di un azione con probabilità proporzionale al rate, aumentando iltempo secondo una distribuzione di probabilità esponenziale con Rate Tota-le. Quest'ultimo si può calcolare come:{

Rate(A) =∑π∈ActionsGπ(i) ∗ λπ

RateTotale =∑A∈ActiveAgentsRate(A)

Si evince che la probabilità di esecuzione di un Agente è:

8

P (A) = Rate(a)RateTotale

In queste formule:

• λπ : CS → <+ è il Rate dell'azione è dipendente dallo stato correntedel Constraint Store.

• G(i) : CS → 0, 1 rappresenta un valore booleano associato allaguardia: 1 se la condizione in Ask è vera, 0 se non lo è.

Lo scorrere del tempo, viene quindi calcolato come:

Tempo = Tempo + ∆T

∆T = −1/T ∗ logU (con U distribuzione uniforme di probabilità tra 0 e 1)

Azioni a Rate In�nito

sCCP prevede la possibilità di avere delle azioni con Rate in�nito. Questeazioni vengono chiamate Azioni Istantanee ed hanno le seguenti peculiarità:

• Non incrementano il tempo. (∆T = 0)

• Vengono eseguite prima di ogni azione stocastica.

1.3.2 Constraint Store

Essendo un derivato diretto di CCP, anche sCCP ha un suo Constraint Sto-re. Per aggiungere potenzialità al linguaggio, sono state aggiunte le StreamVariables, come de�nite in [1]. In applicazioni di biologia o chimica, spessole variabili devono poter cambiare il loro valore, non solo l'insieme dei valoriche vi si possono attribuire.Nel sequente esempio si capisce i limiti imposti da una struttura senza StreamVariables:

[true-> X=5]

[true-> X=X+1]

Questa istruzione porta ad uno stato inconsistente. Per questo motivo è statopensato il sistema delle Stream Variables: associando ad ogni variabile unalista (in particolare con variabile in coda non istanziata) possiamo aggiungerein coda i nuovi valori. Nel momento in cui ci si trovi a volere il valore di quelladata variabile, basterà guardare il valore in coda, ma la presenza all'internodi essa di tutta la sua storia non viola il resto della teoria. In tutto il restodell'elaborato, nelle situazioni in cui si trova una scrittura del tipo:

9

[true -> x=x+1]

Questa farà riferimento all'aggiunta del valore sulla destra nella lista de�nitadal nome che compare sulla sinistra. Nell'approfondimento pratico vedremocome questa gestione teorica può essere implementata con un sistema divariabile standard a singolo valore.

1.3.3 Grammatica

Program = Declaration.Agente

Declaration = ε | Declaration.Declaration | p(x) : −Agente

Agente = 0 | [→ U]@∞.Agente | Scelta | ∃xAgente | Agente ‖ AgenteScelta = π.Guardia | Scelta+ Scelta

π = [G→ U]@λ | [G→ U]@∞Guardia = 0 | tell∞(c).Guardia | p(y) | Scelta | ∃xGuardia | Guardia ‖ Guardia

Tabella 1.2: Sintassi del sCCP.

L'sCCP ha una diversa grammatica per descriverlo, in cui la di�erenzaprincipale sta nell'assegnazione dei valori di Rate. Oltre a ciò si vede comeogni azione debba avere un peso e, essendo questo vincolato alle guardie, ogniazione deve iniziare con una guardia. Un possibile esempio potrebbe essereil seguente (dove @ è seguito dal Rate):

Agente1 : - [X<=0->X=X+1]@{5}.Agente1() +[X>3->X=X-5]@{3}.Agente1();

Agente2 : - [X>0 ->X=X*2]@{1/X}.Agente2();

Agente1 || Agente2

Analizziamo brevemente questo esempio, supponendo il valore iniziale di Xsia 0.

10

STEP X RATE AZIONE0 0 5 X = X + 11 1 1 X = X ∗ 22 2 0.5 X = X ∗ 23 4 3.25 X = X − 54 -1 5 X = X + 15 0 5 X = X + 1

Per quanto quasi tutti i punti siano deterministici (in questo esempio ad hoc)al punto 3 è stata e�ettuata una scelta. Nello speci�co le azioni attive erano:

a)[X>3->X=X-5]@{3}b)[X>0 ->X=X*2]@{1/X}

Nello speci�co è stata fatta una scelta a favore della prima azione per motivistatistici:

p(a)= 33.25

p(b)= 0.253.25

Ovviamente poteva anche accadere il contrario e avremmo raggiunto unoSTEP 4 con X pari a 8 e Rate totale pari a 3.125. A questo punto nuova-mente si sarebbe e�ettuata una scelta, aggiornata con i nuovi valori di Rate.

p(a)= 33.125

p(b)= 0.1253.125

Questo banalissimo esempio mostra un'oscillazione controllata del valore diX.

1.3.4 Le potenzialità del sCCP

Da questo esempio si desume la versatilità del sistema e la possibilità di im-plementare praticamente ogni tipo di algoritmo: si pensi per un attimo allamacchina URM, gemella di quella Turing, e alle 4 operazioni da essa imple-mentate.

sCCP ha tutte le potenzialità della macchina URM, e quindi di

quella di Turing.

Dimostrazione: Per prima cosa l'enumerabilità dei registri: nella mac-china URM questi sono in�niti ma, lo sono anche in questo caso, in quantole variabili sono le produzioni ottenibili da una grammatica del tipo:

11

S : lettera S | εEd essendo un in�nito numerabile posso associare a ciascuna variabile chegenero un numero intero che diventerà il numero del registro della macchinaURM.Le operazioni della macchina teorica URM sono:

1. Z(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM azzera ilregistro n, lasciando gli altri registri inalterati: rn := 0.

2. S(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM aumen-ta il contenuto del registro n di una unità, lasciando gli altri registriinalterati, rn := rn + 1.

3. T (m,n), m,n=1, 2, 3, ... . In risposta a questa istruzione la URMtrasferisce il contenuto del registro m nel registro n, tutti gli altri registricompreso Rm rimangono inalterati, rn := rm.

4. J(m,n, q), m,n,q=1, 2, 3, ... .In risposta a questa istruzione la URMconfronta il contenuto dei registri rm ed rn se: rm 6= rn allora con-tinua con l'istruzione successiva nel programma, rm = rn allora saltaall'istruzione q nel programma. Si vede subito allora che (supponendox = rn e y = rm)

1. Z(n) Azzeramento → [true -> x = 0]

2. S(n) Incremento → [true -> x = x+ 1]

3. T(m,n) Scambio → [true -> x = y]

4. J(m,n,q) Salto Condizionato → [x == y -> true].IstrQ + [x! = y ->true]

Per aiutare a capire la dimostrazione in altro modo, è possibile esaminare unalgoritmo scritto in questo modo:Agente1:- [x == 0 -> x = x+ 1]@1 . Istruzione + [x == 1 -> x = x+ 1]@1.IstruzioneAgente2:- [x == 2 -> x = x+ 1]@1 . Istruzione + . . .In questo caso il valore di x determina in maniera deterministica quale azio-ne verrà eseguita: l'unica azione con la guardia attiva, infatti, sarà quellaeseguibile. Si può fare un paragone tra la variabile x di questo esempio el'Istruction Pointer di un normale calcolatore: agendo su questa otterremodei salti verso altre azioni.

12

Quindi, avendo veri�cato questo possiamo asserire che :

Eseguendo sCCP tutte le azioni della macchina URM può, co-

me CCP, per la Tesi di Church-Turing computare ogni funzione

computabile.

1.4 ITS

ITS è la seconda semantica di sCCP che è stata implementata. In questasezione ne analizzeremo le qualità e i limiti che, dal punto di vista teorico,ci han permesso di crearla. Dapprima vedremo le limitazioni del linguaggio,analizzando poi variabili di stato, transizioni e in�ne un esempio. È neces-sario ricordare che si vuole giungere ad una simulazione di tipo stocastico.Dell'argomento viene data una trattazione super�ciale, per approfondimentisi rimanda a [5].Il procedimento che si è a�rontato prevede la creazione di una nuova seman-tica per il nostro sorgente sCCP, in modo da descrivere in un altro modo ilmodello descritto nel sorgente stesso. In questo caso si tratta di una visioneche passa dalla visione ad �agenti� ad una visione a transizioni. Le tran-sizioni, de�nite formalmente nella sezione speci�ca, rappresentano in suntoun passo eseguibile dal sistema per andare da uno stato ad un altro stato.Nello speci�co possiamo creare una transizione partendo da qualunque dellenostre azioni. Va ricordato che, non essendoci le variabili locali, ogni agenteè uguale a qualunque altro agente che implementi la stessa de�nizione. Perdescrivere e�cientemente il sistema, si introducono le State Variables.

1.4.1 Limitazioni del linguaggio

Per poter funzionare il sistema a Transizioni il codice deve sottostare aiseguenti vincoli:

• Non può essere utilizzata la composizione in parallelo nelle de�nizioni,ma solo per de�nire lo stato iniziale.

• Non esistono azioni istantanee (con Rate in�nito).

• Ogni azione è nella forma [Ask− > Tell]@{Rate}.Agente.

• Gli Agenti non posseggono variabili locali.

Queste condizioni portano a:

1. Il numero di Agenti è costante.

13

2. Ogni Agente del tipo A è uguale ad ogni altro Agente del tipo A.

3. Ogni passaggio di variabili è fatto per riferimento.

Queste due asserzioni sono fondamentali ai �ni pratici. Alla prima vi si arrivatramite un procedimento molto semplice ed intuitivo. Siamo nella situazionein cui:

• Ho N Agenti iniziali dati dallo stato iniziale.

• Non ho composizione parallela all'interno della de�nizione degli agen-ti(N non può crescere).

• Ogni azione è della forma [ Ask → Tell]@{Rate}.Agente, quindi ilnumero di Agenti non può calare.

In generale, queste proprietà, specie l'assenza di variabili locali, garantisconoche le variabili di stato siano una descrizione corretta dello stato del modellosCCP.

1.4.2 Modello ITS

Un modello ITS viene dato da una tupla ITS = (X,S, T )Dove:

• X è l'insieme costituito dalle variabili globali

• S è l'insieme delle variabili di stato

• T è l'insieme delle transizioni

Le Variabili Globali sono le stesse viste per sCCP.

1.4.3 Le Variabili di Stato

Indicate con la lettera S nella de�nizione del sistema, le variabili di statopermettono di descrivere e di gestire in maniera e�ciente lo stato delle tran-sizioni del sistema. Ogni variabile di stato è associata ad una de�nizione diun agente, e descrive il numero di agenti di quel tipo attualmente attivi nelsistema. Di questa de�nizione, rappresenta il numero di agenti attivi che larappresentano. Il valore di una State Variable è dunque sempre un numeronaturale.Ogni update delle transizioni sCCP dovrà essere modi�cato per descrivereanche l'aggiornamento delle variabili di stato. Ad esempio:

14

A1 : − [ X < 0→ X = X + 1]@{k}.A2

diventa:

[ X < 0→ X = X + 1;SV 1 = SV − 1;SV 2 = SV + 1]@{k}

Incrementare una variabile di stato equivale dunque ad aggiungere un agentedel tipo associato al sistema stesso. Decrementarla equivale ad eliminarneuno.Supponiamo di avere il seguente agente A1 precedentemente descritto. Laguardia sarà passabile se:

X > 0 ∧ SV 1 > 0

E il rate dato dagli agenti dello stesso tipo sarà:

A1λ = SV 1 ∗ k

In altri termini, la prima formula impone che se il numero di Agenti è pari a0, nessuna azione è eseguibile. La seconda fa si che il Rate dato da tutti gliagenti di un tipo sia pari al numero di essi moltiplicato per il rate del singolo.

1.4.4 Transizioni

De�niamo ora le transizioni:

T = (nome, guardia, update, rate)πi := [guardia(X)− > update(X)]@λguardia(X) è passabile ⇔SVi > 0 ∧ Ask(G(X)) == trueupdate(X) = update(X)sCCP, SVi = SVi − 1, SVj = SVj + 1

In altri termini:La guardia è espressa come la guardia di sCCP solo che presenta un vincolodi positività sulla variabile di stato associata.L'update è uguale all'update visto in sCCP ma aggiorna anche lo stato delleState Variables. Vedendo un esempio:

A1 : −[X > 0→ X = X − 1]@{k1}.A2 + [X > 10→ X = 0]@{k2}.A1;A2 : −[true→ X = X + 1]@{k1}.A1;SI : A1

15

Questo sistema, viene convertito in:

t1 = [SV 1 > 0 ∧ X > 0− > X = X − 1;SV 1 = SV 1 − 1;SV 2 =SV 2 + 1]@{k1}t2 = [SV 1 > 0 ∧X > 10− > X = 0; ]@{k2}t3 = [SV 2 > 0∧true− > X = X+1;SV 2 = SV 2−1;SV 1 = SV 1+1]@{k1}

Nell'esempio t2 non tocca le SV perchè incrementerebbe e decrementereb-be la stessa variable.È evidente come una tale forma racchiude tutte le informazioni necessarieper un algoritmo che voglia simulare l'andamento del sistema descritto dalsorgente sCCP ridotto.

1.5 ODE

Con ODE si indicano le Equazioni Di�erenziali Ordinarie ed è proprio daqueste che prende il nome il compilatore di tipo ODE. In questa sezione siesporrà brevemente il collegamento tra ITS ed ODE. Verrà esposto come,sotto opportune ipotesi, sia possibile passare da un sistema di tipo ITS adun sistema di equazioni di�erenziali. Un approfondito studio dell'argomentosi può trovare in [5].

1.5.1 Deterministicità del Linguaggio

Questa semantica per sCCP non presenta evoluzione stocastica: l'evoluzionetemporale è determinata solo dalle equazioni di�erenziali associate al sistemascritto in forma di sCCP ridotto. Questo è un ulteriore vincolo sul sistemastesso.

1.5.2 La de�nizione di ODE

Come visto per sCCP e per ITS, si è dovuto de�nire in termini formali ilsistema. Nello speci�co, assumiamo che le transizioni del sistema siano dellaseguente forma:

τ ∈ T , τ = (guardτ (x, s), X′ = X + k, S ′ = S + h, fτ (X,S))

k rappresenta l'aggiornamento delle variabili globali, il vettore h rappresenta

16

l'aggiornamento delle variabili di stato:

k=

{ki ∈ R, se i è aggiornata esplicitamente0, altrimenti

h=

{hi ∈ R, se i è aggiornata esplicitamente0, altrimenti

Si noti come richiediamo che gli update siano di una forma particolare, ov-verro incrementi/decrementi delle variabili con quantità costanti. Da questade�nizione si ottiene il seguente sistema di ODE:{

X =∑τ∈T kτgτ (X,S)fτ (X,S)

S =∑τ∈T hτgτ (X,Sfτ (X,S)

Dove X, S, h e k sono vettori.In pratica, dal sorgente si deriva una de�nizione sintattica del sistema diequazioni di�erenziali. Questo ha delle relazioni con il sistema stocasticoassociabile allo stesso sorgente, per una discussione su questa relazione sirimanda a [5]. Un programma sCCP che soddis� i vincoli di cui sopra, puòessere visto come una descrizione di alto livello di un sistema di ODE.

17

Capitolo 2

Analisi e Progettazione

In questo capitolo verranno analizzate le fasi di Analisi e di Progettazionesvolte per creare il progetto oggetto di questa tesi.Nella prima sezione è stato analizzato il problema, partendo dai requisitifunzionali.Nella seconda sezione sono state progettate le componenti per rispondere airequisiti.

2.1 Analisi

Nel Capitolo 1 si sono viste le nozioni teoriche riguardanti sCCP e le duevarianti ITS e ODE.Il progetto che si vuole creare, per l'appunto, consiste nell'implementazionedi sCCP nella maniera più versatile e più completa possibile, con un occhiorivolto all'e�cienza.Il progetto è stato sviluppato in ambiente .NET, in particolare è stata uti-lizzata la versione 4.0 del framework Microsoft. Le interfacce gra�che sonostate sviluppate in Windows Presentation Foundation (WPF).

2.1.1 Analisi dei Requisiti

È stato necessario interpellarsi sulle funzionalità necessarie al �ne di creareil framework. È facile immaginare che il requisito fondamentale sia quello dicomprendere codice di tipo sCCP: oltre a ciò è necessario che ne permettala simulazione in maniera integrata. Dato un codice, quindi, vogliamo ave-re come riscontro dei dati sotto forma di gra�co o memorizzati in manieracompatibile con la maggior parte dei sistemi di analisi dati. È stato deciso

18

inoltre di permettere all'utente di poter simulare passo passo per compren-dere l'andamento non solo in chiave temporale, ma anche in chiave di stepesecutivi.Si è voluto fornire anche un'interfaccia per la stesura del codice ma, nel con-tempo, si è voluto far in modo che non fosse l'unica interfaccia possibile inmodo da permettere di accedere alle funzionalità del codice anche da altreGUI scritte in futuro.Un requisito fondamentale che è stato scelto è la creazione del ConstraintStore on demand: partendo da un sorgente contenente le informazioni perindicare le proprie speci�che, il framework dovrà essere in grado di modellareun oggetto che le implementi nella maniera migliore.L'interfaccia gra�ca deve permettere di salvare e riprendere in seguito il la-voro che si sta a�rontando. Oltre a questo deve permettere di impostare deicriteri di arresto dell'esecuzione (raggiungimento temporale o raggiugimentoin passi).Deve esistere un'interfaccia simulativa di tipo batch che può gestire grandicarichi di lavoro in maniera e�ciente e gestire la simulazione con variazionedei parametri iniziali automatica.Oltre a ciò è necessario rendere il sistema in grado di utilizzare diversi tipidi compilatori in modo da dare all'utente la possibilità di utilizzare sia ITSche ODE.Quanto detto si può riassumere nei seguenti punti:

• Il framework deve tradurre del codice scritto in sCCP, comprenderlo esimularlo.

• Il framework deve fornire un'interfaccia all'utente in maniera da met-tere a disposizione tutte le sue funzionalità.

• Il framework deve fornire un'interfaccia ad altri programmi in manierada mettere a disposizione tutte le sue funzionalità.

• Il framework deve generare un'output gra�co o numerico compatibilecon gli altri standard.

• Il framework deve essere capace di creare un Constraint Store speci�coche risponda alle esigenze di ogni applicazione.

• Il framework deve poter gestire anche codice ITS e ODE.

2.1.2 Studio dei Casi d'Uso

Una volta analizzato il problema è stato de�nito il diagramma degli Use Case.Si è visto, da quanto scritto sopra, che gli unici attori presenti sono:

19

• Utente

• Altri Software

Da quanto visto sopra, possiamo riassumere le attività che l'utente può farein:

• Scrivere il sorgente (salvare, caricare, compilarlo)

• Scegliere il compilatore

• Avviare la simulazione (gra�ca o batch)

• Raccogliere i risultati

Mentre gli eventuali altri software dovranno poter:

• Scegliere il compilatore

• Avviare la simulazione (gra�ca o batch)

• Raccogliere i risultati

Da questa prima analisi si arriva al gra�co in �gura nella pagina successiva.

2.2 Progettazione

Ultimata la fase di analisi si è passati a quella di progettazione. In primis,come illustrato nelle successivo sezioni, si è progettata la parte simulativa.Nell'a�rontare l'argomento si è dovuto tener conto della possibilità di volerscrivere altre IDE per i compilatori e di poter avere più compilatori per lastessa IDE. Oltre a questo è stato necessario utilizzare un sistema standardper l'output dei dati.Per riuscire a mantenere il massimo distacco tra le componenti, si è decisodi utilizzare delle interfacce per sottolineare i punti di contatto. In questomodo se qualcuno dovesse volere riscrivere una parte del programma, nondeve far altro che reimplementare l'interfaccia associata.È stato fondamentale dividere il codice sorgente dell'utente in due blocchi di-stinti: una parte va a de�nire la con�gurazione degli agenti (compresi agentiiniziali, de�nizioni agenti, ecc.) detta SourceAM, mentre l'altra serve a mo-dellare il Constraint Store come l'utente desidera (variabili globali, funzioni,constraints, parametri, operatori ... ) detta SourceCS.

20

Use Cases Diagram

2.2.1 Standardizzazione di Input ed Output

Si è fortemente cercata l'indipendenza delle parti su tutti i fronti, per questosi è deciso di utilizzare degli standard già a�ermati per gestire input ed out-put. Principalmente si doveva rendere compatibile con future espansioni evarianti l'input (rappresentato per la maggior parte dai sorgenti) e l'output(i dati di risposta della simulazione).Per modellare l'input serviva un linguaggio in grado di esser modellato per lenostre esigenze e che fosse di semplice lettura: per questo motivo si è sceltoXML. Essendo molto utilizzato, un domani chiunque potrebbe creare un'in-terfaccia gra�ca diversa che generi il codice XML da fornire al compilatoresenza grossi sforzi. Un domani uno sviluppatore potrebbe voler creare unaIDE completamente gra�ca in cui l'utente non debba scrivere una sola lineadi codice: grazie all'utilizzo di XML non necessiterà di alcun parser o vali-datore se non il DTD stesso dei �le XML utilizzati.Per la veri�ca della correttezza sintattica dei �le XML sono stati creati dei

21

�les DTD apposta. L'utilizzo di questo sistema ha portato ad una sempli-�cazione anche nella creazione dei compilatori stessi: ogni compilatore avràun suo DTD per analizzare il codice così creato.Per quanto concerne l'output si è scelto per un formato molto leggero eduniversale: il CSV (comma separated values). Questo formato è compatibilecon moltissimi programmi di analisi dati (come Mathlab o Excell) ed è prati-camente un plain text e quindi leggibile anche con un qualunque text editor(esattamente come XML).

2.2.2 I Macro Moduli

Per creare questo progetto è stato necessario utilizzare un approccio di tipoTop-Down in cui si è iniziato immaginando dei macro blocchi che poi sonoandati a de�nirsi mano a mano che si scendeva nel dettaglio. Fin dal prin-cipio si sapeva che dovevano esistere delle classi che assolvessero ai seguenticompiti:

• Interfaccia Gra�ca di Scrittura del Codice (Parser GUI)

• Parser da linguaggio a XML per il SourceCS

• Parser da linguaggio a XML per il SourceAM

• Interfaccia Gra�ca per la simulazione gra�ca in tempo reale

• Interfaccia Gra�ca per la simulazione Batch

• Classi di scambio parametri di compilazione

• Compilatore

Con la con�gurazione esposta in �gura un utente può utilizzare il progettoin più modi:

• Utilizzare tutto il progetto, dal Parser GUI per la stesura al compilatoreper simulare

• Utilizzare un proprio Editor e passare il codice per la simulazioneGra�ca / Batch alle due classi predisposte

• Utilizzare solo il compilatore lasciando poi il proprio software a gestirei dati in input e output

22

Figura 2.1: Primo Approccio Progettuale

2.2.3 Il Compilatore

Il Compilatore in questo progetto non è unico e non perchè si è scelto dicrearne più del dovuto, ma perchè ogni Compilatore deve comprendere unparticolare tipo di codice.Avendo di base due tipi di codice, uno scritto per la de�nizione degli agentie l'altro per la de�nizione del Constraint Store, è evidente che ci dovrannoessere un modulo per comprendere l'uno e un per comprendere l'altro. Avre-mo quindi, in generale, una suddivisione tra Parser per SourceAM e uno perSourceCS.È comprensibile come un codice scritto per il Parser X non necessariamentedebba funzionare per il Parser Y, ma la divisione in queste due categorieserve per avere dei risultati comuni.Ad esempio da un Parser per il SourceCS (ParserCS) ritornerà sempre uncontenitore con variabili, funzioni, constraint e quant'altro; allo stesso modoun Parser per il SourceAM (ParserAM) ritornerà sempre un elenco di de�ni-zioni di Agenti ed uno stato iniziale.Avendo scelto di utilizzare in ingresso dei codici XML, i Parser non hannobisogno di librerie particolari per produrre il risultato ma gli basta saperanalizzare un �le XML.Va rispettato un vincolo: ParserCS deve eseguire sempre prima di Parse-rAM. La motivazione è molto semplice: ParserAM ha bisogno di sapere chisono le variabili, chi i constraint, chi le funzioni e quant'altro per poter fare

23

correttamente il proprio lavoro.ParserAM conosce in questo modo i dati per la de�nizione del nuovo Con-straint Store; oltre a questo gli vengono forniti gli indirizzi dei RuntimeMa-nager appena istanziati in modo da dare loro i risultati da esso prodotti.

2.2.4 Runtime Manager

Come ParserAM e ParserCS svolgono le funzioni di comprensione del sor-gente, il Runtime Manager svolge quelle di simulatore. Esso infatti conosce,grazie a ParserAM, tutte le de�nizioni sia in termini di Agenti che del Con-straint Store.Viene istanziato fornendogli semplicemente i criteri di arresto (durata tem-porale λ o numero di passi). Un Runtime Manager espone (principalmente)le seguenti funzioni:

• Start - Inizia la simulazione

• Stop - Interrompe la simulazione

• Step - E�ettua un passo della simulazione

• GetGraphData - Fornisce tutti i dati relativi alle variabili ed al loroandamento temporale

• GetGlobalVars - Fornisce il valore attuale della variabili globali

• GetStatus - Fornisce un riassunto di Agenti Attivi, ultime azioni ese-guite, rate, ecc.

Come è evidente il Runtime Manager è in tutto e per tutto il cuore del pro-getto: tutte le altre parti non sono che moduli che permettono l'interazionecon esso.Una volta dato il comando Start, questo simulerà �nchè non gli viene datolo Stop o soddisfa le condizioni di terminazione.Analizzando il linguaggio sCCP ci si è resi conto che un simulatore benstrutturato deve esser dotato di due elementi:

• Il Constraint Store

• Il De�nition Store

24

2.2.5 Constraint Store

Il Constraint Store (CS) sarà la memoria del nostro sistema. In esso cisaranno le variabili e vi si accederà tramite gli Ask e i Tell. Oltre a ciòdobbiamo poter richiedere al CS di ritornare il risultato di una formula:questo viene usato per il calcolo dei Rate. Un'altra funzionalità è quella diritornare lo stato di tutte le variabili in un operazione sola. Al CS viene datoanche il compito di modi�care, se necessario, le formule lette dai Parser.Ricapitolando:

• Ask

• Tell

• GetRate

• GetVariables

• Parse

2.2.6 De�nition Store

Il De�nition Store è il gestore delle de�nizioni di agenti. Deve aiutare lafase di Parsing del SourceAM e deve fornire al RuntimeManager gli agentirichiesti. È unico per ogni Runtime Manager. I requisiti che deve soddisfaresono:

• Creare una de�nizione

• Creare un'azione per una de�nizione

• Fornire le istanze delle de�nizioni

Vista la de�nizione degli agenti, si è deciso di progettare la singola de�nizionepartendo dalle seguenti considerazioni:

• Ogni Agente ha più scelte

• Ogni scelta ha una o più azioni

• Ogni azione può essere composta da una o più azioni atomiche

Per gestire questa condizione si è pensato al seguente sistema. Ogni Agenteha una scelta tra le possibili azioni. Ogni serie di azioni composte in sequenzasono gestite da un Action Manager. Le azioni implementano tutte la stessainterfaccia che espone molti metodi, tra cui quello per l'esecuzione dell'azionee quello per ricevere il Rate dell'azione stessa.Vediamo ora un esempio sulla gestione dell'azione:

25

Agente :- [X > 0 -> X = X-1]@{1}.Agente

+ [X == 0 -> X = 10]@{1}.([ -> Y= Y + 1]@{1}.Agente || Agente + Agente);

Questa struttura viene dapprima spezzata in due:

[X > 0 -> X = X-1]@{1}.Agente

[X == 0 -> X = 10]@{1}.([ -> Y= Y + 1]@{1}. Agente || Agente + Agente);

La prima azione ora diventa:

ActionManager -> [Guardia][Call]

La seconda invece diventa:

ActionManager -> [Guardia][Scelta]

[Scelta] -> ActionManager -> [Guardia][Parallelo([Call][Call])

-> ActionManager -> [Call]

In pratica un ActionManager è una lista di Azioni collegate dalla Composi-zione in Sequenza: quando il Parser individua una scelta aggiunge in codaun'elemento Scelta, il quale avrà i suoi ActionManager per gestire le biforca-zioni.In questo modo si gestiscono le azioni come fossero un albero, in manierae�ciente e assolutamente non rigida.In �gura un diagramma approssimato ma riassuntivo.

2.2.7 Interfaccia Gra�ca

È stato fondamentale progettare da subito anche l'interfaccia gra�ca: graziead un'approfondita analisi delle funzionalità che si volevano esporre si è riu-sciti ad apportare modi�che anche ai diagrammi delle classi che formano ilCore.Per prima cosa è il caso di dividere l'interfaccia gra�ca in tre blocchi distinti:

• GUI per la scrittura del codice

• GUI per la simulazione in tempo reale

• GUI per la simulazione Batch

26

Figura 2.2: Rappresentazione concettuale delle classi

Parser GUI

Questa WPF Window è stata progettata per essere il più semplice possibile.Divisa in due parti in cui scrivere il SourceAM e il SourceCS, o�re le funzionidi base (salva, carica, nuovo, esci) a�ancate dalla possibilità di compilare(AM, CS, Entrambi), di scegliere il compilatore (sCCP, ITS, ODE) e in�nela possibilità di lanciare la simulazione (Gra�ca o Batch).Nel capitolo 3 vedremo un esempio pratico con tanto di immagini prese dalprogramma.

Graphic Simulation GUI

Questa interfaccia si compone di tre �nestre distinte che vengono mostrateuna di seguito all'altra.Nella prima si è progettato che venga data la possibilità di scegliere i para-metri di arresto, i �le XML da caricare (SourceAM e SourceCS, impostatidal Parser GUI con i giusti valori), la precisione del gra�co e il numero disimulazioni parallele.Nella seconda �nestra è stata data la possibilità di scegliere i dettagli delgra�co: si possono scegliere le variabili da analizzare mostrandole tracciate,di quali variabili mostrare la media, di quali la varianza. Per ogni linea datracciare si può scegliere il colore e la didascalia.Avendo concentrato le scelte prima dell'esecuzione, l'ultima �nestra è quasi

27

completamente dedicata al gra�co. Si sono volute mostrare anche le variabilicon i loro valori e gli agenti in vita, ma la maggior parte dello schermo è presadal gra�co. Questa �nestra si è pensato debba avere funzionalità interattive(permettndo di iniziare o fermare la simulazione o di fare un singolo passo),permettendo di salvare e ricaricare lo stato ed anche di esportare un �le .CSVcontente i dati raccolti.

Batch Simulation GUI

La simulazione batch deve raccogliere i seguenti dati:

• Scelta criteri di arresto

• Scelta numero di esecuzioni

• Scelta �le da eseguire

• Scelta �le da salvare

• Scelta delle variazioni delle variabili in ingresso

Come nel caso precedente si è pensato di procedere con tre schemate perpoter scegliere le opzioni. Nella prima si possono così concentrare le infor-mazioni in merito ai criteri di arresto, �le di eseguire, �le da salvare e numerodi esecuzioni.Nella seconda così ci si può concentrare sulle variazioni dello stato iniziale:per ogni variabile ed ogni stato si devono poter impostare dei possibili valoriiniziali e il sistema deve poi valutare le esecuzioni sugli opportuni valori ini-ziali.A questo punto nella terza videata basta predisporre un indicatore di com-pletamento e qualche controllo sulla durata delle operazioni (per evitareloop).

28

Capitolo 3

Interfaccia

In questo capitolo tratteremo l'utilizzo del framework in oggetto di questoelaborato.Nella prima parte analizzeremo le procedure per l'installazione.Nella seconda discuteremo in merito alla stesura del codice, analizzando indettaglio come stendere un semplice codice d'esempio.Nella terza sezione vedremo come simulare in forma gra�ca e non.

3.1 Installazione

L'installazione del progetto risulta molto semplice. Una volta scaricato il�le compresso del progetto, basta scompattare la cartella. A questo punto èpossibile eseguire il �le sCCP-GUI.exe ed utilizzare il programma.Se il programma non dovesse funzionare, è probabile che il computer sul qua-le si sta lavorando non disponga del .NET Framework 4.0.Per l'instazzazione di quest'ultimo, basta visitare il sito di Microsoft e scari-care il software in questione.

3.2 Il Codice

Una volta lanciato l'eseguibile sCCP-GUI.exe, apparirà un'interfaccia gra�-ca per la stesura del codice. Oltre ai soliti comandi che si trovano in unausuale IDE (salva, carica, esci, nuovo, compila) ne sono stati aggiunti altriper lanciare la simulazione di tipo Batch e di tipo Gra�co.Il corpo della �nestra principale è diviso in due aree di testo: in quella disinistra verrà scritto il Source AM, mentre in quella di destra il SourceCS.Il menù Compile permette di scegliere di compilare il SourceAM, il Sour-ceCS o entrambi.

29

Nel menù Engine è possibile scegliere il simulatore tra i tre visti nelleprecedenti sezioni:

• sCCP

• ITS

• ODE

Se si dovesse scegliere ODE, verrà data la possibilità di scegliere quale meto-do utilizzare per risolvere il problema (Implicit Runge Kutta...). Oltre a ciòè possibile scegliere la precisione del solver. Nel menù Constraint Store èpossibile scegliere se utilizzare il Constraint Store basato su muParser oppurequello basato su Flee.Se si volesse scavalcare la l'interfaccia gra�ca per la stesura del codice, è possi-bile lanciare i simulatori direttamente. Questi si trovano nella stessa cartella,con il nome sCCP-GraphicSimulator.exe e sCCP-BatchSimulator.exe. Nel-l'ultima sezione di questo capitolo verrà spiegato l'utilizzo di questi e comeinterfacciarli ad eventuali altre IDE.

3.2.1 Il Codice SourceAM

In questa sezione si daranno alcune informazioni sul come scrivere il codiceSourceAM. Per prima cosa dobbiamo ricordare che a seconda del compila-tore il linguaggio subisce delle restrizioni dovute alle limitazioni teoriche. Inquesta sezione parleremo, in modo del tutto generale del codice sCCP.Il SourceAM è costruito in questo modo:

Agent_Definitions

/* Definitions */

End_Agent_Definitions

Initial_State

/* Initial State */

End_Initial_State

All'interno dello spazio dedicato alle de�nizioni, possono venir scritti agentiin questo modo:

NomeAgente(Variabili) :- Azione (.Azione)+

Variabili = Nome | Nome = Valore

Azione = Guardia | Chiamata | Parallelo | Scelta

Guardia = [Ask -> Tell]@{Rate}

Chiamata = NomeAgente(Variabili)

Parallelo = Azione || Azione ...

Scelta = Azione + Azione ...

30

Per la compatibilità delle istruzioni assegnate in Ask, Tell o Rate si rimandaal Capitolo 4. Un Tell può esser costituito da più chiamate al ConstraintStore; queste devono essere separate da un �;�. Se il codice viene compila-to da sCCP è possibile assegnare dei valori iniziali alle variabili locali cosìde�nite, altrimenti rimangono dei semplici segnaposto: nel momento in cuiverrà chiamato l'Agente fornendogli dei riferimenti in ingresso, questo verràmodi�cato per inserire la nuova variabile al posto del segnaposto.In sCCP è previsto l'operatore di dereferenziazione, come in C.Ad ogni assegnazione, se viene passata una variabile in una chiamata ricor-siva, questa viene passata per riferimento, mentre se si vuole passare solo ilvalore si deve utilizzare l'operatore *.Esempli�cando:

Agente(X):- [X > 0 -> X = X-1]@{k1}.Agente(X);Agente2 :- Agente(Y);

Nel momento in cui viene invocato Agente(Y), il segnaposto viene sostituito:

Agente(Y):- [Y > 0 -> Y = Y-1]@{k1}.Agente(Y);

Se invece l'istruzione fosse stata:

Agente2 :- Agente(*Y);

Agente(X) sarebbe rimasto uguale ma sarebbe stato assegnato ad X il valoredelle variabile attuale della variabile Y.Questo meccanismo è utilissimo per speci�care lo Stato Iniziale, in quantopermette di modellare degli agenti con lo stesso comportamento su variabilidiverse.Lo Stato Iniziale è così composto.

Initial_State

/* Agenti */

End_Initial_State

Agenti = Numero * Chiamata || Chiamata

Chiamata = NomiAgente || NomiAgente(Variabili)

Un esempio di inizializzazione, facendo riferimento ad Agente(X) visto primapuò essere il seguente:

Initial_State

Agente || Agente(Y) || 2 * Agente(Z)

End_Initial_State

31

3.2.2 Il Codice SourceCS

In questa sezione si vedrà come scrivere il SourceCS per modellare il Con-straint Store con il quale interagiranno gli agenti del SourceAM.Il sorgente deve dar la possibilità di de�nire:

• Variabili

• Parametri

• Costanti

• Operatori

• Funzioni

• Constraints

Per ogni elemento esiste una sintassi per la sue generazione. Il SourceCS haquesta forma:

Global_Var

/* Var Defs */

End_Global_Var

Params

/* Param Defs */

End_Params

Functions_Def

/*Function Defs */

End_Functions_Def

Constraints_Def

/* Constraint Defs */

End_Constraints_Def

Var Defs := NomeVariabile = Valore ;

Param Defs := param NomeParametro Valore ;

Function Defs := Constant OR Function OR Operator

Constant := CONST costante valore ;

Function := Nome(Vars) = Semantica ;

Operator := operat Simbolo/i Semantica ;

Constraint Defs := Nome(Vars) = (Var = Semantica; Var = Semantica ...);

Ogni elemento dichiarato all'interno del SourceCS è richiamabile negli Ask,nei Tell e nei Rate del SourceAM. Nel capitolo 5 sono illustrati alcuni esempicompleti di programmi funzionanti. Si rimanda il lettore a quella sezione pervedere in pratica le de�nizioni viste in questa e nella precedente sezione.

32

3.3 La Simulazione

In questa sezione si analizzeranno sCCP-GraphicSimulator e sCCP-BatchSimulator.Entrambi possono venir eseguiti come programmi stand alone e vengono ese-guiti dalla stessa sCCP-GUI quando si inviano i comandi di simulazione. Persimulare dalla sCCP-GUI si deve utilizzare il Menu Run, il quale permettedi scegliere tra Graphic Simulation e Batch Simulation.Una volta mandata in esecuzione da sCCP-GUI, è come se questa non esi-stesse più e ci si trova a contatto diretto con il simulatore.

3.3.1 Graphic Simulator

Il Graphic Simulator è composto da tre videate, ognuna con uno speci�coutilizzo. Queste vengono mostrate in ordine e l'ultima è quella che mostra lasimulazione vera e propria. Queste servono a:

1. Scelta dei criteri di arresto, scelta sorgenti e numero di simulazioni

2. Scelta delle variabili da monitorare, dei colori delle linee etc

3. Simulazione e gra�ci

Prima Schermata

Nella prima schermata sono impostabili i criteri di arresto. Questi possonoessere di due tipi: sul numero di passi o sul tempo di sistema. Una volta sceltoil criterio di arresto si può passare alla scelta della precisione dell'analisi. Sesi è scelto di concludere a un dato tempo, si può scegliere di campionare Npunti (decretanto così la precisione dell'output) oppure si può scegliere unpasso temporale di campionamento ed utilizzare direttamente quello.Nel caso la scelta ricada su un criterio di terminazione legato al numero dipassi, si può scegliere ogni quanti passi campionare.Oltre a questo si possono scegliere altre cose:

• Il numero di simulazioni

• Il �le XML che descrive il Constraint Store

• Il �le XML che descrive l'Agent Manager

• Se mostrare il gra�co durante la simulazione o alla �ne

Nel caso il simulatore venga caricato dalla sCCP-GUI, i campi contenenti ipercorsi dei �les vengono già assegnati con i nomi corretti.

33

Seconda Schermata

Nella seconda schermata l'utente può impostare le impostazioni riguardanti ilgra�co. Nella lista superiore vengono indicate le variabili globali del progetto.Una volta selezionata, l'utente può scegliere se:

• Stampare i singoli valori della variabile delle diverse simulazioni

• Stampare la media dei valori della variabile derivanti dalle diversesimulazioni

• Stampare la varianza dei valori della variabile derivanti delle diversesimulazioni

Una volta cliccato su uno dei tre pulsanti, viene aggiunta una nuova riganella lista dei valori da stampare. In questa lista è possibile con�gurare piùparametri:

• Il nome da mostrare nella legenda del gra�co

• Il colore della linea

• La sorgente dei dati

La sorgente dei dati serve per selezionare di quale simulazione si vuole tenertraccia. Ad esempio è possibile calcolare la media tutte le simulazioni eccettouna e di questa mostrare il valore singolo. In questo modo si può comparare,per �ni l'andamento medio con l'andamento di una singola simulazione.Una volta selezionati i valori, si può premere sul tasto OK per passare allaterza schermata.

Terza Schermata

La terza schemata è stata progettata per interfacciarsi con il RuntimeMa-nager dando all'utente tutte le informazioni di cui ha bisogno. Buona partedello schermo è coperto dal gra�co. Sulla destra vengono riportati i valoridelle variabili e gli agenti vivi. In basso a sinistra una label riassume lo sta-to del Runtime Manager (ultima azione eseguita se si va per step, rate delsistema etc).I Menù permettono di di interagire con il sistema:File:

• New - Crea una nuova simulazione copia di quella in esecuzione

• Load Status - Carica una simulazione precedentemente salvata

34

• Save Status - Salva una simulazione

• Save CSV - Salva i dati su disco in Comma Separated Values

• Close - Chiude la simulazione

Run:

• Single Step - Esegue un passo nella simulazione

• Start/Stop - Avvia/Interrompe la simulazione

3.3.2 Batch Simulator

Il Batch Simulator è strutturato in 3 parti, come il Graphic Simulator. Letre �nestre hanno scopi diversi rispetto a quanto precedentemente visto:

1. Scelta criteri di arresto e precisione dei dati, scelta della locazione deiCSV con i risultati e dei �le XML da compilare

2. Scelta delle diverse con�gurazioni di valori iniziali e parametri nellediverse simulazioni

3. Semplice indicatore dell'avanzamento del lavoro

Prima Schermata

La prima �nestra è stata impostata allo stesso modo della prima del GraphicSimulator. I criteri di arresto vengono introdotti nello stesso modo. Nel-l'interfaccia è sostituita la CheckBox che prima serviva la visualizzazione delgra�co a run-time o alla �ne della simulazione; questa ora serve per stabilirese l'utente vuole il risultato salvato in un unico �le o in uno diverso per ognisimulazione. Oltre a questo una TextBox o�re la possibilità di scegliere dovesalvare l'output prodotto.

Seconda Schermata

La seconda schermata permette all'utente di scegliere diverse con�gurazionidi valori delle variabili e dei parametri. Questa schermata serve, ad esempio,a vedere come varia il comportamento del sistema mano a mano che un pa-rametro cresce. Da una ComboBox si può scegliere il valore da modi�care,una volta aggiunto si può scegliere come farlo variare. È possibile scegliereche la variabile acquisica N valori uniformemente distribuiti su un'intervallo,oppure che il valore di questa venga incrementato / decrementato �ntanto

35

che rimane all'interno di un intervallo.Il numero di simulazioni sarà proporzionale al numero di combinazioni pos-sibili. Se ad esempio si fa variare la prima variabile su 3 valori e un'altra su2, ci saranno 6 simulazioni.

Terza Schermata

La terza schermata è assolutamente stringata: presenta solo una barra diavanzamento dei processi. Quando le simulazioni vengono completate, que-sta avanza. Quando la simulazione è conclusa, viene riportato il tempoimpiegato, l'istante di inizio elaborazione e di �ne elaborazione.

36

Capitolo 4

Implementazione

Dopo aver esposto le nozioni teoriche nel capitolo 1, l'analisi e la progettazio-ne nel capitolo 2 e aver mostrato l'interfaccia nel capitolo 3, in questo quartocapitolo si presenterà l'implementazione.Nella prima sezione verranno analizzate velocemente le schermate. Nellesuccessive si analizzeranno a turno i diversi compilatori.

4.1 Dettagli dell'Interfaccia Gra�ca

Per la programmazione dell'interfaccia gra�ca sono stati utilizzate delle com-ponenti esterne, non scritte dal candidato. Nello speci�co si sono usate leseguenti librerie:

• ColorPicker

• DynamicDataDisplay

La prima consentiva di prelevare un colore da una tavolozza ed è stata inseri-ta nella scelta dei colori nella simulazione gra�ca. Sempre nella simulazionegra�ca si è utilizzato il DynamicDataDisplay. Questi altro non è se non uncontrollo WPF che gestisce dei gra�ci a linea.Quando viene istanziato la �nestra con il gra�co vengono letti i parametri edesunte le linee da disegnare. A questo punto vengono memorizzate in undizionario, per ogni linea, una lista di ObservablePoint. Ogni volta che verràaggiunto un punto in una di queste liste, questo verrà tracciato nella correttalinea.Quando viene lanciata una simulazione, viene anche attivato un thread cheva a controllare ogni 500ms se vi sono nuovi dati disponibili dal Runtime-Manager. Questi vengono convertiti in modo da essere utilizzabili e vengono

37

inseriti nelle liste di punti opportune.Nel gestire simulazioni parellele contemporanee, onde evitare problemi concalcoli della media e inconsistenza dei dati, si è deciso di disegnare i punti �noall'istante temporale del RuntimeManager di tempo minimo. Ad esempio, siconsiderino 4 simulazioni che dopo 500ms si trovano nel seguente stato:

Sim1 : T = 35 Sim2 : T = 50 Sim3 : T = 80 Sim4 : T = 12

A questo punto il simulatore vede che Sim4 è la simulazione più in ritardo edisegna sul gra�co tutti i punti richiesti �no al tempo 12.Nel caso una delle simulazioni dovesse incontrare un blocco dovuto al codice(rate pari a 0), non sarà possibile continuare la tracciatura del gra�co.L'interfaccia gra�ca si appoggia su un OutputManager che gli permette dimemorizzare su disco lo stato corrente, i risultati delle elaborazioni e diricaricarli all'occorrenza.

4.2 SCCP

SCCP è il primo compilatore e simulatore che è stato scritto per questo pro-getto. È quello che presenta maggiori requisiti da implementare in quantodeve poter simulare tutte le caratteristiche del linguaggio SCCP. Nelle pros-sime sezioni vedremo nel dettaglio come sono state implementate le diversecomponenti che lo formano.Inizieremo esaminando il Constraint Store, parleremo poi del De�nition Sto-re, del Runtime Manager e in�ne dei Parser (ParserCS a ParserAM).

4.2.1 Il Constraint Store

Nella sezione 1 abbiamo appreso come il Constraint Store debba risponderead Ask e Tell, mentre nella fase di progettazione ci si è resi conti che lefunzionalità andavano ampliate. Nello speci�co si è giunti a:

• Ask

• Tell

• GetRate

• Parse

• Metodi per istanziare variabili, parametri, funzioni, operatori, con-straint e quant'altro.

38

• GetVariables

È stato necessario appoggiarsi ad un parser di espressioni matematiche pergestire il Constraint Store. La scelta è ricaduta su muParser (modulo esternonon scritto dal tesista).

muParser

MuParser è reperibile all'indirizzo muparser.sourceforge.net.È gratuito e disponibile in forma nativa per C++ e Wrappato per ambiente.NET.Questa libreria permette di calcolare il valore di espressioni contenenti nu-merosi operatori e dà anche la possibilità di espandere le proprie potenzialitàtramite opportuni metodi. Oltre a ciò permette di memorizzare al propriointerno parametri e variabili. È uno dei migliori parser matematici gratuitia livello di performances.In questa prima tabella vengono esposte le funzioni built-in in muParser.

39

Name ARC Explanationsin 1 sine functioncos 1 cosine functiontan 1 tangens functionasin 1 arcus sine functionacos 1 arcus cosine functionatan 1 arcus tangens functionsinh 1 hyperbolic sine functioncosh 1 hyperbolic cosinetanh 1 hyperbolic tangens functionasinh 1 hyperbolic arcus sine functionacosh 1 hyperbolic arcus tangens functionatanh 1 hyperbolic arcur tangens functionlog2 1 logarithm to the base 2log10 1 logarithm to the base 10log 1 logarithm to the base 10ln 1 logarithm to base e (2.71828...)exp 1 e raised to the power of xsqrt 1 square root of a valuesign 1 sign function -1 if x<0; 1 if x>0rint 1 round to nearest integerabs 1 absolute valuemin var. min of all argumentsmax var. max of all argumentssum var. sum of all argumentsavg var. mean value of all arguments

40

Operator Meaning Priority= assignement -1and logical and 1or logical or 1xor logical xor 1<= less or equal 4>= greater or equal 4!= not equal 4== equal 4> greater than 4< less than 4+ addition 5- subtraction 5

multiplication 6/ division 6^ raise x to the power of y 7?: if then else operator 1

In questa tabella vengono esposti gli operatori built-in in muParser.

Interfacciamento con muParser

Come visto, muParser ha delle peculiarità molto importanti per quanto ri-guarda la de�nizione di funzioni, variabili e quant'altro. Per quanto riguardaAsk, Tell e GetRate la loro de�nizione diventa banale: basta che il ConstraintStore faccia da Wrapper, facendo attenzione a casi particolari. Ad esempioil parsing di un'istruzione vuota genera un'eccezione, ma si è deciso inveceche l'Ask di una tale istruzione sia sempre valido, quindi si è dovuta gestirel'eccezione e ritornare il valore true.La de�nizioni di variabili e parametri è molto semplice, così come l'ottenereil valore delle variabili in muParser; basta anche in questo caso fare poco piùche un Wrapper. Gli argomenti più spinosi rimangono: la de�nizione di UserDe�ned Funcion (UDF) e il Parsing delle stringhe per i Parser.Per risolvere il problema delle UDF è stato escogitato un metodo molto mal-leabile che permette di gestire funzioni molto complicate e con molti para-metri. Per de�nire una nuova funzione in muParser, questo non si aspettaaltro se non un delegato da invocare passando i parametri quando la incontradurante il parsing.Per creare a runtime una funzione che risolva questo problema si sono usateopportune classi neutre. Viene de�nita una classe Function che si aspetta iningresso una lista parametri e la semantica della stessa. I parametri non han-no un valore, ma solo il nome del segnaposto nella semantica. Questa classe

41

prevede un metodo Solve che accetta come parametri un array di double e unintero contenente il numero di parametri. Questa �rma è esattamente quellache si aspetta muParser per creare una nuova funzione.Associato il nome alla funzione Solve della classe appena generata, il Parserla invocherà al momento opportuno.Quando questa viene invocata, va a sostituire tutti i parametri che ricevein ingresso (dei double) ai segnaposti indicati prima come parametri (dellestring). A questo punto la stringa può venir risolta da muParser in manieraricorsiva risolvendo il problema.Vediamo ora un semplice esempio:

F(X,Y,Z) = (X + Y) / Z;

Il Parser la spezza in modo da ottenere una lista di stringhe contente [X,Y,Z]e la semantica (X+Y) / Z. A questo punto crea la Function passando i valori.Nel momento della chiamata:

F(1,3,5)Invoke Solve([1,3,5],3)Sostituzione Parametri ai segnaposto: (X + Y) / Z ⇒ (1 + 3) / 5return Parser.Solve((1 + 3) / 5);

Da questo pseudocodice si comprende subito la linearità dei passaggi e lacorrettezza degli stessi.Un problema altrettando spinoso da trattare per il Constraint Store è il Par-sing per il ParserAM. Questo serve per rendere compatibili le stringhe chepoi verranno passate a muParser.Un esempio banale è dato dalla gestione delle variabili globali: per distingue-re le une dalle altre, alle variabili globali viene applicato il pre�sso GLOBAL.Se non viene fatto un parsing corretto, un Agente che avesse un Ask del tipo[X > 0] creerebbe un'eccezione per variabile non trovata. Il Constraint Storedeve, per l'appunto, controllare le formule e modi�carle:

[X > 0] ⇒ [GLOBALX > 0]

Il Constraint è una particolare UDF che serve ad e�ettuare molteplici opera-zioni parametrizzate. Un esempio di Constraint potrebbe essere il seguente:

CS(ix, ipsilon) = ( X = ix/2; ipsilon = Y+2;);

Il seguente constraint pone ad X il valore di ix /2 (qualunque sia il valore diix) e modi�ca il valore di ipsilon ponendolo a Y + 2.

42

È facile comprendere il caos che si può creare durante questa conversione.È stato necessario convertire le stringe in maniera che ogni chiamata diven-tasse diversa dalle altre: è da ricordare infatti che le funzioni de�nite inmuParser accettano solo parametri double e non stringhe.La soluzione che si è adottata prevede di parsare le stringhe associando undiverso constraint per ogni sua invocazione, così da poter modi�care la se-mantica a seconda della chiamata.Si consideri ad esempio il constraint CS prima de�nito e si analizzi la chia-mata:

[ -> CS(K,MyCount)]@{...

È necessario creare il constraint partendo dalla de�nizione e tenendo contodi:

• Variabili Globali (se X è globale diventa GLOBALX)

• Nome del Constraint Store (deve essere diverso per ogni invocazione)

• Sostituire in tutte le istruzioni il nome della variabile presente nellachiamata.

Tenendo conto di queste particolari condizioni, il Constraint Store produrràin risposta alla richiesta di parsing:

CS1(GLOBALK, MyCount)

Dove in muParser è de�nita una funzione che esegue:

GLOBALX = GLOBALK / 2

MyCount = GLOBALY + 2

Per quanto concerne la creazione degli operatori de�niti dall'utente, muParsergestisce il tutto in maniera simile.La sintassi de�nita è come:operat SIMBOLO (elemento1, elemento2, precedenza)Ad esempio:

operat ^= (p1, p2 ,1) = (p1 - p2) /2;

Questo operatore, ad esempio fa la media dei due elementi. La gestione inmuParser è simile, l'unica di�erenza è la precedenza dell'operatore, indicatadal terzo parametro. È possibile capirne il signi�cato guardando la tabellacon i built-in operators. Dopo aver costruito il Constraint Store basato sumuParser si è riscontrata una mancanza di performance dovuta alla noncompilazione delle formule. Per questo motivo si è creato un altro ConstraintStore basato su un altra libreria: FLEE.

43

FLEE

FLEE(Fast Lightweight Expression Evaluator) è un valutatore di espressionimolto veloce dalle funzionalità ridotte. La libreria è gratuita e disponibile su�ee.codeplex.com.Vediamo ora i vantaggi di questa libreria:

• Compila le formule, fornendo delle prestazioni molto maggiori

• Si interfaccia facilmente con altre librerie per aggiungere funzionalità

• Supporta la chiamata di funzioni di sistema e codice IL

Flee presenta anche dei notevoli svantaggi:

• Non permette l'assegnazione come elemento delle formule (X = X+1risponde false)

• Non permette la creazione di parametri o costanti

• Non permette di creare degli operatori custom

A questo punto si è deciso di creare un Constraint Store limitato ma decisa-mente più veloce. In questo non sarà possibile:

• De�nire Constraints

• De�nire Operatori custom

Se per un particolare programma non servono queste due funzionalità è pos-sibile utilizzare questo Constraint Store che, come sarà esposto nel quintocapitolo, ha delle performance di gran lunga superiori. La de�nizione del-le funzioni è stata implementata in una maniera simile a quanto visto permuParser. In questo caso si è creato un Function Manager che espone unafunzione F che accetta come parametro una stringa. Il Constraint Store mo-di�cherà tutte le chiamate alle funzioni che trova in questo modo:

miaF(X,2,K) → F(miaF,X,2,K)

Quando FLEE incontrerà F, invocherà la funzione del Function Manager.Questi spezzerà la stringa usando come divisore le virgole. Al primo postotrova il nome della funzione da evocare e la evocherà dall'elendo di funzionide�nite.I Tell sarebbero inutili se impossibilitati a modi�care il sistema. Si è quin-di intervenuti per rendere possibile la modi�ca delle variabili. Quando il

44

Constraint Store riceve un Tell, veri�ca se la stringa è formata da �nome va-riabile� seguita dal simbolo =. Se così è allora viene risolta la parte successivaall'uguale e il risultato viene assegnato alla variabile. Nel caso la variabileappartenga alla lista di parametri fornita dal SourceCS, l'assegnazione nonviene fatta, trattando di fatto la variabile come una costante.Ora verranno brevemente esposte le funzionalità di Flee:

Operazioni Aritmetiche Flee permette di eseguire tutte le operazioniaritmetiche come somme, prodotti, elevamenti a potenza e moduli.ES: X * 2 + B ^ 100 % 10

Operazioni di Confronto Le operazioni di confronto ammesse sono tuttele più comuni. Per indicare il �diverso� si utilizza l'operatore <>, mentre perveri�care l'uguaglianza di due oggetti si può usare semplicemente l'uguale.ES: (X <> Y)

Operazioni di And/Or/Xor/Not Essendo ogni operazione in Flee for-temente tipizzata, l'utilizzo di questi operatori varia a seconda del contesto.In alcuni casi Flee utilizzerà l'And logico, mentre in altri farà quello Bit aBit per esempio.ES (logico): a > 100 And Not b = 100ES (bit a bit): (100 or 2) and 1

Operazioni di Shift Grazie agli operatori � e � è possibile fare degli Shiftdei valori.ES: 100 � 2

Operatori di Contatenazione Come in molti liguaggi di programmazio-ne moderni, il + in Flee sta ad indicare la concatenazione tra stringhe.ES: �abc� + �def�ES: �the number is: � + 100

Operatori di Indicizzazione Con Flee si possono modellare ed utilizzareArray dentro le formule. ES: arr[i + 1] + 100

Scrittura dei Simboli In Flee ogni valore viene interpretato in un parti-colar modo per tipizzarlo nella maniera corretta:

• Char - Un carattere tra singoli apici 'a'

45

• Boolean - true o false

• Real - Ogni numero con un punto decimale. Con 'd' ed 'f' si puòspeci�care la precisione (�oat, double)

• Integral - Ogni numero intero. Con 'U' lo si speci�ca Unsigned, mentrecon 'L' lo si considera a 64 bit

• Hex - Numero esadecimale, espresso nella notazione: 0xFF12

• String - Insieme di caratteri racchiuso tra due doppi apici

• Null - Alla variabile viene assegnato il valore null

• DateTime - Una data scritta come: #08/06/2008#

Casting Essendo tutte le variabili fortemente tipizzate (e non tutte doublecome in muParser), la conversione si fa tramite �cast�.ES: 100 + cast(obj, int)

Operatori Condizionali Come visto in muParser, anche quì è presenteun operatore condizionale.ES: If(a > 100 and b > 10, �both greater�, �less�)

Operatore In Questo operatore è un operatore booleano che ritorna l'ap-partenenza di un valore o meno ad un insieme. Lo si può utilizzare con unvalore ed una lista di valori dello stesso tipo.ES (List): If(100 in (100, 200, 300, -1), �in�, �not in�)ES (Collection): if(100 in collection, �in�, �not in�)

Le funzioni messe a disposizione da Flee sono le stesse disponibili nella libreriaMath di .NET. Grazie alla sua �essibilità, infatti, tramite questa istruzionesi può fargli utilizzare l'intero pacchetto:

context.Imports.AddType(typeof(Math));

Questa si può utilizzare con qualunque namespace o classe, di questa impor-terà tutte le funzioni publiche e statiche.Nonostante tutte queste funzionalità di Flee non è stato possibile implemen-tare degli operatori custom come fatto in muParser. Non è stato altresìpossibile permettere la gestione dei Constraint.All'utente verrà data la possibilità di scegliere tra i due Constraint Store aseconda delle sue esigienze: in caso di performance si consiglia Flee, in caso

46

di semplicità di scrittura tramite Constraint si consiglia muParser.Per una descrizione più approfondita di Flee, si rimanda al sito del progetto.

4.2.2 De�nition Store

Come è stato de�nito il Constraint Store per la gestione dei vincoli, ora verràanalizzato il lavoro che è stato svolto per il De�nition Store. Dalla teoria edalle fasi di analisi e progettazione è emerso che il De�nition Store deve:

• Gestire la creazione di una de�nizione

• Gestire la modi�ca delle de�nizioni

• Fornire un'interfaccia al ParserAM per aiutarlo nella creazione dellede�nizioni

• Istanziare su richiesta le de�nizioni

Oltre a fornire le funzioni sopra esposte, il De�nition Store deve creare deglioggetti utilizzabili dal Runtime Manager, ossia Agenti pronti ad eseguire leproprio azioni.Si è subito deciso che il De�nition Store dovesse, in primis, contenere unalista di de�nizioni. Il passo successivo è stato decidere che, al momento dellacreazione di una nuova de�nizione, questa venisse fornita al chiamante.In questo modo il chiamante, utilizzando i metodi della de�nizione può mo-di�carla aggiungendoci azioni e variabili locali.Questo è possibile grazie all'implementazione di interfacce contenute nel Pro-getto Commons, in comune all'intera soluzione.Il De�nition Store contiene tutte le classi che de�niscono le azioni viste inteoria. Queste sono intercambiabili in quanto tutte implementano la classeIAction (presente anch'essa in Commons).Avremo quindi le seguenti azioni:

• Guard: gestisce un'azione di tipo guardia

• Choose: gestisce una scelta

• Parallel: gestisce un parallelo

• Call: gestisce la chiamata

• Tell: gestisce un Tell a rate in�nito (all'interno dei Parallel)

• Ask: gestisce un Ask a rate in�nito (all'interno dei Parallel)

Oltre alle azioni e le de�nizioni, il De�nition Manager deve fornire anche gliAgenti.

47

Le Azioni

Le azioni (come visto nel capitolo 2.2.6) vengono raccolte in ActionManagerche a loro volta vengono contenuti da Actions. Actions gestisce più Action-Manager (come fosse una scelta), mentre un ActionManager gestisce una listadi Azioni �nchè si trova il bivio dato da una scelta.È ora riportato un esempio che aiuterà a spiegare l'utilizzo di Actions eActionManager.

Ag :- [-> X=X+1]@{1} . Ag . [X > 0 -> ]@{X}.Ag + [ -> ]@{1}.Ag2

+ [ X>5 -> X=0]@{1} . Ag || Tell(Y=X);

Questo agente avrà come azioni un oggetto costituito come quello in �gura:Le azioni implementano l'interfaccia IAction, che garantisce la loro esposi-

zione dei seguenti metodi:

• Execute: fa eseguire l'azione

• ReceiveLocalVariables: permette di impostare le variabili locali all'a-zione

• GetRate: ritorna il rate dell'azione

• GetAskVars: ritorna le variabili che in�uiscono sull'eseguibilità dell'a-zione

• GetTellVars: ritorna le variabili che vengono modi�cate dall'azione

• Refresh: aggiorna l'azione se sono state modi�cate variabili che lainteressano

• IsRateIn�nite: permette di sapere se l'azione ha rate in�nito

48

• ForceRefresh: forza il refresh

• GetActionData: ritorna un oggetto con i dettagli dell'azione

L'utilizzo di funzioni come Refresh, GetAskVas e GetTellVars sono indispen-sabili al �ne di ottenere un miglioramento delle performance. Nella sezionededicata al Constraint Store, vedremo come queste verranno utilizzate.

Agent e AgentDe�nition

AgentDe�nition è una classe che contiene tutte i dati utili per la creazionedi un agente e i metodi per far si che il parser possa crearla.Agent viene creato dalla AgentDe�nition ed è l'oggetto centrale di sCCP.Dalla teoria si evince che un agente è costituito dalle Variabili Locali e dal-l'elenco delle proprie azioni. Questo è importante anche perchè ci fa capireche inizialmente tutti gli agenti dello stesso tipo sono uguali.Da questo si può desumere che l'istanziazione di un Agent da un AgentDe�-nition sia alquanto semplice in quanto consta della crezione dello stesso e delpassaggio delle proprie azioni e delle proprie variabili locali. Nello speci�coogni Agent implementerà l'interfaccia IAgent. Per le speci�che dell'interfac-cia IAgent e delle altre, si rimanda ai sorgenti del codice, dove i commentispiegano l'utilizzo di ogni funzione.Verrà ora spiegato velocemente cosa succede quando viene invocato l'Excecu-te a un Agente. Assieme all'Execute viene passato un valore è Reale: questogenerato dal Runtime Manager e serve nella scelta dell'azione.Vediamo ora uno pseudo codice:

Execute(RATE)

i := 0

while(RATE > 0)

RATE = RATE - RateAzione[i]

if (RATE < 0)

Esegui Azione[i]

else

i ++

Nello speci�co tale azione viene compiuta dall'oggetto Actions che ogni Agentha. Azione[i] è un ActionManager e come tale inizierà l'esecuzione eseguen-do ogni IAction che ha in lista. Se dovessimo incontrare un'azione di tipoChoose, questa gestirà autonomamente (con il rate residuo) la scelta che devefare.

49

4.2.3 Runtime Manager

Il Runtime Manager è forse l'elemento più importante dell'intero modulo: èil vero e proprio motore della simulazione. Nella fase di progettazione si sonodiscusse la operazioni che deve sostenere, in questa fase vedremo, in formaridotta, gli elementi principali.Un possibile pseudocodice per rappresentare l'operato di uno Step simulativoè il seguente:

if (IsWorkEnded è vero) return;

if (Ci sono Agenti Con Rate Infinito)

Esegui il Primo

Rimuovilo dalla lista

else

Ottieni il Rate Totale

Execute(Rate Totale * Rand(0,1))

Aggiorna il tempo

if (Il tempo passato supera la precisione)

Aggiorna GraphData

Terminazione

La condizione di IsWorkEnded viene posta vera dopo il raggiungimento delcriterio di arresto. Questo può essere di due tipi: temporale o sul numero dipassi.Questo �ag è accessibile anche dal chiamante in modo che sappia quando illavoro è terminato.

Agent Pool

Agent Pool è una classe appoggio del Runtime Manager che gestisce gli agen-ti. Nello speci�co ritorna i valori del Rate del Sistema, sceglie l'agente daeseguire in base al valore casuale generato dal Runtime manager e gestiscel'eliminazione degli agenti dopo l'esecuzione.Una delle cose più importanti che vengono fatte dall'Agent Pool è la gestionedei Refresh. Questi sono gestiti in maniera intelligente ragioni di performan-ce.Prima si è mostrato lo scheletro della classe IAction e si è rimandato il trat-tamento di metodi come GetAskVars e GetTellVars. Questi servono perl'appunto per la gestione dei Refresh.Dopo ogni esecuzione, Agent Pool controlla quali sono le variabili modi�cate

50

dell'azione che ha eseguito (GetTellVars) e sa quali sono gli agenti (memoriz-zati in opportune liste) che subiscono un cambiamento a causa delle variabiliglobali cambiate. Questo può essere di due tipologie:

• Modi�ca di variabili presenti nell'Ask

• Modi�ca di variabili presenti nel Rate

Se nessuna delle due condizioni si veri�ca, allora quel dato agente avrà lostesso stato del passo precedente (valori delle guardie e rate). In questo mo-do si migliora l'e�cienza mano a mano che sale il numero di agenti. È facileimmaginare sistemi con centinaia di agenti di tipi diversi, che condividonopoche variabili: in questi casi l'aumento di e�cienza è molto rilevante.Se durante il Refresh un'azione ha rate in�nito, questa avvisa subito il Run-time Manager che mette l'agente nella coda speciale dei Rate in�niti. L'ope-razione di aggiornamento continua e se vi sono altre azioni a Rate in�nito,queste vengono messe in coda. In questo modo al passo successivo, eseguirà.

Aggiornamento GraphData

GraphData è stato costruito per fornire lo stato delle variabili. Inizialmenteera costituito da un dizionario di stringhe e liste di double in cui ogni listatracciava l'andamento della variabile indicata dalla stringa.Ad esempio con:

GraphData[X]

Si ottiene la lista di valori che ha assunto la variabile X. Per motivi di perfor-mance alla classe GraphData è stato aggiunto l'elemento Time. Questo vienemodi�cato nel momento in cui vengono inseriti i nuovi valori nel dizionario.È stato implementato in questo modo per favorire il lettore dei dati: bastavedere se è stato incrementato Times piuttosto che contare tutti i valori nelleliste.

4.2.4 ParserCS

Il ParserCS è una classe costruita per leggere e interpretare degli opportuni�les XML. Questi devono fornire una modellazione del Constraint Store ecome tale possono contenere:

• Dichiarazioni di Variabili

• Dichiarazioni di Parametri

51

• Dichiarazioni di Funzioni

• Dichiarazioni di Costanti

• Dichiarazioni di Constraints

• Dichiarazioni di Operatori

Come visto nel capitolo 3, il codice è strutturato in maniera da essere divisoin blocchi. ParserCS analizza il documento XML sezione per sezione, par-tendo dalla de�nizione delle variabili e �no alla de�nizione dei Constraints.Per ognuno degli elementi utilizza delle opportune strutture per contenerel'informazione (ad esempio per una variabile basta l'accoppiata Nome e Va-lore Iniziale). Quando il ParserCS ha �nito l'analisi del documento XML,viene generato un oggetto di tipo CSXMLParserResult che dato in ritorno.A questo punto verrà utilizzato il ParserAM, al quale deve venir fornito ilrisultato del ParserCS.ParserCS accetta �le XML che rispettino il seguente DTD:

<!DOCTYPE XMLConstraintStore [

<!ELEMENT XMLConstraintStore (VarDefinitions, ParDefinitions,

FunctionDefinitions, Constraints)>

<!ELEMENT VarDefinitions (Var)*>

<!ELEMENT Var (#PCDATA)>

<!ELEMENT ParDefinitions (Par)*>

<!ELEMENT Par (#PCDATA)>

<!ELEMENT FunctionDefinitions (Function)*>

<!ELEMENT Function (Operator | Func | Constant | Call)+>

<!ELEMENT Operator (Operand, Operat, Operand, OpSemantic,

Precedence)>

<!ELEMENT Operand (#PCDATA)>

<!ELEMENT Operat (#PCDATA)>

<!ELEMENT OpSemantic (#PCDATA)>

<!ELEMENT Precedence (#PCDATA)>

<!ELEMENT Func ((Parameter)*, Semantic)>

<!ELEMENT Parameter (#PCDATA)>

<!ELEMENT Formula (#PCDATA)>

<!ELEMENT Conditional (if, then, else)>

<!ELEMENT if (#PCDATA)>

<!ELEMENT then (#PCDATA)>

<!ELEMENT else (#PCDATA)>

<!ELEMENT Constant (#PCDATA)>

52

<!ELEMENT Constraints (Constraint)*>

<!ELEMENT Constraint (Parameter | Istr )*>

<!ELEMENT Istr (VarName, Semantic)*>

<!ELEMENT VarName (#PCDATA)>

<!ELEMENT Semantic (Formula | Call)>

<!ELEMENT Call (Parameter)>

<!ATTLIST Constraint Name CDATA #REQUIRED>

<!ATTLIST Call Name CDATA #REQUIRED>

<!ATTLIST Var Name CDATA #REQUIRED>

<!ATTLIST Function Name CDATA #REQUIRED>

<!ATTLIST Par Name CDATA #REQUIRED>

]>

4.2.5 ParserAM

ParserAM deve analizzare un �le XML molto più complicato rispetto a quellodel Constraint Store. In questo caso gli elementi non sono di forma standardma possono variare. Ad esempio l'azione:

[X > 0 -> X=X-1; Y=Y+1]@{1} . AG1 . [X == 0 -> Y = 0]@{1}

Diventa:

<Choice>

<Action>

<Ask>X&gt;0</Ask>

<Tell>

<Istr>X=X-1</Istr>

<Istr>Y=Y+1</Istr>

</Tell>

<Rate>1</Rate>

</Action>

<Parallel>

<AgentParallel>

<Call>AG1</Call>

<Rate></Rate>

</AgentParallel>

</Parallel>

<Action>

<Ask>X==0</Ask>

<Tell>

<Istr>Y=0</Istr>

53

</Tell>

<Rate>1</Rate>

</Action>

</Choice>

I �le XML in ingresso al ParserAM (per sCCP) devono esser validati dalseguente DTD.

<!DOCTYPE XMLAgentStore [

<!ELEMENT XMLAgentStore ((Agent)+, Initial)>

<!ELEMENT Agent (Local*,Choose)>

<!ELEMENT Local (LocalVar)*>

<!ELEMENT LocalVar (#PCDATA)>

<!ELEMENT Choose (Choice*)>

<!ELEMENT Choice (Action, (Action | Parallel | Call | Choose)*) >

<!ELEMENT Action (Ask, Tell, Rate)>

<!ELEMENT Ask (#PCDATA)>

<!ELEMENT Tell (Istr)*>

<!ELEMENT Istr (#PCDATA)*>

<!ELEMENT Rate (#PCDATA)>

<!ELEMENT Parallel (AgentParallel)+>

<!ELEMENT AgentParallel ((Ask , Rate) | (Tell , Rate)

| (Call, Rate) | Choose)>

<!ELEMENT Call (#PCDATA)>

<!ELEMENT Initial (AliveAgent)+>

<!ELEMENT AliveAgent (#PCDATA)>

<!ATTLIST LocalVar Name CDATA #REQUIRED>

<!ATTLIST Agent Name CDATA #REQUIRED>

<!ATTLIST AliveAgent Num CDATA #REQUIRED>

]>

Per riuscire a comprendere codici in questa forma, si è dovuti ricorrere aduna ricorsione. In pratica il compilatore instanzierà una de�nizione e viaggiungerà le variabili locali (leggibili come le variabili globali del ParserCS).Fatto ciò inizierà a scendere l'albero delle azioni. Per ogni Choose ci sonodiverse Choice, quello che il codice farà sarà generare un ActionManager perogni Choice. Se durante l'analisi delle azioni dovesse incontrare una Choose,invocherebbe ricorsivamente il metodo.Per comprendero meglio, si guardi il seguente pseudo codice.

for each Agent

D = NuovaDefinizione;

54

for each Local

Aggiungi Variabile Locale a D

for each Choice

Aggiungi un ActionManager a D

Invoca Choice(Punto di Partenza)

Choice(Punto di Partenza)

for each Azione dal PuntoDiPartenza

Se Azione != Scelta

Aggiungi Azione

Altrimenti

Aggiungi Choose(PuntoAttuale)

Choose(Punto di Partenza)

Crea Azione Scelta;

for each Choice

Aggiungi ActionManager a Scelta;

Invoca Choice(Punto di Partenza)

Ritorna Azione Scelta

4.3 ITS

In questa sezione analizzeremo il funzionamento del compilatore ITS. In par-ticolare si scenderà nel dettaglio solo nelle parti che di�eriscono notevolmenteda sCCP, accennando soltanto alle altre di�erenze.Nella prima parte si andranno ad analizzare Constraint Store e De�nitionStore. Nella seconda si analizzeranno il Transition System e il Runtime Ma-nager. Nella terza sezione si analizzeranno le di�erenze a livello dei Parser.Dalla teoria sappiamo che per ITS:

• Non può essere utilizzata la composizione in parallelo

• Non esistono azioni istantanee (con Rate in�nito)

• Ogni azione è nella forma [Ask− > Tell]@{Rate}.Agente

• Gli Agenti non posseggono variabili locali

4.3.1 Constraint Store e De�nition Store

Si è deciso di utilizzare lo stesso Constraint Store rispetto a quanto visto persCCP. Le speci�che, infatti, non pongono limitazioni in merito. Il De�nition

55

Store assume invece una diversa connotazione: come visto nella parte teo-rica, ora il fulcro principale della simulazione non sono gli agenti, bensì letransizioni.Il De�nition Store a questo punto si è costruito in maniera tale che:

• Raccolga le de�nizioni fornite dal ParserAM

• Abbia come unico tipo di Azione quella che verrà chiamata ITSAction

• Elabori le de�nizioni per tornarne una rappresentazione in chiave ditransizioni.

Il De�nition Store fornisce al ParserAM le stesse funzionalità del De�nitionStore di sCCP, con la sola di�erenza che fornisce un parco azioni più piccolo.Dalla teoria abbiamo visto che tutte le azioni devono essere nella forma:

[Ask -> Tell]@{Rate}.Call

Ci serviranno solo le azioni di Guardia e di Chiamata per coprire l'insiemedelle possibili azioni.Il De�nition Store o�re il metodo InstanceAllDe�nitions che fornisce in ri-torno tutti i dati necessari per creare le transizioni. Nello speci�co ritorna,per ogni azione:

• Nome della de�nizione a cui appartengono

• Contenuto dell'Ask

• Lista contenente i diversi Tell

• Contenuto del Rate

• Nome contenuto nella Call

Ricevuti questi dati, il Runtime Manager e il Transition System dovrannoessere in grado di creare il sistema a transizioni.

4.3.2 Runtime Manager

La semantica ITS modi�ca completamente il modo di approcciarsi al proble-ma, spostando l'attenzione dagli agenti alle transizioni. Una transizione èun'azione che porta il sistema da uno stato ad un altro stato. Le transizionivengono de�nite, come visto nella sezione 1:

πi := [G(X)− > U(X)]@λ

56

G(X) è passabile ⇔SVi > 0 ∧ Ask(G(X)) == trueU(X) = U(X)sCCP, SVi = SVi − 1, SVj = SVj + 1

Si è deciso di implementare le transizioni in maniera da renderle il più sem-plici possibile. In altre parole una transizione gestisce praticamente solo lapropria esecuzione e il proprio refresh, per il resto fornisce i dati al sistemache si adegua di conseguenza.Durante la fase di costruzione del Transition System vengono costruite letransizioni e tutte le strutture dati che verranno elaborate successivamente.Tra queste viene creato un vettore di double (di lunghezza pari al numerodelle de�nizioni) che contiene le State Variables. Queste sono così accessibilia tempo costante, senza alcuna ricerca. Ad ogni transizione vengono associa-te due State Variables: quella della de�nizione a cui appartengono e quelladella de�nizione che hanno nella Call.Oltre a ciò è stato creato un oggetto che permette di sapere quali sono letransizioni di cui va fatto il refresh a partire dall'ultima transizione eseguita.Questo è molto importante perchè rende il singolo passo molto più veloce.Al momento dell'inizializzazione, al Transition System viene passato l'elen-co degli Agenti attivi e questo setterà di conseguenza i valori delle StateVariables (se ci sono tre copie del primo agente attive inizialmente, SV[1]sarà uguale a 3). A questo punto possiamo de�nire il ciclo di base di unoStep all'interno del Transition System (Rate è il valore scelto dal RuntimeManager):

Scegli Transizione T a Partire dal Rate

Esegui Transizione T

Decrementa SV[T.ToDecr] //"Uccide" un agente

Incrementa SV[T.ToIncr] //"Crea" un agente

for each Transizione Influenzata da T

Aggiorna RateTree

Aggiorna Transizione

Per quanto riguarda il Runtime Manager il codice è simile a quanto visto:

if (IsWorkEnded è vero) return;

Ottieni il Rate Totale

Esegui(Rate Totale * Rand(0,1))

Aggiorna il tempo

if (Il tempo passato supera la precisione)

Aggiorna GraphData

Si vede subito che manca la gestione degli Agenti a Rate In�nito, come daspeci�ca.

57

Rate Tree

Rate Tree è una classe che è stata pensata per incrementare le prestazionidel TDSHA. Sapendo che il numero di transizioni è costante, si è volutocreare un sistema che garantisca delle prestazioni migliori della ricerca linearedell'azione da eseguire. Per questo motivo si è deciso di utilizzare un alberodi ricerca con le seguenti proprietà:

• È un albero binario quasi completo

• Le foglie hanno come valore il rate delle transizioni

• Ad ogni nodo interno viene associata la somma dei valori

L'albero viene creato passandogli tutte le transizioni. Nel momento in cuiviene eseguita una transizione, vengono aggiornati i rate cambiati. Quandoviene modi�cato il valore di una foglia, il cambiamento si propaga �no allaradice dell'albero.Nel momento in cui viene e�ettuata la richiesta per selezionare un'azionedato un rate:

NodoAttuale = Radice

Valore = ValoreInInput

while(NodoAttuale ha figli)

if(Valore < NodoAttuale.FiglioSX.Value)

NodoAttuale = NodoAttuale.FiglioSX

else

Valore = Valore - NodoAttuale.FiglioSX.Value

NodoAttuale = NodoAttuale.FiglioDX

return NodoAttuale

In questo modo la ricerca di una transizione, dato un Rate, procede a velocitàlogaritmica rispetto al numero di transizioni, assumendo che ogni transizionemodi�chi un numero costante di variabili di sistema. Questo non è l'uni-co grande risultato che si ottiene in questo modo: per sapere il Rate totaledel sistema basta semplicemente prendere il valore della radice, evitando lasomma lineare. Nel calcolo del Rate e nell'aggiornamento del Rate stesso vatenuto in considerazione che il numero di transizioni è �sso, mentre il numerodi agenti di un tipo può variare. Una transizione sarà più probabile quantisono gli agenti che possono eseguirla. Questo vuol dire che è proporzionalealla State Variable associata.Supponendo i indice della transizione e j indice della State Variable:

58

λ′i = SV [j] ∗ λi

In questo modo viene rispettata anche la condizione di non eseguibilità delleazioni con State Variable nulla in quanto avranno Rate nullo.Tramite test si è notato un peggioramento delle performance per un numeromolto basso di transizioni. Ci si è subito accorti che l'overload per la gestionedell'albero è più alto del risparmio che questo provoca nella gestione lineare.Per questo motivo è stata introdotta una versione di ITS che si attiva auto-maticamente con poche transizioni e risolve il problema.Come vedremo nel capitolo 5, ITS ha delle prestazioni molto migliori rispettoad sCCP. Bisogna ad ogni modo ricordare che si può utilizzare solo per unsottoinsieme dei programmi sCCP, per cui si paga la performance in perditadi �essibilità.

4.3.3 ParserCS e ParserAM

ParserCS, così come il Constraint Store, sono gli stessi visti per sCCP. Si èpensato di mantenerli uguali in quanto la teoria non aggiungeva vincoli sulConstraint Store.Per quanto concerne ParserAM, questi ha una forma più semplice in quantola grammatica associata a TDSHA prevede un linguaggio più semplice. Nellospeci�co non c'è la possibilità di avere azioni diverse da Guardia -> Chiamatae quindi la lettura del �le XML risulta più semplice.È qui riportato il DTD che i �le XML devono rispettare.

<!DOCTYPE XMLAgentStore [

<!ELEMENT XMLAgentStore ((Agent)+, Initial)>

<!ELEMENT Agent (Choose)>

<!ELEMENT Choose (Choice*)>

<!ELEMENT Choice (Action, Call) >

<!ELEMENT Action (Ask, Tell, Rate)>

<!ELEMENT Ask (#PCDATA)>

<!ELEMENT Tell (Istr)*>

<!ELEMENT Istr (#PCDATA)*>

<!ELEMENT Rate (#PCDATA)>

<!ELEMENT Call (#PCDATA)>

<!ELEMENT Initial (AliveAgent)+>

<!ELEMENT AliveAgent (#PCDATA)>

<!ATTLIST Agent Name CDATA #REQUIRED>

<!ATTLIST AliveAgent Num CDATA #ReQUIRED>

]>

59

4.4 ODE

In questa sezione tratteremo il compilatore e simulatore ODE. Come si èvisto nel primo capitolo, si vuole creare un compilatore che codi�chi codiceridotto sCCP in un sistema di equazioni di�erenziali. Una volta e�ettuatala traduzione in equazioni di�erenziali, basta fornirla al Solver. Nella pri-ma sezione parleremo dei Parser. Nella seconda sezione è stato trattato ilTransition System.

4.4.1 ParserAM e ParserCS

Per la gestione del Constraint Store e del ParserCS ci si è a�dati alle classistandard scritte per sCCP.ParserAM è molto simile a quello visto per TDSHA. La di�erenza è che ilParser deve essere più selettivo per accettare (come chiesto dalla teoria) lasola formula del tipo:

V ar = V ar + k con k ∈ <

Per questo motivo il Parser accetterà solo istruzioni del tipo:

V ar = V ar + kV ar = V ar − kV ar+ = kV ar− = k

Le ultime due sono state introdotte (e funzionano solo in ODE) per sem-pli�care la scrittura.Il Parser traduce ogni Tell scritto nella forma sopra indicata come:

Nome Variabile | Segno | Valore

In questo modo l'utilizzatore può spezzare la stringa in tre parti divise dalsimbolo |, veri�carle ed utilizzarle.

4.4.2 Transition System

Una volta che il De�nition Store ha tradotto i dati del Parser per il Runti-me Manager, questi li passa al Transition System. Questi li trasformerà intransizioni.Per poter risolvere un sistema di equazioni di�erenziali abbiamo bisogno di

60

un Solver. Nel nostro caso la scelta è ricaduta su DotNumerics (non scrittodal tesista).DotNumerics è disponibile all'indirizzo http://www.dotnumerics.com/. Èuna libreria per ambiente .NET che integra molte funzionalità utili all'ana-lista numerico, che si occupa principalmente di Algebra Lineare, EquazioniDi�erenziali e problemi di Ottimizzazione.Questa libreria o�re, per quanto concerne le ODE, quattro solver:

• Explit Runge Kutta

• Implicit Runge Kutta

• Gear s BDF

• Adams-Moulton

Dopo la fase di creazione delle transizioni, vi sono altre due fasi da espletare:l'inizializzazione del sistema e la de�nizione del singolo passo.

Solve

Solve è la funzione che inizializza ed esegue il simulatore. Di seguito ladescrizione in pseudo codice.

Crea Array con valori delle variabili

Crea OdeFunction FUN Con Parametro ODECalculus

Inizializza il sistema con la funzione FUN e il numero di variabili

double[,] sol = Risolvi (variabili, tempo iniziale, tempo finale, precisione)

for each Variabile

if (non è una State Variable)

Aggiungila al dizionario

return dizionario

ODECalculus

ODECalculus è la funzione che viene richiamata dal solver per ogni step chedeve e�ettuare. Bisogna ricordarsi che il solver è DotNumerics e il ConstraintStore è muParser o Flee: questo implica che non condividono variabili e ri-ferimenti. Per poter mantenere il sistema in stato di coerenza, ad ogni stepdevo aggiornare i rispettivi valori. Per trasformare le transizioni in equazioniprocediamo nel modo seguente:

61

Crea double[] F della lunghezza pari al numero di variabili

Aggiorna il Constraint Store con il valore attuale delle variabili

Incrementa lo stepnumber

for each Transizione T

T.Refresh(stepnumber)

RateTransizione = RateT * StateVariableAssociata

for each Update in T

Update.Variabile += Update.k * RateTransizione;

ritorna F

62

Capitolo 5

Test

In questo capitolo prenderemo in considerazione alcuni programmi scritti inSCCP (o SCCP ridotto). Di questi programmi analizzeremo l'e�cienza dellasimulazione dei diversi compilatori.Nella prima sezione presenteremo un semplice sistema Client Server pensatoper il compilatore sCCP. In questa sezione verranno fatti dei test prestazio-nali di SCCP.Nella seconda sezione è stato risolto un problema relativo al modello di LotkaVolterra. Useremo questo modello per comparare le performance per i diversicompilatori.Nella terza sezione presenteremo un modello di un sistema di biologia mole-colare, ovvero la sintesi del Glucosio da Lattosio.Nella quarta sezione si è presentato un modello ad Hoc per il confronto delleprestazioni tra sCCP ed ITS.Il calcolatore utilizzato per i Test è un Acer 5920g (2.1GHz, 3MB Cache,3GB Ram).

5.1 Esempio #1: client server

5.1.1 Analisi del problema

In questa sezione sarà descritto uno scenario e la sua descrizione in SCCP.Con questo esempio si è voluta sottolineare la versatilità del linguaggio, ca-pace di descrivere sistemi di diversa natura.In un sistema sono presenti N Client ed M Server, con N ed M positivi ed ar-bitrari. Ogni Client richiede dati ad un Server, il quale li fornisce in risposta.Ogni Server e�ettua un'operazione di Logging delle connessioni che accetta.C'è la possibilità che un Server si rompa: in tal caso e non sarà disponibile

63

per un certo periodo di tempo, durante il quale verrà riparato.Se un Server non risponde entro un certo Timeout, il Client che lo stavainterrogando inoltrerà la query ad un altro Server. Analizzando lo scenario,possiamo identi�care le seguenti azioni:

• Request: Un Client invia una richiesta

• Reply: Un Server risponde ad una richiesta

• Processing: Un Client elaborata l'informazione ottenuta da un Server

• Logging: Un Server fa logging della connessione

• Break: Un Server va in crash

• Repair: Un Server viene riparato

• Timeout: Un Client interrompe l'attesa di una risposta dal Server.

Per de�nire lo stato del sistema abbiamo introdotto le seguenti variabili:

Nome Signi�catoS0 Numero di Server liberiS1 Numero di Server in fase di ReplyingS2 Numero di Server in fase di LoggingSb Numero di Server rottiC0 Numero di Client in fase di richiesta informazioniC1 Numero di Client in fase di attesa dell'informazioneC2 Numero di Client che stanno processando l'informazione

Per ottenere dei valori per il Rate delle azioni si sono fatte le seguentisupposizioni:

• Il rate dell'azione Request proporzionale al numero di Client in attesadi esser serviti e del numero di Server liberi. (λRequest ∝ C0 * S0)

• Il rate dell'azione Reply è proporzionale al numero di Client in attesadella risposta e al numero di Server in fase di Replying. (λReply ∝ C1* S1)

• Il rate dell'azione Log è proporzionale al numero di Server in fase diLogging. (λLogging ∝ S2)

• Il Rate dell'azione Process è proporzionale al numero di Client in fasedi Processing. (λProcessing ∝ C2)

64

• Il rate di rottura di un Server è proporzionale al numero di serverfunzionanti. (λBreak ∝ S)

• Il rate dell'azione Repair è proporzionale al numero di Server rotti.(λRepair ∝ Sb)

• Il rate dell'azioen Timeout di un Client è proporzionale al numero diClient in attesa. (λT imeout ∝ C1)

Relativamente alle costanti di proporzionalità, facciamo le seguenti ipotesi:

• Una rottura del Server è molto meno frequente di una corretta risposta.(kb = 0.001 ∗Krep)

• I server impiegano molto meno tempo nel logging che nel risponderealle richieste dei Client. (klog = 10 ∗ krep).

5.1.2 Modello sCCP

Il modello precedentemente descritto è codi�cato nel seguente codice SCCP.Prima è stato riportato il codice per AM, poi quello per il Constraint Store.

Agent_Definitions

Request :- [(C0 > 0) and (S0 > 0) -> C0= C0-1;

C1=C1+1;S0=S0-1;S1=S1+1 ]@{kr*C0*S0}.Request();

Reply :- [(C1 > 0) and (S1 >0) -> C1=C1-1;C2=C2+1;

S1=S1-1;S2=S2+1 ]@{ka*S1*C1}.Reply();

Processing :- [C2 > 0 -> C2=C2-1;C0=C0+1]@{kp*C2}.Processing();

Logging :- [S2 > 0 -> S2=S2-1;S0= S0+1]@{kl*S2}.Logging();

Repair :- [Sb > 0 -> Sb=Sb-1;S0=S0+1]@{krep*Sb}.Repair();

Break(S = 0) :- [S > 0 -> S=S-1;Sb=Sb+1]@{kb*S}.Break(S);

Timeout:- [C1 > 0 -> C1=C1-1,C0=C0+1]@{Ktimeout*C1}.Timeout();

End_Agent_Definitions

Initial_State

Request || Reply || Processing || Logging || Repair

|| Break(S=S0) || Break(S=S1) || Break(S=S2) || Timeout

End_Initial_State

Non avendo avuto la necessità di utilizzare operatori, constraints o funzionicustom, il codice per il Constraint Store presenta solo de�nizioni di variabilie parametri.

65

Global_Var

S0 =3;

S1 =0;

S2 =1;

Sb = 0;

C0 = 5;

C1 = 2;

C2 = 1;

End_Global_Var

Params

param kr 1;

param ka 1;

param kp 1;

param kl 10;

param krep 1;

param kb 0.001;

param Ktimeout 1;

End_Params

5.1.3 Analisi delle prestazioni

L'esempio precedente è stato utilizzato per e�ettuare un'analisi sulle presta-zioni diversi utilizzi di SCCP.Siamo particolarmente interessati a individuare costo per disegnare i gra�cie la di�erenza di performance tra la versione Batch e versione in tempo reale.Un altro elemento di particolare interesse è valutare la diversa e�cienza trai due Constraint Store implementati (basati su muParser e Flee). A questoscopo sono state predisposte delle analisi per confrontare l'e�cienza sottodiversi carichi di lavoro.

# Sim. # Passi Batch(muP) RT Graph(muP) Batch(F) RT Graph(F)1 1000 3.01s 7.36s 0.12s 2.53s2 1000 3.57s 11.10s 0.22s 4.61s4 1000 6.84s 28.40s 0.43s 7.93s16 1000 54.78s 101.13s 1.91s 24.09s1 10000 32.89s 267.45s 0.86s 128.19s1 100000 334.23s 807.59s 7.72s 401.98sCon muP si intende Constraint Store di tipo muParser, mentre con F si

intende Constraint Store di tipo Flee.

66

Da questa tabella si vede quanto le prestazioni siano in�uenzate, come ovvio,dal numero di simulazioni che vengono fatte. La proporzionalità mostratadai dati è assolutamente in linea con quanto si poteva immaginare. È impor-tante notare il peso che ha la tracciatura di un gra�co in tempo reale: questoin�uenza le prestazioni in maniera considerevole.Il Constraint Store che utilizza Flee è decisamente più veloce e questo si no-ta soprattutto nel comparare i tempi della modalità Batch rispetto all'usodi muparser. Il tempo per singola simulazione, considerando l'esempio di100000 passi in cui l'inizializzazione del sistema incide meno:

Time(muParser) = 3.34 ms/stepTime(Flee) = 0.07ms/step

In altre parole Flee si dimostra circa 50 volte più veloce di muParser.Tracciare il gra�co, soprattutto con molte linee o molti punti, può rallentaredi molto la simulazione. Con muParser sembra avere un impatto minore suitempi, ma se si analizza l'aumento di questi è comparabile solo che sulle cifrebasse di Flee appare più signi�cativo.

5.2 Esempio #2: Lotka-Volterra

Lotka Volterra è uno degli esempi classici di modelli matematici per unsemplice ecosistema preda-predatore.

5.2.1 Analisi del Sistema

Il modello usa le seguenti variabili: y(t) è il numero dei predatori presenti altempo t e x(t) è il numero di prede presenti al tempo t. L'evoluzione tem-porale è usualmente descritta del seguente sistema di equazioni di�erenzialiordinarie.

y′(t) = (Cx(t)−D) ∗ y(t), C > 0, D > 0x′(t) = (Ax(t)−Bx(t)y(t), A > 0, D > 0

Dalle due equazioni si giunge al sistema:dxdt

= (A−By)xdydt

= (Cx−D)yI quattro coe�cienti A,B,C e D rappresentano:A = Tasso di riproduzione delle predeB = Tasso di mortalità delle prede

67

C = Necessità prede per predatoreD = Mortalità predatori

Le azioni che possono venir desunte sono le seguenti:

• Un Predatore si riproduce

• Un Predatore muore

• Una Preda si riproduce

• Una Preda moure

Nel momento in cui si parla di riproduzione per un predatore, si assumeimplicitamente che esso abbia accumulato una quantità su�ciente di cibo perraggiungere l'età fertile. La morte della preda e la nascita di un predatoresono spesso conglobati nella stessa azione.Abbiamo, quindi, tre sole azioni:

1. Predatore si riproduce / Preda Muore (λeat&reproduce ∝ X * Y)

2. Predatore muore (λdie ∝ Y)

3. Preda si riproduce (λreproduce ∝ X)

Dove X e Y sono rispettivamente il numero di Prede e di Predatori, comeindicato ad inizio sezione.

5.2.2 Modello sCCP

Il modello sCCP è il seguente:

Agent_Definitions

Predatore :-

[X > 0 -> Y = Y + 1; X = X - 1]@{Km * X * Y}.Predatore() +

[Y > 0 -> Y = Y - 1]@{Kd * Y}.Predatore();

Preda :-

[X > 0 -> X = X + 1]@{Kr * X}.Preda();

End_Agent_Definitions

Il Constraint Store sarà descritto dal codice seguente:

68

Global_Var

X = 2200;

Y = 1800;

End_Global_Var

Params

param Km 0.005;

param Kd 10;

param Kr 10;

End_Params

Lo stato iniziale è formato da Preda e Predatore in parallelo.

Initial_State

Predatore || Preda

End_Initial_State

5.2.3 Analisi delle Prestazioni

Di questa simulazione verrà fornita un analisi comparativa dei tre compila-tori. Si noti come presentiamo i risultati non rispetto al numero di passi marispetto al tempo simulato. In quanto per il gestore di equazioni di�erenzialiil numero di passi è un concetto diverso rispetto ad SCCP ed ITS. I tempiindicati per tutti e tre i simulatori sono relativi ad un Constraint Store ditipo Flee.

Tempo Finale SCCP ITS ODE0.1 0.31s 0.36s 0.16s1 2.92s 3.26s 0.17s10 33.8s 32.81s 0.77s

È palese dai risultati quanto il compilatore ODE scali meglio con questoesempio. Trattandosi infatti di rate molto alti (basta vedere le formule delsorgente), SCCP ed ITS procedono a passi molto piccoli, dovendone faredecine e centinaia di migliaia per compiere un'unità temporale. Vedremonell'esempio successivo come il compilatore ODE si comporti male in modellicon caratteristiche diverse.Aumentando ancora il tempo, nel modello stocastico si veri�ca inevitabil-mente l'estizione di una delle due specie, se sopravvivono solo predatori, essisi estinguono per assenza di prede, se invece sopravvivono solo le prede, illoro numero va ad in�nito.Generalmente, conviene testare una simulazione con ITS ed ODE su un breveintervallo per scoprire quale dei due scali meglio con il problema che si vuole

69

analizzare.In un esempio con così poche transizioni ITS non riesce a guadagnare moltovantaggio su SCCP, anzi in alcuni casi rimane indietro rispetto al simulatorecompleto. Da come è costruito, ci si aspetta che ITS scali meglio con pro-blemi con un grande numero di transizioni in cui la raccolta del rate ed altreattività risultino molto più celeri di SCCP.

5.3 Esempio #3: Sintesi di Glucosio da Latto-

sio in E-Coli

In questa sezione si è analizzato un sistema completamente diverso dal pri-mo visto: si è voluto infatti mettere l'accento sulla capacità descrittiva dellinguaggio implementato per la simulazione di sistemi completamente diversi.

5.3.1 Analisi del Sistema

Abbiamo descritto una rete genica di controllo della sintesi di glucosio dalattosio in E-Coli, un battere della �ora intestinale. La conversione vieneattivata quando c'è carenza di glucosio o abbondanza di lattosio.Sono coinvolti due geni, il primo produce una proteina che agisce come re-pressore del secondo gene. Il secondo gene produce una proteina coinvoltanel processo di trasformazione del lattosio in glucosio.In questo esempio viene ignorato il livello di glucosio, ponendo l'attenzionesolo sul lattosio. Il repressore è una proteina che si lega ad una porzione delgene del lattosio (operone) ed impedisce all'RNA polimerase di fare il suolavoro (ovvero trascrivere il gene in mRNA, che a sua volta viene tradotto inuna proteina). Il lattosio, però, inibisce il suo repressore, legandosi ad essoe rendendolo inattivo. Si tratta di un classico esempio di controllo mediantefeedback nei sistemi biologici.Vengono identi�cate le seguenti classi di azioni:

• Trascrizione (λTrascrizione ∝ Gene)

• Traduzione (λTraslazione ∝ RNA)

• Complessazione (λComplessazione ∝ Mol1 * Mol2)

• Decomplessazione (λDecomplessazione ∝ Complex)

• Trascrizione (RNAp modellato esplicitamente) (λrnapTranscription ∝ Boun-ded rnap)

70

• Degradazione (λDegradazione ∝ Mol)

• Conversione (λConversione ∝ Mol * Prot)

Il sistema è descritto dalle seguenti variabili:

Nome Signi�catoIdna Gene che codi�ca le proteine che fanno da inibitoriIrna mRNA che viene tradotto nelle proteine inibitriciI Proteine inibitriciOp Regione promotrice del gene che produce la proteina Z,consuma il lattosioRnap RNA polimerase, è la molecola che trascrive il DNA è che si lega ad OpRna mRNA che verrà tradotto nella proteina ZZ Proteina che digerisce il lattosioLactose LattosioILactose Complesso lattosio proteina inibitriceIOp Complesso lattosio operoneRnapOp complesso RNApolmerase operone, dà il via alla trascrizione del gene

5.3.2 Modello sCCP

Il sistema è descritto dal seguente codice SCCP ridotto:

Agent_Definitions

transcription(Gene,Rna,k) :-

[Gene > 0 -> Rna = Rna + 1]

@{k*Gene}.transcription(Gene,Rna,k);

translation(Rna,Protein,k) :-

[Rna > 0 -> Protein = Protein + 1]

@{k*Rna}.translation(Rna,Protein,k);

reversibleBinding(Mol1,Mol2,Complex,k1,k2) :-

[(Mol1 > 0) and (Mol2 > 0) -> Mol1 = Mol1 - 1;Mol2 = Mol2 - 1;

Complex = Complex + 1]@{k1*Mol1*Mol2}

.reversibleBinding(Mol1,Mol2,Complex,k1,k2) +

[Complex > 0 -> Mol1 = Mol1 + 1;Mol2 = Mol2 + 1;

Complex = Complex - 1]@{k1*Complex}

.reversibleBinding(Mol1,Mol2,Complex,k1,k2);

rnapTranscription(boundedRNAP,RNAP, operon,Rna,k) :-

[boundedRNAP > 0 -> boundedRNAP = boundedRNAP - 1;

RNAP = RNAP + 1;operon = operon + 1;Rna = Rna + 1]

@{k*boundedRNAP}.rnapTranscription(boundedRNAP,RNAP, operon,Rna,k);

degradation(Mol,k) :-

71

[Mol > 0 -> Mol = Mol - 1]@{k*Mol}.degradation(Mol,k);

conversion(Mol,Prot,k) :-

[(Mol > 0) and (Prot > 0) -> Mol = Mol - 1]

@{k*Mol*Prot}.conversion(Mol,Prot,k);

End_Agent_Definitions

Con il Constraint Store formato dalle sole de�nizioni di variabili e parametri:

Global_Var

Idna=1;

Irna=0;

I=50;

Op=1;

Rnap=100;

Rna=0;

Z=0;

Lactose=10000;

ILactose=0;

IOp=0;

RnapOp=0;

End_Global_Var

Params

param c1 0.02;

param c2 0.1;

param c3 0.005;

param c4 0.1;

param c5 1;

param c6 0.01;

param c7 0.1;

param c8 0.01;

param c9 0.03;

param c10 0.1;

param c11 0.00005;

param c12 0.01;

param c13 0.002;

param c14 0.01;

param c15 0.001;

End_Params

Ed in�ne lo stato iniziale, dove le classi di azioni modellate come agenti sCCPvengono istanziate come azioni del modelli, passando le opportune variabiliagli agenti.

72

transcription(Idna,Irna,c1) || //InhibitorTranscription

translation(Irna,I,c2) || //InhibitorTranslation

reversibleBinding(I,Lactose,ILactose,c3,c4)||//LactoseInhibitorBinding

reversibleBinding(I,Op,IOp,c5,c6) || //InhibitorBinding

reversibleBinding(Op,Rnap,RnapOp,c7,c8) || //RnapBinding

rnapTranscription(RnapOp,Rnap,Op,Rna,c9) || //Transcription

translation(Rna,Z,c10) || //Translation

conversion(Lactose,Z,c11) || //Conversion

degradation(Irna,c12) || //InhibitorRnaDegradation

degradation(I,c13) || //InhibitorDegradation

degradation(ILactose,c13) || //LactoseInhibitorDegradation

degradation(Rna,c14) || //RnaDegradation

degradation(Z,c15) //ZDegradation

5.3.3 Analisi delle Prestazioni

Sono stati e�ettuati, anche in questo caso, dei test con tutti e tre i simulatori.In tabella i risultati (sempre utilizzando Constraint Store di tipo Flee).

# Simulazioni Tempo SCCP ITS ODE1 1000 0.21s 0.20s 2.60s2 1000 0.24s 0.29s 2.93s4 1000 0.84s 0.56s 6.05s16 1000 3.47s 2.56s 24.33s128 1000 29.56s 21.11s 204.12s

Come ragionevole aspettarsi, in questo esempio si ritrovano alcuni elementicomuni all'analisi delle prestazioni di Lotka-Volterra. Essendo un esempiopiù complesso vediamo come ITS si comporti meglio di SCCP. Il guadagno èconsiderevole e sale assieme alla complessità del programma: se avessimo unproblema con migliaia di transizioni, sicuramente ITS lavorerebbe a velocitàdi ordini di grandezza superiori ad SCCP.

5.4 Esempio 4: Numero elevato di Agenti

In questo semplicissimo esempio vengono testate le performance di ITS edsCCP in un ambiente ad alto numero di agenti. Il programma scritto è ilseguente:

Agent_Definitions

A1 :- [ -> X = X + 1]@{b*X}.A1();

73

End_Agent_Definitions

Initial_State

5000 * A1

End_Initial_State

L'unica variabile globale è X.

Tempo SCCP ITS100 18.21s 0.03s250 45.24s 0.06s500 88.84s 0.11s1000 175.22s 0.20s

In questo semplice esempio si vede la maggior e�cienza di ITS in manieralampante. Avendo il sistema molti agenti, operazioni come il calcolo del Ratein sCCP risultano molto dispendiose. In ITS, invece, queste rimangono co-stanti e proporzionali al numero di transizioni e non al numero degli agenti.In particolare anche l'operazione di scelta dell'agente è molto dispendiosa insCCP e istantanea in ITS. Nello speci�co, la scelta dell'agente costa:

sCCP: ∝ #AgentiITS: ∝ log (#Agenti)

Mentre il calcolo del rate costa:

sCCP: ∝ #AgentiITS: const

Ad ogni modo va ricordato che in ITS va sommato il peso dell'aggiorna-mento dell'albero stesso, ma anche questo è logaritmico e quindi di pocoimpatto.

74

Capitolo 6

Conclusioni

Il lavoro si è concentrato sulla creazione di un framework funzionante e ver-satile per la simulazione di programmi sCCP.Il programma è, ad oggi, funzionante e privo di bug che ne pregiudichino ilfunzionamento, completo o parziale.Il lavoro per la progettazione e realizzazione del Software ha richiesto circasei mesi di lavoro da parte del candidato. Durante questi sei mesi di lavoroson state prodotte quasi 20.000 righe di codice e oltre 250 classi.Le prestazioni dei compilatori permettono di e�ettuare simulazioni di realeinteresse in tempi relativamente brevi.Sono state fatte delle veloci comparative con Dizzy (software gratuito perl'analisi biologica) e le performance posson considerarsi comparabili. Il co-dice per la descrizione degli agenti è relativamente semplice e alla portata ditutti, nonostante ciò non è banale e probabilmente questo documento nonpuò ritenersi una documentazione su�ciente per un utente che voglia utiliz-zare il software senza conoscere il linguaggio sCCP.Deve ancora venir svolto del lavoro in merito alla segnalazione degli errori,in certi casi troppo stringati o assenti.Ad ogni modo l'esperienza è stata sicuramente utile a livello formativo, inquanto ha messo il tesista di fronte alla creazione di un progetto in tutte lesue fasi, dall'analisi alla progettazione �no allo sviluppo e il test dello stesso.

75

Bibliogra�a

[1] Luca Bortolussi (2007). Constraint-based Approaches to

Stochastic Dynamics of Biological Systems, PHD Thesis,Editrice Universitaria Udinese.

[2] Horst Reichel (2003). Formal Models of Concurrency

[3] K. Apt. (2003). Principles of Constraint Programming,Cambridge University Press

[4] Luca Bortolussi (2006). Stochastic Concurrent Constraint

Programming, In proceeding of 4th International Work-shop on Quantitative Aspects of Programming Languages,QAPL, ENTCS, volume 164, pagine 65-80

[5] Luca Bortolussi e Alberto Policriti. Dynamical Systems

and Stochastic Programming: To Ordinary Di�erential

Equations and Back

76