A Comparison of Code Fragments

A Comparison of Code Fragments

Naam: E-mail: Studentennummer: Afstudeergraad:

Niels Sluijs [email protected] 0107662 Bachelor of Science

Universiteit: Faculteit: Instituut: Begeleiders:

Universiteit van Amsterdam F.N.W.I. O.W.I.I. BSc. R. Cilibrasi, dr. L. Torenvliet 16 juni 2004

Datum:


0. Inhoudsopgave 0. 1. 2. 3. 4. 5. 6. 7.

Inhoudsopgave Samenvatting Introductie Software Engineering 3.1. Ontwerp 3.2. Ontwerpkeuzes De applicaties 4.1. De testapplicatie 4.2. De plugin Tests 5.1. Testplan 5.2. Testresultaten Conclusies en aanbevelingen Bibliografie

Blz. 2. Blz. 3. Blz. 4. Blz. 7. Blz. 7. Blz. 9. Blz. 14. Blz. 14. Blz. 16. Blz. 20. Blz. 20. Blz. 23. Blz. 32. Blz. 34.

Appendix: A. De opdracht B. Software Engineering B.1. Requirementanalyse B.2. Systeemspecificatie B.3. Uitgangspunten B.4. Risicoanalyse C. De testdatabase D. CD-ROM

Blz. 35. Blz. 36. Blz. 36. Blz. 37. Blz. 38. Blz. 38. Blz. 40. Blz. 42.

-2-


1. Samenvatting In deze scriptie wordt gekeken of het mogelijk is om codefragmenten te clusteren met behulp van de maat ‘Normalized Compression Distance’. Het doel van het clusteren van codefragmenten is om het mogelijk te maken een programmeur te kunnen assisteren bij het programmeren. Onder assisteren wordt hier verstaan dat er een applicatie wordt ontwikkeld die codefragmenten kan aanbieden die eenzelfde bedoeling/structuur hebben als waar de programmeur mee bezig is. Nadat de applicatie ontworpen en ontwikkeld is, worden er tests mee uitgevoerd om te kijken wat de prestaties van de applicatie zijn. Een belangrijke maat voor de bruikbaarheid, dat uit de testresultaten naar voren komt, is de performance van de applicatie, zowel in snelheid als in kwaliteit van de gevonden codefragmenten. Uit de testen blijkt dat de performance van de applicatie geschikt zal zijn om een programmeur te kunnen assisteren.

-3-


2. Introductie De essentie van het hergebruiken van software componenten werd door D. McIlroy in 1968 als eerste erkend, [3]. Sindsdien zijn er al vele methoden verzonnen om het mogelijk te maken om software gedeeltelijk of geheel her te gebruiken. Enkele voorbeelden van zulke methoden zijn: object georiënteerde talen, het opstellen van ‘Application Programmer Interface’, enzovoorts. Veel programmeurs vinden echter elke dag bestaande algoritmen opnieuw uit of implementeren inefficiënte algoritmen tijdens het schrijven van hun programma’s. Het hergebruiken van software, of het staan op de schouders van anderen, kan op dit moment maar in een beperkte mate. Dit komt vooral omdat het vergelijken van stukken code op dit moment niet goed mogelijk is. Conceptual graphs In de scriptie van G. Mishne [4] wordt min of meer gekeken of met behulp van ‘conceptual graphs’ het mogelijk is om codefragmenten in een database op te zoeken. Een ‘conceptual graph’ is een bipartite, gerichte en eindige graaf. Het doel van een ‘conceptual graph’ is het uitdrukken van betekenis in een vorm die logisch, berekenbaar en voor de mens leesbaar is. Het zoeken van een gelijksoortig codefragment in de database gebeurt bij deze methode aan de hand van structuur, die door de ‘conceptual graph’ gedefinieerd wordt. De complexiteit van deze methode is echter relatief gezien erg groot. Uit testresultaten van Mishne blijkt dat het vinden van een codefragment, op een computer met een 1,5 GHz Pentium processor, gemiddeld vijf tot zes minuten duurt. Deze methode is hierdoor niet geschikt als “online” hulpprogramma voor de programmeur. Met “online” wordt hier bedoeld dat een gebruiker een codefragment aanlevert en min of meer direct een antwoord terugkrijgt. Normalized Compression Distance Recentelijk hebben Cilibrasi en Vitányi een methode ontwikkeld genaamd ‘Normalized Compression Distance’ (NCD), [1]. Met deze methode is het mogelijk om data te clusteren. Het clusteren van data wordt gedaan met behulp van compressors. De methode is universeel op alle vormen van data die eenzelfde bedoeling hebben. Cilibrasi, De Wolf en Vitányi hebben de methode onder andere gebruikt bij het clusteren van muziekstukken, [2]. Andere onderzoeksgebieden waarin de methode wordt gebruikt zijn onder andere: het detecteren van SPAM, het detecteren van plagiaat en het clusteren van Turkse krantenartikelen.

-4-

A Comparison of Code Fragments Het idee achter de methode NCD is grofweg gezegd dat als twee objecten meer gemeen hebben, dan kan de één meer beknopt worden geschreven gegeven de ander. De wiskunde achter de methode NCD is gebaseerd op de Kolmogorov complexiteit van een bestand, de lengte in bits van de meest gecomprimeerde versie van een bestand. Helaas is de Kolmogorov complexiteit van een bestand niet berekenbaar. Om toch in staat te zijn de theorie in de praktijk te benaderen wordt voor het berekenen van de NCD gebruik gemaakt van een standaard compressor. Een mooie eigenschap van deze methode is dat zij geen kennis nodig heeft van het probleemgebied waarop de methode wordt toegepast. Ook blijkt de methode robuust te zijn onder verandering van onderliggende compressor: statistische compressor (PPMZ), LempelZiv woordenboek gebaseerde compressor (gzip) en block gebaseerde compressor (bzip2). De resultaten die met deze methode zijn geboekt door de bedenkers, zijn tot nu toe erg goed. Zij zijn instaat geweest om de ‘phylogeny’ van 24 levensvormen te clusteren, zoals deze in de biologie bekend is. Ook hebben zij 36 muziekstukken geclusterd. De muziekstukken waren twaalf pop, twaalf jazz en twaalf klassieke stukken. De groepering na het toepassen van de methode was 12 – 12 – 12 en zover de bedenkers weten is dit correct. De kans dat per toeval deze uitkomsten uit de tests komen is astronomisch klein. De reden waarom de bedenkers denken dat de methode iets merkwaardig doet wordt beknopt weergegeven door Laplace: “If we seek a cause wherever we perceive symmetry, it is not that we regard the symmetrical event as less possible than the others, but, since this event ought to be the effect of a regular cause or that of chance, the first of these suppositions is more probable than the second. On a table we see letters arranged in this order C o n s t a n t i n o p l e, and we judge that this arrangement is not the result of chance, not because it is less possible than others, for if this word were not employed in any language we would not suspect it came from any particular cause, but this word being in use among us, it is incomparably more probable that some person has thus arranged the aforesaid letters than that this arrangement is due to chance.” De ‘Normalized Compression Distance’ (NCD) tussen twee objecten wordt gegeven door: NCD( x, y ) =

C ( xy) min{C ( x), C ( y )} . max{C ( x), C ( y )}

C(xy): de gecomprimeerde lengte van de aaneengeschakelde objecten x en y. C(x): de gecomprimeerde lengte van object x. C(y): de gecomprimeerde lengte van object y. Het resultaat uit NCD is een positief getal 0 P r P 1 + R, dat aangeeft hoe verschillend twee objecten van elkaar zijn. Een kleinere uitkomst betekend dat de objecten meer met elkaar overeenkomen. De R in de bovengrens komt door imperfecties van de compressietechnieken. Voor de meeste standaard compressiealgoritmes zal R niet boven de 0.1 uitkomen. -5-

A Comparison of Code Fragments Een andere formulering van de NCD is het aantal bits van informatie dat niet gedeeld wordt door de twee objecten, voor zover de compressor kan zeggen, per bit informatie dat maximaal gedeeld zou kunnen worden tussen de twee objecten. NCD als methode om codefragmenten te vergelijken Hierboven is aangegeven dat één van de redenen waarom hergebruik van software maar in beperkte mate mogelijk is, omdat het vergelijken van code niet goed mogelijk en/of te complex is. Mishne heeft geprobeerd om met behulp van de ‘conceptual graphs’ methode codefragmenten met elkaar te vergelijken. De reden waarom deze methode niet geschikt zal zijn, is de complexiteit van de methode. Op dit moment is de rekenkracht van standaard computers te gering om met de ‘conceptual graphs’ methode binnen een korte tijd een antwoord te vinden. In dit project zal worden onderzocht of met behulp van de NCD methode een applicatie ontwikkeld kan worden, dat wel geschikt is als “online” hulpprogramma om een programmeur te ondersteunen. Met ondersteunen wordt hier bedoeld dat de applicatie codefragmenten zal aanbieden die eenzelfde bedoeling/structuur hebben als waar de programmeur mee bezig is.

-6-


3. Software Engineering In dit hoofdstuk worden de software engineering aspecten van het systeem behandeld, dat ontwikkeld zal worden. De lezer die geïnteresseerd is in andere software engineering aspecten wordt verwezen naar appendix B Software Engineering. Hier vindt u de requirementanalyse, systeemspecificatie, uitgangspunten en risicoanalyse. Deze software engineering is opgesteld met behulp van kennis die is opgedaan bij het vak Groot Software Project en uit het boek Maciaszek [7].

3.1. Ontwerp De componenten die gespecificeerd zijn in appendix B.2. Systeemspecificatie, zijn tijdens het ontwerpen van de applicatie gebruikt. Database

Application

Filter Comparison tool User code Notify user Text editor

