Next: 7. Tapasztalatok Up: Deklaratív nyelvek oktatásának támogatása Previous: 5. Az ETS rendszer Tartalomjegyzék
Az előző fejezetben az olvasó megismerkedhetett az ETS rendszer tervével. Annak igazolásaként, hogy a tervek alapján könnyen kivitelezhetőek az egyes komponensek, mintaként magam is megvalósítottam a házi feladatokat feldolgozó komponens egy-két részletét. Elkészült a tesztelő jelentős része, valamint az SML programok hasonlóságvizsgálatához szükséges hívási gráfot építő program. E két programot mutatom be a fejezet két szakaszában.
sec:hfterv. szakaszban bemutattam az ETS azon komponensének tervét, amely a házi feladatok feldolgozásáért felelős. Hogy a terv életképességét igazolhassam, úgy döntöttem, hogy elkészítem a komponens egy kísérleti megvalósítását, amelyet remélhetőleg a gyakorlatban is lehet majd alkalmazni. Azért is ezt a komponenst választottam, mert a nagy házi feladatok értékeléséért felelős szkript-csomag jelenleg használt változatának létrehozásában is döntő szerepem volt, üzemeltetésének egyik felelőse jelenleg is én vagyok.
A programot - cha:ets. fejezet bevezetőjében elmondottaknak megfelelően - Prologban valósítottam meg. Az elkészült részek sajnos nem fedik le a komponens összes megtervezett szolgáltatását, de ami megvan, az elegendő ahhoz, hogy bemutassam a megvalósítással kapcsolatos elképzeléseimet.
Természetesen a legfontosabb szolgáltatás, a programtesztelés megvalósításával kezdtem. Erre két okom is volt. Az egyik, hogy ennek megléte nélkül nem nagyon beszélhetünk HF-eket feldolgozó komponensről. A másik, hogy ez a szolgáltatás változott a tervekben a jelenleg használthoz képest a legtöbbet, tehát ennek az elkészítése jelentette a legnagyobb kihívást. A programozás során megírtam számos olyan általános célú eljárást, amelyet később a többi szolgáltatás megvalósításakor is felhasználhattam, ill. felhasználhatok majd. Így például alig jelentett többletmunkát egyes levelek kicsomagolásának vagy az archívum kitakarításának mint szolgáltatásnak az elkészítése. Most lássuk, mi az, ami nincs meg:
A továbbiakban igyekszem bemutatni az elkészült részeket, ezek működését és vezérelhetőségét. A programot GUTS-nak, azaz englishGrand Unified Testing System-nek neveztem el. Ennek az az oka, hogy az új program - a korábbival ellentétben, a terveknek megfelelően - egyformán képes tesztelni a jelenlegi nagy és kis házi feladatokat, sőt olyan feladatfajtákat is, amelyek egyelőre nem is léteznek.6.1
A megvalósításkor alapvetően tartottam magam a megtervezett és
fig:newdirst. ábrán (![[*]](crossref.png)
. oldal) bemutatott
könyvtárstruktúrához. Az egyetlen eltérés a sablonok elhelyezésében
mutatkozik, ennek okára hamarosan fény derül. A hallgató nevéből és
azonosítójából képzett név, amit ott <name>-ként jelöltem, a
megvalósításban úgy áll elő, hogy a hallgató nevének szóközök és ékezetek
nélküli változatához egy ponttal elválasztva hozzáfűzzük a hat karakteres,
az adatbázisban tárolttal egyező, nagy- vagy kisbetűsített NEPTUN kódját, a
sajátom pl. HanakDavid.e6070b lenne.
Ahogy a tervezéskor is írtam, Prolog-megvalósítás esetén logikusabb szöveges állományok helyett Prolog-modulként megadni a komponens által üzenetként felhasznált szövegeket. Ennek az is az előnye, hogy nagyon könnyű paraméterezni, azaz változó tartalmú mezőkkel megtűzdelni az egyes blokkokat. Az egyes tesztesetek fejlécét kiíró Prolog-predikátum például a következő lehet:
print_testcase(N, Limit) :-
format('~t~d~2+. teszteset, időlimit = ~|~t~d~3+ sec~n',
[N, Limit]),
print('---------------------------------'), nl.
amely kiírja az adott teszteset számát és a hozzá rendelt időlimitet is.
Ez és a többi sablon a templates.pl állományban található, ez pedig az env/permanent könyvtárban helyezkedik el, a komponens törzsét képező guts.pl állománnyal együtt.
A félévenként változó részek legfontosabb része az egyes nyelvek tesztelésére szolgáló keretprogramok és inicializációs állományok csoportja. Ezek a Deklaratív programozás tárgy esetében a megfelelő SML- és Prolog-állományok, ezek architektúra-függő változatai, valamint az inicializálásért felelős setup nevű állomány, amely szintén Prolog-kifejezéseket tartalmaz, mivel ezt a tesztelő könnyen be tudja olvasni. A példa kedvéért a 2001-es tavaszi félév NHF-jeinek ellenőrzéséhez használható SML-állományok elhelyezését mutatja fig:dirsml. ábra.
Az ellenőrzéshez használt keretprogramról már sok szó esett sec:hfterv. szakaszban. Feladata a tesztesetek bemeneti adatainak beolvasása, a hallgató programjának meghívása, és a megoldás kiírása vagy értékelése, attól függően, hogy a tesztelőt milyen paraméterekkel futtatjuk. Tulajdonképpen azt mondhatjuk, hogy a keretprogramban a tesztosztálytól, a nyelvtől és a tesztsortól egyaránt függő részek vannak. Egyetlen kikötés van: minden tesztsor minden tesztesetére ugyanennek a keretprogramnak kell működnie. A tesztesetfüggő viselkedését a parancssori argumentumai szabályozzák, amelyből kettő van. Az első a tesztelendő program bemenő adatainak megadására szolgál, a második pedig egy állomány neve, amelybe az előállított megoldást kell valamilyen formában kiírnia a keretprogramnak. Hogy a két argumentum konkrétan mit jelent, az attól függ, hogy mi van a tesztelő paraméter-állományában - ennek bemutatására később kerül sor.
Ebben az állományban azok a beállítások vannak, amelyek függnek a tesztosztálytól és a nyelvtől, de függetlenek a tesztsortól. Tartalmára egy példa fig:ml-setup. ábrán látható, amelyet a következőkben részletesen bemutatok.
Az állomány - mint többször említettem - Prolog-kifejezésekből áll, ezek sorrendje tetszőleges. A tartalmuk a következő:
itm:testd-par. oldalon egy felsorolásban áttekintettem, hogy
melyek a tesztelő paraméterei. Ennek ismeretében itt az egyetlen újdonság
paramétereket meghatározó állomány szerkezete, amely - nem meglepő módon
- Prolog-kifejezések sorozata. Mivel ezt az állományt maga a
Prolog-interpreter értelmezi, egyszerű tényállítások helyett eljárások is
szerepelhetnek. Elhelyezésére vonatkozóan nincs megkötés, ugyanis - amint
az a későbbiekből kiderül (ld. .oldal,
6.5. ábra) - az elérési útja parancssori argumentuma a GUTS
programnak. fig:testdparam. ábrán a példákhoz már eddig is
felhasznált 2001-es tavaszi félév NHF-tesztelésének paraméterei láthatók.
Az ábra természetesen szorul némi magyarázatra. Az itt szereplő beállítások határozzák meg a tesztosztályt és a tesztsort, valamint az függô, ám a nyelvtől független paramétereket (vö. nyelvi inicializációs állomány). Az alábbiakban áttekintem, hogy egy ilyen állományban milyen kifejezéseknek kell lenniük (a sorrendjük tetszőleges).
Ebben a két esetben a keretprogram második argumentuma azon állomány
neve, amelybe a megoldást kell valamilyen formában kiírni.
Ha a timer paraméter aktív (argumentuma yes), akkor a mért futási időket egy füzér formájában eltárolja az ID azonosítójú eredmény entitáshoz rendelt <Lang>_time nevű attribútumban.
Noha a komponens ezen része egyelőre nem készült el, határozott elképzeléseim vannak arról, hogy milyen felületen keresztül fog érintkezni a felhasználóval és a tesztelővel. Ebben a szakaszban két állomány felépítését mutatom be: az első a fogadóprogram paraméter-állománya, amelyben itm:maild-par. oldalon bemutatott paramétereket adhatjuk meg, a második a két program kapcsolatát biztosító spool állomány, amelyben a beérkezett levelek állnak sorba, tesztelésre várakozva.
fig:maildpar. ábrán a fogadóprogram egy lehetséges paraméter-állománya látható. Természetesen itt is Prolog-kifejezések állnak, amelyek lehetnek akár egyszerű tényállítások, akár eljárások, mivel ezt az állományt is közvetlenül a Prolog-interpreter értelmezi. Az állomány elhelyezése, akárcsak a tesztelő esetében, itt sincs megkötve. A kifejezések a következők lehetnek:
A program több Prolog-állományból áll (funkcionalitás szerint csoportosítva), de a save_program/2 könyvtári eljárás segítségével egyetlen futtatható állományt állítok elő belőle, így gyakorlatilag úgy használható, mint bármely más program. A működését elsődlegesen az argumentumokkal tudjuk befolyásolni, az első argumentuma ugyanis az igényelt szolgáltatás azonosítója. Ha itt help-et adunk meg, kapunk egy rövid ismertetést a használatról, ez látható fig:guts. ábrán.
A három fő szolgáltatás, amely jelenleg elérhető, a testd (teszt-démon), extract (levél kicsomagolása) és purge (archívum takarítása) argumentumokkal hívható elő. A teszt-démon futtatásához meg kell adnunk a már ismertetett szerkezetű paraméter-állomány nevét. A takarításhoz szükség van a félév és a tesztosztály azonosítójára, levelek kicsomagolásához ezen felül még a hallgató nevére is, és opcionálisan a verziószámra.
A működés a terv specifikációja és a paraméterek részletes ismertetetése után, úgy vélem, nem igényel külön magyarázatot. Kivételt talán csak a futási idők mérése és az időlimit figyelése jelent, ezekről érdemes pár szót ejteni.
Az időlimit betartatása POSIX-kompatibilis architektúrákon rendszer-szolgáltatás. Fontos megérteni, hogy az időlimit nem a valós időre vonatkozik, hanem az aktívan felhasznált CPU-időre. Ez utóbbi nem telik eseményre, pl. bevitelre várakozáskor. A korábbi években volt olyan állapota az NHF értékelő rendszernek, amikor ez a rendszer-szolgáltatás nem volt elérhető (egy másik program letiltotta). Ez abban a félévben sok fennakadást okozott, ezért még akkor írtam egy idő-őr-nek keresztelt C nyelvű programot, amely egyfelől aktiválja a rendszer-szolgáltatást, másrészt - a biztonság kedvéért - egy állítható szorzóval figyeli a valós időt is. Ez akkor is jól jön, ha a korlátozandó program eseményre várakozik, és ezért nem fogyasztja a CPU-időt. A limit leteltét (akár valós, akár CPU-időről van szó) speciális kilépési kóddal jelzi. Ha a program futása valamilyen hibakóddal szakad meg, akkor továbbengedi a hibakódot, tehát teljesen transzparens. A SICStus Prolog architektúra-független nyelv, a megfelelő rendszerhívás nem is érhető el közvetlenül, tehát duplán jól jártam az idő-őrrel.
A futási időt sem közvetlenül a Prolog-tesztelőben mérem, noha erre már van eljárás definiálva. Csakhogy ez a könyvtári függvény vagy a saját processz CPU-idő fogyasztását méri, vagy az eltelt valós időt, itt pedig a gyerek processzként indított hallgatói program CPU-idejére van szükség. Éppen ezért a Unix-architektúrákon meglévő time programot használom, amely képes ennek mérésére.
app:naplo. függelékben olvasható egy minta naplóállomány, amelyet a GUTS rendszer állított elő. Ebben minden információ benne van, amit elvárhatunk. A fejléc pontosan tájékoztat a körülményekről és a tesztelt programról. A tesztesetek jól elválnak egymástól, a program eredményét és futási idejét jelző sor kitűnik környezetéből. A futtatás során kiírt hibaüzenetek és figyelmeztetések is megjelennek. Az eredményekről nyelvenként egy-egy rövid összesítés is olvasható. A naplóban megjelenő fix szövegek mind a sablonok részei, ezért könnyen módosíthatóak.
A rendszer paramétereivel hatékonyan és tömören le lehet írni a tesztfeladatot. Az ismertetés során bemutatott példákból is látszik, hogy a rendszer alkalmas NHF-ek tesztelésére, de a paraméterek lehetővé teszik KHF-ek és más jellegű feladatok ellenőrzését is. Elmondható, hogy egy újabb feladattípus ellenőrzéséhez minimális mennyiségű programozásra van szükség.
Természetesen akad még számtalan kisebb-nagyobb hiányosság, melyek pótlása a GUTS rendszer aktív használatának előfeltétele. A két legfontosabb ezek közül a levelek fogadása és az adatbázis frissítése. Úgy gondolom azonban, hogy a program ,,befejezése'' nem igényel nagyon sok munkát, és valószínűnek tartom, hogy a következő félévben már ez a rendszer fogja értékelni a hallgatók megoldásait.
ssec:masolat. fejezetben röviden beszámoltam egy olyan rendszerről, amely képes forráskódú programokról megállapítani, hogy másolatai-e egymásnak. Azt is leírtam, hogy a jelenleg működő program csak Prolog-programokat képes összehasonlítani, de a bővítési lehetőség adott, hogy más nyelveket is támogasson. Mivel a Deklaratív programozás tárgy keretében a Prolog mellett SML nyelvet is oktatnak, indokolt, hogy a hasonlóságvizsgáló program mihamarabb alkalmas legyen SML-programok ellenőrzésére is. Ehhez csak arra van szükség, hogy legyen egy olyan alprogram, amely képes feltérképezni egy SML-program hívási gráfját, és ezt megfelelő formátumban átadni. A hívási gráf nem más, mint az a gráf, amelyet a következőképpen kapunk:
A diplomatervezés keretében elkészítettem egy SML nyelven írt programot, amely pontosan ezt a feladatot látja el. Mielőtt azonban rátérnék a konkrét megvalósítás ismertetésére és a hasonlóságvizsgáló programmal való összeillesztésének vizsgálatára, érdemes kicsit elidőzni a funkcionális nyelvek hívási gráfjai körüli általános érvényű kérdéseknél, amelyek a gráfépítő program írása közben merültek fel. Nem adok minden kérdésre teljes választ, de mindenütt igyekszem valamilyen módszert javasolni a probléma feloldására. Mivel az eddigiekben három programról volt szó, és a továbbiakban is szükséges lesz mindháromra hivatkozni, az alábbi logikus elnevezéseket vezetem be:
Többször szót fogok ejteni az SML-értelmezőről is. Amikor pedig úgy fogalmazok, hogy ,, helyen regisztráljuk függvény meghívását'', akkor arra gondolok, hogy a gráfépítő program az -hoz tartozó csomópontból a -hez tartozó csomópontba vezető élet vesz fel a gráfba; azaz feltételezi, hogy -t -ból meghívták.
Hívási gráf építésekor funkcionális nyelveknél felmerül egy-két olyan kérdés, amely más - akár deklaratív, akár imperatív - nyelveknél nem jön elő. Ennek fő oka a funkcionális nyelvek alapvető jellegzetességeiben, a megalkotásuk alapjául szolgáló függvényelméletben keresendő. Azok számára, akik nem járatosak a funkcionális nyelvekben, egy igen rövid ismertető olvasható app:funk. függelékben. Az ebben foglaltak ismerete elengedhetetlen a fejezet további részének megértéséhez.
ssec:grafprob-elso.-6.2.4. szakaszokban felvetek néhány problémát, amely a hívási gráfok építését megnehezíti. Ezek egy része általában a funkcionális nyelvekre jellemző, mások SML-specifikusak. A problémákra rögtön elméleti megoldásokat is javasolok, de ezek egy része - mint látni fogjuk - a gyakorlatban csak nehezen kivitelezhető.
Az általában a funkcionális nyelvekre érvényes problematikus kérdések jelentős része abból a jellegzetességből adódik, hogy a funkcionális programozásban a függvényérték (azaz olyan érték, amely egy függvényt képvisel) éppen olyan érték, mint az összes többi. Ebből adódóan sokkal rugalmasabban használható, ugyanakkor nehezebb a felhasználását nyomon követni. Az alábbi felvetések app:funk. függelék egy-egy témaköréhez kapcsolódnak.
Vegyük a függelékben is bemutatott egyszerű példát:
- val f = cos; > val f = fn : real -> realHa most f-et alkalmazzuk egy értékre, akkor melyik függvényt hívjuk meg: f-et vagy cos-t? Ha pontos választ akarunk adni, akkor azt kell mondanunk, hogy voltaképpen egyiket sem, hanem azt a függvényt, amelyet mindkét név jelöl. Praktikus szempontból azonban talán egyszerűbb, ha azt mondjuk, hogy a cos függvényt hívtuk meg, mivel ezt definiáltuk elsőként (a könyvtár részeként). Ennek kiderítéséhez a nyelv szintaktikáján túl természetesen ismerni kell bizonyos mértékben a szemantikáját is, azaz a gráfépítőnek meg kell értenie, hogy mit jelent a val f = cos kifejezés, és meg kell jegyeznie, hogy az f név ettől a ponttól kezdve a cos függvény egy másik neve.
Mivel a már egyszer lekötött nevek átdefiniálhatóak, megtehetjük, hogy például a cos nevet egy újabb függvényértékhez kötjük. Noha egy ilyen átnevezésnek nem lenne túl sok értelme, és az SML-program átláthatóságát is nagy mértékben rontaná, ,,jó'' eszköz lehet arra, hogy becsapjuk a hasonlóságvizsgáló programot, ha a gráfépítő erre a lehetőségre nem ügyel. A probléma az, hogy a hívási gráf - az SML-program állapotával ellentétben - statikus, egyszerre kell értelmezni az egészet. Ha egyszer használtuk a cos nevet, akkor attól kezdve mindig ugyanazt kell jelölnünk vele, az ilyen átdefiniálást tehát másképp kell kezelni. A megoldás az lehet, hogy a gráfépítő automatikusan átnevezi az újradefiniált függvényt (mondjuk cos2-re), és ettől kezdve ezen a néven hivatkozik rá (azaz minden további cos hívás helyett cos2-t regisztrál). Így olyan, mintha nem a cos nevet definiáltuk volna fölül az SML-programban, hanem egy teljesen új nevet hoztunk volna létre, és ettől a ponttól kezdve mindig azt használtuk volna az eredeti cos helyett.
A lambda-jelöléssel definiált anonim függvények létezése újabb problémát jelent. Vegyük a következő példát:
- (fn x => x*x) 12; > val it = 144 : intEbben az esetben melyik függvényt hívtuk meg? Nyilvánvalóan nem a * (egész szorzás) függvényt, legalábbis nem közvetlenül. Amit meghívtunk, annak viszont nincs neve. Ilyenkor a gráfépítő programnak valamilyen módon el kell neveznie az anonim függvényt, és innentől kezdve ezzel a névvel hivatkoznia rá. Az ,,innentől kezdve'' fordulatot az előző mondatban az indokolja, hogy egy anonim függvény is kaphat nevet, ha például argumentumként adjuk át egy magasabb rendű függvénynek. (Ilyenkor nem szabad az adott argumentum nevét felhasználni, hiszen az általa jelölt érték mindig más és más.)
Ahogy azt a függelék D.4. fejezetében is leírtam, egy részlegesen alkalmazható függvény definiálásakor voltaképpen több függvény definíciójáról van szó. Vegyük például a következő függvénydefiníciót:
- fun add a b = a+b; > val add = fn : int -> int -> int - add 2; > val it = fn : int -> intA harmadik sorban meghívtuk az add függvényt? Szigorúan véve nem, hiszen a definíciójában megadott a+b kifejezést még nem értékeltük, nem értékelhettük ki. Ugyanakkor mégiscsak meghívtuk, hiszen az általa jelölt függvényértéket alkalmaztuk egy másik értékre, és mi ez, ha nem a függvény meghívása. A látszólagos ellentmondást talán úgy lehet a legjobban feloldani, hogy a hívási gráfba nem egy, hanem két függvény definícióját vesszük fel, mondjuk addA-t és addB-t. Amikor egy add 2 jellegű kifejezéssel találkozunk, azt mondjuk, hogy meghívtuk addA-t (hiszen lekötöttük az első argumentumot), amikor pedig ezt a függvényértéket alkalmazzuk egy újabb értékre, akkor addB meghívásáról beszélünk. Ha egy részlegesen alkalmazható függvénynek nem két, hanem több ilyen argumentuma van, akkor azt természetesen nem két, hanem több függvény definíciójának kell tekintenünk.
Ha így döntünk, akkor felmerül egy újabb probléma. Az add függvényben törzsében lévő hívásokat melyik újonnan létrehozott függvényhez kell regisztrálnunk: addA-hoz vagy addB-hez? Általánosságban azt mondhatjuk, hogy mindig a legutolsóhoz, hiszen a részlegesen alkalmazható függvények törzse addig nem értékelődik ki, amíg az összes argumentumot meg nem határoztuk. Sajnos azonban lehetséges úgy definiálni egy függvényt, hogy az részlegesen legyen alkalmazható, és már az első argumentuma alapján végezzen számításokat (természetesen más függvényeket meghívva), például:
- val pyth = fn a => let val a2 = a*a
in fn b => sqrt(a2 + b*b) end;
> val pyth = fn : real -> real -> real
Azaz egyszerűen egymásba ágyazunk két anonim függvényt. A lényeg, hogy a
val a2 = a*a definícióban szereplő kifejezés már az első
argumentum meghatározása után kiértékelődik, és a visszaadott
függvényértékben már a kiszámított érték szerepel. Ebben az esetben, ha
precízek szeretnénk lenni, azt kell mondanunk, hogy a * (valós
szorzás) függvényt pyth2A is meghívta (pyth2B is meghívja
a b*b kifejezés kiértékelésekor). Ennek kiderítése viszont már
meglehetősen bonyolult feladat.
Tekintsük egy magasabbrendű függvény alkalmazásának a következő példáját:
- map (fn x => x+1) [1,4,9]; > val it = [2, 5, 10] : int listFelmerül a következő probléma: az (fn x => x+1) anonim függvényt hol hívjuk meg? Tulajdonképpen nem a legkülső szinten, hiszen csak továbbadjuk a függvényértéket a map-nek, és nem alkalmazzuk egy másik értékre. Ugyanakkor azt is furcsa lenne állítani, hogy a map hívja meg, hiszen a map definíciójában elő sem fordul ez a kifejezés. Gondoljuk csak meg: ha azt mondjuk, hogy a map hívja a függvényt, akkor a hívási gráf map-hez tartozó csomópontjából kiinduló élek attól fognak függni, hogy a map-et hány helyen és hogyan hívjuk meg az SML-programban! Mivel első ránézésre egyik lehetőség sem tűnik jónak, vizsgáljuk meg alaposabban mindkettőt.
Tegyük fel, hogy a hívást ott regisztráljuk, ahol a függvény neve (anonim esetben a definíciója) szerepel (azaz a példa esetében a legkülső szinten). Ebben az esetben nagyon könnyű becsapni a hasonlóságvizsgáló programot, mert nem kell mást tenni, mint a függvény alkalmazásának helyéről a nevet egy külsőbb hívási szintre vinni, és csak a függvényértéket továbbadni egy argumentumban. Az SML-program ettől kuszább lesz, de ha a cél a másolás leplezése, akkor ez nem akadály. Ez a fajta regisztráció tehát nem szerencsés, ugyanakkor meglehetősen egyszerű, mert nincs szükség hozzá a nyelv szemantikájának ismeretére, puszta szintaktikai elemzéssel megállapítható a hívás helye.
A másik lehetőség, hogy mégiscsak azon a helyen regisztráljuk a hívást, ahol a függvényértéket alkalmazzuk egy argumentumra. Ebben az esetben végig kell követni a függvényérték átadogatását (esetleg több szinten keresztül is), és figyelni, hogy hol hívódik meg. Noha ez a megoldás lényegesen bonyolultabb, leginkább azért, mert a már definiált függvényekhez tartozó részgráfot újra és újra módosítani kell, elméleti szempontból mégiscsak ez a jobb választás, hiszen ez felel meg jobban a funkcionális nyelvek logikájának. Az imént vázolt probléma, azaz a map és más könyvtári függvényekhez tartozó részgráfok változékonysága megszüntethető egy ügyes trükkel. Ez pedig az, hogy magasabb rendű könyvtári függvények hívása esetében mégiscsak a hívóhoz jegyezzük be az argumentumként átadott függvény meghívását. Ez ugyan torzítja a hívási fát, mégis több információt árul el a programról magáról, és jobban elkülöníti a könyvtári részeket, amelyek - lévén, hogy a legtöbb program használ könyvtári elemeket - kevésbé informatívak.
Vegyük a következő példát:
- nth([sin,ln,sqrt], 2) e; > val it = 1.6487212707 : realHa a gráfépítés során következetesen azt a logikát követjük, hogy a függvények meghívását azon a helyen regisztráljuk, ahol alkalmazzuk őket, akkor itt nagy gondban vagyunk. E logika alapján az, hogy a sin, ln és sqrt függvények melyikét hívtuk meg, csak futási időben deríthető ki, hiszen a 2 helyén tetszőlegesen bonyolult kifejezés állhat. Ha ismét a hallgató fejével gondolkozunk, a fenti nth hívás remek eszköz az sqrt függvény meghívásának leplezésére. Ezen a ponton csődöt mond minden korábbi elképzelés arról, hogy a hívási gráf pontosan felépíthető anélkül, hogy futtatnunk kellene a programot.
Van néhány kisebb probléma, amely ugyan nem olyan tulajdonságokból adódik, amelyek csak a funkcionális nyelvekre lennének jellemzőek, az előzőekkel kombinálva mégis érdekes helyzetek adódhatnak.
Természetesen semmi akadálya, hogy függvényt deklaráljunk lokálisan. Erre a függelékben is láthatunk példát apps:lokal. fejezetben. Ha ilyesmivel találkozik a gráfépítő, akkor ügyelnie kell arra, hogy a lokálisan deklarált név elfedhet korábban deklaráltakat, ám a blokkból kilépve ez a fedés megszűnik. A helyzet nem ugyanaz tehát, mint a nevek újradefiniálásánál, ahol a régi jelentést el lehetett dobni.
Ahogy a C-ben lehetséges kölcsönösen rekurzív, azaz egymást hívó függvények definiálása (predeklarációval), úgy az SML-ben is lehetőség van erre. Az ilyen esetekre a kölcsönösen rekurzív függvények definiálásakor egy speciális kulcsszóval kell felhívni a fordító figyelmét. Mivel a funkcionális programok értelmezése alapvetően szekvenciális, általában nincs szükség rá, hogy gráfépítéskor előre tekintsünk, csak a korábban definiált függvényeket kell figyelembe vennünk. Itt más a helyzet, hiszen a kölcsönösen rekurzív függvények egymást hívják.
Szintén lehetséges kölcsönösen rekurzív függvények definiálása lokális kifejezéssel. Az ebben definiált függvények ui. meghívhatják a kifejezést magába foglaló külső függvényt.
Az SML - modern programozási nyelvhez illően - moduláris nyelv. A könyvtári függvények különböző modulokban vannak definiálva, és nagy részüket csak a modulnév megadásával tudjuk elérni, pl. így: Math.cos. A nyelv azonban lehetőséget ad a modulok névterének megnyitására, ilyenkor az adott modulban definiált nevek bemásolódnak az aktuális névtérbe, és a rájuk való hivatkozáskor már nem kell megadni a modulnevet. Ilyenkor a gráfépítőnek észre kell vennie, hogy továbbra is ugyanarról a függvényről van szó. Egy modul megnyitása természetesen el is fedhet korábban definiált neveket.
A könyvtáriak mellett a saját magunk által írt függvényeket is modulokba szervezhetjük. Ily módon a programunkat több önálló részre oszthatjuk. Az ideális gráfépítőnek ilyen esetekben fel kell térképeznie, hogy a modulok hogyan hivatkoznak egymásra, és mindegyik modult fel kell dolgoznia.
A modulok megnyitása kombinálható a lokális kifejezésekkel és deklarációkkal. Ilyenkor a modul névtere csak az adott kifejezés vagy deklaráció erejéig nyílik meg, a blokkból kilépve elveszik. Ilyen esetekben ismét előfordulhat egy-egy név átmeneti elfedése.
Az SML-program feldolgozása közben a gráfépítőnek nyilván kell tartania a már definiált függvényeket, és ehhez persze tudnia kell, hogy egy függvény neve honnan olvasható ki. Általában ez a közvetlenül a fun vagy val kulcsszó után következő név, kivéve, ha előtte a függvényt infixnek deklaráltuk, mert ilyenkor az első argumentum-mintát követő név az, hacsak nem az op kulcsszóval együtt adjuk meg, mely esetben mégiscsak az első név a függvény neve. Másként fogalmazva két eset lehetséges:
Az eddigiek alapján levonható az a következtetés, hogy a hívási gráf építése az SML-programok forráskódjának tanulmányozása alapján rengeteg buktatóval jár, sőt bizonyos esetekre nem is tud megoldást nyújtani. Érdemes elgondolkozni azon a lehetőségen, hogy a gráfot inkább futási időben építsük fel. Erre három mód kínálkozik.
Az előző fejezetben elmondottakat alaposan átgondolva én a statikus, forráskód alapján történő gráfépítést választottam a megvalósításkor. Ennek oka a következő volt: a korábban ismertetett problémák - főként azok, amelyek megoldása igen körülményes vagy csaknem lehetetlen - jelentős része csak ritkán bukkan fel az átlagos SML-programokban, főként azokban, amelyeket olyan hallgatók írnak, akik csak fél éve ismerkednek a nyelvvel. Merem állítani, hogy itt is igaz a közismert ,,80-20 szabály'', azaz a problémák 80 százaléka csak az esetek 20 százalékában jön elő, sőt könnyen meglehet, hogy még ennél is kedvezőbb a helyzet. Ez alapján tehát kijelenthető, hogy egy viszonylag primitív, a felvetett problémákat nem vagy csak részben kezelő gráfépítő algoritmus is kellően hatékony lehet.
Az elkészült gráfépítő program ismertetését néhány technikai részlettel kezdem, majd kitérek arra is, hogy az előbbiekben vázolt problémák közül melyeket kezeli a program, és melyeket nem, és ezen döntéseimet meg is indoklom.
Az MOSML-interpreter - mint már említettem - szabadon hozzáférhető, ráadásul a forráskódja is tetszés szerint módosítható, részei szabadon felhasználhatóak. Ennek a forrásnak csupán a hatékonyság szempontjából legkritikusabb része, a byte-kód értelmező van C-ben írva, a többi, beleértve a szintaktikai elemzőt és az erre alapuló fordítót is, SML-ben. Ezt az elemzőt használtam fel a programomban, segítségével ugyanis beolvasható egy szintaktikai hibáktól mentes SML-program és átalakítható egy meglehetősen összetett SML-adatstruktúrává. Ebben a struktúrában rengeteg olyan adat van, amelyre a hívási gráf felépítéséhez nincs szükség, és szerkezetének kialakításakor inkább a hatékony kezelhetőség, mintsem az átláthatóság volt szempont, éppen ezért nem volt egészen triviális kinyerni a szükséges információkat. Egy helyen a fordítóba is ,,bele kellett nyúlnom'', mert nem látszott ki egy függvény6.3, amelyet meg szerettem volna hívni.
Ezek után nem meglepő, hogy maga a gráfépítő is SML-ben készült. Ennek két kézenfekvő oka is volt: az egyik, hogy így fel tudtam használni a kész szintaktikai elemzőt, a másik, hogy az SML nyelvet meglehetősen jól ismerem és hatékonyan tudom használni. A deklaratív nyelvek tömörségére jellemző, hogy a teljes gráfépítő program (az elemzőt nem számítva) kevesebb, mint 500 sor. A program kimenete egy szöveges állomány, amely kódoltan, Prolog-kifejezések formájában - mivel a hasonlóságvizsgáló program Prologban készült, és ilyen kifejezéseket tud kényelmesen beolvasni - tartalmazza az adott SML-program hívási fáját. Szerencsére ez a megkötés nem okozott nagyobb gondot, mintha bármilyen más szöveges formában kellene kiírni az adatokat. A könyvtári függvények hívásának felismeréséhez természetesen rendelkezésre kell, hogy álljon a könyvtári függvények teljes listája. Ez szerencsére kinyerhető a könyvtári modulok forrásából, ill. a hozzájuk adott ún. szignatúra állományokból. Ehhez egy egyszerű szkriptet készítettem, amely előállítja a szükséges adatokat tartalmazó, a gráfépítővel összeszerkesztett SML-modult. Ennek a megoldásnak az is az előnye, hogyha bővül az MOSML könyvtár, akkor pillanatok alatt kényelmesen adaptálni lehet a változásokhoz a gráfépítő programot is.
Alapvető döntést kellett hoznom a tekintetben, hogy a gráfépítő foglalkozzon-e szemantikai kérdésekkel is, vagy csak az elemző által kinyert nyers szintaktikai információkat használja fel. Sajnos egy alapos szemantikai elemzés lényegesen bonyolultabb, ezért úgy döntöttem, hogy a legtöbb kérdésben csak a szintaktikát veszem figyelembe. Mint azt már írtam, megfigyeléseim szerint egy relatíve egyszerű program is kellően pontos hívási gráfot tud építeni, ezért a szemantikai elemzés ,,ára'' meglehetősen nagy lenne a haszonhoz képest. E döntésemből adódóan a függvényértékek problémakörére javasolt megoldásaimat nem alkalmaztam a programomban. A gráfépítő a hívást mindig ott regisztrálja, ahol az egyes függvények neve szerepel, emiatt az anonim függvények meghívását sem kezeli (hiszen azok mindig pontosan egy helyen szerepelnének a gráfban). A szemantika megfelelő szintű kezelése egy következő fejlesztési fázis részeként kerülhet ismét szóba.
Ugyanebből az okból a program nem ismeri fel a val kulcsszóval definiált függvényeket. Ilyen esetekben ugyanis a függvény törzsét vagy a már ismertetett lambda-jelöléssel kell megadni, vagy valamely másik függvény részleges alkalmazásával (mint pl. val addTwo = add 2). Ennek felismeréséhez viszont a gráfépítőnek ismernie kellene, hogy mely függvények alkalmazhatóak részlegesen, és fel kellene ismernie az alkalmazásukat is. Jelenleg csak a fun kulcsszavas definíciókat kezeli, ezek ugyanis pusztán szintaktikai információk alapján felismerhetők. Gyakorlati szempontból azért nem kritikus ez a hiányosság, mert az SML-programok átláthatósága kedvéért nem szokás a val kulcsszó segítségével függvényeket definiálni.
Egy függvényt természetesen egy nem-függvény értékkel is elfedhetünk. A program jelenlegi változata nem veszi észre, hogy egy név nem függvény többé, ilyenkor tévesen az előző függvény meghívásaként értékeli az adott név egy-egy előfordulását. Ez a hiányosság kellemetlen: gyakran előfordul, hogy egy-egy hallgató nem tud róla (vagy nem jut eszébe), hogy létezik pl. length nevű könyvtári függvény, és a névhez egy egész értéket köt (mondjuk egy füzér hosszát). Szerencsére a hívási gráf ebből adódó torzulása sem túl jelentős.
A program egyelőre nem kezeli jól a több modulból álló programokat sem, azaz nem képes felismerni, hogy egy állomány gráfjának felépítéséhez először egy másik állományt kell feldolgoznia. Mivel a beadott házi feladatok az esetek elhanyagolhatóan kis részében készülnek több modullal, ez a hiányosság sem túl kritikus, de a közeljövőben célszerű kiküszöbölni.
ssec:gr-prob. fejezetben ismertetett ,,egyéb'' problémák többségét megfelelően kezeli a gráfépítő. Jól kezeli a lokális kifejezések és deklarációk kérdését, például az olyan eseteket, amikor egy lokális kifejezésben átmenetileg felüldefiniáljuk a könyvtári sin függvényt. Ha ilyenkor a kifejezésben szerepel a sin hívás, a gráfépítő észreveszi, hogy az nem a könyvtári függvényre, hanem a lokálisan definiáltra vonatkozik. Ehhez a lokálisan definiált függvényeknek egyedi nevet generál.
Ugyancsak jól működik a könyvtári modulok kezelése. A gráfépítő megjegyzi a modulok megnyitását, és a modulbeli függvények meghívásakor továbbra is az adott függvény teljes nevét (tehát modulnévvel együtt) regisztrálja a hívási gráfban.
A gráfépítő program jól kezeli a kölcsönösen rekurzív függvényeket is, tehát a függvényként felismert nevek listája nem teljesen lineárisan bővül, hanem szükség esetén blokkokban.
Szintén jól működik az infixnek deklarált operátorok definíciójának kezelése. Ehhez nyilvántartom az infix deklarációkat és az ezek hatását megszüntető nonfix deklarációkat is.
Tekintsük az alábbi rövid - kissé értelmetlen - példaprogramot, amely a gráfépítő által kezelt problémák egy részét jól demonstrálja.
structure Pro = struct
fun f x = x+1
local fun f (x,y) = x+y
in fun g (SOME xy) = f xy
| g NONE = let fun f () = 0 in f() end
end
fun h s = implode (i (map (chr o f o ord) (explode s)))
and i (c::cs) = c :: explode (h (implode cs))
| i [] = []
end
A példában az f függvény három változata szerepel: egy globális,
egy lokális deklarációban előforduló, és egy lokális kifejezésben
előforduló. A h és az i függvények kölcsönösen egymást
hívják a számos könyvtári függvény mellett. Most pedig lássuk, mit
produkál belőle a gráfépítő!
match:call_graph([
'Pro.f'-['General.+'],
'Pro.$local1.f'-['General.+'],
'Pro.g.$2.f'-[],
'Pro.g'-['Pro.$local1.f','Pro.g.$2.f'],
'Pro.h'-['Misc.implode','Pro.i','Misc.map','Misc.chr','General.o',
'Pro.f','General.o','Misc.ord','Misc.explode'],
'Pro.i'-['Misc.explode','Pro.h','Misc.implode']]).
match:non_called_preds([]).
match:useless_preds(['General.+','General.o','Misc.chr','Misc.explode',
'Misc.implode','Misc.map','Misc.ord']).
A hívási gráf (a call_graph/1 funktorú kifejezés argumentuma) a
három f függvénnyel kezdődik, látható, hogy mindháromnak más a
neve, amely a definíciójuk helyétől függ. Ezután következik g
törzse, amelyben két f változat is meg van hívva. Végül a
h és i függvények következnek, amelyek több könyvtári
függvény mellett egymást is hívják. A useless_preds/1 funktorú
kifejezés argumentumában a könyvtári függvények vannak pontosan egyszer
felsorolva, mivel ezek kevesebb információt adnak a programról, és így
lehetővé válik, hogy a hasonlóságvizsgáló program a gráfból kihagyja őket.
Az is látszik, hogy a General és Misc könyvtári modulok
alapértelmezés szerint meg vannak nyitva, azaz egy sima explode
hívást a gráfépítő - helyesen - Misc.explode-ként értelmez. A
non_called_preds/1 funktorú kifejezés argumentuma mindig üres
lista - ide akkor lehetne értelmes adatot írni, ha az SML-programot
futtatnánk is, és futás közben figyelnénk, hogy mely függvények nem
hívódnak meg. Erre a gráfépítő jelenleg nem képes, és nem tartom
valószínűnek, hogy egyhamar képes lesz. Ehhez ugyanis az SML-programok
fordítási folyamatába kell beavatkozni oly módon, hogy az egyes függvények
neve megőrződjék. (Erről arra ssec:grafprob-utso. szakaszban már
esett szó.)
Összességében elmondható, hogy a program egyszerűsége ellenére megbízhatóan és hatékonyan képes egy egyetlen modulból álló SML-program hívási gráfjának elfogadható pontosságú feltérképezésére. A ,,rosszindulatú támadásoknak'' ugyan nem tud igazán ellenállni, de ezen a szinten elfogadható az a védelem is, hogy az érdekeltek egyszerűen nem tudják meg a program hiányosságait.
A programot természetesen a gyakorlatban is kipróbáltam, méghozzá úgy, ahogyan a jövőben használni fogjuk: az általa előállított kimenet alapján SML-programokat hasonlítottam össze Lukácsy Gergely programjával. A tapasztalatok kedvezőek: több tanév házi feladataira küldött megoldásokhoz generáltam hívási gráfokat, és minden esetben (mintegy 150 programra) értelmes adatokat szolgáltatott. Az összehasonlítás kimutatta, hogy mindhárom vizsgált tanévben volt másolás, és ezt a manuális vizsgálat meg is erősítette.
Megállapítható tehát, hogy a gráfépítő program alapvetően megfelel elsődleges céljának, noha számos ponton fejlesztésre szorul.