Bonyolultsági mértékek szoftverek méréséhez oktatási segédlet

Bonyolultsági mértékek szoftverek méréséhez oktatási segédlet Király Roland TÁMOP 4.2.4. A/2-11-1-2012-0001 Nemzeti Kiválóság Program Jedlik Ányos Doktorjelölti Ösztöndíj a konvergencia régiókban pályázat. 2013.07.11

1. Bonyolultsági mértékek elemzése A mértékeket egy speciális adatszerkezet, a szemantikus gráf SG (lásd.: [10] cikkben) elemzése során gyűjtött információk felhasználásával számítjuk ki. Értékes sorok száma Az effective_lines_of_code a kódrészlet, konkrétabban a függvény, vagy modul azon sorainak számát adja, amelyek forrásszöveget tartalmaznak. Az effective jelző tehát azt jelenti, hogy az eredményben nem szerepelnek sem az üres, sem a kommenteket tartalmazó sorok. 1. Definíció. [effective_lines_of_code] Jelölje a forrásszöveg összes sorát L(M ), és a csak kommenteket tartalmazó sorokat K(M ) (K(M ) ⊂ L(M )). Ekkor a forrásszöveg értékes sorainak a száma, vagyis az: ELOC(M ) := |L(M ) \ K(M )|2.

A mérték alkalmazható az SG gráf tetszőleges moduljára: ELOC(mi ) := |L(mi ) \ K(mi )|, és használhatjuk modulok egy csoportjának mérésére is: ELOC(m1 , ..., mk ) :=

k X

ELOC(mi ).

i=1

Mindezek mellett az ELOC mértéket alkalmazhatjuk függvények egy csoportjára ELOC(f1 , ..., fk ) is. A mért függvények több modulból is kikerülhetnek. Az egyetlen kikötés, hogy az SG szemantikus gráf tartalmazza azokat. Fontos megjegyezni, hogy a ELOC(mi ) 6= ELOC(F (mi )), vagyis a modulra mért érték nem azonos a függvényeire mért eredmények összegével, mivel a modul a függvények lexikális elemein kívül tartalmazhat rekordokat, makrókat, és egyéb elemeket.

1

Átlagos sor hossz Az average_length_of_line mérték az adott függvényben, vagy modulban található sorok hosszának az átlagát adja vissza. (A strukturált bonyolultság lekérdezésére kifejlesztett (és a ??. fejezetben bemutatott) nyelvtan segítségével, a max_length_of_line mértékhez hasonlóan ez az érték is előállítható, ha alkalmazzuk annak avg, vagy sum nevű filtereit, de a belső interface számára fontos, hogy a mértékek külön is szerepeljenek.) Ez a mérték annak ellenére, hogy nem tűnik fontosnak, nem kihagyható, mivel az egyes programozók, és cégek programjaiknál előírják az átlagos sorhosszok alkalmazását, valamint a forrásszöveg olvashatóságát rossz irányba befolyásolhatják a túl hosszú sorok. Az eredmény kiszámításához a ELOC mértéket kell alapul vennünk, és a ??.1. definícióban leírtak szerint ki kell számítanunk a sorok hosszát, majd a kapott eredményt átlagolnunk, vagyis az ALOL(M ) = b

ELOC(M ) c. CHOC(M )

Az ALOL mérték nem veszi figyelembe az eredmény meghatározása során az üres, vagy a kizárólag kommenteket tartalmazó sorok hosszát. A szemantikus gráf bejárása szintén azonos az ELOC mértéknél bemutatottal. A mértéket alkalmazhatjuk függvények, vagy modulok mérésére is, de fontos megjegyezni, hogy az ALOL(mi ) 6= ALOL(F (mi )) vagyis a függvények átlagos sorhossza nem azonos a modul átlagos sorhosszával.

Karakterek száma A chars_of_code a programszöveg karaktereinek számát adja vissza. A mérés során kapott érték nem tartalmazza a kommentek jeleinek a számát, valamint nincs benne a sortörés, és egyéb white space karakterek száma sem. 2. Definíció. [chars_of _code] Ha L(M ) a forrásszöveg összes sora, és K(M ) a csak kommenteket tartalmazó sorok, S = L(M )\K(M ) az értékes sorok halmaza, si ∈ S ennek a halmaznak egy eleme, wi az si sorban található kommentek, és white space karaktereinek halmaza, és n = |S|, akkor CHOC(M ) =

n X

(|si | − |wi |)

2

i=1

A mérték az effective_lines_of_code-hoz hasonlósan alkalmazható függvények csoportjára CHOC(f1 , ..., fj ), de használhatjuk egy modul COC(mi ), vagy modulok egy csoportjának COC(m1 , ..., mj ) mérésére. Mivel a CHOC mérték alapja a sorok, és a sorok jeleinek a száma, itt is igaz, hogy a CHOC(mi ) 6= CHOC(F (mi )), vagyis a modulra mért összesített érték nem azonos a függvényeire mért eredmények összességével. A mérték kiszámításához szükséges gráf útvonal azonos a effective_lines_of_code mértéknél definiálttal, de itt az útvonalak bejárásával kapott csomópontokban talált lexikális elemek jeleinek számát kell összegezni ahhoz, hogy az eredményét megkapjuk.

2