Figuur 3.1.1. Componentenspecificatie: Hier ziet u de componentenspecificatie zoals deze is opgesteld. Met de pijlen wordt aangegeven hoe een codefragment de verschillende componenten van het systeem zal passeren.

Systeem: O1. Het systeem is opgedeeld in twee hoofdonderdelen: a. Database; b. Applicatie; O2. O3.

Database: De component database is de opslagplaats waar de codefragmenten zich bevinden; De component database biedt aan de applicatie de mogelijkheid om in haar data te kijken; -7-

A Comparison of Code Fragments O4.

O5.

O6.

O7. O8. O9.

O10. O11. O12.

O13. O14. O15. O16. O17.

O18. O19. O20. O21. O22. O23.

De component database bevat per codefragment de volgende onderdelen: a. De tekst van het codefragment; b. De gecomprimeerde lengte van het codefragment in bytes; Applicatie: De applicatie is opgedeeld in vijf subcomponenten: a. Text editor; b. User code; c. Filter; d. Comparison tool; e. Notify user; De applicatie zal worden geschreven in de programmeertaal Java. Er zullen echter compressors worden gebruikt die zijn geschreven in de programmeertaal C; Text editor: De component text editor krijgt van het tekstverwerkingsprogramma codefragmenten; De component text editor biedt aan component filter codefragmenten van het tekstverwerkingsprogramma aan; Het tekstverwerkingsprogramma dat de codefragmenten aan de component filter zal aanbieden zal jEdit [11] zijn; User code: De component user code krijgt van de gebruiker codefragmenten; De component user code biedt aan component filter codefragmenten van de gebruiker aan; De gebruiker kan zijn/haar codefragmenten aan de component user code doorgeven door middel van knippen-plakken in een G.U.I.; Filter: De component filter krijgt van component text editor codefragmenten; De component filter krijgt van component user code codefragmenten; De component filter biedt aan component comparison tool codefragmenten; De component filter bewerkt de verkregen codefragmenten, zodat de component comparison tool beter instaat is om codefragmenten met elkaar te kunnen vergelijken; Het programma dat gebruikt zal worden voor de filter is het programma ‘Artistic Style’ [8]; Comparison tool: De component comparison tool krijgt van component filter codefragmenten; De component comparison tool krijgt van component database codefragmenten; De component comparison tool biedt aan component notify user codefragmenten aan; De component comparison tool vergelijkt de aangeleverde code fragmenten met elkaar; De methode dat de component comparison tool zal gebruiken is ‘Normalized Compression Distance’ (NCD); De compressors die gebruikt zullen worden om de NCD te berekenen, zijn: a. Java implementatie van de gzip-compressor; b. C implementatie van de gzip-compressor [10]; c. C implementatie van de bzip2-compressor [9];

-8-

A Comparison of Code Fragments O24. O25.

O26. O27. O28. O29.

De kosten van de codefragmenten worden berekend in component comparison tool; De kostenfunctie van de codefragment is: Cost = NCD + (1/howRecentShown). Notify user: De component notify user krijgt van component comparison tool codefragmenten; De component notify user is in staat om de gebruiker op de hoogte te stellen van gevonden codefragmenten; De component notify user stelt de gebruiker op de hoogte van gevonden codefragmenten. In een apart scherm zullen de gevonden codefragmenten aan de gebruiker worden getoond;

3.2. Ontwerpkeuzes 1. Het systeem is opgedeeld in twee hoofdonderdelen: a. Database; b. Applicatie; Omdat dit project zich alleen richt op het ontwikkelen van de applicatie, en niet het in detail uitwerken van een database, is ervoor gekozen om tijdens het ontwerpen de database en applicatie min of meer apart te definiëren. 2. De component database bevat per codefragment de volgende onderdelen: a. De tekst van het codefragment; b. De gecomprimeerde lengte van het codefragment in bytes; Er is gekozen om naast de tekst van de codefragmenten, ook de lengte van de gecomprimeerde codefragmenten op te nemen. Hierdoor wordt het aantal compressies dat nodig is om de NCD te berekenen verminderd. 3. De applicatie zal worden geschreven in de programmeertaal Java. Hiervoor is gekozen, omdat Java systeemonafhankelijk is en deze programmeertaal in voorgaande vakken het meest bestudeerd is. Er zal echter wel geprogrammeerd moeten worden in de programmeertaal C. Dit moet gedaan worden, omdat voor het berekenen van de NCD gebruik gemaakt wordt van compressors. De compressors zullen waarschijnlijker sneller werken als deze in C zijn geprogrammeerd, in plaats van Java. Ook dient er voor het aanroepen van de filter in C te worden geprogrammeerd worden Om instaat te zijn om te kunnen communiceren tussen de Java en C implementaties dient gebruik gemaakt te worden van de ‘Java Native Interface’, JNI [12].

-9-

A Comparison of Code Fragments 4. Het tekstverwerkingsprogramma dat de codefragmenten aan de component filter zal aanbieden zal jEdit [11] zijn. Voor het geautomatiseerd verkrijgen van codefragmenten uit een tekstverwerker zijn een aantal mogelijkheden: •

Afvangen wat de gebruiker intypt: Het voordeel hiervan is dat de gebruiker in principe geen last ondervindt dat een andere applicatie ‘meeleest’ met wat de gebruiker intypt. Het nadeel echter is dat er veel tekstverwerkers zijn die de programmeur ‘helpen’ bij het schrijven van zijn/haar code. Onder dit ‘helpen’ wordt verstaan dat de tekstverwerker bijvoorbeeld bij een ‘{‘ automatisch een ‘}’ plaatst, of dat op het moment dat er een ‘.’ wordt ingetypt een keuzelijst gegeven wordt met volgende logische stappen waar de gebruiker uit kan kiezen. Deze handelingen zijn dus niet zichtbaar als het toetsenbord wordt afgevangen.

•

De bestanden waar de gebruiker mee bezig is regelmatig op te slaan, of op te laten slaan: Het voordeel hiervan is dat dit voor iedere tekstverwerker werkt, die automatisch per tijdsinterval haar bestanden kan opslaan. Kan een tekstverwerker dit echter niet zelf, dan is het mogelijk om via de ‘Robot’ klasse, van Java, per tijdsinterval een Control + S te laten uitvoeren (indien dit de sneltoets voor opslaan is). Het nadeel hiervan is dat de gebruiker aan de applicatie moet doorgeven in welke bestanden hij/zij zit te werken.

•

Door in de tekstverwerker waarin de gebruiker zijn code genereert, herhaaldelijk een Control + A en Control + C actie te laten verrichten: Het voordeel hiervan is dat voor iedere tekstverwerker die Control + A en Control + C als sneltoetsen heeft, voor ‘alles selecteren’ - kopiëren, hiermee kan werken. Het nadeel hiervan is dat het lastig is om na een Control + A en Control + C door te gaan waar de gebruiker gebleven was met typen. Omdat de actie ‘alles selecteren’ kopiëren nogal vaak zal voorkomen tijdens het programmeren, zal dit door de gebruiker als zeer onprettig worden beschouwd. Een ander nadeel hiervan is dat gebruik gemaakt wordt van het klembord. Indien de gebruiker hier zelf gebruik van wil maken wordt telkens zijn waarde overschreven door de acties Control + A en Control + C.

•

Met behulp van een geheugendump kijken wat de teksten zijn waarmee de gebruiker bezig is: Het voordeel hiervan is dat de gebruiker in principe geen last ondervindt, dat een andere applicatie ‘meeleest’ met wat de gebruiker aan code op het ‘scherm’ heeft - 10 -

A Comparison of Code Fragments staan. Het nadeel hiervan is dat het geheugen niet gemakkelijk bereikbaar en doorzoekbaar is. De stukken code van een tekstverwerker zijn wel terug te vinden, maar dit gebeurt niet overzichtelijk. •

Doormiddel van een plugin te maken voor een tekst editor: Het voordeel hiervan is dat de applicatie ‘weet’ waarmee de gebruiker bezig is en volledige toegang heeft tot de teksten waarmee de gebruiker bezig is. Het nadeel hiervan is dat het programma niet universeel is voor andere tekstverwerkers;

Er is gekozen voor de laatste optie, dus het maken van een plugin voor een tekstverwerker. De tekstverwerker die gekozen wordt moet ‘open source’ zijn, zodat de code gelezen kan worden om een plugin te schrijven. Bovendien zal het voor de plugin een voordeel zijn als de tekstverwerker platformonafhankelijk is. Een tekstverwerker die hieraan voldoet is jEdit [11]. Een voordeel die jEdit met zich mee brengt is dat het veel ondersteuning biedt aan het maken en invoegen van plugins, in de tekstverwerker. 5. De gebruiker kan zijn/haar codefragmenten aan de component user code doorgeven door middel van knippen-plakken in een G.U.I. Dit wil dus zeggen dat de gebruiker in staat is om zelf zijn/haar codefragmenten aan de applicatie door te geven. Er is hiervoor gekozen, omdat de applicatie bezig zou kunnen zijn met een codefragment dat de gebruiker niet interessant genoeg vindt, maar hij/zij zelf wel een codefragment heeft wat wel door hem/haar interessant gevonden wordt. Hierdoor is hij/zij instaat om toch een zoekopdracht te laten uitvoeren met als invoer zijn/haar codefragment. 6. De component filter bewerkt de verkregen codefragmenten, zodat de component comparison tool beter instaat is om codefragmenten met elkaar te kunnen vergelijken. Omdat structuur de essentie van de vergelijkingsmethode is, zou het heel goed mogelijk kunnen zijn dat als de opmaak van de codefragmenten op eenzelfde manier wordt gedaan er beter classificaties kunnen plaats vinden. De filter zal niet de rol vervullen om commentaar uit de codefragmenten te filteren. Dit wordt gedaan omdat commentaar ook een belangrijk deel van de source code is. In een onderzoek is gebleken dat de NCD ook teksten, in verschillende talen, clustert die over hetzelfde onderwerp gaan. Als er dus een beschrijving van de algoritme in

