Szegedi Tudományegyetem Informatikai Tanszékcsoport
Tervezési minták felismerése objektum orientált programkódban
Szakdolgozat
Készítette:
Témavezetők:
Bán Dénes
Dr. Ferenc Rudolf
Hegedűs Péter
BSc hallgató
egyetemi adjunktus
doktorandusz
Szeged 2012
Feladatkiírás
A szakdolgozat célja a Columbus rendszerben már implementált LIM (Language Independent Model) formátumra épülő, a jelenlegi XML alapú módszertől különböző mintafelismerő program létrehozása, és működésének tesztelése. A kódnak C++ nyelven kell elkészülnie, hogy használhassa a LIM-et és segédosztályait.
2
Tartalmi összefoglaló
A téma megnevezése: Tervezési minták felismerése objektum orientált programkódban
A megadott feladat megfogalmazása: Az elsődleges cél egy, a Columbus programban jelenleg használt tervezési mintafelismerő algoritmustól különböző, ígéretesnek tűnő detektálási módszer implementálása.
A megoldási mód: A programkódot ezen túl is LIM formában tárolja a rendszer, de ebből a futás során adott tulajdonságok jelenlétét vagy hiányát jelképező mátrix készül, és erre illesztjük a szintén mátrix formában reprezentált tervezési mintát.
Alkalmazott eszközök, módszerek: A megoldás egy önálló C++ program, amely a rendszer információinak beolvasása miatt használja a LIM-hez kapcsolódó header-öket és library-ket, valamint a boost numerikus csomagjában található uBLAS-t, ami hatékony alacsony szintű mátrix műveleteket valósít meg.
Elért eredmények: A program megfelelő küszöbértékkel sikeresen képes mintapéldányok azonosítására a megadott példarendszerből.
Kulcsszavak: DP, Forráskód elemzés, Mintafelismerés, Tervezési minták
3
Tartalomjegyzék
Feladatkiírás .................................................................................................................................................... 2 Tartalmi összefoglaló....................................................................................................................................... 3 Tartalomjegyzék .............................................................................................................................................. 4
BEVEZETÉS .......................................................................................................... 6 1. A TERVEZÉSI MINTÁKRÓL ............................................................................. 7 1.1. Mik azok a tervezési minták? .................................................................................................................. 7 1.2. Miért fontos a felismerésük? ................................................................................................................... 7
2. MINTAFELISMERŐ ALGORITMUSOK BEMUTATÁSA ................................... 9 2.1. Lehetséges mintafelismerési stratégiák ................................................................................................... 9 2.1.1. Illeszkedés szerinti csoportosítás ........................................................................................................ 9 2.1.2. A vizsgálat aspektusa szerinti csoportosítás ..................................................................................... 10 2.1.3. A rendszer reprezentálása szerinti csoportosítás ............................................................................... 11 2.1.4. A minták reprezentálása szerinti csoportosítás ................................................................................. 13 2.1.5. Az eredmények formátuma szerinti csoportosítás ............................................................................ 13 2.2. Mintafelismerés mátrixokkal ................................................................................................................. 13 2.2.1. Az adatok reprezentálása .................................................................................................................. 14 2.2.2. Blondel algoritmusa .......................................................................................................................... 14 2.2.3. Többszörös illeszkedés ..................................................................................................................... 15
3. A MÁTRIX ALAPÚ ALGORITMUS IMPLEMENTÁCIÓJA .............................. 17 3.1. A PatternFinder áttekintése .................................................................................................................. 17 3.1.1. Szerkezet ........................................................................................................................................... 17 3.1.2. Használat .......................................................................................................................................... 18 3.2. Függőségek .............................................................................................................................................. 19 3.2.1. LIM ................................................................................................................................................... 19 3.2.2. uBLAS .............................................................................................................................................. 19
4
3.3. Belső tervezési minták ............................................................................................................................ 19 3.3.1. Singleton ........................................................................................................................................... 20 3.3.2. Composite ......................................................................................................................................... 20 3.3.3. Memento ........................................................................................................................................... 21 3.3.4. Visitor ............................................................................................................................................... 22 3.4. A rendszer részletes bemutatása ........................................................................................................... 22 3.4.1. A mátrixok ........................................................................................................................................ 23 3.4.2. System .............................................................................................................................................. 24 3.4.3. Pattern ............................................................................................................................................... 25 3.4.4. Config ............................................................................................................................................... 25 3.4.5. PatternFinder..................................................................................................................................... 26 3.5. Továbbfejlesztési lehetőségek ................................................................................................................ 26
4. TESZTELÉS..................................................................................................... 28 4.1. A tesztelt rendszer .................................................................................................................................. 28 4.2. Teszteredmények .................................................................................................................................... 28
5. ÖSSZEFOGLALÁS.......................................................................................... 31 Irodalomjegyzék ............................................................................................................................................ 32 Nyilatkozat ..................................................................................................................................................... 33
5
BEVEZETÉS A tervezési minták használata a szoftverfejlesztési módszertanok fejlődése és szabványosodása miatt
egyre elterjedtebb. A felmerülő fogalmak és folyamatok
objektumorientált modellezése már közel sem számít újdonságnak, de különböző problémák is tartalmazhatnak hasonló, ismétlődő komponenseket és ezek megvalósításához a fejlesztőknek mindig újra „fel kellett találniuk a kereket”. Ezért is fordítanak napjainkban egyre nagyobb hangsúlyt arra, hogy ezeket az ismétlődéseket kipróbált és bevált módokon oldják meg. Ez viszont a dokumentációkra – illetve azok hiányára – vonatkozó tendenciák miatt magával vonja olyan programok szükségességét is, amik minimális emberi beavatkozással képesek létező – esetleg legacy – rendszerek kódjából az adott rendszerre vonatkozó metainformációk előállítására. Viszont a rendszerek és a minták ábrázolására, az illeszkedés vizsgálatára illetve az eredmény tartalmára nézve is számtalan lehetőség kínálkozik, amelyek közül egyik sem feltétlenül „jobb”, mint a másik. Így az ilyen célú felismerő programok ma is folyamatos fejlődés, kísérletezés alatt állnak. Ennek a dolgozatnak a célja, hogy bemutassa egy ilyen, elméletben már bizonyított módszer LIM alapú implementációját – némileg kiegészítve azt a többszörös illeszkedések helyes felismerése miatt – és tesztelje azt éles környezetben. A dolgozat első fejezetében részletesebben bemutatom a tervezési mintákat, hasznukat és felismerésük fontosságát. A második fejezetben először a mintaillesztő algoritmusok áttekintése, csoportosítása szerepel, majd konkrétan az általam választott módszer bemutatása. A harmadik fejezet a megvalósítás átfogó képét, használatát, szerkezetét és részletes jellemzését tartalmazza. A negyedik fejezetben a működés tesztelése céljából a mintafelismerés egy valós rendszeren futtatott eredményeit elemzem. Végül az ötödik fejezetben összefoglalom az addig elhangzottakat.
6
1. A TERVEZÉSI MINTÁKRÓL 1.1. Mik azok a tervezési minták? A tervezési minták napjaink szoftverfejlesztésének egyre jelentősebb résztvevői. Tulajdonképpen nem mások, mint a tervezési fázisban gyakran előforduló, ismétlődő problémák vagy probléma-komponensek tapasztalati úton bizonyított legjobb megoldásai – „best practices”. Használatuk segíthet egy programot struktúráltabbá, átláthatóbbá tenni, ezáltal könnyítheti annak fejlesztését, megértését, karbantartását [1][2]. Egy adott specifikáció megvalósításakor fontos, hogy alkalmazkodjunk a jelenlegi elvárásokhoz, de az sem mellékes, ha eközben olyan objektumokat, hierarchiákat hozunk létre, amik részt vehetnek későbbi feladatainkban is. Ez a két szempont nem egyeztethető könnyen össze, és – mivel szinte mindig a „most” élvez elsőbbséget – a jövőben kis módosítások miatt is rászorulhatunk a szerkezet újratervezésére, ami nemcsak a ráfordított idő tekintetében káros, de a létrejövő termék minőségét is lényegesen ronthatja. Itt jönnek a képbe a tervezési minták, amik ezekhez a gyakori problémákhoz adnak egy „megoldásvázlatot”. Így a megoldás magja egy olyan absztrakció lesz, ami más helyeken is hatékonyan alkalmazható, viszont a minta vázlatosságának konkréttá alakítása teljesen rajtunk múlik, tehát minden alkalommal képesek leszünk az aktuális helyzethez alkalmazkodni [3]. Egy tervezési minta információtartalom szempontjából rendelkezhet egy névvel, egy típussal – ami a [3] csoportosítása szerint lehet létrehozási, szerkezeti és viselkedési –, kontextussal vagy kontextusokkal, amelyekre vonatkozhat, egy sablonnal, ami leírja az osztályok, objektumok, interfészek ajánlott együttműködését, valamint – mind pozitív, mind negatív – következményekkel, amikkel a minta alkalmazása járhat. Ezekkel az elemekkel bármely általános modellezési szituációhoz sikeresen megadhatók olyan sémák, amik elősegíthetik a kód újrafelhasználhatóságát [3].
1.2. Miért fontos a felismerésük? Képzeljünk el egy olyan – a valós életben is könnyen előfordulható – helyzetet, amikor egy embernek vagy egy csapatnak a tiszta lappal kezdés helyett az a feladata, hogy egy mások által készített szoftvert fejlesszen, vagy módosítson. Ahhoz azonban, hogy később bármi érdemi is történhessen, először meg kell érteni a rendszer felépítését és működését, ami hangzása ellenére általában a folyamat egyik legnehezebb szakasza. 7
Ilyen esetekben kritikus a kód dokumentáltságának mértéke. A szomorú valóság az, hogy a tanulmányi és/vagy tudományos körökön kívüli üzleti világban gyakori jelenség, hogy a – néha irracionálisan szűk – határidők tartása és a működőképességre helyezett hangsúly miatt a rendszerhez tartozó dokumentáció a semmi felé konvergál. Jó eset, ha a kódban elhelyezett kommentekből, habár nem is a megfelelő absztrakciós szinten, de visszavezethető a rendszer működése. Jobb eset, ha ezek a kommentek kompatibilis formában vannak valamilyen, hivatkozásokat és áttekintést is tartalmazó dokumentumot generálni képes CASE eszközzel. Még jobb a helyzet, ha a rendszerhez UseCase, Class vagy Sequence diagramokat, illetve egyéb szabványos, magas szintű leírásokat és ábrákat is csatolnak. Ha már olyan kóddal van dolgunk, amiben tervezési mintákat is használtak, az szintén előny, de annyira ritkán jó a helyzet, hogy ezekhez külön dokumentáció is társuljon. Pedig ha tudnánk, hogy hol használtak egy adott mintát, – például a forrásban megjelölték volna, hogy egy osztály melyik pattern melyik szerepét tölti be – akkor azt is könnyebben kihámozhatnánk, hogy miért. De a hiányzó információval utólag már nem lehet mit kezdeni, azt kell használni, ami van. Mintafelismerés tekintetében a kódból kinyerhető adatoknál nincs is többre szükség, viszont az, hogy lehetséges, még nem jelenti azt, hogy egyszerű vagy gyors, és ezáltal azt sem, hogy a projekt esetleges idő- és költségkorlátait is figyelembe véve kivitelezhető. Többek közt ezért lehet fontos az olyan módszerek és programok vizsgálata, amik képesek egy rendszert valamilyen köztes – nyelvfüggetlen – formátumra alakítani, és arra patternek előre definiált adatbázisából példányokat illeszteni.
8
2. MINTAFELISMERŐ ALGORITMUSOK BEMUTATÁSA Sajnos az informatika – azon belül is a mesterséges intelligencia, nyelvfeldolgozás, stb. – egyelőre még nem tart olyan szinten, hogy az „S rendszer tartalmazza-e a P mintát” jellegű kérdésekre automatikusan választ kaphassunk. Ezért nekünk kell olyan algoritmusokat keresnünk, amelyek atomi műveleteiket tekintve kellően alacsony szintűek, mégis a fenti kérdésre adnak eredményeket. Ilyen algoritmusokból számtalan létezik, ezért a fejezet első felében konkrét felsorolásuknál sokkal hatékonyabb, különböző szempontok szerinti csoportosításuk bemutatása következik [2]. A fejezet második részében pedig az általam választott módszer leírása [4], értékelése és a többszörös illeszkedések helyes kezelése miatt alkalmazott apróbb módosítása szerepel.
2.1. Lehetséges mintafelismerési stratégiák A jelenleg használatos mintafelismerési módszereket több aspektus szerint is lehet vizsgálni. Az aspektusokon belüli lehetőségek egyike sem feltétlenül jobb, mint egy másik, csak esetleg más helyzetekben máshogy teljesítenek.
2.1.1. Illeszkedés szerinti csoportosítás Az illesztő algoritmusok fontos ismertető jegye, hogy csak tökéletes egyezést detektál, vagy képes-e egy olyan értéket visszaadni, ami megmutatja, hogy mennyire jártunk közel. Az első gyakorlatilag egy boolean válasz, – van-e találat – a második pedig egy metrika, a hasonlóság mértéke. A csak pontos egyezést elfogadó verzió – az algoritmus többi szempontjától függetlenül – általában
egyszerűbben
implementálható.
Futási
időben
is
jobban
járunk,
mert
kihasználhatjuk, hogy amint találunk egy eltérést, azonnal befejezhetjük a keresést. Igaz, hogy az eredmények szempontjából nem elsődleges a programozók munkájának könnyítése, és az idő sem tűnhet olyan nagy előnynek, de bizonyos rendszerek rendelkezhetnek akkora méretekkel,
illetve
bizonyos
illesztési
módok
rendelkezhetnek
olyan
kedvezőtlen
skálázhatósággal, hogy nem mindig lesz választásunk. Ha viszont a lehetőségek engedik, – a látszólagos paradoxon ellenére – pontosabb eredményeket kaphatunk, ha nem csak pontos találatokat keresünk. Ennek nyilván ára van
9
komplexitás és futás terén is, de ha megfelelően értékeljük ki az egyezés mértékét, elkerülhetünk sok fals negatívot. A tervezési minták, ha nem is ritkán, de közel sem mindig „tankönyvi” formájukban szerepelnek. Sok olyan eset lehetséges, amikor az általános leírásuk önmagában is megfelelő megoldást ad egy modellezési problémára, de szintén sok szituációban indokolt lehet a módosításuk – például egy osztály egyszerre több mintában is szerepet játszhat, vagy plusz funkcionalitással kell kiegészíteni. Ilyen esetekben a csak pontos egyezést vizsgáló algoritmusok a legkisebb mértékű változtatás miatt is adhatnak hamis választ. Ezzel szemben a hasonlósági értékekkel az átalakított példányok is kinyerhetők. Legtöbbször ezekhez a keresésekhez egy küszöbérték paraméter is tartozik, amely állításával megadhatjuk, hogy mekkora hasonlósági érték felett tekintünk egy potenciális illeszkedést találatnak. Így a vizsgálat rendszerenként finomhangolható, és ha a küszöböt a lehetséges maximális értékére állítjuk, akkor a pontos egyezés is szimulálható.
2.1.2. A vizsgálat aspektusa szerinti csoportosítás
anObjectStructure
aConcreteElementA
aConcreteElementB
aConcreteVisitor
accept( aVisitor ) visitConcreteElementA( aConcreteElementA )
operationA()
accept( aVisitor ) visitConcreteElementB( aConcreteElementB )
operationB()
2.1. ábra: A Visitor minta dinamikája viselkedési elemzéshez 1
Arra is több lehetőség van, hogy a rendszert milyen oldalról vizsgáljuk. Ez lehet:
1
Forrás: http://java.boot.by/scea5-guide/ch07s02.html
10
Szerkezeti: Ekkor csak a szoftver statikus felépítése releváns. Abból kinyerhetünk olyan, osztályokra vonatkozó információkat, mint például „Mely osztályok az ősei/leszármazottai”, „Mely osztályokkal van kapcsolatban (asszociáció)”, „Mely osztályok példányait tartalmazza (kompozíció, aggregáció)”, „Absztrakt-e”, „Tartalmaz-e másik osztályéval hasonló signature-ű metódust”, stb. Ezek az információk – mint ahogy a csoport neve is mutatja – bőven elegendők a szerkezeti tervezési minták felismeréséhez, de lehetnek helyzetek, amikor másra is szükség van.
Viselkedési: Itt már nem az a fontos, hogy egy adott osztály mikkel léphet kapcsolatba, hanem hogy ténylegesen mikkel lép kapcsolatba. Sok mintánál előfordulnak olyan gyakori, egymást követő eseménysorozatok, amelyek szűrésével pontosíthatjuk a keresést. Ezek elemzéséhez az egyik legelterjedtebb és legpontosabb módszer a kód futtatása és hívási gráfok építése. Emellett léteznek statikus
alapú
algoritmusok
is,
amik
valamilyen
statisztikai
becsléssel
következtetnek a valós dinamikus viselkedésre.
Szemantikai: Az utolsó – és az NLP relatív fejletlensége miatt valószínűleg legkevésbé használt – aspektus a forrásban használt nevezéktanok figyelembe vétele. Ez magában foglalhatja az attribútumok/metódusok nevére történő reguláris kifejezés illesztéstől a hozzájuk tartozó kommentek átfésüléséig mindent. Önmagában talán nem a legjobb mintakeresési eljárás, de egy korábban kiválogatott találatlista szűkítésében, vagy éppen küszöbérték alatti fals negatívok jelzésében hatékony segítséget nyújthat.
2.1.3. A rendszer reprezentálása szerinti csoportosítás Gyakran használt lehetőségek a vizsgált rendszer ábrázolására:
AST: Absztrakt szintaxis fa ( Abstract Syntax Tree ), általában nyelvfüggő forma, ami az adott programozási nyelv elemeit hierarchikus szerkezetben tárolja. Csomópontként szerepelhet benne például egy osztály, aminek gyerekei az attribútumai és metódusai – amelyeknek esetleg további gyerekei a hozzájuk tartozó típusinformációk, módosítók, stb.
11
Root class: ClassA attribute: A type: int visibility: private
class: ClassB method: M param: P
2.2. ábra: Minta egy absztrakt szintaxisfára2
Mátrix: Ha a rendszert csak jól definiált tulajdonságok egy halmaza szerint elemezzük, akkor tárhely és feldolgozhatóság szempontjából is érdemes lehet a mátrixok használata. Például az előforduló asszociációkat ábrázolhatja egy – a gráfok szomszédsági mátrixaihoz nagyon hasonló – totálisan unimoduláris mátrix, ahol 1 jelezné, hogy a sor osztálya asszociált az oszlop osztályával, 0 pedig a kapcsolat hiányát. Ha a külön tulajdonságokhoz különböző prímeket rendelünk, és csak egy mátrixot használunk, – ami a releváns prímek szorzatait tárolja mezőnként – akkor még kevesebb hely szükséges.
2.3. ábra: Rendszertulajdonságok ábrázolása mátrixokkal
2
Saját rajz, a [2]-ben található AST ábra általánosított változata
12
ASG: Absztrakt szemantikai gráf ( Abstract Semantic Graph ), két lehetséges eleme a csúcs, ami egy, a forrásban előforduló entitást jelöl, és az él, ami pedig az ezek közötti kapcsolatot és annak típusát mutatja.
XML: A napjainkban olyan gyakran használt formátum éppen azért népszerű, mert tetszőleges tag-ek és szerkezetek definiálhatók benne, így alkalmas lehet többet között analizálandó szoftverek forrásának tárolására is.
2.1.4. A minták reprezentálása szerinti csoportosítás Az előző pontban leírt módszerek a tervezési minták leírására is vonatkozhatnak. Nyilván logikus választás, ha a rendszert és a mintát azonos módon ábrázoljuk, de ez egyáltalán nem kötelező és nagyban függ az alkalmazott algoritmustól is. Persze a fentieken kívül még számtalan mód lehet az elvárt viselkedés reprezentálására. Például valamilyen szintaxis szerinti formális logikai specifikáció, amit a rendszerből előállított tényekre illesztünk, vagy akár egy vizuális nyelvtanban megadott pattern, amit képfeldolgozási módszerekkel vetünk össze a rendszer – például gráfként – ábrázolt változatával. A lehetőségek, és az azokon belüli variánsok száma gyakorlatilag végtelen.
2.1.5. Az eredmények formátuma szerinti csoportosítás Az sem lényegtelen, hogy a keresést végző algoritmus mekkora információtartalmú válaszokat ad. Nagyban csökkentheti a komplexitást, ha csak a találatok darabszámát várjuk el. Viszont ha arra is szükség van, hogy melyik osztály melyik mintabeli szerepre illeszkedik, akkor már nem minden esetben annyira könnyű a helyzet. Ezen felül a válasz tartalmazhatja a rendszerosztályok forrásfájlját – és akár az azon belüli sorszámot –, vagy például közelítő illesztésnél a hasonlóság mértékét is.
2.2. Mintafelismerés mátrixokkal Az általam választott módszer egy olyan struktúrális, közelítő értékekkel dolgozó vizsgálat, ami mind a rendszert, mind a tervezési mintákat mátrix formában tárolja [1]. Az illesztést Blondel gráfhasonlósági algoritmusa [4] végzi, a kiértékelés pedig parametrikus küszöbértékkel, illetve ennek esetleges csökkentésével és adott rendszerosztályok ideiglenes törlésével történik.
13
2.2.1. Az adatok reprezentálása A hatékony felismeréshez a rendszer több különböző tulajdonságát kell elemeznünk, ezért a system és a pattern is egy-egy mátrix-csoporttal fejezhető ki, amiben minden adott jellemzőhöz tartozik egy mátrix. A tervezési mintákat – mivel azt, hogy mit keresünk, úgyis nekünk kell megadnunk – azonnal ilyen formára alakíthatjuk és tárolhatjuk őket fájlokban vagy egy adatbázisban. A rendszerből kinyerhető információkat viszont minden külön keresésnél manuálisan kell erre a köztes formára hoznunk. Ez jelen esetben nem a nyers kódból, hanem a forrás LIM-es változatából [5] fog történni.
2.2.2. Blondel algoritmusa Ha minden szükséges adat a helyén – és megfelelő formában – van, akkor futtathatjuk a felismerés lényegi részét, vagyis Blondel hasonlósági algoritmusát [4]. Ez a módszer a tervezési minták felismerésénél sokkal általánosabb, két tetszőleges – szomszédsági mátrixszal megadott – GX és GY gráf csúcsai közti hasonlóságot és annak mértékét számítja ki. Mivel minden GX-beli csúcsot minden GY-beli csúccsal össze kell vetni, ezért az eredmény is egy mátrix, aminek minden értéke GX sor-adik és GY oszlop-adik csúcsának egyezési pontszámát tartalmazza. Az algoritmus pszeudokódja a következő: 1. Legyen A a GX gráf nX × nX méretű szomszédsági mátrixa. 2. Legyen B a GY gráf nY × nY méretű szomszédsági mátrixa. 3. Legyen Z0 egy nY × nX méretű konstans 1-eket tartalmazó mátrix. 4. Iteráljuk páros sokszor a következőt:
‖
‖
5. Álljunk meg, ha Zk értéke konvergál. 6. Az
eredményként
visszaadott
S
hasonlósági
mátrix
Zk
utolsó értéke. A mintafelismerésben ez az algoritmus úgy használható, hogy a rendszerben és a mintában közösen előforduló összes tulajdonság mátrixára egyesével lefuttatjuk, majd az így kapott mátrixokat összegezzük és átlagoljuk. Az eredmény egy olyan mátrix, ami már 14
absztraktabban, egyes tulajdonságok illeszkedése helyett azt mutatja, hogy az adott rendszerosztály mennyire hasonlít a tervezési minta valamelyik szerepére. Ez sokkal pontosabb lehet, mint más, „hagyományos” gráfillesztő algoritmusok által adott eredmények. Ha azok csak pontos izomorfizmusokat vesznek figyelembe, akkor az illeszkedés szerinti csoportosításról szóló részben kifejtettek alapján világos, hogy kis eltérések is okozhatnak hamis negatív válaszokat. Ha pedig képesek is valamilyen gráfelméleti alapú közelítésre – például hány változtatást kellene végrehajtani az egyik gráfon, hogy izomorf legyen a másikkal –, akkor sem lesz mindig pontos, mert az objektumorientáltság szemantikája miatt könnyen előfordulhatnak olyan esetek, amikor két gráf szerkezete látszólag eltérő, de az általuk reprezentált működés közel sem annyira. Blondel algoritmusa viszont ilyenkor is helyesen becsli meg a hasonlóságot, ezért eredményesebben használható például eredeti formájuktól különböző alakban szereplő tervezési minták felismerésére.
2.2.3. Többszörös illeszkedés Az eredményül kapott mátrix értékei a [0,1] intervallumon helyezkednek el, ahol 1 jelenti a teljes hasonlóságot és 0 az egyezés teljes hiányát. Viszont, mivel a keresési algoritmus normalizálást is tartalmaz, ezek az értékek nem csak az illeszkedéstől függenek, hanem egymástól is. Például egy pontszám tökéletes hasonlóság mellett sem lesz 1, ha a rendszerben van több osztály is, amik ugyanazon szerep felé hajlanak. Vagyis ha két egyformán jó találat van egy oszlopban, akkor az algoritmus mindkettőhöz 0,5-öt fog rendelni, így egyikük sem jelenne meg egy 0,6-os küszöbszámú keresésnél. Ezt a problémát lehet úgy is kezelni, hogy a teljes rendszert öröklődési hierarchiákra bontjuk, és feltételezzük – a gyakorlati példákból következtetve helyesen –, hogy ezeken belül már nem lesz többszörös illeszkedés [1]. Én azonban egy multiplicitás paramétert használok, ami annyit jelent, hogy a küszöböt hajlandó vagyok n-edére csökkenteni, ha ez esetben legalább n darab találat is lenne. Ha van ilyen csoport, akkor felteszem, hogy az értékeik azért alacsonyak, mert mind egyformán jól illeszkednének, csak a normalizálás közbejátszott. Megoldásként a jelöltekből egyszerre egyet választok, a többit ideiglenesen törlöm a rendszerből és rekurzívan újrafuttatom a kereső algoritmust. Ha az osztály ekkor sem ér a küszöb fölé, akkor csak egy kis vizsgálati időt vesztettünk, ha viszont igen, akkor láthatjuk, hogy valós találat, amit a környezete „fedett el”.
15
A multiplicitás paraméter tehát megadja, hogy a határérték hányadáig próbálkozhatunk. Az irreleváns találatok elkerülése és a keresés szükségtelen hosszabbítása miatt ezt a küszöbcsökkentő engedményt szerepenként csak egyszer hajtom végre.
16
3. A MÁTRIX ALAPÚ ALGORITMUS IMPLEMENTÁCIÓJA Miután az eddigiekben megismerkedtünk a mintafelismerés elméleti hátterével, lehetőségeivel és ki is választottunk egy ígéretesnek tűnő módszert, ideje, hogy áttérjünk a konkrét implementációra. Ebben a fejezetben a PatternFinder program szerkezeti áttekintése, használata és paraméterezése, a fejlesztése során használt tervezési minták bemutatása és részletes leírása következik.
3.1. A PatternFinder áttekintése 3.1.1. Szerkezet
PatternFinder Matrix
SingleMatrix
Függőségek DPConstants
MatrixGroup uBLAS
Exception(s)
Config
ProgConstants
Pattern
PatternFinder
System
SystemState LIM
3.1. ábra: A PatternFinder szerkezete
A rendszer alacsony szinten egy, a boost [6] numerikus csomagjában található uBLAS-ra [7] épülő mátrix „wrappert” tartalmaz, ami egyrészt kényelmes – például objektumorientált 17
szintaxisú transzponálás, normalizálás és átlagolás, több felüldefiniált operátor az olvasható műveletekhez, stb. –, másrészt pedig lehetőséget nyújt mátrixok csoportos kezelésére. Egy absztrakcióval feljebb ezt használja fel a forrást és a mintát ábrázoló osztály is. A rendszer betöltéskor kód helyett az abból előre elkészített .lim kiterjesztésű fájlban lévő gráfot járja be és a kinyert információkat szempontonként mátrixokba gyűjti. A különböző vizsgálati aspektusok reprezentálásához egy másik fájl szimbolikus konstansokat is tartalmaz. A mintákat viszont egyszerűen csak be kell olvasni, előfeldolgozást nem igényelnek, hiszen eleve a kívánt formában tárolhatók. A legfelső szinten pedig a PatternFinder osztály található, ami a Config osztály segítségével értelmezi a parancssori argumentumokat, majd inicializálja a mátrixokat és futtatja a korábban bemutatott keresési algoritmust. Találat esetén kiírja, hogy melyik forrásdarab melyik mintabeli szerepre illeszkedik, és hogy mekkora konfidenciával. A rendszer továbbá saját kivételeket és visszatérési értékeket is definiál, a hiba-, progressés debuginformációk többszintű megjelenítéséről pedig a log függvény gondoskodik.
3.1.2. Használat A PatternFinder forrása *nix alapú rendszeren készült, így a fordítása és a paraméterezése is az ott megszokottakhoz alkalmazkodik – makefile tartozik hozzá, -p / --param alakú kapcsolók, stb. –, de semmilyen platformfüggő részt nem tartalmaz, ezért bárhol használható. Lehetséges parancssori argumentumai a következők:
-v / --verbosity: paramétere egy pozitív egész, ami megadja, hogy futás közben mennyire részletes kimenetet szeretnénk. 1 esetén – alapértelmezésben – csak a találatokat írja ki, 2-nél azok mellett a rendszer és a minta inicializálásával kapcsolatos lépéseket, 10 fölött pedig minden más, legtöbbször debughoz használható információt is.
-t / --threshold: paramétere egy tetszőleges [0,1] intervallumba eső lebegőpontos szám, a mintaillesztés küszöbértéke. Alapértelmezésben 0,5.
-c / --convergence: Blondel hasonlósági algoritmusának iteratív számítási része elviekben csak akkor ér véget, ha a mátrixok szorzata konvergál, ami esetenként nagyon sokáig is tarthat – és kerekítési hibák miatt akár végtelen ciklushoz is vezethet. Ezért célravezetőbb lehet, ha a folyamatot egy adott maximális ismétlésszám után befejezzük, az így kapott eredmény is kellően közelítheti a
18
keresett hasonlóságot. A -c kapcsoló paramétereként ezt a felső határt jelentő pozitív egészt várja. Alapértelmezésben 100.
-m / --multiplicity: paramétere a többszörös illeszkedésről szóló részben bemutatott pozitív egész, ami az esetleges küszöbcsökkentések maximális számát adja meg. Alapértelmezésben 10.
A keresés futtatásához tehát első és második pozícionális paraméterként a rendszert reprezentáló .lim fájlt és a tervezési mintát ábrázoló .pattern fájlt kell megadnunk, ezután pedig a fent említett négy kapcsoló bármelyikét alkalmazhatjuk, tetszőleges sorrendben. Például: PatternFinder system.lim pattern.pattern -t 0.4 -c 200
3.2. Függőségek 3.2.1. LIM A LIM – vagyis Language Independent Model – egy, a Szegedi Tudományegyetemen kifejlesztett nyelvfüggetlen rendszermodell [5]. Segítségével a forrásból kinyerhető információkat a kód lexikális elemzésénél absztraktabban, gráfszerű szemantikával járhatjuk be. Gyakorlatilag egy általánosított ASG, ami csomópontokkal reprezentálja az entitásokat – osztály, interfész, metódus, attribútum, stb. – és élekkel pedig az ezek közti kapcsolatokat. A PatternFinder fordításához szükségesek a LIM-hez tartozó fejlécek és könyvtárak, mert a System osztály egy .lim kiterjesztésű fájlban tárolt gráf analizálásával állítja elő a később használatos rendszermátrixokat.
3.2.2. uBLAS Az uBLAS [7] a boost [6] C++ kódkönyvtár numerikus csomagjában található, alapvető lineáris algebrai számítások elvégzését támogató osztályok és template-ek gyűjteménye. A PatternFinder lefordításához – néhány másik boost header-rel együtt – nélkülözhetetlen, mert a SingleMatrix az itt már megvalósított mátrixokkal kapcsolatos osztályokra és műveletekre épül.
3.3. Belső tervezési minták Ha már jelen dolgozatban a tervezési minták használatának és felismerésének fontosságát hangsúlyozom, külön szót ejtenék az implementáció során alkalmazott mintákról is [3]. 19
3.3.1. Singleton
3.2. ábra: A Singleton minta UML diagramja3
A Singleton létrehozási minta célja, hogy egy adott osztályból egyszerre csak korlátozott számú példány létezhessen, és ezekhez szabványos módon bárhonnan hozzá lehessen férni. Ezt egy osztály úgy érheti el, ha csak privát – vagy protected – konstruktorral rendelkezik, és saját típusú statikus adattagot tartalmaz, amibe csak egyszer tárol el példányt, minden további lekérés esetén azt adja vissza. Ez a specifikáció magától értetődően jó választás volt a System, a Pattern, a Config és a PatternFinder osztályoknál is.
3.3.2. Composite
3.3. ábra: A Composite minta UML diagramja4
3
Forrás: http://en.wikipedia.org/wiki/Singleton_pattern
4
Forrás: http://en.wikipedia.org/wiki/Composite_pattern
20
A Composite egy szerkezeti minta, ami arra szolgál, hogy objektumokat, illetve az adott objektumokból álló csoportokat azonosan kezelhessük. Ehhez először egy, a közös viselkedést modellező interfészt definiálunk, majd ezt megvalósítjuk a konkrét egyeddel és egy tömbszerű osztállyal is, ami interfész típusú – vagy ha korlátozni akarjuk a rekurzió mélységét, akkor konkrét egyed típusú – objektumokat tárolhat. Ez a minta a PatternFinder-ben a mátrixok reprezentálásánál játszott fontos szerepet, mert így Blondel algoritmusát nem kell aspektusonként külön végrehajtani, azonos formában használhatjuk mátrixok csoportjait is.
3.3.3. Memento
3.4. ábra: A Memento minta UML diagramja
A Memento viselkedési minta akkor használható, ha egy objektum belső állapotát az egységbezárás megsértése nélkül szeretnénk egy „külső” helyen tárolni. Az Originator szerepkört betöltő objektum állapota tetszőleges időpontban egy ilyen memento-ba menthető, és később ugyanígy vissza is állítható, ezért is szokták leggyakrabban undo/redo jellegű funkcionalitás implementálásakor alkalmazni. Ezt a sablont a PatternFinder-ben a System, SystemState, PatternFinder hármas valósítja meg. A többszörös találatok miatti küszöbcsökkentés során szükség van rendszerosztályok ideiglenes törlésére, de hogy ezt később helyre is hozhassuk, a PatternFinder egy SystemState-ekből álló vermet tart fent.
21
3.3.4. Visitor
3.5. ábra: A Visitor minta UML diagramja5
A Visitor egy olyan viselkedési minta, melynek célja, hogy anélkül hozhassunk létre egy objektumhoz vagy objektumok egy csoportjához tartozó új műveleteket, hogy azok szerkezetét módosítanunk kellene. Ez a minta a LIM [5] implementációjában szerepel, a PatternFinder csak néhány megfelelő visit metódust deklarál a System osztályban a bejáráshoz.
3.4. A rendszer részletes bemutatása Az eddigiek alapján remélhetőleg sikerült egy átfogó képet kapnunk a PatternFinder működéséről. A következő részekben egy alacsonyabb szintű elemzés és az implementációs részletek bemutatása következik.
5
Forrás: http://en.wikipedia.org/wiki/Visitor_pattern
22
3.4.1. A mátrixok Mivel a rendszer keresési módszerének alapja Blondel algoritmusa [4] – aminek pedig a mátrixok –, ezért már az implementálás korai szakaszában kulcsfontosságú volt egy olyan környezet megteremtése, amelyben könnyen, intuitíven és hatékonyan használhatunk mátrixokat és végezhetünk rajtuk műveleteket. A hatékonyságért az uBLAS-ból [7] importált, sebességre optimalizált mátrix reprezentációk és operációk, a könnyűségért a köréjük épített wrapper felel. Ahhoz pedig, hogy a módszer magját adó iterációt intuitívan tudjuk lekódolni – vagyis ne kelljen a rendszer minden aspektusára egyesével futtatni –, a Composite minta segítségével egy egyszerre több mátrixot is tartalmazni képes gyűjtőosztályt is létrehoztam. A közös publikus interfészt a Matrix absztrakt osztályban definiáltam. Itt olyan tagfüggvények deklarációja szerepel, mint például a mátrixot saját egyes normájával leosztó normalize(), a helyben transzponálást végző transpose(), a sorokat és oszlopokat indexeik halmazának megadásával eltávolítani képes kill( rowIDs, colIDs ) és egy öröklődésre felkészített kiíratási szerkezet. Ez egy ezen a szinten megvalósított << operátort jelent, ami csak átadja a vezérlést az egyelőre pure virtual display metódusnak, így a leszármazó osztályoknak csak azt kell felüldefiniálniuk, és máris egyszerűen megjeleníthetők. Ezeken felül azt szerettem volna, hogy az eredmények könnyen leolvashatók legyenek, és hogy a mátrixműveletek után ne kelljen külön energiát fordítani arra, hogy előkeressük, melyik sor/oszlop melyik rendszerosztályt vagy mintabeli szerepkört jelöli. Ezért a hagyományos mátrixot címkézettre változtattam, és már itt definiáltam az x és y tengely mentén lévő feliratok számára két string vektort. A Matrix-ban előjelzett működés egyedülálló mátrixokra vonatkozó megvalósítását a SingleMatrix osztály tartalmazza. Itt az eddig említetteken kívül implementáltam egyszeres és többszörös mátrixszal való szorzást – az uBLAS [7] prod függvényével –, összeadást, osztást, értékadást és összehasonlító operátorokat is. A mátrix méreteinek lekéréséhez a size1() és a size2() metódusok használhatók. Mivel itt még egyértelmű, hogy melyik mátrixra célzunk – tekintve, hogy egy darab van, nem úgy, mint a többszörösnél –, itt készítettem el a () operátort index alapú, és a byLabels( y, x )6 tagfüggvényt címke alapú értékeléréshez. Az osztály a könnyű inicializálhatóságért egy statikus constant( x, y, value ) függvénnyel is rendelkezik.
6
A paraméterek azért ilyen sorrendben szerepelnek, mert a tulajdonságmátrixok nem mindig
szimmetrikusak, és így intuitívebb utalni arra, hogy melyik osztály – y – van kapcsolatban melyikkel – x.
23
A SingleMatrix kompozit párja a MatrixGroup, aminek fontos korlátozása, hogy csak azonos méretű mátrixok tárolására alkalmas – a későbbi szorzások és a méret egységes lekérhetősége miatt. Minden eddigi funkcionalitást tartalmaz – csak végigiterál a mátrixain, és delegálja a megfelelő hívást – és azokon felül még a „gyerekek” kezelésére szolgáló add( key, matrix ), remove( key ) és exists( key ) függvényeket is. A bennfoglalt mátrixokhoz egyesével a [] operátorral, együtt pedig a matrices() metódussal férhetünk hozzá. Az iterációs algoritmusra előkészülve egy olyan beépített cache-elést is megvalósítottam, ami egyenlőség ellenőrzésekor eltárolja mindkét félben, hogy egy adott aspektus szerinti SingleMatrix-uk egyezett-e. Ha ez a flag beáll, akkor onnantól kezdve az a mátrix nem vesz részt semelyik olyan műveletben, ami Blondel módszere során előfordul, így sok felesleges számolástól megkímélheti a processzort, ha például az egyik szempont információit tartalmazó mátrixra hamarabb konvergálna a kereső ciklus, mint egy másikra. Ahhoz, hogy ez ne keveredjen az „egyszerű” == operátorral – és hogy olvashatóbb legyen a forrás –, erre a függvényre convergedTo( otherMatrix ) néven lehet hivatkozni. A flag-ek visszaállítását a clearConverged() végzi. Mivel az algoritmus végén csak egy mátrixra van szükség, ezért az átlagolás céljából egy average() metódust is készítettem, ami a MatrixGroup-ot minden pozíció számtani közepeiből álló SingleMatrix-szá konvertálja.
3.4.2. System A System osztály a vizsgált rendszert reprezentálja. A rendszer pedig – az adatok kigyűjtése után – nem más, mint egy MatrixGroup. Ezért az osztály egyik lényegi összetevője a data() nevű függvények által hozzáférhető mátrixcsoport eltárolása. A másik elsődleges funkcionalitása ezeknek az adatoknak a kezdeti előállítása. Ehhez először a load() metódusában – nem a konstruktorában, mert Singleton – egy stringet vár a beolvasandó .lim nevével. Ha azt – a columbus-ban és annak al-namespace-eiben található eszközökkel – sikeresen betöltötte, saját magával „vizitálja” a kész gráfot. Ezt azért teheti meg, mert maga is a VisitorAbstractNodes osztályból származik, és így egyéni visit() tagfüggvényeket definiálhat. A PatternFinder ebben a fázisban jelenleg öt típusú információt gyűjt – leszármazás, absztrakt osztály, önreferencia visszaadása, önreferencia tartalmazása, privát konstruálhatóság – a logical csomagban lévő Class, Method és Attribute csomópontok vizsgálatával. Miután a releváns értékeket a kezdetben konstans nulla mátrixok megfelelő pozíciójában rögzítette, készen áll a keresés megkezdésére [5].
24
A System működéséhez tartozik még a SystemState osztály is, ami az előbbi belső állapotát a Memento tervezési mintának megfelelően tárolja. Erre bővebben majd a PatternFinder osztály find() metódusánál térek ki.
3.4.3. Pattern A Pattern osztály a System-hez hasonlóan csak egy vékony szemantikai Singleton wrapper egy kitüntetett MatrixGroup köré. Plusz szerepe a .pattern kiterjesztésű fájlok beolvasásánál jelentkezik – ami itt is a load() metódusban történik. Ezek a fájlok tetszőleges tervezési minták már eleve „mátrixos” formában megfogalmazott alakjait hivatottak tárolni. Szerkezetük a következő – a Composite mintán keresztül bemutatva: Composite
A minta neve
Structural
A minta típusa
3
A mintában résztvevő osztályok száma
Component Composite 0 0 0 0 0 0 0 1 0 0 …
}
A minta szerepköreinek nevei
Leaf
Egy konkrét aspektus (asszociáció)
}
Az aspektushoz tartozó mátrix …
3.1. táblázat: A .pattern kiterjesztésű fájlok szerkezete
Ha a betöltés sikeresen megtörtént, akkor onnantól a Pattern osztály csak azt a célt szolgálja, hogy egy központosított elérési lehetőséget biztosítson az adatokhoz.
3.4.4. Config A Config osztály – szintén Singleton, mert csak egy példány lehet belőle, ami viszont bárhonnan elérhető kell, hogy legyen – a parancssori argumentumok feldolgozásáért felel. Előkészítésekor az initialize() metódusa paraméterként a main() argc-jét és argv-jét kapja, amelyekből felismeri a pozícionális értékeket – a .lim és a .pattern fájlok neveit – és a lehetséges kapcsolókat. Ha az azokhoz tartozó értékek nem léteznek, range-en kívül esnek vagy esetleg nem is megfelelő típusúak, akkor alapértelmezett értéket kapnak.
25
A paraméterekre kódból a következőképp hivatkozhatunk: Config::instance().param( "nameOfParam" ); Ez – tekintve, hogy a parancssorban minden string – a nameOfParam kulcshoz tartozó stringet fogja visszaadni, ha az létezik, és egy Exception-t dob, ha nem. De hogy ne kelljen sokszor külön a stringek számmá alakításával foglalkoznunk, definiáltam egy doubleParam() metódust is, ami a boost [6] lexical_cast operátorát és négy jegyre pontos kerekítést alkalmazva egyből lebegőpontos értékkel tér vissza.
3.4.5. PatternFinder A PatternFinder osztály a rendszer lelke, itt történik a mintafelismerés. Inicializálása során előkészít egy vermet a SystemState-eknek, egy halmazt azoknak a mintaszerepeknek, amelyeknél már volt küszöbcsökkentés, a Config alapján betölti a System-et és a Pattern-t és végül veszi a metszetüket – csak azokhoz az aspektusokhoz tartozó mátrixokat hagyja meg, amelyek mind a rendszerben, mint a mintában előfordulnak. Ezután indul a find() futása, ami először a System- és Pattern mátrixokon végrehajtja Blondel algoritmusát – blondel() –, majd az ebből kapott hasonlósági mátrixot elemzi az analyze() függvénnyel. Ha minden mintaszerephez pontosan egy darab küszöbérték feletti találat tartozik, akkor kiírja, hogy melyikhez melyik rendszerosztály illeszkedett, és hogy mekkora konfidenciával. Ha viszont van olyan mintakomponens, amihez több találat is lenne – esetleg csak a határ csökkentése után –, akkor azokat egy jelölt listába helyezi, és végül ennek a listának a legkisebb számosságú elemét adja vissza. Ha ez nem üres, akkor elmenti a System jelenlegi állapotát egy SystemState-be, ezt a states verem tetejére helyezi, majd a choose() segítségével úgy töröl ideiglenesen a rendszerosztályokból, hogy egyszerre mindig csak egy maradhasson a jelöltek közül és rekurzívan megismétli a keresést. Végül helyreállítja a System előző állapotát és befejezi a futását.
3.5. Továbbfejlesztési lehetőségek A PatternFinder, habár jelenlegi formájában is életképes lehet, sok helyen javítható. Egyrészt – mivel ez a dolgozat inkább a központi algoritmus fejlesztésére összpontosított – mennyiségileg is eredményesen bővíthető plusz tervezési minták .pattern formájú reprezentálásával vagy a LIM-ből kinyerhető egyéb információk feldolgozásához szükséges visit() metódusok megírásával. 26
Másrészt a kód műveleteinek hatékonyabbá tételével is egyre nagyobb méretű rendszerek vizsgálatára nyílna lehetőség. A cél a kitűzött funkcionalitás elérése volt, optimalizálásra aránylag kevés idő/energia jutott. Ezek mellett természetesen a legnagyobb előrelépést a forrás futás közbeni dinamikus elemzése, viselkedési vizsgálata jelentené. Abból sok olyan információ válna elérhetővé, ami LIM-ben nem kifejezhető. Végül javítási opció lehet a kód lexikai, szemantikai analizálása is. Önmagában nem a legjobb választás talán, de az előzőekben említettekkel kombinálva sok kétes esetben döntő szerepet játszhatna.
27
4. TESZTELÉS 4.1. A tesztelt rendszer A PatternFinder működését egy FormulaManager7 nevű programcsomagon teszteltem. Ez egy olyan alkalmazás, ami formulákat képes reprezentálni illetve kiértékelni. Különlegessége, hogy fejlesztése során kifejezett hangsúlyt fektettek arra, hogy minél több tervezési mintát belefoglaljanak az implementációba. Ezáltal sokkal életszerűbben mutatja be a minták előfordulását, mert más referencia megvalósításokkal szemben azok itt valós kontextusban, egymással együtt működve, esetleg eredeti formájuktól eltérő alakokban fordulnak elő.
4.2. Teszteredmények Az elvégzett tesztelés „proof of concept” jellegű, egyrészt időhiány miatt, másrészt pedig azért, mert jelen dolgozatnak nem célja hatékonysági referenciaértékek felállítása, csak a lehetőség demonstrálása, miszerint mátrix alapú műveletek is sikeresen használhatók a mintafelismerésben. A tesztelés során a FormulaManager-ből parse-olt .lim fájlra a Singleton tervezési minta következő reprezentációját illesztettem: Singleton Creational 1 Singleton 3 1 4 1 5 1
7
Forrás: http://www.sed.hu/src/FormulaManager/
28
Itt a 3, 4 és 5 sorban azt jelenti, hogy a vizsgált osztály: 3. tartalmaz-e olyan metódust, ami az osztályra mutató referenciatípust ad vissza 4. tartalmaz-e öntípusú attribútumot 5. tartalmaz-e privát konstruktort Az ezek után következő 1-ek pedig maguk az 1×1-es mátrixok, amik megadják, hogy a fenti tulajdonságok teljesülését el is várjuk. A program futását az alábbi paranccsal indítottam el: PatternFinder FormulaManager.lim patterns/singleton.pattern -t 0.3
Ami a következő eredményt írta ki: Match No: 1 Singleton --> XMLCreator#Cl (0.319444) Match No: 2 Singleton --> HTMLCreator#Cl (0.319444) Match No: 3 Singleton --> CSVCreator#Cl (0.319444) A FormulaManager forrásának manuális, statikus elemzésével könnyen kiderül, hogy az valóban csak ezt a három Singleton példányt tartalmazza. Mivel itt számíthatunk rá, hogy a tervezési mintákat meg is jelölték – hiszen felhasználásuk és annak dokumentálása a fejlesztés egyik explicit célja volt –, ezért elég egy egyszerű grep-féle keresést végeznünk. A grep [Ss]ingleton -C 3 -R . parancs kimenete a 4.1-es listázásban megtekinthető.
Ha a -v paramétert magasabb értékre állítjuk, akkor az úgy keletkező plusz információkból azt is megtudhatjuk, hogy a többi, küszöbérték alatt maradt osztály mekkora hasonlósági pontszámot kapott – a 4.2-es táblázatban csak a nem nulla értékek szerepelnek. A táblázatból jól látszik, hogy már három aspektus vizsgálata esetén is eléggé kiugró pontszámmal jelennek meg a valós találatok. Itt is megjegyezném, hogy a 0,3-as értéket nem „hagyományos” értelemben kell a hasonlóság mértékének tekinteni. Habár a pontszámok tényleg 0 és 1 közé korlátozottak, a keresési algoritmusban szereplő normalizálás és átlagolás a környezetétől nagyban függővé teszi egy adott osztály értékelését.
29
class XMLCreator : public OutputCreator { public: XMLCreator(vector<Expression*>,TreeOperations*,string); //pattern Singleton participant Singleton::Instance() static XMLCreator* instance(){ if (_instance == 0) _instance = new XMLCreator(); class HTMLCreator : public OutputCreator { public: HTMLCreator(vector<Expression*>,TreeOperations*,string); //pattern Singleton participant Singleton::Instance() static HTMLCreator* instance(){ if (_instance == 0) _instance = new HTMLCreator(); class CSVCreator : public OutputCreator { public: CSVCreator(vector<Expression*>,TreeOperations*,string); //pattern Singleton participant Singleton::Instance() static CSVCreator* instance(){ if (_instance == 0) _instance = new CSVCreator();
4.1. listázás: A kód statikus elemzésének kimenete
Singleton CSVCreator#Cl
0.3194444
ExpIterator#Cl
0.0416667
Expression#Cl
0.0416667
HTMLCreator#Cl
0.3194444
Iterator#Cl
0.0416667
IteratorPtr#Cl
0.1111111
IterState#Cl
0.1111111
List#Cl
0.0416667
MainMenu#Cl
0.0416667
MenuHelp#Cl
0.1666667
NullIterator#Cl
0.0416667
Table#Cl
0.0416667
XMLCreator#Cl
0.3194444
4.2. táblázat: A mintaillesztés eredménye
30
5. ÖSSZEFOGLALÁS A tervezési minták ismerete és használata az intelligens szoftverfejlesztés egyik fontos összetevője. Ezért is lényeges, hogy a modellezési fázisban alkalmazzuk ezt a tudást, illetve hogy minél könnyebben – optimális esetben automatikusan – képesek legyünk már kész forráskódból visszanyerni az ehhez kapcsolódó információkat. Dolgozatom első részében kifejtettem a tervezési minták hasznát és kitértem a detektálásukból származó előnyökre is. A második fejezetben különböző szempontok szerinti csoportosításban áttekintettem a szakirodalomban jelenleg leggyakrabban szereplő módszerek komponenseit, majd az általam választott, a mintaillesztést mátrixműveletekkel megvalósító algoritmust részletesebben is bemutattam. A harmadik fejezet az addigi elmélet konkrét implementációjáról szól. Itt először egy absztraktabb, később pedig egy alaposabb leírás szerepel a PatternFinder rendszerről. Esik szó a program használatáról, függőségeiről, a készítése során hasznosított, belső tervezési mintákról és az osztályhierarchiájáról is. Végül a negyedik fejezetben egy egyszerű teszt segítségével mutatom meg a módszer működését éles környezetben.
31
Irodalomjegyzék
[1]
N. Tsantalis, A. Chatzigeorgiou, G. Stephanides, S. Halkidis, Design Pattern Detection Using Similarity Scoring, IEEE Transactions on Software Engineering 2006
[2]
J. Dong, Y. Zhao, T. Peng, A Review of Design Pattern Mining Techniques, International Journal of Software Engineering and Knowledge Engineering 2009
[3]
E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software 1994
[4]
V. Blondel, A. Gajardo, M. Heymans, P. Senellart, P. Van Dooren, A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching, Society for Industrial and Applied Mathematics 2004
[5]
Á. Beszédes, R. Ferenc, T. Gyimóthy, Columbus: A Reverse Engineering Approach, In Pre-Proceedings of the 13th Workshop on Software Technology and Engineering Practice, IEEE Computer Society, 2005
[6]
Boost C++ Libraries, Website, 2012. http://www.boost.org/doc/libs/1_49_0/
[7]
uBLAS Basic Linear Algebra Template Library for C++, Website, 2010. http://www.boost.org/doc/libs/1_49_0/libs/numeric/ublas/
32
Nyilatkozat
Alulírott Bán Dénes, Programtervező Informatika szakos hallgató, kijelentem, hogy a dolgozatomat a Szegedi Tudományegyetem, Informatikai Tanszékcsoport Szoftverfejlesztés Tanszékén készítettem, a Programtervező Informatikus BSc diploma megszerzése érdekében. Kijelentem, hogy a dolgozatot más szakon korábban nem védtem meg, saját munkám eredménye, és csak a hivatkozott forrásokat (szakirodalom, eszközök, stb.) használtam fel. Tudomásul veszem, hogy szakdolgozatomat a Szegedi Tudományegyetem Informatikai Tanszékcsoport könyvtárában, a helyben olvasható könyvek között helyezik el.
2012. május 16.
................................................................. Bán Dénes
33