1. Állítás. Jelölje a megfelelő gráfútvonalon kapott eredmény listát L, jelölje az L egy p eleméhez kötött kommentek jeleinek számát c(p), valamint az ugyanezen elemekhez kötött akárhány sorvége jelek számát db(p ↓), és a p ∈ A által reprezentált forrásszöveg elemeinek hosszát length(p). Ekkor a mérték eredménye, vagyis X CHOC(M ) = (length(p) − c(p) − db(p ↓)). p∈L

Függvények száma A number_of_functions mérték a modulokban definiált függvények számát adja vissza. Ez a mérték különösen releváns funkcionális programok jellemzése során, mivel azok nagy számban tartalmaznak függvény konstrukciókat, így a lines_of_code mellett, annak használatával következtethetünk a modulok méretére. 1. Megjegyzés. Az -import(m,f ). formulával láthatóvá tett függvényeket, valamint az F (M ) függvényei által hívott függvények számát a mérték nem tartalmazza, ai : m : f(e1 , ..., en ) vagy f(e1 , ..., en ) valamint a több ággal (clause) rendelkező függvények ágait nem számolja bele az összesített értékbe. Az m : f (e) formula a minősített hívásokat jelöli, f (e) pedig a más modulokból importált, valamint a mért modulban hívott függvényeket, e és ei ∈ E tetszőleges kifejezések, amelyek a meghívott függvény aktuális paraméterei. 3. Definíció. [number_of _f unctions] A mérték eredménye az SG szemantikus gráfban szereplő összes modulra N OF (M ) = |F (M )|. A mérték segítségével mérhetünk egy modult N OF (mi ) = |F (mi )|, vagy modulok egy csoportját N OF (m1 , ..., mk ) =

k X

|F (mi )|.

i=1

Makrók száma A number_of_macros mérték az adott modulban, vagy modulokban definiált makrók, pontosabban makró definíciók számát adja meg. 2. Megjegyzés. Makró definíciók: def1 (v1 , e1 ). .. . deft (vt , et ).

3

makró definíciók, ahol vi ∈ V makró nevek, és ei ∈ E kifejezések, amelyeket a makró nevére hivatkozva érhetünk el azokban a modulokban, ahol a makró definíciója látható. 4. Definíció. [number_of _macros] Az mi ∈ M modul által tartalmazott makró definíciókat jelölje D(mi ) := {def1 , .., deft }, ahol defi egy makró definíció. A D(mi ) a fejléc fájlokkal láthatóvá tett makró definíciókat nem tartalmazza. Ekkor a mérték eredménye az összes modulra X N OM (M ) = |D(m)|.2 m∈M

A mérték használható egy modulra: N OM (mi ) = |D(mi )|, és alkalmazható modulok egy csoportjára is N OM (m1 , ..., mk ) =

k X

|D(mj )|.

j=1

Rekordok száma A number_of_records mérték az adott modulban definiált rekordok számát adja vissza. A rekordok használatának lehetősége sok esetben olvashatóbbá, de mindenképpen alakíthatóbbá teszi a forrásszöveget azáltal, hogy a rekordokat használhatjuk a függvény paraméterek dinamikusabbá tételére. A rekord update [?] mechanizmus alkalmazásával a rekordokat a függvények formális paramétereként használva, a paraméter lista aktualizálása során nem kell minden rekord mezőt szerepeltetnünk, és a rekord mezők bővítésével a függvények paraméterezésének átalakítása nélkül adhatunk extra információt a függvény ágakhoz, más ágak megváltoztatása nélkül. Mintaillesztés során tuple mintára illeszthetünk rekordokat, és ez fordítva is történhet azzal a megkötéssel, hogy az n-es első eleme meg kell egyezzen rekordnévvel. Mindezek miatt a rekordok fontos szerepet kapnak a bonyolultság vizsgálata során. 3. Megjegyzés. A rekordok definíciója a modulok első szakaszában szerepelhet a következő formában: rec1 (n1 , f11 [= v11 ], ..., fn1 [= vn1 ]). .. . rect (nt , f1t [= v1t ], ..., fnt [= vnt ]). Ahol reci ∈ R rekord definíciók, ni ∈ N rekord nevek, fij a rekord mezőinek a nevei, és vij (opcionális) a mezők értékei. 5. Definíció. [number_of _records] Az mi ∈ M modul által tartalmazott makró definíciókat jelölje R(mi ) := {rec1 , .., rect }, ahol reci egy rekord definíció. A R(mi ) a fejléc fájlokkal láthatóvá tett makró definíciókat nem tartalmazza. Ekkor a mérték eredménye az összes modulra X N OR(M ) = |R(m)|.2 m∈M

4

A mérték használható egy modulra: N OR(mi ) = |R(mi )|, és alkalmazható modulok egy csoportjára is N OR(m1 , ..., mk ) =

k X

|R(mj )|.

j=1

Fejléc fájlok száma A number_of_headers mérték a modulban szereplő fejléc fájlok számát adja vissza. A több modul függvényei által közösen használt adatokat, rekordokat, makrókat, vagy szélsőséges esetekben függvényeket fejléc fájlokba rendezik, majd ezeket a fájlokat az include(filepath) formában elérhetővé teszik modulok számára. E mechanizmus miatt a programokban fontos szerephez jutnak, mivel a modulok kapcsolatrendszerét, a hívási gráfokat, és adatfolyam analízisek eredményeit befolyásolhatják. 6. Definíció. [number_of _headers] Jelölje H = {h1 , ..., hk } a fejléc fájlokat (*.hrl), és A = M ∪ H, valamint jelölje az include(x, y) azt, ha x ∈ M az include(filepath) formában láthatóvá teszi az y ∈ A fájlt. Ekkor In(M ) = {(x, y) |y ∈ A ∧ ∃x ∈ M ∧ include(x, y) ∧ x 6= y} esetén N OH(M ) = |In(M )|. 1. Magyarázat. Az include(x, y) formulában megengedjük azt az esetet, amikor egy modul egy másik modult tesz láthatóvá. A mérték alkalmazható modulok egy csoportjára N OH(m1 , ..., mk ) =