- 11 -

A Comparison of Code Fragments commentaar gegeven staat, zelfs als die door verschillende programmeurs gegeven wordt, is de kans dat de NCD ze dichter bij elkaar brengt als de teksten over hetzelfde gaan groter dan wanneer ze worden weggelaten. 7. Het programma dat gebruikt zal worden voor de filter is het programma ‘Artistic Style’ [8]. Net als bij de keuze voor de tekstverwerker moet het programma, dat de taak van filter zal spelen, ‘open source’ zijn. Hierdoor zal het mogelijk zijn om de filter in de applicatie te verweven. Bovendien moet de applicatie om kunnen gaan met verschillende programmeertalen. Het programma dat hieraan voldoet is Artistic Style. Dit programma ondersteunt de volgende programmeertalen: C, C++, C# en Java. 8. De methode dat de component comparison tool zal gebruiken is de methode ‘Normalized Compression Distance’ (NCD). Een doel van dit afstudeerproject is om twee delen van onderzoek te combineren. Er is al veel onderzoek gedaan in het hergebruiken van software en er is al enig onderzoek gedaan in de methode ‘Normalized Compression Distance’. Er is echter nog geen onderzoek gedaan over het toepassen van de methode ‘Normalized Compression Distance’ voor het hergebruiken van software. 9. De compressors die gebruikt zullen worden om de ‘normalized compression distance’ te berekenen, zijn: a. Java implementatie van de gzip-compressor; b. C implementatie van de gzip-compressor [10]; c. C implementatie van de bzip2-compressor [9]; In het artikel van Cilibrasi en Vitányi [1] zijn twee experimenten terug te vinden die tekstbestanden met elkaar laat classificeren: ‘5.2 Language Trees’ en ‘5.3 Literature’. Bij experiment 5.2 wordt gebruik gemaakt van een Limpel-Ziv - type compressor: ‘gzip’ en bij experiment 5.3 wordt gebruik gemaakt van een block gebaseerde compressor: ‘bzip2’. Omdat codefragmenten in principe ook tekstbestanden zijn, zouden deze twee compressors dus een logische keuze zijn om de compressies mee uit te voeren. De keuze om ook C implementaties van compressors te gebruiken is gedaan, omdat de compressies de ‘bottleneck’ van de applicatie zullen (qua snelheid van het vinden van een resultaat) zijn.

- 12 -

A Comparison of Code Fragments 10. In een apart scherm zullen de gevonden codefragmenten aan de gebruiker worden getoond. Omdat erbij het gebruik maken van een ‘popup’ scherm twee grote nadelen zijn: - Door de meeste mensen wordt een ‘popup’ scherm irritant gevonden, en - Hoe wordt er bepaald of een codefragment relevant is voor de gebruiker? Met andere woorden wat is een goede waarde voor een ‘threshold’, om wel of niet een resultaat te laten zien. Er is dus gekozen om de applicatie, als de gebruiker dit wil, altijd zichtbaar te maken. Hierdoor wordt nadeel één weerlegd. Het resultaat, dat wordt getoond in het scherm, zal het fragment zijn met de laagste ‘kosten’. Het fragment met de laagste kosten hoeft niet het fragment met de laagste NCD te zijn. Dit is gedaan om ervoor te zorgen dat de gebruiker, bij eenzelfde invoer, ook de fragmenten krijgt te zijn die een iets grotere of gelijke afstand hebben. Hierdoor wordt nadeel twee dus weerlegt. 11. De kostenfunctie van een codefragment is: Cost = NCD + (1/howRecentShown). Als ervoor wordt gekozen om alleen het fragment met de kleinste NCD waarde te laten zien, dan zal de gebruiker alleen het eerst gevonden beste antwoord zien. Om het toch mogelijk te maken dat de gebruiker ook antwoorden ziet die dicht bij het codefragment staan wordt er bij de NCD een koste opgeteld. Deze koste is per codefragment afhankelijk van hoelang het geleden is dat het fragment aan de gebruiker getoond is. Is het fragment als laatste getoond, dan is de variabele howRecentShown: 1. Hoe langer het fragment niet is getoond hoe groter howRecentShown wordt. Dit impliceert dus dat de kosten die bij de NCD worden opgeteld naar nul gaan en een fragment wat lang niet is laten zien steeds ‘aantrekkelijker’ wordt om te laten zien.

- 13 -


4. De applicaties In dit hoofdstuk worden de twee applicaties behandeld die gemaakt zijn in dit project. De applicatie die in hoofdstuk 4.1. De testapplicatie wordt besproken is ontwikkeld om de tests mee uit te voeren. Het testplan kunt u vinden in hoofdstuk 5.1. Testplan en de resultaten van de tests kunt u vinden in hoofdstuk 5.2. Testresultaten. De applicatie die in hoofdstuk 4.2. De plugin wordt besproken is een plugin die gemaakt is om het daadwerkelijk mogelijk te maken om een programmeur te assisteren. Indien u de software engineering aspecten van deze applicatie wilt doornemen, dan kunt u deze vinden in hoofdstuk 3. Software Engineering en appendix B. Software Engineering. Indien u geïnteresseerd bent in één of beide applicaties, dan kunt u deze vinden op de CDROM die is bijgesloten in appendix D. CD-ROM.

4.1. De testapplicatie

Figuur 5.1.1: Screenshot van de ‘graphical user interface’ van de testapplicatie.

In Figuur 5.1.1 ziet u een screenshot van de testapplicatie. Hieronder volgt een beschrijving van wat u op Figuur 5.1.1. ziet. Database In het tekstveld van ‘Directory’ kan opgegeven worden waar de database zich op de harde schijf bevindt. De database die hier gebruikt heb is, is de database ‘test_database_java’, voor een beschrijving zie appendix C De testdatabase. In deze applicatie is het noodzakelijk dat de database bestaat uit een map met: bestanden met codefragmenten, en/of mappen, waarin weer mappen en/of bestanden met codefragmenten staan; - 14 -

A Comparison of Code Fragments Met behulp van de knop ‘Load’ kan opdracht aan de applicatie gegeven worden om de database in het geheugen te laden. In het tekstvak achter ‘Time to load (s)’ wordt het aantal seconden weergegeven dat het duurde om de database met codefragmenten in het geheugen te laden. In het tekstvak achter ‘Number of fragments’ wordt het aantal codefragmenten weergegeven dat in het geheugen geladen is. User code Hierin bevindt zich een tekstvak waarin codefragmenten ingevoerd kunnen worden. Dit kan gedaan worden door de codefragmenten in te typen of door gebruik te maken van kopiëren – plakken. Result In het tekstvak van ‘File name’ wordt weergegeven wat de bestandsnaam van het gevonden codefragment is. In het tekstvak komt het resultaat te staan van de beste match die wordt gevonden met het codefragment van de gebruiker en de codefragmenten uit de database. Het resultaat zal dat codefragment zijn, waarvan de kostenfunctie het kleinste getal teruggeeft. Voor de kostenfunctie, zie hoofdstuk 3.1. Ontwerp O25. Bedieningspaneel Met de radiobuttons kan aangegeven worden welke compressor gebruikt moet worden bij het uitvoeren van de compressies. GZIP (J): Indien deze geselecteerd is dan wordt gebruik gemaakt van de gzip compressie methoden zoals deze worden aangeleverd in de package ‘java.util.zip’. GZIP (C): Indien deze geselecteerd is dan wordt gebruik gemaakt van de gzip compressie. Deze compressie is eraan toegevoegd, omdat het vermoede bestaat dat de Java implementatie langzamer, in tijd, is dan een C implementatie. BZIP2 (C): Indien deze geselecteerd is dan wordt gebruikt gemaakt van de bzip2 compressie. Deze compressie is door de heer Cilibrasi, één van de bedenkers van de ‘Normalized Compression Distance’, aangeraden. Echter wordt de compressie niet in Java code uitgevoerd. Dit wordt gedaan door functies aan te roepen die in de programmeertaal C zijn geschreven.

- 15 -

A Comparison of Code Fragments Het verschil tussen de optie GZIP (J) en GZIP (C) is: GZIP (J) wordt door ‘Java code’ uitgevoerd en de GZIP (C) wordt uitgevoerd door functies aan te roepen die in de programmeertaal C zijn geschreven. Met behulp van de keuzebox kan aangegeven worden of bij de vergelijkingen de filter gebruikt moet worden. In het tekstvak van ‘Delay (ms)’ kan in milliseconden worden aangegeven wat de tijd is die moet zitten tussen een antwoord en het begin van een nieuwe ronde vergelijkingen. Met behulp van de knop ‘Compare’ kan opdracht aan de applicatie gegeven worden om de vergelijkingen te starten of te stoppen. De knoppen ‘<’ en ‘>’ dienen ervoor om de gebruiker instaat te stellen om de laatst gevonden antwoorden te bekijken. De grootte van de buffer die hierbij gebruikt wordt is tien codefragmenten. In het tekstvak achter ‘Time to search (s)’ wordt het aantal seconden weergegeven dat het duurde om alle vergelijkingen te maken. In het tekstvak achter ‘Best NCD Score’ wordt de beste NCD waarde weergegeven. Dit is dus de ‘normalized compression distance’ tussen het codefragment dat door de gebruiker werd ingevoerd en het codefragment dat in het tekstvak ‘Result’ zichtbaar is gemaakt. Daarnaast is er nog een combobox met een knop ‘Start’ ernaast. Deze elementen zijn opgenomen om de tests te kunnen starten en uitvoeren.

