UNIVERSITA DEGLI STUDI DI TRIESTEFACOLTA DI INGEGNERIA

Corso di Laurea Triennale in Ingegneria dell’Informazione

Tesi di Laurea inReti di Calcolatori

Progetto e realizzazione di unostrumento per la modifica

sistematica di codice JavaScriptfinalizzato al testing

LAUREANDO RELATORE

Dennis Morello prof. Alberto Bartoli

CORRELATORI

prof. Eric Medvetdott. Andrea De Lorenzo

Anno Accademico 2012/2013

Ai miei cari

Indice

1 Introduzione 1

2 Scenario 32.1 Scopo del progetto . . . . . . . . . . . . . . . . . . . . . . 32.2 Language parsing . . . . . . . . . . . . . . . . . . . . . . . 3

2.2.1 Grammatiche . . . . . . . . . . . . . . . . . . . . . 42.3 ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3.1 Cos’e ANTLR? . . . . . . . . . . . . . . . . . . . . 52.3.2 Grammatiche ANTLR . . . . . . . . . . . . . . . . 6

2.3.2.1 Lexer Grammar . . . . . . . . . . . . . . 72.3.2.2 Parser Grammar . . . . . . . . . . . . . . 82.3.2.3 Tree Grammar . . . . . . . . . . . . . . . 8

2.4 Abstract Syntax Tree . . . . . . . . . . . . . . . . . . . . 9

3 Progettazione 113.1 Specifiche del problema . . . . . . . . . . . . . . . . . . . 113.2 Manipolazione di codice sorgente . . . . . . . . . . . . . . 11

3.2.1 Da codice sorgente ad AST . . . . . . . . . . . . . 113.2.2 Manipolazione di AST . . . . . . . . . . . . . . . . 133.2.3 Da AST a codice sorgente . . . . . . . . . . . . . . 15

4 Implementazione 174.1 Impiego di ANTLR . . . . . . . . . . . . . . . . . . . . . . 17

4.1.1 ANTLRWorks . . . . . . . . . . . . . . . . . . . . 174.2 Ordinamento di un vettore . . . . . . . . . . . . . . . . . 18

4.2.1 BubbleSort . . . . . . . . . . . . . . . . . . . . . . 194.2.1.1 Pseudo-codice di BubbleSort . . . . . . . 19

4.3 Prove eseguite . . . . . . . . . . . . . . . . . . . . . . . . . 204.3.1 Generazione casuale di vettori . . . . . . . . . . . . 214.3.2 Ordinamento con BubbleSort originale . . . . . . . 23

v

INDICE vi

4.3.3 Modifica di BubbleSort . . . . . . . . . . . . . . . 244.3.4 Ordinamento con BubbleSort modificato . . . . . . 244.3.5 Indici di prestazione . . . . . . . . . . . . . . . . . 27

5 Risultati 315.1 Situazioni possibili . . . . . . . . . . . . . . . . . . . . . . 31

5.1.1 Ordinamento corretto . . . . . . . . . . . . . . . . 315.1.2 Ordinamento con mutazione non equivalente . . . 31

5.2 Analisi dei risultati . . . . . . . . . . . . . . . . . . . . . . 325.2.1 1000 mutazioni . . . . . . . . . . . . . . . . . . . . 335.2.2 5000 mutazioni . . . . . . . . . . . . . . . . . . . . 345.2.3 Confronto tra i risultati . . . . . . . . . . . . . . . 36

6 Conclusioni 376.1 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . 37

7 Ringraziamenti 39

Capitolo 1Introduzione

Modificare in modo automatico e sistematico il codice sorgente di unprogramma puo essere utile in varie applicazioni, quali ad esempio lacorrezione automatica di bug.

Un modo per raggiungere questo scopo e quello che prevede un ap-proccio evoluzionistico: si generano tante mutazioni casuali al codicesorgente originale e, per ognuna di esse, si valutano i risultati e si scegliela soluzione migliore.

A tal fine, e necessario mettere a punto uno strumento che autonoma-mente esegua modifiche al codice, che si occupi di eseguirlo e che analizzii risultati conseguiti, confrontandoli con quelli attesi.

In questa tesi e stato progettato e sviluppato uno strumento utilein questo ambito, in particolare, uno strumento in grado di misurarel’impatto che una modifica al codice sorgente di un programma producesul suo output, nel senso che verra illustrato dettagliatamente nei capitolisuccessivi.

1

Capitolo 2Scenario

Verranno affrontati in questo capitolo alcuni argomenti preliminari everra chiarito lo scopo del lavoro di tesi.

2.1 Scopo del progetto

Lo scopo di questo lavoro e quello di determinare le conseguenze pro-dotte da mutazioni successive nella struttura del codice sorgente di unafunzione JavaScript.

2.2 Language parsing

Prima di affrontare l’argomento che da il nome a questo paragrafo, enecessario introdurre alcuni concetti.

Un linguaggio naturale si definisce a partire da un alfabeto; con i suoisimboli e possibile formare un insieme di sequenze, dette parole, ma nontutte le sequenze sono parole del linguaggio naturale.

La grammatica del linguaggio fornisce le regole per decidere qualisequenze sono parole del linguaggio.

Le parole del linguaggio naturale possono essere raggruppate in insie-mi detti frasi, ma anche qui non tutte le frasi appartengono al linguaggio.

La sintassi del linguaggio fornisce le regole per decidere quali sequen-ze sono frasi del linguaggio (si parla di frasi sintatticamente corrette).

Un linguaggio di programmazione e un linguaggio artificiale; per po-terlo definire e necessario dare ancora qualche definizione.

Dato un insieme finito non vuoto V (chiamato solitamente alfabeto),si definisce universo linguistico su V , e si indica con V ∗, l’insieme dellesequenze finite di lunghezza arbitraria di elementi di V .

Un linguaggio L sull’alfabeto V e allora un sottoinsieme di V ∗.

3

2. Scenario 4

Nel considerare i linguaggi di programmazione, non siamo interessatia tutti i possibili sottoinsiemi di V ∗, ma solo a quelli definibili in manierafinita; questa descrizione puo essere, per esempio, fornita attraverso unagrammatica (si veda il paragrafo successivo).

Una volta definita la grammatica, per language parsing si intende ilprocesso di analisi di stringhe di simboli, in accordo con quanto sancitodalla grammatica.

Qui non si intende risalire al significato di una sequenza di caratteri,ma semplicemente riconoscere ed isolare alcune sequenze (che in ambitooperativo vengono chiamate token).

2.2.1 Grammatiche

In informatica, una grammatica G e definita da

• Un alfabeto V di simboli terminali

• Un alfabeto N di simboli non terminali

• Un assioma S ∈ N tale che V ∩N = ∅

• Un insieme finito di regole sintattiche P del tipo X → α, doveX ∈ N e α ∈ (N ∪ V )∗ e si legge “X produce α”

Se in una grammatica vi sono piu regole aventi la stessa parte sinistra,ad esempio

X → α1 X → α2 · · · X → αn

allora esse sono raggruppate usando la convenzione notazionale

X → α1 | α1 | · · · | αn

La descrizione della grammatica di un linguaggio di programmazioneavviene per mezzo di un metalinguaggio formale1 che prende il nomedi BNF (Backus-Naur Form, dai nomi dei due studiosi che per primil’hanno introdotta negli anni ’50) e sue varianti.