k X

|In(mi )|,

i=1

ahol In(mi ) = {(mi , y) |y ∈ A ∧ include(mi , y) ∧ mi 6= y}.

Importált modulok Az imported_modules mérték az adott modulba (nem rekurzívan) importált más modulok számát adja vissza. Az import modulok száma arra világíthat rá a mérések során, hogy a mérésben szereplő modulok milyen szoros, vagy éppen laza kapcsolatban állnak egymással. Ez a fajta mérés fontos lehet annak az eldöntésében, hogy egy modul klaszterezési eljárás során egy modul a kapcsolatrendszer alapján mely csoportoknak legyen tagja. A mérték nem tartalmazza a minősített hívások (module:function alakú hívások) számát. 7. Definíció. [imported_moduls] Az mi ∈ M modul által importált modulokat jelölje I(mi ). Kikötjük, hogy mi ∈ / I(mi ), valamint a rekurzívan importált modulokat nem számoljuk az eredménybe. Ekkor az X IM (M ) = |I(m)| m∈M

. 5

A mérték alkalmazható egy modul mérésére IM (mi ) = |I(mi )|, valamint modulok egy csoportjának a mérésére: IM (m1 , ..., mk ) =

k X

|I(mi )|

i=1

Kohézió A cohesion nevű mérték a modulok közötti összes függvény útvonal számát adja eredményül, de a belső függvény kapcsolatok számát nem méri.

4. Megjegyzés. Az mi ∈ M modulokban található függvény hívásokat két esetben tekinthetjük modulok közti függvény útvonalnak: • Az első eset, ha a kapcsolatban szereplő függvény moduljára igaz, hogy tartalmazza a hívó, de nem tartalmazza a hívott fiapp függvény definícióját. • A másik eset, ha az mi nem tartalmazza a hívó, de tartalmazza a hívott fiapp függvény fi definícióját. 8. Definíció. [függvényhívási kapcsolat] Az mi ∈ M modulok tartalmazhatnak függvény definíciókat. Minden fi , fj ∈ F (M ), fi 6= fj párra keressük meg, hogy fi , és fj között van e hívási kapcsolat. Kapcsolat alatt azt értjük, hogy fi hívja fj függvényt, és ezt a következőképp jelöljük: c(fi , fj ). Az összes ilyen kapcsolat halmazát jelölje C(F (M )) = {(fi , fj )|fi , fj ∈ F (M ) ∧ fi 6= fj ∧ ∃c(fi , fj )}. Az mi modulból kifelé tartó függvényhívások jelölése C(mi , F (M )) = {(fi , fj )|fi ∈ F (mi ) ∧ fj ∈ F (M ) ∧ fi 6= fj ∧ ∃c(fi , fj )}. Az mi modulba tartó összes hívás jelölése C(F (M ), mi ) = {(fi , fj )|fi ∈ F (M ) ∧ fj ∈ F (mi ) ∧ fi 6= fj ∧ ∃c(fi , fj )}. Az adott modul egy függvényére az SG szemantikus gráfból érkező összes függvényhívást jelölje C(F (M ), fj ) = {(fi , fj )|fi ∈ F (M ) ∧ fi 6= fj ∧ ∃c(fi , fj )}. Adott függvényből kifelé irányuló függvényhívásokat jelölje C(fi , F (M )) = {(fi , fj )|fj ∈ F (mi ) ∧ fi 6= fj ∧ ∃c(fi , fj )}. Az mi modul belső függvényhívásai C(F (mi ), F (mi )) = {(fi , fj )|fi , fj ∈ F (M ) ∧ fi 6= fj ∧ ∃c(fi , fj )}.

6

5. Megjegyzés. Amennyiben a 8. definíció alapján a c(fi , fj ), és c(fj , fi ) is fennáll, vagyis a függvények kölcsönösen hívják egymást, a kapcsolatok száma kettő. Ha egy függvény többször hív egy másikat függvényt, ezek a kapcsolatok egy útvonalnak számítanak. 9. Definíció. [cohesion] A kohéziós mérték X COH(M ) = C(F (M )) − |C(F (m), F (m))|2. m∈M

A kohézió szempontjából az SG szemantikus gráfban található összes függvénykapcsolatból kizárjuk az olyanokat, ahol a függvényhívás ugyanabból a modulból indul ki, és oda is tart.

Összetartó erő A coupling mérték a modulban található függvények közötti hívási kapcsolatok számát adja eredményül. A belső függvény kapcsolatok számát igen, de a kívülről jövő, vagy a modulból kifelé tartó utak számát nem, vagyis csak a belső hívások számát tartalmazza.

6. Megjegyzés.

appi : mi : f(e1 , ..., en ) vagy mi : f(e1 , ..., en )