4.2. De plugin Figuur 5.2.1: Screenshot van de ‘graphical user interface’ van jEdit en de plugin. Hier ziet u een screenshot van de tekstverwerker jEdit en de plugin van dit project.

Hieronder vindt u een beschrijving van wat u allemaal ziet in het scherm van de plugin.

- 16 -

A Comparison of Code Fragments Figuur 5.2.2.: Screenshot van de ‘graphical user interface’ van de plugin. Hier ziet u een screenshot van de plugin van dit project.

In het tekstvak komt het resultaat te staan van de beste match die wordt gevonden met het codefragment van de gebruiker en de codefragmenten uit de database. Het resultaat zal dat codefragment zijn, waarvan de kostenfunctie het kleinste getal teruggeeft. Voor de kostenfunctie, zie hoofdstuk 3.1. Ontwerp O25. In het bedieningspaneel ziet u de knoppen ‘<’ en ‘>’, deze knoppen dienen ervoor om de gebruiker instaat te stellen de laatste gevonden antwoorden te bekijken. Onder de knoppen ‘<’ en ‘>’, vindt u de ‘toggle’-knop ‘Compare’. Met deze knop kan de gebruiker het zoeken naar fragmenten aan of uit zetten. Is het zoeken naar fragmenten aangezet, dan wordt als invoer een fragment genomen uit de code waar de gebruiker op dat moment mee bezig is. In het tekstvak achter ‘File name’ wordt de naam van het bestand weergegeven van het gevonden codefragment. De naam van het codefragment geeft meestal aan wat de bedoeling van het codefragment is. Onder het tekstvak van ‘File name’ vindt u het tekstvak van ‘NCD score’. Hierin wordt de NCD waarde van het gevonden codefragment weergegeven. Met behulp van de knop ‘User Code’ kan de gebruiker een ander scherm openen waarmee hij/zij zelf een codefragment aan het systeem kan doorgegeven. Zie Figuur 5.2.3. Met behulp van dit scherm is het dus voor de gebruiker mogelijk om zelf te bepalen op welk fragment gezocht wordt. Met behulp van de knop ‘Config’ kan de gebruiker een ander scherm openen waarmee hij/zij de instellingen van de plugin kan wijzigen. Zie Figuur 5.2.4. Figuur 5.2.3.: Screenshot van de ‘graphical user interface’ voor het aanleveren van codefragmenten door de gebruiker. Hier ziet u een screenshot van scherm waarmee de gebruiker zijn/haar codefragmenten kan aanleveren.

In het tekstvak kan de gebruiker zijn/haar codefragment invoeren. Dit kan hij/zij doen door bijvoorbeeld te kopiëren - plakken. Als het codefragment is ingevoerd dan kan de gebruiker door op de ‘Submit’ knop te klikken een zoekopdracht laten uitvoeren, met als invoer zijn/haar codefragment. Het resultaat van de zoekopdracht wordt vervolgens weergegeven in de ‘graphical user interface’ van Figuur 5.2.2. - 17 -

A Comparison of Code Fragments Figuur 5.2.4.: Screenshot van de ‘graphical user interface’ voor het aanpassen van de instellingen van de plugin. Hier ziet u een screenshot van scherm waarmee de gebruiker de instellingen van de plugin kan aanpassen.

Met het selectievakje ‘Start comparisons after plugin is loaded’ kan aangegeven worden of de plugin moet worden gestart bij het opstarten van jEdit. In het tekstvak achter ‘Database’ kan de gebruiker de directory specificeren waar zich de database met codefragmenten bevindt. De gebruiker kan de directory wijzigen door dit in te typen in het tekstvak óf door op de knop ‘Browse’ te klikken en vervolgens een directory te selecteren. Met de radiobuttons achter ‘Compressor’ kan aangegeven worden welke compressor gebruikt moet worden bij het uitvoeren van de compressies. GZIP (J): Indien deze geselecteerd is dan wordt gebruik gemaakt van de gzip compressie methoden zoals deze worden aangeleverd in de package ‘java.util.zip’. GZIP (C): Indien deze geselecteerd is dan wordt gebruik gemaakt van de gzip compressie. Deze compressie is eraan toegevoegd, omdat het vermoede bestaat dat de Java implementatie langzamer, in tijd, is dan een C implementatie. BZIP2 (C): Indien deze geselecteerd is dan wordt gebruikt gemaakt van de bzip2 compressie. Deze compressie is door de heer Cilibrasi, één van de bedenkers van de ‘Normalized Compression Distance’, aangeraden. Echter wordt de compressie niet in Java code uitgevoerd. Dit wordt gedaan door functies aan te roepen die in de programmeertaal C zijn geschreven. Het verschil tussen de optie GZIP (J) en GZIP (C) is: GZIP (J) wordt door ‘Java code’ uitgevoerd en de GZIP (C) wordt uitgevoerd door functies aan te roepen die in de programmeertaal C zijn geschreven. Met behulp van het selectievakje achter ‘Use filter’ kan aangegeven worden of bij de vergelijkingen de filter gebruikt moet worden. Indien dit selectievakje is geselecteerd dan is het mogelijk om een keuze te maken uit de verschillende filterinstellingen (ANSI, K & R, Linux, GNU of Java). In het tekstvak achter ‘Buffer size’ kan de gebruiker aangeven wat de grootte van de buffer is die wordt gebruikt voor het opslaan van de laatste gevonden codefragmenten.

- 18 -

A Comparison of Code Fragments In het tekstvak achter ‘Delay (ms)’ kan in milliseconden worden aangegeven wat de tijd is die moet zitten tussen het beginnen van een nieuwe ronde vergelijkingen. Bij ‘Sliding window’ kan aangegeven worden hoe groot het ‘raam’ is waardoor gekeken wordt bij het automatisch verkrijgen van codefragmenten uit de code van de gebruiker. De code die hieruit verkregen wordt, wordt automatisch vergeleken met de database. Het resultaat van deze vergelijking wordt zichtbaar gemaakt in de ‘graphical user interface’ van Figuur 5.2.2.

- 19 -


5. Tests In dit hoofdstuk wordt als eerste het testplan van het project behandeld. Er zijn zeven testscenario’s gedefinieerd. De uitkomsten van de tests kunt u vinden in het tweede deel van dit hoofdstuk, 5.2. Testresultaten. Alle tests zijn alleen uitgevoerd op de Java testdatabase. Naar verwachting zullen de overige databases zelfde resultaten leveren. Voor een beschrijving van de testdatabase, zie appendix C. De testdatabase. Indien u geïnteresseerd bent in de verschillende invoerfragmenten, dan kunt u deze vinden op de CD-ROM die is bijgesloten in de appendix D. CD-ROM.

5.1. Testplan 1. Wat zijn de verschillen in tijd tussen de verschillende compressiemethoden? Voer voor elke compressor de volgende test uit en geef het resultaat weer in een (frequentie, tijd) - grafiek. De frequentie geeft het aantal keer aan dat het codefragment in een bepaalde tijd is gevonden. Op de horizontale as wordt de tijd weergegeven in honderdsten van seconden. Test: neem uit een document vier verschillende lengtes code. De lengtes van deze fragmenten moeten 10, 20, 40 en 200 regels zijn. Voer voor ieder codefragment, met iedere compressor honderd keer een vergelijking met de gehele testdatabase uit en sla de tijden van de vergelijkingen op. 2. Is in het algemeen de NCD – waarde tussen twee codefragmenten kleiner als de fragmenten gefilterd zijn met eenzelfde instelling? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram. Het histogram geeft op de verticale as de NCD – waarden en op de horizontale as de verschillende filterinstellingen van de codefragmenten weer. Test: neem één paar codefragmenten. Reken voor dit paar de NCD – waarden uit met gebruik van de verschillende filterinstellingen die door het programma Artistic Style [8] geboden wordt. Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C implementatie van gzip, vandaar dat deze niet opgenomen is in de test. De volgende instellingen zijn gedefinieerd in het programma Artistic Style: ANSI, Kernighan & Ritchie, Linux, GNU en Java.

- 20 -

A Comparison of Code Fragments 3. Wat is in het algemeen het verschil in NCD - waarden tussen het wel en niet gebruik maken van de filter? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram. Het histogram geeft op de verticale as het verschil in NCD - waarde en op de horizontale as de verschillende codefragmenten met een andere opmaak weer. Test: gebruik vijf codefragmenten uit hetzelfde document, maar dan ieder met een andere opmaak. Daarnaast is er nog één ander codefragment nodig, om de NCD mee uit te rekenen. Reken per codefragment van verschillende opmaak de NCD - waarde uit tussen het andere codefragment als de filter is ingeschakeld en als de filter is uitgeschakeld. Het verschil in de NCD – waarde met en zonder filter moet worden weergegeven in het histogram. Het filter dat hierbij gebruikt wordt is ANSI, deze levert voor beide compressors een goed resultaat (zie figuren 5.2.4. en 5.2.5.). Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C implementatie van gzip, vandaar dat deze niet opgenomen is in de test. 4. Hoeveel van het originele fragment is nodig om het fragment als beste resultaat terug te vinden in de database? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram. Het histogram geeft op de verticale as weer, wat het percentage dat van het fragment minimaal noodzakelijk is om het fragment als beste resultaat terug te vinden in de database. Op de horizontale as worden de verschillende fragmenten weergegeven. Test: neem tien verschillende codefragmenten uit de database. Voeg net zolang, vanaf boven, een karakter van het fragment toe totdat het fragment gevonden wordt in de database. Er is hier gekozen om vanaf boven karakters toe te voegen, omdat dit min of meer het principe van intypen is. Bovendien moet het eerste resultaat gevonden worden dat minimaal nodig is om het fragment als beste resultaat in de database terug te vinden. Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C implementatie van gzip, vandaar dat deze niet opgenomen is in de test. 5. Hoeveel procent ruis mag erin een codefragment voorkomen, zodat het codefragment toch nog als beste resultaat in de database gevonden wordt? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram Het histogram geeft op de verticale as het percentage ruis in het fragment weer, waarvoor het fragment nog net als beste resultaat wordt gevonden. Op de horizontale as worden de verschillende fragmenten weergegeven.