Il formalismo BNF viene spesso usato non nella sua forma originale,ma utilizzando alcune estensioni che permettono una scrittura piu concisadelle grammatiche; si parla allora di EBNF (Extended BNF - non ci siaddentrera nei dettagli, per maggiori informazioni si rimanda all’indirizzohttp://www.cs.cmu.edu/∼pattis/misc/ebnf.pdf).

1Un metalinguaggio e un linguaggio usato per parlare di un altro linguaggio.

5 ANTLR

2.3 ANTLR

2.3.1 Cos’e ANTLR?

ANTLR2 (ANother Tool for Language Recognition) e uno strumentosoftware tipicamente impiegato nella definizione di linguaggi formali enella costruzione di strumenti che operino su di essi, come traduttori,compilatori o analizzatori di codice sorgente; permette, tra le altre cose,di generare parser di testo e Abstract Syntax Trees (AST) per mezzodella definizione di grammatiche.

Una grammatica ANTLR e un file di testo contenente una successionedi regole che stabiliscano come interpretare il flusso di byte da analizzare(per maggiori dettagli vedasi il paragrafo 2.3.2).

Per ogni file di grammatica, ANTLR genera alcuni file sorgenti Java(ma e possibile, mediante l’inserimento dell’opzione language=x all’inter-no della grammatica, generare file sorgenti nello specifico linguaggio x; lalista dei linguaggi supportati da ANTLR 3 e disponibile all’indirizzo http://www.antlr.org/wiki/display/ANTLR3/Code+Generation+Targets/) che ver-ranno poi utilizzati dall’applicazione sviluppata.

I file sorgenti generati da ANTLR fanno riferimento a strumenti chericonoscano, analizzino e trasformino dati di input la cui struttura siastata meticolosamente descritta nella grammatica; tali strumenti sonosostanzialmente i seguenti:

LexerViene generato a partire dal file contenente la lexer grammar; leggeuna sequenza di byte (siano essi caratteri o dati binari), li dividein token secondo i pattern specificati (si veda il paragrafo 2.3.2.1)e genera una sequenza di token come output; alcuni di essi (comespazi vuoti o caratteri di punteggiatura) possono essere ignorati edomessi dall’output.

ParserViene generato a partire dal file contenente la parser grammar;legge una sequenza di token generata dal lexer e li raggruppa infrasi del linguaggio considerato secondo le regole specificate (par.2.3.2.2); puo inoltre eseguire alcune azioni aggiuntive, come raffina-re le frasi prodotte, emettere del testo a seconda dei token incontrati(tipico comportamento di un traduttore) o generare un AST chevenga poi manipolato per modificare la struttura del linguaggio (equesto l’uso di ANTLR che e stato fatto nel presente lavoro di tesi).

Tree ParserViene generato a partire dal file contenente la tree grammar; visita

2http://www.antlr.org/

2. Scenario 6

l’albero generato dal parser e, per ogni nodo incontrato, esegue leoperazioni eventualmente descritte nella relativa grammatica (par.2.3.2.3). Tali operazioni possono essere principalmente output ditesto o manipolazione di altri nodi.

2.3.2 Grammatiche ANTLR

Come accennato nei paragrafi 2.2.1 e 2.3.1, una grammatica ANTLRe una sequenza di regole che descrivono ciascuna un sottoinsieme dellasintassi del linguaggio; assieme ad esse, una grammatica contiene il suotipo (lexer grammar o tree grammar), il suo nome, alcune opzioni, edeventualmente altre sezioni come la specifica di token, attributi e azioni:

grammarType grammar name;

<<options>>

<<tokens>>

<<attributes>>

<<actions>>

rule1 : ... | ... | ... ;

...

ruleN : ... | ... | ... ;

La sintassi con cui vengono specificate le regole in ANTLR riprende lanotazione Extended Backus-Naur Form (EBNF, si veda paragrafo 2.2.1).

In analogia a quanto avviene in Java nella corrispondenza tra il nomedi una classe e quello del file che la contiene, in ANTLR il nome dellagrammatica deve essere uguale al nome del file in cui e memorizzata; ifile di grammatica hanno usualmente estensione g.

La regola da cui inizia il parsing e chiamata regola di partenza (ogniregola puo esserlo); ogni regola consiste a sua volta in una o piu alterna-tive, che altro non sono che sotto-regole; l’ordine con cui si susseguono eininfluente.

A titolo di esempio, una regola chiamata variableDefinition po-trebbe avere due alternative, la prima per una semplice definizione divariabile (ad esempio var x;) e la seconda per una definizione con ini-zializzazione (var x=12;):

variableDefinition

: declaration

| declarationWithInitialization

;

Da una generica grammatica T contenuta nel file T.g (supponendoche il linguaggio di programmazione scelto per lo sviluppo del progetto

7 ANTLR

sia Java), ANTLR genera i file sorgenti TLexer.java e TParser.java iquali contengono, rispettivamente, il lexer ed il parser per il proprio lin-guaggio; se sono stati specificati dei token immaginari (ridenominazionedi sequenze di caratteri utilizzabili all’interno della grammatica, come adesempio EQUALS=’=’;), essi vengono memorizzati nel file T.tokens.

Nei paragrafi seguenti si analizzeranno le tre tipologie di grammatichedefinibili in ANTLR.

2.3.2.1 Lexer Grammar

Scopo della lexer grammar e quello di definire come debbano essere co-struiti i token a partire dall’analisi in prima battuta dell’input assegnato.

Un token e, nell’accezione tipica, un insieme di caratteri che rispettiuna particolare regola definita nella lexer grammar. Ad esempio, volen-do riconoscere tutti i numeri interi senza segno di lunghezza arbitrariache abbiano come prima cifra un carattere diverso dallo zero, potremmodefinire la regola seguente:

INT : (’1’..’9’)(’0’..’9’)* ;

dove il carattere * indica che il gruppo (’0’..’9’) puo comparire zeroo piu volte.

Una volta definite le regole3 per il riconoscimento dei token desiderati,ogni successione di caratteri che abbia senso per la lexer grammar daraorigine ad un token; se tra le regole definite vi fosse la regola INT descrittanell’esempio sopra, la sequenza di caratteri 0x032C produrrebbe il token32.

Fatte queste premesse, e possibile affermare che la lexer grammar euna sequenza di modi di riconoscere i token d’interesse:

grammar T;

...

RULE_1 : ... | ... | ... ;

...

RULE_N : ... | ... | ... ;

La costruzione dei token e indispensabile per il passaggio successivo,quello che vede come protagonista il parser.

Terminata la stesura di questa grammatica, ANTLR genera il fi-le TLexer.java, che potra poi essere utilizzato nel progetto che si stasviluppando (T e il nome della grammatica dell’esempio).

3Per convenzione, i nomi delle regole della lexer grammar sono tutte maiuscole.

2. Scenario 8

2.3.2.2 Parser Grammar

Una parser grammar e un insieme di regole necessarie al parser per ri-conoscere particolari sequenze di token generate dal lexer; ad esempio,e possibile riconoscere lo statement return di JavaScript specificando laregola

returnStatement : ’return’ expr ’;’ ;

dove expr e un’opportuna regola.Valgono le stesse considerazioni fatte per la lexer grammar relativa-

mente alle alternative di una regola.Specificando l’opzione output=AST nella sezione options della gram-

matica, e possibile generare l’AST associato al particolare input; pergenerare un nodo dell’AST per la regola returnStatement e sufficientemodificarne la definizione come segue:

returnStatement

: ’return’ expr ’;’ -> ^(’return’ expr)

;

Tale regola genera un nodo che ha per padre la stringa "return" e perfiglio il sotto-albero expr.

Per i dettagli su come vengano definiti gli AST in ANTLR si veda ilparagrafo ad essi dedicato.

Da notare che lexer grammar e parser grammar sono di norma con-tenute in un unico file.

Al termine della stesura della parser grammar, e possibile utilizzareANTLR per generare il file TParser.java.

2.3.2.3 Tree Grammar

La tree grammar e un file contenente una sequenza di regole necessariea riconoscere una determinata struttura di un AST.

In particolare, ciascuna regola specifica la conformazione di un sotto-albero costituito da un padre e uno o piu figli (i quali possono essere aloro volta altri padri o foglie).

Ad esempio, la regola seguente riconosce il sotto-albero che rappre-senta lo statement return:

returnNode

: ^(’return’ expr)

;

E poi possibile eseguire operazioni specifiche in corrispondenza di unnodo che rispetti una determinata regola (ad esempio, emettere del testo

9 Abstract Syntax Tree

come output) inserendo dopo la definizione di un’alternativa un blocco dicodice Java (o comunque nel linguaggio target) racchiuso tra partentesigraffe:

returnNode

: ^(’return’ expr) { System.out.println("Nodo return"); }

;

Questa regola, ogni qualvolta si incontri un nodo return, produrra unastampa a video della stringa "Nodo return".

Una volta scritte e combinate tra loro tutte le regole necessarie, se ilfile contenente la grammatica si chiamasse TWalker.g, ANTLR produr-rebbe il file TWalker.java, necessario al riconoscimento effettivo degliAST la cui struttura e conforme alla grammatica; questo file rappresentaquello che in precedenza e stato chiamato tree parser.

2.4 Abstract Syntax Tree

Un Abstract Syntax Tree e una rappresentazione ad albero della strutturasintattica di un codice sorgente scritto in un particolare linguaggio diprogrammazione.

Ogni nodo dell’albero denota un costrutto presente nel codice sor-gente, sebbene non ne rappresenti fedelmente la sintassi, ma solo le partiessenziali. Ad esempio, le parentesi graffe che racchiudono un blocco dicodice nei linguaggi C-like sono implicite in un AST, e non vi vengonorappresentate.

A titolo esemplificativo, sia dato il seguente codice sorgente Java-Script:

1 function prova(a, b) {

2 var c;

3 if (a+b>9) {

4 c=2;

5 } else {

6 c=0;

7 }

8 return c;

9 }

Il corrispondente AST, generato a partire dalla grammatica TinyJavaScript,e quello riportato in figura 2.1.

2. Scenario 10

Figura 2.1: AST corrispondente al codice JavaScript dell’esempio.

Il nodo nil rappresenta la radice4 dell’albero, il nodo SLIST denotauna successione di statement; tutti gli altri nodi hanno un significatoimmediato.

4Secondo la convenzione adottata da ANTLR.

Capitolo 3Progettazione

La fase progettuale mette in chiaro come si sia scelto di affrontare ilpassaggio da un codice JavaScript ad un altro che differisca dal primosolo per una singola modifica, nel senso che verra definito piu avanti.

3.1 Specifiche del problema

Il problema affrontato prevede di analizzare una singola funzione Java-Script (costituita da un insieme di statement di numerosita arbitraria)e di scambiare le posizioni di due parti di codice scelte “a caso”; neiparagrafi successivi si tratteranno approfonditamente i dettagli di questeoperazioni.

3.2 Manipolazione di codice sorgente

Le manipolazioni nel codice sorgente che verranno qui considerate con-sistono in scambi casuali di nodi dell’AST corrispondente.

Per fare cio e necessario prima analizzare il codice, costruirne il re-lativo AST, eseguire gli scambi e visitare l’AST mutato per generare ilnuovo codice sorgente.

3.2.1 Da codice sorgente ad AST

Il passaggio da codice sorgente ad AST richiede come prerequisito lastesura della grammatica necessaria al riconoscimento dei costrutti Java-Script; a tale scopo e stata scritta la grammatica TinyJavaScript nel fileTinyJavaScript.g utilizzando ANTLRWorks (par. 4.1.1); analizziamobrevemente il suo contenuto.

11

3. Progettazione 12

La prima sezione, denominata options, contiene dei settaggi cheANTLR utilizzera per generare il lexer ed il parser (par. 2.3.1):

1 options {

2 output=AST;

3 ASTLabelType=CommonTree;

4 backtrack=true;

5 }

In particolare, l’opzione output=AST; dice ad ANTLR che l’output delparser sia l’AST corrispondente al codice sorgente ispezionato.

Segue poi la definizione di alcuni token immaginari (par. 2.3.2) cheverranno impiegati all’interno della grammatica:

1 tokens {

2 VAR; // variable definition

3 FUNC; // function definition

4 ARG; // formal argument

5 NEW; // new object

6 CALL; // function call

7 INDEX; // array index

8 SLIST; // statement list

9 FOR; // for cycle

10 COND; // condition in for cycle

11 ITERATE; // iteration in for cycle

12 WHILE_DO; // while cycle

13 DO_WHILE; // do..while cycle

14 IF; // if statement

15 THEN; // then block

16 ELSE; // else block

17 SWITCH; // switch statement

18 DEFAULT; // switch default case

19 RETURN; // return statement

20 }

TinyJavaScript.g contiene sia le regole del lexer (normalmente de-notate con lettere maiuscole) sia quelle del parser.

Prendiamo in esame una delle regole del lexer:

1 ID

2 : (’a’..’z’|’A’..’Z’|’_’)(’a’..’z’|’A’..’Z

’|’0’..’9’|’_’)*

3 ;

Questa regola consente di riconoscere tutte le stringhe di caratteri cheinizino con una lettera minuscola o maiuscola oppure col carattere under-

13 Manipolazione di codice sorgente

score e a cui seguono, eventualmente (l’asterisco al termine del secondogruppo significa appunto che quel gruppo e opzionale), altre lettere ma-iuscole o minuscole oppure numeri oppure caratteri underscore. Qual-siasi altro carattere (punteggiatura, parentesi, ...) non viene preso inconsiderazione da questa regola.

Una regola del parser e invece ad esempio questa:

1 ifStat

2 : ’if’ ’(’ cond=condStat ’)’ mthen=stat (’else ’

melse=stat)?

3 -> ^(IF ^(COND $cond) ^(THEN $mthen) ^(ELSE $melse

?))

4 ;

Si tratta, com’e intuibile, della regola per il riconoscimento di costruttiif-then-else, con l’accorgimento che il ramo else puo essere assente.I caratteri “->” indicano che l’AST generato deve avere la strutturaspecificata come segue: il nodo padre e IF seguito dai figli COND, THEN eELSE. Ciascuno di essi e a loro volta padre di altri sotto-alberi, eccettoil nodo ELSE, il quale puo non avere figli se nel corrispondente codiceJavaScript non e presente il blocco else.

Il parsing del codice inizia dalla regola program mediante le istruzioni

1 ANTLRFileStream stream = new ANTLRFileStream("

BubbleSort.js");

2 lexer = new TinyJavaScriptLexer(stream);

3 tokens = new CommonTokenStream(lexer);

4 TinyJavaScriptParser parser = new TinyJavaScriptParser

(tokens);

5 TinyJavaScriptParser.program_return r = parser.program

();

6 tree = (CommonTree) r.getTree ();

Una volta terminato il parsing, la variabile tree contiene l’ASTgenerato.

3.2.2 Manipolazione di AST

La manipolazione dell’AST inizia specificando quanti scambi di nodidevono essere eseguiti; supponiamo siano in numero n.

Si esegue dunque un ciclo for avente n iterazioni; ad ogni iterazionesi compiono le operazioni seguenti:

3. Progettazione 14

• Si inizia un ciclo while, eseguito fintantoche non venga prodottauna mutazione valida; ogni iterazione di questo ciclo prevede leseguenti istruzioni:

– Vengono generati due numeri casuali interi non negativi k1e k2 che assumono come valore minimo 1 e massimo p, conp numero totale di sotto-alberi; tali numeri costituiscono gliindici dei nodi che verranno selezionati

– Si copia l’AST attuale per consentirne il ripristino in caso discambio non valido

– Si esegue lo scambio del nodo k1 col nodo k2

– Si verifica la legittimita dello scambio; se lo e si esce dalciclo while e si procede con la successiva iterazione del ci-clo for esterno, altrimenti si ripristina l’AST alla situazioneprecedente allo scambio e si ripetono i passi del ciclo while

• A mutazione avvenuta, si visita l’AST per generarne il codice sor-gente JavaScript (paragrafo successivo) e viene scritto il risultatosu un file avente nome ModBubble*.js, con * numero progressivoche va da 0 a n− 1

• Al termine del ciclo for la variabile tree contiene la versionemutata della funzione JavaScript originale

Il codice Java che implementa quanto descritto e

1 CommonTree sree;

2 int index = 0;

3 for (int i=0; i<n; i++) {

4 boolean changed = false;

5 while (! changed) {

6 count = 0;

7 trees.clear ();

8 visitTree(tree);

9 k1 = random.nextInt(count);

10 k2 = random.nextInt(count);

11 sree = copyTree(tree);

12 swapNodes(trees.get(k1), trees.get(k2));

13 changed = (sree.toStringTree ().equals(tree.

toStringTree ()) ? false : true);

14 }

15 writeCodeToFile("ModBubble"+index+".js");

16 index ++;

17 }

15 Manipolazione di codice sorgente

Si noti che la presenza del ciclo while assicuri che vengano eseguitiesattamente n scambi.

La funzione visitTree(t) ispeziona l’AST per calcolarne il nume-ro totale di sotto-alberi e, per completezza, li inserisce nell’ArrayListchiamato trees (definito all’inizio della classe):

1 public static void visitTree(CommonTree t) {

2 if (t.getChildCount () > 0) {

3 for (int i=0; i<t.getChildCount (); i++) {

4 if (down) {

5 count ++;

6 trees.add(t);

7 }

8 down = true;

9 visitTree (( CommonTree) t.getChild(i));

10 }

11 } else {

12 count ++;

13 trees.add(t);

14 down = false;

15 }

16 }

Il metodo writeCodeToFile(s) verra discusso nel paragrafo che se-gue.

3.2.3 Da AST a codice sorgente

Il passaggio da AST a codice sorgente avviene visitando l’albero utiliz-zando l’algoritmo Depth-First Search1.

Si parte dal nodo denominato program e si ispezionano i nodi figli, dasinistra verso destra. Ad ogni visita di un nodo si stampa il suo contenutoe si passa all’ispezione dei figli; al raggiungimento del nodo foglia per quelsotto-albero, si passa ad ispezionare il nodo fratello successivo a quelloche si era preso in esame.

Si procede in questo modo fino a quando tutti i nodi dell’AST sianostati ispezionati.

Una volta terminata la generazione del codice JavaScript, si scrive ilrisultato su un file il cui nome viene specificato dal parametro del metodowriteCodeToFile(s).

1 public static void writeCodeToFile(String name) {

2 CodeStringGenerator cg = new CodeStringGenerator(

tree);

1http://en.wikipedia.org/wiki/Depth-first search

3. Progettazione 16

3 cg.visitTree(tree);

4 cg.writeCodeToFile(name);

5 }

La classe CodeStringGenerator contiene tutti i metodi necessari allagenerazione del codice a partire dall’ispezione dell’AST; tra di essi vi ewriteCodeToFile(s), il cui listato e riportato qui sotto:

1 public boolean writeCodeToFile(String fileName) {

2 if (code.length ()==0) visitTree(tree);

3 try {

4 FileWriter fw = new FileWriter(fileName , false);

5 fw.write(code);

6 fw.close();

7 return true;

8 } catch (Exception e) {

9 return false;

10 }

11 }

Come si vede, se la scrittura e andata a buon fine, il metodo restituisceil valore booleano true, altrimenti restituisce false.

Capitolo 4Implementazione

4.1 Impiego di ANTLR

Il tipico impiego di ANTLR consiste nelle seguenti tre macro-operazioni:

1. Uso del lexer e del parser in serie per analizzare il flusso di dati iningresso, controllarne la conformita alle grammatiche sviluppate e,se non sono stati incontrati errori, generare una rappresentazioneintermedia come l’AST;

2. Opzionalmente, modificare l’AST per mezzo di uno o piu TreeParser (par. 2.3.1);

3. Produrre l’output finale utilizzando un Tree Parser, ad esempio pergenerare codice sorgente modificato.

4.1.1 ANTLRWorks

ANTLRWorks (http://www.antlr3.org/works/) e un IDE per la stesuradi grammatiche ANTLR scritto in Java, originariamente sviluppato daJean Bovet in collaborazione con il prof. Terence Parr.

Sebbene attualmente sia disponibile la versione 2.1 che supporta pie-namente le specifiche di ANTLR 4, si e qui preferito utilizzare la versio-ne 1.5 in quanto e stata specificatamente studiata per ANTLR 3.x (laversione di ANTLR utilizzata nel progetto e la 3.5).

ANTLRWorks fornisce funzionalita quali evidenziazione della sintas-si, creazione dell’albero delle regole, ricerca mediante espressioni regolari,refactoring, suggerimenti in tempo reale, generazione del diagramma de-cisionale, interprete interattivo per il testing delle regole, visualizzazionegrafica di AST, esportazione su file dei diagrammi generati, debugger emolto altro ancora.

17

4. Implementazione 18

Seguono alcuni screenshot dell’applicazione:

Figura 4.1: Scrittura di regole ANTLR.

Figura 4.2: Funzionalita di debugging.

4.2 Ordinamento di un vettore

Come algoritmo su cui eseguire le manipolazioni che verranno piu avantidescritte, e stato scelto un algoritmo di ordinamento di un vettore; nellospecifico, e stato considerato BubbleSort.

19 Ordinamento di un vettore

4.2.1 BubbleSort

L’algoritmo BubbleSort (letteralmente “ordinamento a bolla”) funzionain modo piuttosto intuitivo: dato un vettore di n numeri, si inizia aconfrontare il primo elemento con il successivo; se il primo risulta esseremaggiore del secondo allora avviene uno scambio di posizione, altrimen-ti no. Si procede poi confrontando il secondo con il terzo elemento, siriesegue il confronto ed eventualmente si invertono le posizioni; si ripetequesto procedimento sino al confronto tra il penultimo e l’ultimo elemen-to (dunque n− 1 volte), dopodiche si ricomincia dalla prima coppia delvettore. Si continuano ad eseguire confronti lungo tutta la lunghezza delvettore sino a quando non sono stati eseguiti n(n− 1) confronti totali.

Per meglio spiegarne l’idea, si ricorre ad un esempio: si immagini diavere in mano n carte da gioco francesi e si supponga di volerle ordinare.A tale scopo, si confronti la prima carta con la seconda: se la prima emaggiore della seconda allora la prima carta prende il posto della secon-da e viceversa, altrimenti non avviene alcuno scambio. Si proceda poicon la seconda e la terza carta e si ripeta il confronto; l’intero proce-dimento va ripetuto sino all’ultima carta in mano. A questo punto siavra una successione di carte non ancora completamente ordinata; perraggiungere una situazione di ordinamento globale e necessario rieseguireil procedimento descritto sino a quando la mano di carte risulti ordinata.Un limite superiore al numero di confronti che e necessario eseguire perordinare n carte con questo metodo e appunto n(n− 1).

4.2.1.1 Pseudo-codice di BubbleSort

Si riporta di seguito lo pseudo-codice dell’algoritmo BubbleSort:

bubblesort(v):

u = v

n = length(v)

for i=1 to n do

for j=1 to n-1 do

if u[j]>u[j+1] then

k = u[j]

u[j] = u[j+1]

u[j+1] = k

return u

Come si nota, tale algoritmo non modifica il vettore v originale, maproduce una sua copia ordinata.

In realta, nella presente tesi e stata utilizzata una versione modifi-cata della versione elementare di BubbleSort qui esposta: in effetti, non

4. Implementazione 20

sempre e necessario eseguire n(n− 1) iterazioni prima di giungere all’or-dinamento completo; se si introduce una variabile sentinella che segnalil’assenza di scambi in un’iterazione del secondo ciclo for (e dunque si egiunti prematuramente all’ordinamento), e possibile interrompere i ciclie restituire direttamente il vettore u.

Lo pseudo-codice di questa versione ottimizzata di BubbleSort e ilseguente:

smart_bubblesort(v):

u = v

n = length(v)

for i=1 to n do

flag = false

for j=1 to n-1 do

if u[j]>u[j+1] then

k = u[j]

u[j] = u[j+1]

u[j+1] = k

flag = true

if flag==false then

return u

return u

4.3 Prove eseguite

Il linguaggio di programmazione scelto per l’implementazione di Bubble-Sort e JavaScript.

Nel file BubbleSort.js e stato memorizzato il seguente codice:

1 function bubbleSort(array) {

2 var ordered = copyArray(array);

3 for (var i=0; i<ordered.length; i++) {

4 var flag = false;

5 for (var j=0; j<ordered.length -1; j++) {

6 if (ordered[j]) {

7 var k = ordered[j];

8 ordered[j] = ordered[j+1];

9 ordered[j+1] = k;

10 flag = true;

11 }

12 }

13 if (!flag) {

14 break;

15 }

16 }

21 Prove eseguite

17 return ordered;

18 }

E questo il file di partenza che viene modificato dal cuore del programma(par. 3.2.2).

Per interfacciarsi alle funzionalita richieste e stata creata una paginaHTML divisa in varie sezioni.

La prima sezione contiene un form attraverso cui specificare le carat-teristiche dei vettori da generare casualmente; per casualmente si intendeche ciascuno di essi e costituito da un numero casuale di elementi com-presi tra un valore minimo e uno massimo specificati dall’utente e cheogni elemento dei vettori generati e scelto a caso, con il vincolo che nonvi siano ripetizioni di elementi all’interno dello stesso vettore.

Figura 4.3: Form di generazione casuale dei vettori.

La seconda sezione consente di ordinare i vettori generati con l’algo-ritmo BubbleSort originale, ovvero non ancora mutato.

La terza sezione contiene una drop area in cui trascinare i file conte-nenti le versioni mutate di BubbleSort.

Infine, la quarta ed ultima sezione contiene alcuni grafici relativi al-le performance degli algoritmi eseguiti; i dettagli verranno discussi nelcapitolo relativo all’analisi dei risultati.

4.3.1 Generazione casuale di vettori

Il primo step per la valutazione delle prestazioni degli algoritmi prodotticonsiste nella generazione dei vettori su cui poi lavorare.

Una volta specificati il numero di vettori da produrre, il numero mi-nimo e massimo degli elementi di ciascuno di essi e il massimo valoreche ogni elemento puo assumere (inteso come valore assoluto: speci-ficando 100 come valore massimo, i valori possibili saranno contenuti

4. Implementazione 22

Figura 4.4: Output dei vettori generati.

Figura 4.5: Ordinamento dei vettori con BubbleSort non modificato.

Figura 4.6: Inserimento dei file contenenti versioni mutate di BubbleSort.

nell’intervallo discreto [−100, 100]), la funzione che genera i vettori e laseguente:

23 Prove eseguite

1 function genRandMatrix(rows , colsMin , colsMax , valMax)

{

2 var matrix = new Array(rows);

3 for (var i=0; i<rows; i++) {

4 matrix[i] = genRandArray(colsMin , colsMax , valMax)

;

5 }

6 return matrix;

7 }

La funzione genRandArray(a,b,c) produce un vettore che ha tra a

e b elementi e ciascuno di essi e compreso tra -c e +c; e cosı costituita:

1 function genRandArray(colsMin , colsMax , valMax) {

2 var l = posRand(colsMin , colsMax);

3 var array = new Array(l);

4 var rand;

5 var present;

6 for (var i=0; i<l; i++) {

7 present = true;

8 rand = random(valMax);

9 while (present && i>0) {

10 for (var j=0; j<i; j++) {

11 if (array[j]== rand) {

12 rand = random(valMax);

13 break;

14 } else {

15 if (j==i-1) present = false;

16 }

17 }

18 }

19 array[i] = rand;

20 }

21 return array;

22 }

La funzione posRand(a,b) genera un numero intero casuale compresotra a e b; il ciclo while e la variabile booleana present sono necessarieper assicurarsi che non vi siano elementi ripetuti nel vettore generato; lafunzione random(a) genera un numero intero casuale compreso tra -a e+a.

4.3.2 Ordinamento con BubbleSort originale

Dopo che i vettori siano stati generati, si procede al loro ordinamento conla versione originale di BubbleSort; si ottiene come risultato una copia

4. Implementazione 24

correttamente ordinata dei vettori di partenza.

Si noti che i vettori originali non vengono eliminati: dovranno infattiessere ordinati dalle versioni modificate di BubbleSort.

4.3.3 Modifica di BubbleSort

Partendo dal file BubbleSort.js che contiene il codice JavaScript diBubbleSort originale, si esegue il programma sviluppato per la gene-razione di n versioni mutate di BubbleSort; il funzionamento di taleprogramma e sintetizzabile nei seguenti passaggi:

• Analizza il file BubbleSort.js e dal codice sorgente genera l’AST(par. 3.2.1)

• Esegue n volte quanto segue:

– Sceglie a caso due nodi dell’albero

– Verifica se lo scambio e fattibile (i due nodi non devono esserel’uno l’antenato dell’altro e non devono essere lo stesso nodo)

– Esegue un tentativo di scambio; se lo scambio e andato abuon fine (nel senso che il nuovo albero e conforme alla treegrammar) allora si procede al prossimo scambio, altrimenti siripetono i due passi precedenti fintantoche non venga eseguitouno scambio valido (par. 3.2.2)

– L’AST mutato viene ritrasformato in codice JavaScript ed ilrisultato viene scritto nel file ModBubble*.js, dove al postodel carattere * vi e un numero progressivo compreso tra 0 en− 1 (par. 3.2.3)

• Al termine del ciclo, tutte le mutazioni sono state scritte su file;il programma e stato studiato appositamente per avere la certezzache in ogni caso vi siano esattamente n mutazioni

Il risultato dell’esecuzione del programma appena descritto e una suc-cessione di n file, ciascuno contenente una funzione BubbleSort che diffe-risce da quella contenuta nel file immediatamente precedente e successivosolamente per una modifica al corrispondente AST.

4.3.4 Ordinamento con BubbleSort modificato

L’ordinamento dei vettori con le versioni mutate di BubbleSort iniziatrascinando tutti i file ModBubble*.js all’interno della drop area nellapagina HTML descritta sopra.

25 Prove eseguite

La drop area di figura 4.6 e stata ottenuta mediante l’inserimentodi due tag <div> annidati; il primo funge da contenitore, il secondo eassociato agli eventi necessari alla cattura dei file:

1 <div id="drop_container">

2 <div id="drop_zone">Drop Algorithms Here!</div>

3 </div>

Gli eventi necessari alla cattura dei file sono due: handleDragOver ehandleFileSelect. Il primo serve a rendere l’effetto visivo della dispo-nibilita ad accogliere file durante il loro trascinamento nella drop area,il secondo si occupa effettivamente di leggerli e di eseguire le versioni diBubbleSort in essi contenute.

L’associazione degli eventi alla drop area avviene per mezzo delleistruzioni sottostanti:

1 var dropZone = document.getElementById(’drop_zone ’);

2 dropZone.addEventListener(’dragover ’, handleDragOver ,

false);

3 dropZone.addEventListener(’drop ’, handleFileSelect ,

false);

Il contenuto della funzione handleDragOver() e il seguente:

1 function handleDragOver(evt) {

2 evt.stopPropagation ();

3 evt.preventDefault ();

4 evt.dataTransfer.dropEffect = ’copy ’;

5 }

Il contenuto della funzione handleFileSelect() e invece questo:

1 function handleFileSelect(evt) {

2 evt.stopPropagation ();

3 evt.preventDefault ();

4

5 var files = evt.dataTransfer.files;

6 perfs = new Array(files.length);

7 bubbles = new Array(files.length);

8 fnames = new Array(files.length);

9 w = 0;

10

11 strPerfIndexes = "<h3 >PERFORMANCE INDEXES </h3 >";

12 var txtPerfMatrix = document.getElementById("

txtPerfMatrix");

4. Implementazione 26

13 setHidden(txtPerfMatrix , false);

14

15 for (var i=0, f; f = files[i]; i++) {

16 if (!f.type.match(’javascript ’)) {

17 continue;

18 }

19 var reader = new FileReader ();

20 fnames[i] = f.name;

21 reader.onload = loaded;

22 reader.readAsText(f);

23 }

24 }

Brevemente, la variabile files e di tipo FileList, un vettore dioggetti File i quali sono a loro volta interfacce ai file selezionati. Questefunzionalita sono messe a disposizione dalla File API di HTML5 (http://www.w3.org/TR/FileAPI/).

All’interno del ciclo for viene innanzitutto verificato che il file at-tuale sia effettivamente un sorgente JavaScript; se lo e si procede con leistruzioni successive, altrimenti si passa ad analizzare il prossimo file (sec’e).

L’oggetto reader, istanziazione di FileReader, mette a disposizionela funzionalita di lettura del contenuto del file.

L’istruzione reader.onload = loaded; serve per lanciare la funzio-ne loaded() una volta chiamata reader.readAsText(f);.

La funzione loaded() e proprio quella che estrae il contenuto del file,lo valuta, ne crea un oggetto function e la applica ai vettori da ordinare:

1 function loaded(evt) {

2 var fileString = evt.target.result;

3 bubbles[w] = fileString;

4

5 try {

6 newBubbleSort = eval("("+fileString+")");

7 ordermatrix = matrixOrder(omatrix);

8 var perfArrays = new Array(rows);

9 for (var j=0; j<rows; j++) {

10 perfArrays[j]= perfIndexArray(bubblematrix[j],

ordermatrix[j]);

11 }

12 perfs[w] = globalPerfIndex(perfArrays);

13 } catch (e) {

14 perfs[w] = null;

15 } finally {

16 strPerfIndexes += fnames[w]+": <b>"+perfs[w]+"</b

><br/>";

27 Prove eseguite

17 w++;

18 txtPerfMatrix.innerHTML = strPerfIndexes;

19 }

20 }

Viene poi calcolato l’indice di prestazione (par. 4.3.5) relativo a quellamutazione di BubbleSort e viene scritto sulla pagina HTML (riga 18)sotto la drop area.

Figura 4.7: Output degli indici di prestazione.

4.3.5 Indici di prestazione

L’indice di prestazione tra due vettori costituiti dagli stessi elementi e quidefinito come media aritmetica delle reciproche distanze tra la posizioneoccupata dall’i-esimo elemento nel primo vettore e la posizione occupatadallo stesso elemento nel secondo vettore:

k =1

n

∑i,j

d(i, j)

Supponendo che il primo vettore sia v = [3, 1, 2] e che il secondo siau = [1, 2, 3], si procede al calcolo del vettore w, in cui l’i-esimo elemen-to rappresenta il numero di posizioni per cui differisce v[i] dallo stessoelemento all’interno di u.

Nel caso in esame, il numero 3 occupa la prima posizione in v e in uoccupa la terza posizione; la distanza vale dunque w[1] = |3− 1| = 2.

Completando il calcolo delle distanze ai due elementi rimanenti, siottiene w = [2, 1, 1], il quale genera un indice di prestazione k pari a(2 + 1 + 1)/3 = 4/3 ' 1, 33.

4. Implementazione 28

Si noti che nel caso in cui k = 0 allora i due vettori sono ordinati allostesso modo (e quindi vi e massima similitudine), mentre all’aumentaredi k aumenta il grado di mutazione nelle posizioni degli elementi.

Detta n la lunghezza dei vettori da confrontare, un limite superioreper k e k = n/2 se n e pari, mentre e k = 2

∑(n− l)/n con l = (n−1), (n−

3), · · · , 2 se n e dispari (situazioni che corrisponderebbero all’inversionetotale delle posizioni degli elementi tra il primo ed il secondo vettore);da queste considerazioni, si puo affermare che

0 ≤ k ≤

{n se n pari

2∑

(n− l)/n se n dispari

Non vi sono situazioni di ambiguita nel calcolo dell’indice k poiche,per come sono stati generati i vettori di partenza (par. 4.3.1), nessunodi essi contiene elementi ripetuti.

Ora che e stato definito l’indice di prestazione relativo ad una singolacoppia di vettori, si puo introdurre la definizione di indice globale diprestazione, denotato con K: esso rappresenta la media aritmetica degliindici di prestazioni kr relativi a tutti i vettori generati:

K =1

n

n∑r=1

kr

Questo indice e significativo in quanto, data una mutazione τ diBubbleSort originale, K rappresenta sinteticamente la correttezza delrisultato rispetto a quello desiderato.

Diremo che τ e una mutazione equivalente se, per ogni vettore d’in-gresso, il risultato prodotto e uguale a quello di BubbleSort originale. Intal caso l’indice globale di prestazione Kτ associato a τ vale 0.

Supponiamo, per maggiore chiarezza, che la mutazione τ sia taleche i vettori da esso generati siano ordinati secondo un ordinamentodecrescente1 (ovvero il contrario di quanto faccia BubbleSort originale).Partendo dai vettori

x1 = [1,−3,−6] x2 = [1, 0, 2] x3 = [−6, 7]

l’esecuzione di BubbleSort originale su di essi produrrebbe i vettori

y1 = [−6,−3, 1] y2 = [0, 1, 2] y3 = [−6, 7]

mentre l’esecuzione di τ produrrebbe

z1 = [1,−3,−6] z2 = [2, 1, 0] z3 = [7,−6]

1Si tratta di una situazione prettamente esemplificativa, in quanto una simile mu-tazione e impossibile nel presente lavoro (qui si considerano mutazioni costituite dascambi di nodi dell’AST).

29 Prove eseguite

Per valutare la “bonta” di τ (nel senso di cui sopra) si procede dunqueal calcolo degli indici kr:

k1 = (2+0+2)/3 ' 1, 33 k2 = (2+0+2)/3 ' 1, 33 k3 = (1+1)/2 = 1

e dunque l’indice di prestazione globale associato a τ vale

Kτ = (k1 + k2 + k3)/3 = (1, 33 + 1, 33 + 1)/3 ' 1, 22

Puo capitare, e anzi e una situazione piuttosto frequente, che perqualche τ il risultato della sua esecuzione non sia un vettore: a talproposito si veda il paragrafo 5.1.2.

L’algoritmo per il calcolo dei kr e il seguente:

1 function perfIndexArray(a1, a2) {

2 return Math.round(sumArray(rankArray(a1 , a2))/a1.

length *100) /100;

3 }

dove sumArray(v) restituisce la somma degli elementi del vettore v,mentre la funzione rankArray(a,b) e definita in questo modo:

1 function rankArray(a1, a2) {

2 var matched;

3 var distances = new Array(a1.length);

4 for (var i=0; i<a1.length; i++) {

5 matched = false;

6 for (var j=0; j<a2.length && !matched; j++) {

7 if (a1[i]==a2[j]) {

8 distances[i] = Math.abs(i-j);

9 matched = true;

10 }

11 }

12 }

13 return distances;

14 }

Per quanto riguarda infine il calcolo dell’indice globale di prestazioneKτ , l’algoritmo che lo calcola e il seguente:

1 function globalPerfIndex(perfArray) {

2 return Math.round(sumArray(perfArray)/perfArray.

length *100) /100;

3 }

dove il vettore perfArray contiene tutti gli indici kr.

Capitolo 5Risultati

In questo capitolo verranno discussi i risultati ottenuti a fronte dell’ese-cuzione degli esperimenti.

5.1 Situazioni possibili

Si esamineranno nel seguito le situazioni che si possono verificare dopol’esecuzione di una mutazione di BubbleSort originale.

5.1.1 Ordinamento corretto

Il caso di ordinamento corretto si verifica dopo l’esecuzione dell’algoritmoBubbleSort originale o di una sua mutazione equivalente1 τeq.

Come risultato, si avranno dei vettori correttamente ordinati in sensocrescente, degli indici di prestazione kr tutti nulli e un indice globale diprestazione associato all’algoritmo in esame Kτ anch’esso nullo.

5.1.2 Ordinamento con mutazione non equivalente

Se la mutazione τ di BubbleSort non e equivalente, vi sono le seguentisituazioni mutualmente esclusive:

• Errore a runtime: τ produce un errore durante la sua esecuzioneche ne provoca la prematura terminazione

• Output diverso da vettore: τ viene eseguito senza intoppi mal’oggetto restituito non e un vettore

• Output e un vettore: τ viene eseguito senza intoppi e l’oggettorestituito e un vettore non correttamente ordinato

1Si veda il paragrafo 4.3.5.

31

5. Risultati 32

• Ciclo infinito: τ resta bloccato in un ciclo infinito e non terminamai

I primi due casi, seppure rappresentino l’esito della maggioranza degliesperimenti, hanno l’effetto di generare degli indici kr,τ (intendendo contale notazione l’indice di prestazione riferito al vettore r dopo l’esecuzionedi τ) e Kτ non ben definiti; si e scelto quindi di comportarsi nei seguentimodi:

• Errore a runtime: kr,τ = null e Kτ = null

• Output diverso da vettore: kr,τ = NaN e Kτ = NaN

Il caso invece di corretta esecuzione di τ e di output di un vettore(inevitabilmente non correttamente ordinato data l’ipotesi di mutazionenon equivalente) presentera degli indici di prestazione globali e non glo-bali tutti diversi da zero; l’unica situazione in cui essi sono nulli e chetutti i vettori da ordinare siano costituiti da un solo elemento (situazionebanale).

Tali indici saranno tanto piu elevati tanto piu diverso dalla situazioneideale sara l’ordinamento degli elementi dei vettori prodotti.

Infine, nel caso di ciclo infinito, non viene prodotto alcun indice diprestazione, dato che e necessario forzare la terminazione del programma.

5.2 Analisi dei risultati

Per avere un quadro suffucientemente ampio dei risultati ottenuti, sonostati condotti due esperimenti; il primo producendo 1000 mutazioni diBubbleSort, il secondo producendone 5000.

Per ogni esperimento sono stati elaborati due grafici:

• Grafico di tentativi di scambio per mutazione: mostra quantitentativi di scambio si sono resi necessari per passare dalla muta-zione τi alla mutazione τi+1; in ascisse e riportato il numero dimutazione, mentre in ordinate i corrispondenti numeri di scambirichiesti

• Grafico di errori a runtime: mostra quante mutazioni han-no prodotto un errore a runtime e quante invece hanno terminatocorrettamente

Un terzo grafico, detto grafico degli indici globali di prestazione,che mostra l’andamento degli indiciKτ al variare della mutazione τ , non estato incluso nel presente lavoro poiche non fornisce alcuna informazionesignificativa a causa dei risultati ottenuti.

33 Analisi dei risultati

Per entrambi gli esperimenti sono stati presi in esame 30 vettori,ciascuno dei quali costituito da un numero di elementi variabile da 10 a30 e ogni elemento puo assumere valori interi nel range [−100, 100].

5.2.1 1000 mutazioni

Si analizza per prima cosa il numero di tentativi di scambio per muta-zione: dai dati raccolti si osserva che si va da un minimo di 1 tenta-tivo di scambio ad un massimo di 34 tentativi, con una media di 5,14tentativi/mutazione.

0

10

20

30

40

50

0 200 400 600 800 1000

Per quanto riguarda l’esito dell’esecuzione degli algoritmi mutati, eemerso che 968/1000 hanno prodotto errori a runtime terminando prema-turamente, 31/1000 sono stati interamente eseguiti e 1/1000 presentavaun ciclo infinito che ha richiesto la terminazione forzata del programma.

5. Risultati 34

0

100

200

300

400

500

600

700

800

900

1000

Non eseguiti Eseguiti Cicli infiniti

Delle 31 mutazioni che hanno terminato correttamente la propriaesecuzione, solo 2 hanno restituito vettori; si tratta in particolare delleprime 2 mutazioni:

Mutazione Indice Kτ

τ0 6,29τ1 6,30τ2 null

· · · null o NaN

τ999 null

Tabella 5.1: Indici globali di prestazione nel primo esperimento.

Un indice Kτ pari a circa 6 significa che mediamente ogni vettoreordinato da quella mutazione presenta elementi distanti 6 posizioni daquelle che dovrebbero assumere nel caso di ordinamento corretto.

5.2.2 5000 mutazioni

In questo secondo esperimento il numero di tentativi di scambio per mu-tazione sono i seguenti: si va da un minimo di 1 tentativo di scambio adun massimo di 45 tentativi, con una media di 25,92 tentativi/mutazione.

35 Analisi dei risultati

0

10

20

30

40

50

0 1000 2000 3000 4000 5000

L’esito dell’esecuzione degli algoritmi mutati ha evidenziato che 4923/5000hanno terminato prematuramente a causa di errori a runtime, 49/5000sono stati eseguiti per intero e i rimanenti 28/5000 non terminavano acausa di cicli infiniti.

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Non eseguiti Eseguiti Cicli infiniti

Delle 49 mutazioni che hanno correttamente terminato la propriaesecuzione, nessuna di esse ha restituito vettori e dunque gli indici globalidi prestazione assumono tutti o valori null oppure NaN:

5. Risultati 36

Mutazione Indice Kτ

τ0 null

τ1 null

τ2 null

· · · null o NaN

τ999 null

Tabella 5.2: Indici globali di prestazione nel secondo esperimento.

Cio significa che ogni mutazione priva di cicli infiniti non producevettori, per ogni input.

5.2.3 Confronto tra i risultati

Nel primo esperimento, quello che coinvolge 1000 mutazioni di Bubble-Sort, si sono evidenziati risultati piu soddisfacenti rispetto al secondoesperimento, sia in termini di numero medio di tentativi di scambio ne-cessari per passare dalla mutazione τi alla mutazione τi+1 (5,14 contro25,92), sia in termini di numero di mutazioni che hanno prodotto vettori(2 contro 0).

La seguente tabella riassume la situazione:

Esperimento 1 Esperimento 2

Mutazioni coinvolte 1000 5000

Media scambi/mutazione 5,14 25,92

Mutazioni con errori a runtime 96,80% 98,46%Mutazioni eseguite interamente 3,10% 0,98%

Mutazioni con cicli infiniti 0,10% 0,56%

Mutazioni con output vettore 0,20% 0,00%

Tabella 5.3: Comparazione dei risultati.

In ultima analisi, all’aumentare del numero di mutazioni generate di-minuisce la percentuale di mutazioni che producono vettori (solitamentesolo le prime lo fanno).

Non ci si deve stupire del fatto di aver ottenuto una cosı bassa per-centuale di mutazioni pseudocorrette: le modifiche successive effettuateagli AST sono di natura casuale e consistono nello scambio di nodi; cio sitraduce in un codice sorgente che inevitabilmente subisce grandi modifi-che anche per (apparentemente) piccole mutazioni (si pensi ad esempioallo scambio tra la primissima istruzione e lo statement return).

Capitolo 6Conclusioni

L’obiettivo di questo lavoro di tesi e stato quello di studiare gli effettiprodotti da una serie di mutazioni successive nel codice di una funzioneJavaScript sui dati d’ingresso.

Quanto esposto nei capitoli precedenti permette di affermare che taleobiettivo sia stato pienamente raggiunto.

Il software sviluppato permette, infatti, di eseguire un numero a pia-cere di mutazioni su una funzione JavaScript memorizzata su file cheviene chiesta in ingresso; a partire da questa, il software esegue tuttele elaborazioni necessarie e, oltre ai file contenenti le versioni modificatedella funzione originale, produce inoltre una statistica circa il numero ditentativi di scambio eseguiti per ogni mutazione effettiva.

Un secondo software sviluppato in JavaScript si occupa poi di ge-nerare i vettori su cui eseguire i test, di prendere in ingresso l’insiemedei file contenenti gli algoritmi mutati e di generare gli indici globali diprestazione.

6.1 Sviluppi futuri

Una possibile estensione di quanto qui svolto potrebbe essere quella diconsiderare un numero maggiore di mutazioni e lavorare su piu funzioniiniziali, al fine di giungere ad un probabile miglioramento degli indiciglobali di prestazione.

Un’altra strada percorribile che richiede, almeno in prima battuta, lasola scrittura di nuove grammatiche, e quella di prendere in considera-zione altri linguaggi di programmazione.

In ogni caso, in questa tesi la grammatica e stata sviluppata in modotale da isolare ogni singola parte degli statement previsti; e ragione-

37

6. Conclusioni 38

vole pensare che considerando invece statement interi la probabilita digiungere a mutazioni fallimentari diminuisca.

Capitolo 7Ringraziamenti

Desidero ringraziare in maniera sentita il prof. Alberto Bartoliper avermi offerto la possibilita di far parte del suo laboratorio,concedendomi, cosı, di trascorrere un periodoa stretto contatto con il mondo della ricerca.Un grazie al prof. Medvet, o meglio Eric,che si e dimostrato spesso polemico ma sempre costruttivo.Un grazie al dott. De Lorenzo,per noialtri Andrea, sempre disponibilea chiarire tutti i miei dubbi e senza il qualequesto lavoro non sarebbe stato ne meno difficilene piu divertente :PImpossibile dimenticareGiulio e Danielegli altri tesisti che hanno lavoratocon me nel mai banale Machine Learning Lab.Un ringraziamentoche non puo trovare lo spazio appropriatofra le ultime righe di questa tesi,lo devo ai miei amici,vecchi e nuovi,ed ai miei fantastici coinquilini,che hanno allietato il mio passato,che rendono unico il mio presente,e che spero continueranno a farmi donodella loro presenza nel mio futuro.Non mi sembra opportuno ringraziarli ad uno ad uno,perche sarebbe un elenco troppo lungoe soprattutto perche citare i loro nomi

39

Ringraziamenti 40

conferirebbe un ordine implicitoche non renderebbe giustiziae non rispecchierebbei miei sentimenti.Un immenso grazie va ad Alessio,per avermi sostenuto in questo percorsouniversitario, per essersi subıto i mieisfoghi piu o meno fondati ma, soprattutto,per avermi sopportato tutti questi anni e,spero, continuera a farlo per molti anni a venire.Infine, il mio pensiero vaai miei genitorii quali mi hanno dato tuttoun affetto senza limiti,una giusta educazione,un sostegno nei periodi di necessita.. . . ai miei genitoriche hanno favorito le mie passionie che tuttora si prodigano in questa direzione.. . . ai miei genitoriperche credonon avrei potuto averne di migliori.

Come ultimissima cosa vorrei inveceinvitare chi mi ha ripetutamente smontatoe criticato a farsi un esame di coscienza edammettere che, in fondo, qualche torto ce l’avesse.Auguro a costoro di guarire dal bruttomorbo dell’invidia.