függvényhívások ahol mi a mért modul, mi : f (e1 , . . . , en ) a modul függvényének minősített hívása, és f (e1 , . . . , en ) a függvény hívása mi modulból. e1 , . . . , en kifejezések a függvény aktuális paramétereként, és n a hívott függvény paramétereinek a száma. 10. Definíció. [coupling] A coupling mérték CP (mi ) = |C(F (mi ), F (mi ))|2.

Modulba irányuló függvényhívások száma A function_calls_in mérték minden, a modul függvényeire irányuló, de külső modulból érkező függvényhívás (application) számát méri. 11. Definíció. [f unction_calls_in] Az összes, az adott modulba irányuló függvényhívások száma F CI(mi ) = |C(F (M ), mi )|.

Modulból kifelé tartó függvényhívások száma A function_calls_out mérték minden, a modul függvényeiből induló, és más modulok felé irányuló függvényhívások számát adja vissza.

7

12. Definíció. Az mi modulból kifelé irányuló függvényhívások száma, F CO(mi ) = |C(mi , F (M )))|.

Függvény hívási mélység maximuma A max_depth_of_calling mérték a függvények hívási útvonalainak a hossza. (Az eredmény nem azonos rekurzív hívások legnagyobb mélységével, azokat a max_depth_of_recursion függvény szolgáltatja.) A működés megértéséhez segítségünkre lehet a 1 példa, ahol mért legnagyobb hívási mélység három. Hívási mélység ... f([A|B], Acc) -> Acc0 = exec(A, Acc), f(B, );s f([], Acc0)-> acc0. exec(A, Acc)-> io:format("~w",[A]), A + Acc. ...

1. ábra. Függvények hívási mélysége

13. Definíció. [függvényhívási lánc hossza] A c(fi , fj ) pár egyben hívási lánc, melynek hossza egy. Jelöljön egy fi függvényből kiinduló hívási láncot l(fi , fj ), ha ∃f1 , f2 , ...fm , hogy ∃c(fi , f1 ) ∧ c(f1 , f2 ) ∧ ... ∧ c(fm , fj ), és @f ∈ F (M ), hogy c(fj , f ), vagyis fj nem tartalmaz függvényhívást. Ekkor az |l(fi , fj )| = m + 1 14. Definíció. [max_depth_of_calling] Legyen L(fi ) = {l(fi , fk )| ∃fk ∈ F (M ), fi 6= fk } az fi -ből induló hívási láncok halmaza. Ekkor a függvény hívási mélység maximuma M DOC(fi ) = max{|l(fi , fk )| | l(fi , fk ) ∈ L(fi )} A mértéket alkalmazhatjuk egy függvényre, függvények egy csoportjának M DOC(f1 , ..., fk ) = max