- 21 -

A Comparison of Code Fragments Test: neem tien verschillende codefragmenten uit de database. Verander per fragment willekeurige karakters net zolang totdat het bijhorende codefragment niet meer in de database als beste resultaat teruggevonden wordt. Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C implementatie van gzip, vandaar dat deze niet opgenomen is in de test. 6. Hoeveel van het originele fragment is nodig om het fragment als beste resultaat terug te vinden in de database, als de helft van de maximale ruis in het fragment optreed? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram. Het histogram geeft op de verticale as weer wat het percentage is dat van het fragment, met de helft van de maximale ruis, minimaal noodzakelijk is om het fragment als beste resultaat terug te vinden in de database. Op de horizontale as worden de verschillende fragmenten weergegeven. De maximale ruis dat in het fragment voorkomt, wordt bepaald door de uitkomsten van test 5. Test: neem tien verschillende codefragmenten uit de database. Verander per fragment de helft van het percentage maximale ruis door willekeurige karakters. Voeg vervolgens net zolang, vanaf boven, een karakter van het fragment toe totdat het fragment gevonden wordt in de database. Er is hier gekozen om vanaf boven karakters toe te voegen, omdat dit min of meer het principe van intypen is. Bovendien moet het eerste resultaat gevonden worden dat minimaal nodig is om het fragment als beste resultaat in de database terug te vinden. Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C implementatie van gzip, vandaar dat deze niet opgenomen is in de test. Nota Bene: de fragmenten die bij deze test gebruikt worden zijn identiek aan de fragmenten van test 4 en test 5. 7. Hoeveel procent ruis mag erbij het codefragment toegevoegd worden, zodat het codefragment toch nog in de database als beste resultaat gevonden wordt? Voer voor de bzip2- en gzip-compressor (beide de C implementatie) de volgende test uit en geef het resultaat weer in een histogram. Het histogram geeft op de verticale as weer wat het percentage ruis is, dat in het codefragment is toegevoegd, waarvoor het fragment nog net als beste resultaat in de database gevonden wordt. Op de horizontale as worden de verschillende fragmenten weergegeven. Test: neem tien verschillende codefragmenten uit de database. Voeg aan het fragment, zowel aan de bovenkant als aan de onderkant van het fragment, willekeurige karakters toe, net zolang totdat het bijhorende codefragment niet meer als beste resultaat in de database teruggevonden wordt. Na verwachting zal de Java implementatie nagenoeg dezelfde resultaten leveren als de C

- 22 -

A Comparison of Code Fragments implementatie van gzip, vandaar dat deze niet opgenomen is in de test.

5.2. Testresultaten 1. Wat zijn de verschillen in tijd tussen de verschillende compressiemethoden? gzip Java 100 90 80

Frequentie

70 10

60

20

50

40

40

200

Figuur 5.2.1. gzip Java: grafiek van de resultaten van test 1 met gzip Java compressor. In de grafiek ziet u de frequentie van matches met codefragmenten op een bepaald tijdstip. De tijdsschaal is hier in honderdsten van seconden.

30 20 10 0 1

12 23 34 45 56 67 78 89 100 111 122 133 144 155 166 177 188 199 Tijd

Modale voorkomen van tijden van gzip Java: - Codefragment met 10 regels: 0,44 seconden; - Codefragment met 20 regels: 0,52 seconden; - Codefragment met 40 regels: 0,64 seconden; - Codefragment met 200 regels: 1,69 seconden; gzip C 90 80 70

Frequentie

60 10

50

20 40

40

200 30 20 10 0 1

12 23 34 45 56 67 78 89 100 111 122 133 144 155 166 177 188 199 Tijd

Modale voorkomen van tijden van gzip C: - Codefragment met 10 regels: 0,42 seconden; - Codefragment met 20 regels: 0,52 seconden; - Codefragment met 40 regels: 0,67 seconden; - Codefragment met 200 regels: 1,91 seconden;

- 23 -

Figuur 5.2.2. gzip C: grafiek van de resultaten van test 1 met gzip C compressor. In de grafiek ziet u de frequentie van matches met codefragmenten op een bepaald tijdstip. De tijdsschaal is hier in honderdsten van seconden.

A Comparison of Code Fragments Figuur 5.2.3. bzip2 C: grafiek van de restultaten van test 1 met bzip2 C compressor. In de grafiek ziet u de frequentie van matches met codefragmenten op een bepaald tijdstip. De tijdsschaal is hier in honderdsten van seconden.

bzip2 C 90 80 70

Frequentie

60 10

50

20 40

40

400 30 20 10 0 1

50 99 148 197 246 295 344 393 442 491 540 589 638 687 736 785 834 883 Tijd

Modale voorkomen van tijden van bzip2 C: - Codefragment met 10 regels: 1, 75 seconden; - Codefragment met 20 regels: 2,05 seconden; - Codefragment met 40 regels: 2,73 seconden; - Codefragment met 200 regels: 9,01 seconden; Zoals te zien in de figuren 5.2.1., 5.2.2. en 5.2.3. is de gzip, zowel de Java implementatie als de C implementatie, sneller dan de bzip2 C implementatie bij invoer van even grote codefragmenten. Opmerkelijk om te zien is dat bij een vrij kleine invoer de gzip C implementatie ten op zichte van de bzip2 C implementatie sneller, in tijd, is en dat naarmate de invoer toeneemt de gzip Java implementatie steeds sneller wordt ten opzichte van de gzip C implementatie (en haar zelfs op een gegeven moment inhaalt). De C implementatie van de gzip compressor is juist gebruikt, omdat aan het begin van het project de verwachting bestond dat een Java implementatie langzamer zou zijn dan een C implementatie. Een verklaring voor het feit dat beide gzip compressors ongeveer dezelfde tijd nodig hebben om te comprimeren is dat in Java de compressor ook door ‘native code’ wordt uitgevoerd. In de map ‘bin’ van de Java Runtime Environment is dan ook het bestand ‘zip.dll’ terug te vinden. 2. Is in het algemeen de NCD – waarde tussen twee codefragmenten kleiner als de fragmenten gefilterd zijn met eenzelfde instelling? gzip C 0.910 0.905 0.900 Fragment 2 Geen

NCD

0.895

Fragment 2 ANSI Fragment 2 KR

0.890

Fragment 2 Linux Fragment 2 GNU

0.885

Fragment 2 Java

0.880 0.875 0.870 Geen

ANSI

KR

Linux

GNU

Java

Lay-out Fragment 1

- 24 -

Figuur 5.2.4. gzip C: histogram van de resultaten van test 2 met gzip C compressor. In het histogram ziet u op de verticale as de NCD waarden en op de horizontale as de verschillende filterinstellingen van de codefragmenten staan.


bzip2 C

0.860 0.850 Fragment 2 Geen

0.840

NCD

Fragment 2 ANSI 0.830

Fragment 2 KR

Figuur 5.2.5. bzip2 C: histogram van de testresultaten van test 2 met bzip2 C compressor. In het histogram ziet u op de verticale as de NCD waarden en op de horizontale as de verschillende filterinstellingen van de codefragmenten staan.

Fragment 2 Linux

0.820

Fragment 2 GNU 0.810

Fragment 2 Java

0.800 0.790 Geen

ANSI

KR

Linux

GNU

Java

Lay-out Fragment 1

Uit de histogrammen van figuren 5.2.4. en 5.2.5. kan worden opgemaakt dat het toepassen van een filter voor de gzip compressor een ander gevolg heeft dan voor de bzip2 compressor. Voor de gzip compressor kan min of meer gezegd worden dat de beste resultaten worden gehaald als op fragment 1 geen filter wordt toegepast. Indien erop fragment 1 toch een filter wordt toegepast, dan is de NCD score lager als op fragment 2 ook een filter wordt toegepast. Echter geldt niet voor de gzip compressor dat als op fragment 1 en 2 eenzelfde compressor wordt toegepast het resultaat daarvan ook de beste NCD score oplevert. Bij de filterinstellingen ANSI voor fragment 1 wordt dit bevestigd. Het beste resultaat wordt hier geboekt als filter Kernighan & Ritchie (KR) of Java wordt gebruikt voor fragment 2. Voor de bzip2 compressor kan gezegd worden dat als op één fragment een filter wordt toegepast, de NCD score beter is als op het andere fragment ook een filter wordt toegepast. Daarnaast kan uit Figuur 5.2.5. geconcludeerd worden dat als op fragment 1 een filter wordt toegepast, dan wordt het beste resultaat gehaald door op fragment 2 hetzelfde filter toe te passen. Als op beide codefragmenten eenzelfde filter wordt toegepast, dan wordt de beste NCD score gehaald als het filter GNU is. Voor beide compressors valt nog wel op te merken dat het gebruik van de filter KR hetzelfde resultaat oplevert als het gebruik van filter Java.

- 25 -

A Comparison of Code Fragments 3. Wat is in het algemeen het verschil in NCD - waarden tussen het wel en niet gebruik maken van de filter? Figuur 5.2.6. gzip C: histogram van de resultaten van test 3 met gzip C compressor. In het histogram ziet u op de verticale as de NCD waarden en op de horizontale as de verschillende codefragmenten met verschillende opmaak.

gzip C 0.905

0.9

NCD

0.895 Zonder Filter

0.89

Met Filter

0.885

0.88

0.875 1

2

3

4

5

Fragment

bzip2 C 0.86 0.855 0.85

NCD

0.845 0.84

Zonder Filter

Figuur 5.2.7. bzip2 C: histogram van de resultaten van test 3 met bzip2 C compressor. In het histogram ziet u op de verticale as de NCD waarden en op de horizontale as de verschillende codefragmenten met verschillende opmaak.

Met Filter

0.835 0.83 0.825 0.82 0.815 1

2

3

4

5

Fragment

Uit de histogrammen van figuren 5.2.6. en 5.2.7. kan worden opgemaakt dat het toepassen van een filter voor de gzip compressor een ander gevolg heeft dan voor de bzip2 compressor. Alleen voor de lay-out in fragment 3 wordt een beter resultaat gehaald als de filter aanstaat voor de gzip compressor. Voor de bzip2 compressor geldt dat het toepassen van een filter het resultaat van de NCD score niet verslechterd, de waarde blijft bij fragment 4 constant en bij de rest van de fragmenten zorgt het filter voor een verbetering. Een ander aspect dat in beide figuren opvalt, is dat voor beide compressors geldt dat het wel of niet toepassen van een filter op de lay-out van fragment 4 geen invloed heeft op de hoogte van de NCD score. Een verklaring zou kunnen zijn: in fragment 4 zijn alle ‘newline feeds’ verwijderd, het filter is niet geavanceerd genoeg om hiervan een opmaak te creëren. Dit fragment ziet er dan dus identiek hetzelfde uit als het filter wel en niet wordt toegepast.

- 26 -

A Comparison of Code Fragments 4. Hoeveel van het originele fragment is nodig om het fragment als beste resultaat terug te vinden in de database? gzip C 60%

50%

Percentage

40% Minimale hoeveelheid van een fragment

30%

Figuur 5.2.8. gzip C: histogram van de resultaten van test 4 met gzip C compressor. In het histogram ziet u op de verticale as het percentage dat minimaal van een fragment nodig is om het fragment terug te vinden als beste resultaat in de database. Op de horizontale as worden de verschillende codefragmenten weergegeven.

20%

10%

0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 C 70% 60%

Percentage

50% 40%

Minimale hoeveelheid van een fragment

30%

Figuur 5.2.9. bzip2 C: histogram van de resultaten van test 4 met bzip2 C compressor. In het histogram ziet u op de verticale as het percentage dat minimaal van een fragment nodig is om het terug te vinden als beste resultaat in de database. Op de horizontale as worden de verschillende codefragmenten weergegeven.

20% 10% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 versus gzip 18% 16% 14%

Percentage

12% 10% Verschil bzip2 en gzip

Figuur 5.2.10. bzip2 versus gzip: histogram van de resultaten van test 4. De gzip resultaten zijn van de bzip2 resultaten afgetrokken. In het histogram ziet u op de verticale as het percentuele verschil en op de horizontale as de verschillende codefragmenten.

8% 6% 4% 2% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

Omdat de fragmenten oplopen qua grote in aantal tekens, kan uit de Figuren 5.2.8. en 5.2.9. opgemaakt worden dat er geen logisch verband bestaat tussen de grote van een fragment en de minimale hoeveelheid dat van dat fragment nodig is om het fragment in de database terug te vinden. Uit Figuur 5.2.10. kan worden opgemaakt dat als de gzip compressor gebruikt wordt er minder van het originele fragment nodig is om het fragment in de database terug te vinden dan voor de bzip2 compressor.

- 27 -

A Comparison of Code Fragments 5. Hoeveel procent ruis mag erin een codefragment voorkomen, zodat het codefragment toch nog als beste resultaat in de database gevonden wordt? gzip 40% 35%

Percentage

30% 25% 20%

Percentage ruis in fragment

15% 10%

Figuur 5.2.11. gzip C: histogram van de testresultaten van test 5 met gzip C compressor. In het histogram ziet u op de verticale as het percentage ruis dat maximaal mag voorkomen in een codefragment, zodat het fragment toch nog als beste resultaat in de database gevonden kan worden. Op de horizontale as worden de verschillende codefragmenten weergegeven.

5% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 30%

25%

Percentage

20%

15%

Percentage ruis in fragment

10%

5%

Figuur 5.2.12. bzip2 C: histogram van de testresultaten van test 5 met bzip2 C compressor. In het histogram ziet u op de verticale as het percentage ruis dat maximaal mag voorkomen in een codefragment, zodat het fragment toch nog als beste resultaat in de database gevonden kan worden. Op de horizontale as worden de verschillende codefragmenten weergegeven.

0% 1

2

3

4

5

6

7

8

9

10

Fragment

Figuur 5.2.13. bzip2 versus gzip: histogram van de testresultaten van test 5. De bzip2 resultaten zijn van de gzip resultaten afgetrokken. In het histogram ziet u op de verticale as het percentuele verschil en op de horizontale as de verschillende de codefragmenten.

bzip2 versus gzip 15%

Percentage

10%

5% Verschil bzip2 en gzip 0% 1

2

3

4

5

6

7

8

9

10

-5%

-10% Fragment

Omdat de fragmenten oplopen qua grootte (in aantal tekens), kan uit figuren 5.2.11. en 5.2.12. opgemaakt worden dat voor de gzip compressor de tendens lijkt dat hoe meer tekens een fragment bevat hoe minder ruis, in het algemeen, bij het fragment opgeteld kan worden, zodat het fragment nog als beste resultaat teruggevonden wordt in de database. Voor de bzip compressor lijkt het percentage ruis dat bij een codefragment opgeteld kan worden, zodat het fragment nog steeds als beste resultaat in de database teruggevonden kan worden, min of meer constant te zijn.

- 28 -

A Comparison of Code Fragments Uit Figuur 5.2.12. kan worden opgemaakt dat als de gzip compressor gebruikt wordt erbij de kleinere fragmenten (in aantal karakters) relatief meer ruis opgeteld kan worden, zodat het fragment terug gevonden wordt als beste resultaat in de database, dan voor de bzip2 compressor. Ook kan worden opgemaakt dat als de bzip2 compressor gebruikt wordt, dan kan er bij de grotere fragmenten (in aantal karakters) relatief meer ruis opgeteld worden, zodat het fragment terug gevonden wordt als beste resultaat in de database, dan voor de gzip compressor. 6. Hoeveel van het originele fragment is nodig om het fragment als beste resultaat terug te vinden in de database, als de helft van de maximale ruis in het fragment optreed? gzip C 60%

50%

Percentage

40%

Minimale hoeveelheid van een fragment, met helft van maximale ruis

30%


20%

10%

0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 C 70% 60%

Percentage

50% 40%

Minimale hoeveelheid van een fragment, met helft van maximale ruis

30%


20% 10% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 versus gzip 20%

15%

Percentage

10% Test 6

5%

Test 4

0% 1

2

3

4

5

6

7

8

9

10

-5%

-10% Fragment

- 29 -

Figuur 5.2.14. gzip C: histogram van de testresultaten van test 6 met gzip C compressor. In het histogram ziet u op de verticale as het percentage dat minimaal van een fragment nodig is om het terug te vinden als beste resultaat in de database, als de helft van de maximale ruis in het fragment optreedt. Op de horizontale as worden de verschillende codefragmenten weergegeven. Om de uitkomsten beter te kunnen vergelijken met de resultaten uit test 4, zijn de uitkomsten van de gzip compressor van test 4 ook in de figuur opgenomen.

Figuur 5.2.15. bzip2 C: histogram van de testresultaten van test 6 met bzip2 C compressor. In het histogram ziet u op de verticale as het percentage dat minimaal van een fragment nodig is om het terug te vinden als beste resultaat in de database, als de helft van de maximale ruis in het fragment optreedt. Op de horizontale as worden de verschillende de codefragmenten weergegeven. Om de uitkomsten beter te kunnen vergelijken met de resultaten uit test 4, zijn de uitkomsten van de bzip2 compressor van test 4 ook in de figuur opgenomen. Figuur 5.2.16. bzip2 versus gzip: histogram van de testresultaten van test 6. De gzip resultaten van test 6 zijn van de bzip2 resultaten van test 6 afgetrokken. In het histogram ziet u op de verticale as het percentuele verschil en op de horizontale as de verschillende codefragmenten. Om de uitkomsten beter te kunnen vergelijken met de resultaten uit test 4, zijn de resultaten uit Figuur 5.2.10. overgenomen in deze figuur.

A Comparison of Code Fragments Uit de figuren 5.2.14. en 5.2.15. blijkt dat bij beide compressors het toevoegen van ruis het resultaat verslechtert voor de kleinere fragment, fragmenten 1 en 2. Echter blijkt ook dat het toevoegen van ruis een positief effect kan hebben bij de grotere fragmenten, zie resultaten van de fragmenten 7 en 9. Uit Figuur 5.2.16. kan worden opgemaakt dat het toevoegen van de helft van de maximale ruis een nadelig effect heeft op de gzip compressor, ten opzichte van de bzip2 compressor, naarmate de fragmenten qua omvang groter worden. Uit de resultaten van test 4 kon de conclusie worden getrokken dat de gzip compressor minder van het exacte fragment nodig heeft om het fragment in de database terug te vinden, echter blijkt uit de resultaten van test 6 dat voor de grotere fragmenten met de helft van de maximale ruis erin de bzip2 beter zou kunnen werken. 7. Hoeveel procent ruis mag erbij het codefragment toegevoegd worden, zodat het codefragment toch nog in de database als beste resultaat gevonden wordt? gzip C 20000% 18000% 16000%

Percentage

14000% 12000% 10000%

Percentage maximaal extra ruis

8000% 6000% 4000%