k [ i=1

8

M DOC(fi ),

valamint alkalmazhatjuk modulok mérésére is. A modult jellemző hívási lánc maximuma megegyezik a modul függvényeire mért hívási láncok maximumával, ahol: M DOC(mi ) = M DOC(F (mi )) Az eredmény az összes modulra mérve: M DOC(M ) = max

[

M DOC(m).

n∈M

Case kifejezések maximális beágyazottsága A max_depth_of_cases a függvényben, vagy a modul függvényeiben szereplő case vezérlő szerkezetek beágyazottságának maximuma. Beágyazottság ... case Data of {Pid, D} -> D ! Pid; _ -> case Data of ... end end ...

2. ábra. Case kifejezések egymásba ágyazása A case kifejezéseket mérésekor nem azok számát, hanem a beágyazottságukat kell vizsgálnunk, hasonló módon, mint a függvény hívási mélység esetén. c0 : case e of p1 [when g1 ] → e11 , . . . , e1l1 ; .. . pn [when gn ] → en1 , . . . , enln end Ahol e, ei ∈ E kifejezések, p ∈ P minták gi ∈ G őr feltételek az ágakban. A case kifejezések ágaiban az eij kifejezések tartalmazhatnak beágyazott vezérlő szerkezeteket, többek között újabb case kifejezéseket. 15. Definíció. [max_depth_of _cases] Jelöljük T (fi )-vel az fi függvényben található összes case kifejezés halmazát. Jelölje t(c1 , c2 ) azt, ha c1 case kifejezés valamely ága tartalmazza c2 case kifejezést, és @c3 case kifejezés, hogy t(c1 , c3 ) ∧ t(c3 , c2 ).

9

Jelölje ts (c, cx ) azt az esetet, hogy a c case kifejezés valamely ágában valamely mélységben tartalmazza a cx case kifejezést, vagyis ∃ c1 , ..., cn case kifejezések, hogy t(c, c1 ), t(c1 , c2 ), ..., t(cn−1 , cn ), t(cn , cx ). A |ts (c, cx )| beágyazás mélysége ez esetben n + 1. Legyen T0 (fi ) azon case kifejezések halmaza, amelyeket egyetlen T (fi ) halmazbeli case kifejezés sem tartalmaz (felső szintű case kifejezések). Ekkor az M DC(fi ) = max{|ts (c, cx )| |c ∈ T0 (fi ), cx ∈ T (fi )}2. A mértéket alkalmazhatjuk egy függvényre, függvények egy csoportjára M DC(f1 , ..., fj ) = max

k [

M DC(fi ),

i=1

valamint modulok mérésére is, ahol a modult jellemző beágyazottság maximuma megegyezik a függvényeire mért maximummal: M DC(mi ) = M DC(F (mi )) Az eredmény az összes modulra mérve: M DC(M ) = max{M DC(mi )|mi ∈ M }

Kifejezések maximális beágyazottsága A max_expr_depth mérték az adott függvény függvényben szereplő vezérlőszerkezetek, vagy egyéb kifejezések (üzenet küldő, fogadó kifejezések, függvény kifejezések, ...) egymásba ágyazottságának mértékét méri, és a maximumát adja. A mérték kiszámítása közel azonos a max_depth_of_cases mértéknél látottakkal, annyi különbséggel, hogy a definícióban, valamint a kiszámításhoz szükséges útvonal kifejezésben nem csak a case kifejezéseket, hanem if, try, f unction, és egyéb a programokban szereplő kifejezések beágyazottságát vizsgáljuk. 16. Definíció. [max_expr_depth] Jelölje ts (k, kx ) azt az esetet, hogy a k kifejezés valamely mélységben tartalmazza a kx kifejezést, vagyis ∃ k1 , ..., kn kifejezések, hogy t(k, k1 ), t(k1 , k2 ), ..., t(kn−1 , kn ), t(kn , kx ). A |ts (k, kx )| beágyazás mélysége ez esetben n + 1. Legyen T0 (fi ) azon kifejezések halmaza, amelyeket egyetlen T (fi ) halmazbeli kifejezésbe sincsenek beágyazva (felső szintű kifejezések). Ekkor az M ED(fi ) = max{|ts (k, kx )| |k ∈ T0 (fi ), kx ∈ T (fi )}2. A mértéket alkalmazhatjuk egy függvény M ED(f ), függvények egy csoportjának M ED(f1 , ..., fj ), valamint modulok mérésére is, ahol a modult jellemző beágyazottság maximuma megegyezik a függvényeire mért maximummal: M ED(mi ) = M ED(F (mi )) 10

Az eredmény az összes modulra mérve: M ED(M ) = max{M ED(mi )|mi ∈ M }

Függvény ágak száma A number_of_funclauses mérték a függvény clauseainak (ágainak) a számát adja. A függvény definícióját, és minden ágat az eredményhez számolunk. Azonos nevű, de más aritású függvényeket nem adjuk az összeghez kell különbözniük. Ekkor a két azonos nevű függvény teljesen független egymástól). Mindezek alapján a 3 példában a number_of_funclauses értéke kettő, mivel az f függvény egy, és két paraméteres formában két különböző függvénynek számít. A programokban a case, valamint az if vezérlő szerkezetek helyett a több ággal rendelkező, (overload) függvények alkalmazása megszokott módszer. Azonos nevű függvények -export([f/2, f/1]). f(Fun, [H|Tail])-> Fun(H), f(Tail); f(_, [])-> ok. f(A)-> A + 10. ...

3. ábra. Fügvény klózok száma A függvények (hasonlóan az Objektum Orientált nyelvek overload metódusaihoz) több ágból állhatnak, ahol az ágakat a formális paraméterlista, vagy az ágak őrfeltételei különböztetnek meg egymástól. A number_of_funclauses mérték egy függvényt alkotó ágak számát adja eredményül. 17. Definíció. [number_of _f unclauses] Jelöljük F c(fi )-vel az fi függvény ágainak halmazát. Ekkor a mérték eredménye az F c(fi ) halmaz számossága, vagyis az N F CL(fi ) = |F c(fi )|. A mérték alkalmazható egy N F CL(f ), vagy több függvényre ágainak a megszámlálására k X N F CL(f1 , ..., fk ) = N F CL(fi ) j=1

11

egyaránt, de mérhetjük vele a modulokban definiált összes függvény ágainak a számát is, ami megegyezik a modul függvényeiben található összes ágak számával, vagyis az N F CL(mi ) = N F CL(F (mi )), ahogy az összes modulra mért eredmény megegyezik az egyes modulokban mért eredmények összegével: X N F CL(M ) = N F CL(F (mi )). mi ∈M

7. Megjegyzés. Az SG szemantikus gráfban a függvény első, - vagy egy ág esetén az egyetlen ágát - a függvény definíciójának tekintjük, a mérték kiszámítása során azonban minden ágat klóznak számolunk.2

McCabe féle ciklomatikus szám A mc_cabe bonyolultság mérték értéke a Thomas McCabe által konstruált vezérlési gráfban [1] definiált alapvető útvonalak számával azonos, vagyis azzal, hogy hányféle kimenete lehet egy függvénynek nem számítva a benne alkalmazott további függvények bejárási útvonalainak a számát. A Mc Cabe ciklomatikus számot eredetileg a procedurális nyelvek alprogramjainak a mérésére fejlesztette ki Thomas J. Mc Cabe [1]. Ez a mérőszám alkalmas a funkcionális nyelvek, így a modulokban implementált függvények mérésére is. Mc Cabe a programok ciklomatikus számát a következőképpen definiálja: 18. Definíció. [Mc Cabe-féle ciklomatikus szám] A G = (v, e) vezérlési gráf V (G) ciklomatikus száma V (G) = e − v + 2p, ahol p a gráf komponenseinek a számát jelöli, ami megegyezik az erősen összefüggő gráfban található lineárisan összefüggő körök számával [5]. A mértéket a ?? fejezetben kiegészítjük néhány új tulajdonsággal. 19. Definíció. [M cCabe] A M cCabe ciklomatikus szám a modulok függvényein mért értéke megegyezik Az fi függvény ágait (overload változatait) jelölje f c(fi ), és az ágakban található if , valamint case kifejezések ágait jelölje if (fi ), és ca(fi ). Ekkor a M cCabe ciklomatikus szám függvényekre mért eredménye M CB(fi ) = |f c(fi )| + |case_cl(fi )| + |if _cl(fi )|. A mértéket alkalmazhatjuk függvények egy csoportjára M CB(f1 , ..., fk ) =

k X

M CB(fj ).

j=1

Az mi ∈ M modul függvényein mért eredmény megegyezik a modul összes függvényén mért értékek összegével: M CB(mi ) = M CB(F (mi )) Az összes modulra mért érték pedig a modulokra mért értékek összege: X M CB(M ) = M CB(F (m)) m∈M

12

8. Megjegyzés. A mért modulban meghívott függvények akárhány kimenettel (visszatérési pont) rendelkeznek is, egy útvonal végének számítanak, ezért ezeket nem vesszük figyelembe.

Függvényre irányuló hívások száma A calls_for_function mérték az adott függvényre történő hívások számát adja vissza. Ez a forrásszöveg jellemzése szempontjából nagyon fontos érték, mivel ez alapján lehet eldönteni, hogy egy függvény egy intef ace modul valamely számításokat végző függvénye, vagy egy library modul olyan segéd függvénye, amelyet más modulok használnak egy adott részfeladat elvégzésére. A kiszámítás módja hasonlít a modulra irányuló függvény hívások számának kiszámítására, de itt a modul egyetlen függvényét mérjük és a modulon belülről induló hívásokat is figyelembe vesszük. 20. Definíció. [calls_f or_f unction] Valamely fi függvényre irányuló függvényhívások száma CF F (fi ) = |C(F (M ), fi )|. A mérték alkalmazható függvények egy csoportjára CF F (f1 , ..., fk ) =

k X

CF F (fj ).

j=1

Függvényből kiinduló hívások száma A calls_from_function mérték az adott függvényből induló függvény hívások számát méri, vagyis azt, hogy a függvény hány másik függvényt hív meg. Amennyiben egy függvényt kétszer hív a mért függvény, a kapcsolatot egynek számoljuk, és a rekurzív hívásokat sem vesszük figyelembe. 21. Definíció. [calls_f rom_f unction] Valamely fi függvényből kiinduló függvényhívások száma CF M F (fi ) = |C(fi , F (M ))|. A mérték alkalmazható függvények egy csoportjára CF M F (f1 , ..., fk ) =

k X

CF M F (fj )

j=1

.

Függvény kifejezések száma A number_of_funexpr mérték a modulban szereplő (function expression) függvény kifejezések számát adja vissza. A függvény kifejezés hívását nem, de a bevezetését (definíció) méri. A 4 forrásszövegben szereplő függvény kifejezések száma a látszat ellenére egy. A programok bonyolultsága mellett azok olvashatóságát, valamint továbbfejleszthetőségét is nagyban befolyásolja az alkalmazott függvény kifejezések, és (λ) függvények) száma mind a forráskód, mind a szintaxisfa tekintetében.

13

Függvény kifejezések ... 1. F = fun(A) -> A + 1 end, 2. F(1), 3. F2 = fun a/1, ...

4. ábra. Függvény kifejezések száma 9. Megjegyzés. A függvény kifejezések következő két formáját tudjuk detektálni a forráskódot reprezentáló szemantikus gráfban (az első forma a 4 forrásszövegben az első sorban elhelyezett, az F változóba kötött kifejezésnek, a második az F 2 változóba kötöttnek felel meg): f exp1 : fun(p11 , . . . , p1n ) when g1 → e11 , . . . , e1l1 ; .. . m (pm 1 , . . . , pn ) when gm m e1 , . . . , e m lm

→

f exp2 : fun m : g/n or fun g/n Ahol a függvény kifejezéseket a f un nyelvi elem vezeti be, a pij ∈ P paraméterek, gi ∈ G őrfeltételek, és ei ∈ E kifejezések. 22. Definíció. [number_of _f unexpr] Jelölje az fi függvény által tartalmazott függvény kifejezéseket F exp (fi ) = {f1exp , ..., fnexp }, mely halmaz nem tartalmazza az fi függvény által hívott más függvényekben található függvény kifejezéseket. Ez esetben a number_of_funexpr mérték N F E(fi ) = |F exp (fi )|. A mértéket alkalmazhatjuk több függvényre N F E(f1 , ..., fk ) =

k X

N F E(fi ),

i=1

és modulokra egyaránt. Az modulokra mért eredmény megegyezik a modulokban definiált függvényekre mért eredmények összegével N F E(mi ) = N F E(F (mi )) és az összes modulra mért érték azonos a modulokra mért értékek összegével X N F E(M ) = N F E(m). m∈M

14

Üzenetküldések száma A number_of_mess_pass mérték egy függvény esetén az abban található üzenetküldéseket megvalósító kódrészletek, modul esetén a modulban szereplő összes függvényben előforduló üzenetküldések számát méri. Az Erlang pl. támogatja az elosztottságot, és az elosztott programokban az adatcserét közös memória használata nélkül valósítja meg. A függvényekből induló, vagy másképpen a modulok közti szinkron, és asszinkron üzenetküldések száma ezért nagyban befolyásolhatja a mért program bonyolultságát. 10. Megjegyzés. A nyelvi primitíveket az üzenetküldés megvalósítására. Az üzenet küldése a ! operátorral, az üzenetek fogadása a receive kifejezéssel történik. r0 : e1 ! e2 r0 : receive p1 when g1 → e11 , . . . , e1l1 ; .. . pn when gn → en1 , . . . , enln after M S → en+1 , . . . , en+1 1 ln+1 end ahol az e1 ! e2 az e1 kifejezés küldése az e2 kifejezésben adott cél számára. Az szinkron üzenetküldéseknél a fogadó félnél az r0 az üzenet fogadását teszi lehetővé. A receive ágaiban a pi ∈ P minták, amelyekre az üzenetben kapott kifejezés illeszkedhet, a gi ∈ G hasonlóan a case ágainál látottakhoz őr feltételek, és eij ∈ E kifejezések az ágakban. Az üzenet fogadásához tartozik egy olyan ág, amelyet az af ter kulcsszó vezet be, és ez alapértelmezett ágként akkor következik, ah az üzenet az előző ágakra nem illeszkedett, és az M S paraméterben megadott időkorlát letelt. A mérték az üzenetküldések számát méri, vagyis az e1 ! e2 alakú kifejezéseket a függvényben. 23. Definíció. [number_of _mess_pass] Az fi függvény tartalmazhat üzenetek küldését megvalósító, e1 ! e2 alakú kifejezéseket, ezeket jelölje S(fi )) = {s1 , ..., sn }. Ekkor a number_of_mess_pass mérték eredménye a N OM P (fi ) = |S(fi )| A mértéket alkalmazhatjuk függvények halmazára N OM P (f1 , ..., fk ) =