Figuur 5.2.17. gzip C: histogram van de resultaten van test 7, met de gzip C compressor. In het histogram ziet u op de verticale as het percentage ruis dat bij een fragment opgeteld kan worden, zodat het fragment toch nog als beste resultaat in de database teruggevonden wordt. Op de horizontale as worden de verschillende codefragmenten weergegeven.

2000% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

bzip2 C 40000% 35000%

Percentage

30000% 25000% 20000%

Percentage maximaal extra ruis

15000% 10000%

Figuur 5.2.18. bzip2 C: histogram van de resultaten van test 7, met de gzip C compressor. In het histogram ziet u op de verticale as het percentage ruis dat bij een fragment opgeteld kan worden, zodat het fragment toch nog als beste resultaat in de database teruggevonden wordt. Op de horizontale as staan de verschillende codefragmenten.

5000% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

Uit de figuren 5.2.17. en 5.2.18. kan worden opgemaakt dat voor zowel de gzip als bzip2 compressors, relatief gezien, bij kleinere fragmenten (in omvang), meer ruis opgeteld kan worden, zodat het fragment nog wel als beste resultaat in de database teruggevonden wordt. Neemt het fragment in grootte toe, dan kan er relatief gezien minder ruis bij worden opgeteld, om het fragment toch nog terug te vinden als beste resultaat in de database.

- 30 -

A Comparison of Code Fragments Figuur 5.2.19. bzip2 versus gzip: histogram van test 6 resultaten. De gzip resultaten van test 7 zijn van de bzip2 resultaten van test 7 afgetrokken. In het histogram ziet u op de verticale as het percentuele verschil en op de horizontale as de verschillende de codefragmenten.

bzip2 versus gzip 20000% 18000% 16000%

Percentage

14000% 12000% 10000%

Verschil bzip2 en gzip

8000% 6000% 4000% 2000% 0% 1

2

3

4

5

6

7

8

9

10

Fragment

Uit Figuur 5.2.19. kan opgemaakt worden dat de bzip2 compressor, met relatief meer extra ruis, het fragment als beste resultaat in de database kan terugvinden. Uit de figuur kan je ook concluderen dat naarmate het fragment groter wordt (qua omvang), hoe dichterbij de resultaten van de bzip2 en gzip compressor komen te liggen.

- 31 -


6. Conclusies en aanbevelingen In dit project is onderzocht of met behulp van de NCD methode een applicatie ontwikkeld kan worden, dat geschikt is als “online” hulpprogramma om een programmeur te ondersteunen. Met ondersteunen wordt hier bedoeld dat de applicatie codefragmenten zal aanbieden die eenzelfde bedoeling/structuur hebben als waar de programmeur mee bezig is. Uit de resultaten van test 1 kan geconcludeerd worden dat de methode in principe snel genoeg is om binnen een redelijk korte tijd een antwoord te geven. Op dit moment wordt voor elk zoekresultaat een vergelijking gemaakt met alle fragmenten van de database. Omdat de grootte van de testdatabase, die in dit project gebruikt is, zeer klein is levert het vergelijken met alle fragmenten uit de testdatabase geen hinder op. Op het moment dat een ‘echte’ database gebruikt gaat worden, dan kan de responstijd van het programma nogal oplopen, waardoor het programma wellicht niet geschikt is als “online” hulpprogramma. Een mogelijk vervolgonderzoek zou dan zijn om te kijken of het mogelijk is om alleen gedeelten van de database te hoeven doorzoeken. De fragmenten die in de database staan hebben ieder tot elkaar een NCD waarde. Je zou dus verwachten dat als een gebruikersfragment wordt vergeleken met een fragment uit de database en het resultaat van deze vergelijking dichtbij het getal 1 ligt, dat andere fragmenten die relatief dichtbij het fragment in de database staan niet dichtbij het gebruikersfragment staan. Ook kan het omgekeerde aangenomen worden, dat als een gebruikersfragment met een fragment uit de database wordt vergeleken en het resultaat van deze vergelijking dichtbij het getal 0 ligt, dat andere fragmenten die relatief dichtbij het fragment in de database staan wel dichtbij het gebruikersfragment staan. Voor het aanleggen van een database met meer en betere inhoud kan er onderzoek gedaan worden hoe de NCD methode hierbij ingezet kan worden. Omdat de reciproque van de NCD tussen twee fragmenten aangeeft hoe ver twee fragmenten van elkaar afstaan, zal het hierdoor ook mogelijk zijn om te bepalen of een fragment zich al in de database bevindt. Uit de resultaten van de testen 2 en 3 kan in het algemeen geconcludeerd worden dat het toepassen van eenzelfde filter op codefragmenten voor de bzip2 compressor lagere NCD waarden kan opleveren. Uit deze resultaten kan ook opgemaakt worden dat het toepassen van een filter op codefragmenten voor de gzip compressor, een negatief effect op de NCD waarden heeft. Als door het toepassen van een filter de onderliggende afstanden niet veranderen, dan zal het toepassen van een filter geen invloed hebben op de resultaten. Deze conclusie kan echter niet uit de test worden getrokken. Om hierachter te komen zal dus nog enig onderzoek verricht moeten worden. Het bepalen of een resultaat op een zoekopdracht goed is, is erg moeilijk. Vandaar dat in de testen 4, 5, 6 en 7 als invoerfragmenten uit de database zelf werden genomen. Alleen in deze situatie kan een computer goed bepalen of er een goede match heeft plaatsgevonden. De algemene conclusie die uit testen 4, 5 en 6 getrokken kan worden is dat de gzip compressor voor de kleinere fragmenten beter werkt dan de bzip2 compressor. In deze testen werkt de gzip compressor beter tot en met fragment 5. Fragment 5 heeft een grootte van 1177 karakters of 41 regels. De algemene conclusie die uit test 7 getrokken kan worden, is dat de bzip2 compressor veel beter is als er rondom het fragment veel ruis optreedt. Vandaar dat in de plugin voor het - 32 -

A Comparison of Code Fragments automatisch aanleveren van codefragmenten gebruik gemaakt wordt van een zogenaamd ‘window’, zodat de aangeleverde fragmenten nooit groter zijn dan n regels. Wat in een vervolgonderzoek aan te raden is om te onderzoeken, is wat het gevolg is van het hernoemen van variabelen en functies in een codefragment. Dit is aan te raden, omdat hiermee een nog beter beeld gegeven kan worden wat de performance van de applicatie is. De plugin zal op dit moment vooral nuttig zijn voor mensen die net beginnen met programmeren of een nieuwe programmeertaal onder de knie willen krijgen. De eindconclusie van dit project is dat de applicatie dat in dit project ontwikkeld is, geschikt is als “online” hulpprogramma om een programmeur te assisteren bij het programmeren. Indien de aangeleverde codefragment niet meer dan ongeveer 40 regels bevat, dan is de NCD methode met behulp van de gzip compressor snel en goed genoeg om een antwoord te vinden. Echter dient er nog wel veel aan onderzoek te worden gedaan, wil de applicatie daadwerkelijk succesvol zijn in het assisteren.

- 33 -


7. Bibliografie Artikelen: [1] Cilibrasi, R. en Vitányi, P. (2003) Clustering by Compression. CWI en Universiteit van Amsterdam. [2] Cilibrasi, R. Vitányi, P. en De Wolf, R. (2003) Algorithmic Clustering of Music. CWI en Universiteit van Amsterdam. [3] McIlroy (1968), D. Mass-produced software components. In P. Naur and B. Randell, editors, Software Engineering, NATO Science Committe report, pages 138–155. [4] Mishne, G. (2003) Source Code Retrieval using Conceptual Graphs. Institute for Logic, Language and Computation (IILC) Universiteit van Amsterdam. Boeken: [5] Bruegge, B. en Dutoit, A.H. (2000) Object-Oriented Software Engineering, Prentice Hall, New Jersey. [6] Dawson, C.W. (2000) The Essence Of Computing Projects, A Student’s Guide, Pearson Education, Harlow. [7] Maciaszek, L.A. (2001) Requirements analysis and system design, Pearson Education, Harlow. Internetpagina’s: [8] Artistic Style (2002): a source code indenter and reformatting tool / library for C, C++, C#, or Java source files, URL: http://sourceforge.net/projects/astyle. [9] Bzip2 (2002): high-quality data compressor, URL: http://sources.redhat.com/bzip2/. [10] Gzip (2003): a compression utility, URL: http://www.gzip.org/. [11] jEdit (2004): Open Source programmer's text editor, URL: http://www.jedit.org/. [12] JNI (2004): Stearns, B. Java Native Interface, URL: http://java.sun.com/docs/books/tutorial/native1.1/.

- 34 -


A. De opdracht Hier vindt u de opdracht van het project. Deze opdracht is geschreven en verzonnen door de heer Torenvliet. Project Description: A Comparison of Code Fragments Imagine you, a programmer, sitting behind a screen trying to write a program of some sort before the deadline expires. It is not going too well. There are syntactic errors and when the compiler finally lets your program pass, it doesn’t do what you expected. Array boundaries are overrun and the performance is hopeless. You stare at your code and try to find ways to improve it. Suddenly, a small figure pops up at the edge of your screen. There is a text balloon above the figure that says: “Excuse me, it seems that you are trying to write a routine for sorting, in particular in Java. As it so happens, I have several of these routines in my database. Might I offer you one or two for your inspection?” Of course, you gladly accept the offer and your project is advanced a major step. Programming these days, is often done “standing on the shoulders of others” instead of trying to write a piece of software yourself, you almost always first try to “google” (which has lately become a verb) a suitable piece first. The problem is, how to find the piece of software that has the functionality that you require? What is the piece of software present on the internet that most resembles the routine in your head, and partially entered into your computer? Recently, Cilibrasi and Vitányi developed a measure called “information distance”. This measure is usable on all types of objects that have similar meaning have similar structure. To find out which objects have more similar structure they use compression techniques. If one object has a lot of information pertaining to another, then it is possible to give a very short description of the second object, when knowledge about the first object is present. This simple observation led to some astonishing results classifying pieces of music, viruses, languages and much more. Meanwhile many tools for classification have been developed and are available. The project proposed here is aimed at using these tools for the purpose of retrieving code fragments (routines if you will) from a database. First an extensive database of algorithms in various programming languages will be created, and then an access mechanism based on information distance will be programmed that retrieves the piece of software that is closest in this measure to the input code fragment. Alternatively, the students may instead choose to focus on a web-search engine variant, or other domain-specific search tool. Several students will be working under guidance of Cilibrasi, scientist and expert programmer, himself on this project.