k X

N OM P (fi ),

i=1

és modulokra egyaránt. Az modulokra mért eredmény megegyezik a modulokban definiált függvényekre mért eredmények összegével N OM P (mi ) = N OM P (F (mi ))

15

, és az összes modulra mért érték azonos a modulokra mért értékek összegével X N OM P (M ) = N OM P (m). m∈M

11. Megjegyzés. Egy függvényre mérve gráfútvonalat specializálni kell a függvény nevéből, és paraméterszámából álló párral.

Külső hívások száma Az external_calls a mérésben szereplő függvényre alkalmazott, de más modulokból érkező függvényhívások számát adja vissza úgy, hogy egy függvény felől érkező több hívás is csak egynek számít. Ez, és a következő három (internal_calls, internal_calls_from, external_calls_from) mérték is releváns, mikor a függvényeket modulokba próbáljuk sorolni, vagy klaszterezési feladatokat szeretnénk megoldani. 24. Definíció. [external_calls] Az fi függvényre irányuló, más modulokból érkező függvényhívások száma ECL(fi ) = |C(F (M ), fi )|.

Belső hívások száma A internal_calls a mérésben szereplő függvényekre alkalmazott, de a függvényeket tartalmazó modulból érkező függvényhívások számát adja vissza úgy, hogy egy függvény felől érkező több hívás is csak egynek számít. A mérték kiterjesztése a calls_for_function mértéknek úgy, hogy kizárólag a modulon belülről érkező hívásokat veszi figyelembe. A definíció, és a kiszámítás módja szinte teljesen megegyezik az internal_calls mértéknél tárgyaltakéval annyi különbséggel, hogy itt a hívó, és a hívott függvény moduljának meg kell egyeznie, vagyis mindkét függvény definícióját ugyanaz a modul tartalmazza. A mérték eredménye: ICL(fi ) = |C(F (mi ), fi )|, ahol mi ∈ M az fi függvényt tartalmazó modul.

Modulon kívülre irányuló hívások Az external_calls_from a mérésben szereplő függvényből jövő de más modulokba irányuló függvényhívások számát adja vissza. A mérték a function_calls_out (lásd.: a 12. definícióban) mértéket specializálja ki úgy, hogy csak egy adott függvényből kiinduló, de annak moduljától különböző modulokba tartó hívások számát veszi figyelembe, vagyis nem a modulra, hanem annak egyetlen függvényére számolja ki az eredményt. 25. Definíció. [external_calls_from] Jelölje az M 0 = M \ {mi } az összes, kivéve az fi függvényt tartalmazó modult. Ekkor az ECF (fi ) = |C(fi , F (M 0 ))|. Az eredmény kiszámításához a modul, majd a függvény csomópontokból indulva a f uncall éleken át megkapjuk az összes hívást végző függvény csomópontjainak listáját. Ennél a mértéknél azonban az útvonalat egy függvényre kell specializálni a függvény nevéből, valamint a paraméterszámából alkotott párral f unc, {name = name(fi ), arity = arity(fi )}, ahol az fi a mért függvény. A kapott listában meg kell keresnünk azokat az elemeket, amelyek az mi modulban 16

vannak definiálva. A kereséshez a {f unc, back} éleken haladva minden hívást végző függvényhez meg kell annak modulját, majd (fc , mj ) alakú párokat alkotni belőlük, ahol a párok első eleme a hívó függvény, a második annak modulja. A mért függvény modulja adott. A kapott párok listájából ki kell válogatni azokat, ahol a mért függvény modulja nem azonos a párban szereplővel.