- 35 -


B. Software Engineering In dit hoofdstuk worden de overige software engineering aspecten van het systeem behandeld, dat ontwikkeld zal worden. Deze software engineering is opgesteld met behulp van kennis dat is opgedaan bij het vak Groot Software Project en uit het boek Maciaszek [7].

B.1. Requirementanalyse Het is de bedoeling dat het systeem zal voldoen aan de eisen die hier gesteld worden. Het is dan ook belangrijk dat alle eisen die hier gesteld worden dan ook testbaar zijn. 1. 2. 3. 4.

Het systeem moet kunnen communiceren met de gebruiker; Het systeem moet een opslagplaats hebben voor codefragmenten; Het systeem moet aan de gebruiker code fragmenten kunnen aanbieden; Het systeem moet instaat zijn om code van de gebruiker te kunnen vergelijken met codefragmenten dat het systeem tot zijn beschikking heeft; 5. Het systeem moet kunnen werken op een computer met de volgende eigenschappen: a) Besturingssysteem: Microsoft Windows XP Professional Versie 2002 Service Pack 1; b) C.P.U.: AMD Athlon™ XP 2600+; c) R.A.M. geheugen: 512 Mb PC3200; d) Java Runtime Environment: J2SE v 1.5.0 Beta 2; e) Beeldschermresolutie: 1280 bij 1024; 6. Het systeem moet kunnen werken met voor haar onbekende programmeertalen. Onder onbekende programmeertalen kan worden verstaan: nog nieuw te ontwikkelen programmeertalen;

- 36 -


B.2. Systeemspecificatie Voordat er begonnen kan worden met een systeemspecificatie, dient eerst een componentenspecificatie te worden opgesteld. In de componentenspecificatie wordt grafisch weergegeven uit welke componenten het systeem zal bestaan. Database

Application

Filter Comparison tool User code Notify user Text editor

Figuur B.1. Componentenspecificatie: Hier ziet u de componentenspecificatie zoals deze is opgesteld. Met de pijlen wordt aangegeven hoe een codefragment de verschillende componenten van het systeem zal passeren.

Database: S1. De component database is de opslagplaats waar de codefragmenten zich bevinden; S2. De component database biedt aan de applicatie de mogelijkheid om in haar data te kijken; Text editor: S3. De component text editor krijgt van het tekstverwerkingsprogramma codefragmenten; S4. De component text editor biedt aan component filter codefragmenten van het tekstverwerkingsprogramma aan; User code: S5. De component user code krijgt van de gebruiker codefragmenten; S6. De component user code biedt aan component filter codefragmenten van de gebruiker aan;

- 37 -

A Comparison of Code Fragments Filter: S7. De component filter krijgt van component text editor codefragmenten; S8. De component filter krijgt van component user code codefragmenten; S9. De component filter biedt aan component comparison tool codefragmenten; S10. De component filter bewerkt de verkregen codefragmenten, zodat de component comparison tool beter instaat is om codefragmenten met elkaar te kunnen vergelijken; Comparison tool: S11. De component comparison tool krijgt van component filter codefragmenten; S12. De component comparison tool krijgt van component database codefragmenten; S13. De component comparison tool biedt aan component notify user codefragmenten; S14. De component comparison tool vergelijkt de aangeleverde code fragmenten met elkaar; Notify user: S15. De component notify user krijgt van component comparison tool codefragmenten; S16. De component notify user is in staat om de gebruiker op de hoogte te stellen van gevonden codefragmenten;

B.3. Uitgangspunten In deze scriptie wordt alleen ingegaan op het maken van de applicatie en niet op het ontwikkelen van een database. Vandaar dat hier een aantal aannames worden gedaan over de database dat het uiteindelijke systeem zal moeten hebben: 1. De database bevat alle verschillende codefragmenten die er zijn; 2. De database wordt bijgehouden met nieuwe codefragmenten; 3. De database heeft een oneindige grootte;

B.4. Risicoanalyse In dit hoofdstuk worden risico’s geïdentificeerd die belangrijk zijn in het project. Naast het identificeren van de risico’s zullen ook mogelijke oplossingen worden geboden. 1. De methode ‘Normalized Compression Distance’ werkt niet om codefragmenten te clusteren. Mogelijke oplossing: indien deze methode niet werkt kan er opzoek worden gegaan naar een andere methode die wellicht wel zou kunnen werken. Een methode die wel werkt is de ‘conceptual graph’ methode, [4]. In de scriptie geeft de heer Mishne aan dat er in deze methode nog wel het één en ander verbeterd kan worden om de responstijd van het systeem te verkleinen. Bovendien kan er onderzoek worden gedaan waarom de NCD methode niet geschikt is om codefragmenten te clusteren.

- 38 -

A Comparison of Code Fragments 2. Het aantal vergelijkingen dat per minuut kan worden uitgevoerd is kleiner dan één. Indien dit optreedt, dan kan de methode ‘Normalized Compression Distance’ wel gebruikt worden, maar is het in gebruik op dit moment nog te langzaam om daadwerkelijk ook een toepassing te hebben. Mogelijke oplossing: opzoek gaan naar een andere methode die wellicht wel sneller resultaten zou kunnen tonen, bijvoorbeeld het optimaliseren van de ‘conceptual graph’ methode. Bovendien kan er onderzoek worden gedaan waarom de NCD methode zo langzaam werkt. 3. Het is niet mogelijk om codefragmenten uit een text editor te krijgen. Indien dit probleem optreedt kan het project nog wel verder, alleen vervalt de mogelijkheid om automatisch codefragmenten te matchen. Indien er tijd is zou er wel een simpele text editor kunnen worden gemaakt, waarbij volledige toegang in de code van de gebruiker voor de applicatie is. 4. Er kan geen database worden aangemaakt met voldoende codefragmenten, om hierop testen uit te voeren. Mogelijke oplossing: zelf fragmenten verzinnen en/of stukjes codefragmenten kopiëren uit bestaande source code. 5. Het is niet mogelijk om een filter toe te passen op de codefragmenten. Mogelijk oplossing: de filter niet implementeren en verder werken met de applicatie. 6. Het is niet mogelijk om C implementaties van compressors aan te roepen. Mogelijke oplossing: de applicatie in de programmeertaal C schrijven, zodat de compressors wel kunnen worden aangeroepen. Of alleen gebruik maken van de compressor die Java de gebruiker aanbiedt.

- 39 -


C. De testdatabase In dit hoofdstuk wordt de database beschreven, die gebruikt zal worden om tests op uit te voeren. De database waarop de tests zijn uitgevoerd staat in een map. Deze map bestaat uit bestanden met codefragmenten en mappen waarin weer bestanden met codefragmenten of mappen staan. Verschillende mappen Voor de eerste testen heb ik een aantal verschillende mappen aangemaakt met fragmenten allemaal afkomstig van de site van Addison-Wesley (http://www.aw-bc.com/cssupport/), genaamd: test_database_java: o Java Almanac1; o Budd – Classic Data Structures in Java; o Carrano – Data Abstraction and Problem Solving with Java; o Coulouris – Distributed Systems; o Jia – Object-Oriented Software Development using Java Styles, Patterns and Frameworks; o Koffman – Problem Solving with Java; o KoffmanWolz – Problem Solving with Java; o Laszlo – Object-Oriented Programming in Java A Graphical Approach; o LewisChase – Java Software Structures Designing and Using Structures; o Liu – Distributed Computing Principles and Applications; o PohlMcDowell – Java by Dissection The Essentials of Java Programming; o Riccardi – Principles of Database Systems with Internet and Java Applications; test_database_c: o HanlyKoffman – Problem Solving and Program Design in C; o Hanson – C Interfaces and Implementations; o KelleyPohl – C by Dissection; o KelleyPohl – A Book on C; o Standish – Data Structures, Algorithms and Software Principles; o Summit – C Programming FAQs test_database_c++: o Carrano – Data Abstraction and Problem Solving with C++; o Coplien – Advanced C++ Programming Styles and Idioms; o FriedmanKoffman – Problem Solving, Abstraction and Design Using C++; o LippmanLajoie – C++ Primer; o Pohl – C++ Distilled; o Pohl – Object Oriented Programming with C++; test_database_ada: o Feldman – Software Construction and Data Structures with Ada; o FeldmanKoffman – Ada 95 Problem Solving and Program Design; o Weiss – Datastructures and Algorithm Analysis in Ada; test_database_pascal: o Weiss – Data Structures and Algorithm Analyses; 1

Deze komen niet van de site van Addison-Wesley, maar van de site van Java Almanac (http://javaalmanac.com/)

- 40 -

A Comparison of Code Fragments Met behulp van het programma ‘DirectoryInfo’ zijn de volgende eigenschappen van de database vernomen: Naam database

Aantal bestanden

test_database_java

Gemiddelde grootte (in Bytes)

2.729

934,31

932

992,42

test_database_c++

1.200

1.244,33

test_database_ada

542

1.459,22

test_database_pascal

171

569,18

test_database_c

- 41 -


D. CD-ROM

- 42 -

A Comparison of Code Fragments

Recommend Documents