Modulon belülre irányuló hívások A internal_calls_from a mérésben szereplő függvényből kifelé tartó, a függvényt tartalmazó modulba irányuló függvényhívások számát adja vissza úgy, hogy egy függvény felől érkező több hívás is csak egynek számít. A mérték a function_calls_in (lásd.: a 11. definícióban) mértéket terjeszti ki úgy, hogy csak egy adott függvény felé tartó, de annak moduljától különböző modulokból jövő hívások számát veszi figyelembe, vagyis az útvonal kifejezést specializálja egy adott függvényre (nem a modulra, hanem annak egyetlen függvényére számolja ki az eredményt). 26. Definíció. [internal_calls_from] Jelölje az M 0 = M \ {mi } az összes, kivéve az fi függvényt tartalmazó modult. Ekkor az ICF (fi ) = |C(F (M 0 ), fi )|.

Azonosító hossza A length_of_name mérésben szereplő azonosító (függvénynév) karakterekben mért hosszát adja, ami akkor lehet érdekes, ha a kódsorok, és ezáltal a programszöveg olvashatóságát próbáljuk mérni, és javítani. Megjegyzés. Az idi az fi ∈ F (M ) függvényt azonosítja, és a hossza az idi -t alkotó jelek száma, vagyis LON (fi ) = |idi | A függvények nevéhez a szemantikus gráfban a modulokon keresztül juthatunk el. A függvényekről, ahogy minden n ∈ N gráf csomópontról le tudjuk kérdezni az adott típust jellemző attribútumok értékét. A függvényeket a névvel és a paraméterszámmal azonosíthatjuk, ezután meg tudjuk állapítani a név, vagyis az azonosító hosszát.

Paraméterek száma A number_of_funpars a mérésben szereplő függvény formális paraméterlistájának az elemszámát (aritás) adja eredményül. A mérték kiszámításához az adott függvény paramétereinek a számát nem kell direkt módon megszámolni, elég csak megkeresni a függvény definícióját, amely tartalmazza az őt jellemző attribútumokat. A kapott listából ki kell választani a mérésre szánt függvényt, és megnézni az aritását. 12. Megjegyzés. A függvények definíciójában a pi ∈ P minták alkotják az adott függvény paraméterlistáját, és a nyelv szintaxisa alapján az fj függvény minden fic függvény ága megegyező számú paraméterrel rendelkezik, és pi az fj függvény bármely ágának paraméterlistáját reprezentáló minta, akkor a mérték eredménye, vagyis N OF P (fj ) = |pi |.

17

Függvény összesített értéke A function_sum mérték a függvényre, vagy függvényekre jellemző komplexitási mértékekből számított érték. Az eredmény kiszámításához szükséges mértékek felsorolással megadhatóak. 27. Definíció. [f unctions_sum] Jelölje a RefactorErl bonyolultságot elemző algoritmusával mérhető, és ezek közül a a függvényekre alkalmazható bonyolultsági mértékek véges halmazát M ef unc = {mef1 unc , mef2 unc , ..., mefnunc }, valamint legyen S ⊂ M ef unc . Ekkor az X F S(S, fi ) := mef unc (fi ) mef unc ∈S

az fi függvényt jellemző, és az S-ben megadott mértékek összesített értéke.

Hivatkozások [1] McCabe T. J. A Complexity Measure, IEE Trans. Software Engineering, SE-2(4), pp.308-320 (1976) [2] Fóthi Á., Nyéki-Gaizler J. On The Complexity of Object-Oriented Programs in Proc. of the 3rd Symp. on Programming Languages and Software Tools Kaariku, Estonia, (1993) [3] Fóthi Á., Nyéki-Gaizler J., Porkoláb Z. The Structured Complexity of Object Oriented Programs Computers and Mathematics with applications, (2002) [4] Zoltán Porkoláb, Ádám Sipos, Norbert Pataki, Structural Complexity Metrics on SDL Programs. Computer Science, CSCS 2006, Volume of extended abstracts, (2006) [5] Zoltán Porkoláb Programok Strukturális Bonyolultsági Méröszámai. PhD thesis Dr Töke Pál, ELTE Hungary, (2002) [6] Tamás Kozsik, Zoltán Csörnyei, Zoltán Horváth, Roland Király, Róbert Kitlei, László Lövei, Tamás Nagy, Melinda Tóth, Anikó Víg Use Cases for Refactoring in Erlang. In Central European Functional Programming School, volume 5161/2008, Lecture Notes in Computer Science, pages 250–285, (2008) [7] Piwowarsky, P. A Nesting Level Complexity Measure. ACM Singplan Notices 17(9) pp.44-50 (1982) [8] Lövei, L., Hoch, C., Köllö, H., Nagy, T., Nagyné-Víg, A., Horpácsi, D., Kitlei, R., and Király, R.: Refactoring module structure in.:Proceedings of the 7th ACM SIGPLAN workshop on ERLANG Columbia, Canada, (2008) [9] Horváth, Z.: Elosztott funkcionális programok helyessége (Verification of Distributed Functional Programs) Project report, OTKA. http://www.otka.hu, (2006)

18

[10] R. Kitlei, L. Lövei, M Tóth, Z. Horváth, T. Kozsik, T. Kozsik, R. Király, I. Bozó, Cs. Hoch, D. Horpácsi.: Automated Syntax Manipulation in RefactorErl. 14th International Erlang/OTP User Conference. Stockholm, (2008) [11] The IBM United States http://www.ibm.com/us/en/

19