Önálló labor, TDK és diploma-munka (egységesen: munka) témák Szeredi Péter, SZIT 2008. június 1. A DLog leíró logikai (LL) következtető rendszer fejlesztése A DLog egy SHIQ nyelvet támogató adatdoboz következtető rendszer, amely Prologban készült és a LL tudásbázist Prolog kódra fordítja. A SHIQ adatdoboz következtető rendszerek között -- a DLog szerzői tudomása szerint -- számos szabványos tesztre a DLog leggyorsabb következtető rendszer. 1.1. A DLog kiterjesztése hatékony adatbázis interfészekkel A DLog rendszer egyik előnye a többi LL adatboboz következtető rendszerhez képest az hogy a kérdések megválaszolásához szükséges adatállításokat (az adatdoboz tartalmát) elvben képes egy hagyományos relációs adatbázisból kinyerni. Ebben a megközelítésben az LL tudásbázis adatfüggetlen részéből készítünk Prolog programot, amelynek futása során dinamikusan érjük el az adatbázis tartalmát. A munka során fel kell készíteni a DLog rendszert arra, hogy adatbázisokhoz tudjon kapcsolódni. Első lépésként ki kell bővíteni a különféle bementi interfészeket annak érdekében, hogy specifikálni lehessen melyik adatbázis tartalmazza az adatdoboz tartalmát és azt milyen módon (felhasználónév, jelszó, protokoll stb.) lehet elérni. Szükséges lehet egy leképezés megadása is, amely összerendeli az adatbázisban található táblaneveket az LL tudásbázis terminológiai részében szereplő atomi fogalomnevekkel. Második lépésként át kell alakítani a generált Prolog programot annak megfelelően, hogy bizonyos célok/célok csoportjai adatbázislekérdezésekké fognak fordulni. Ez az átalakítás alapvetően klóztörzsek sorrendezését és az abban található célok megfelelő összevonását jelenti, de kiterjedhet több klóz összevonására is. Végül létre kell hozni azt az interfészt, amelyen keresztül a generált Prolog program futása során eléri az adatbázis tartalmát. Egy-egy ilyen adatbázislekérdezés bonyolultsága a konkrét Prolog kérdéstől függ: bizonyos esetekben, például Prolog célok egy csoportjának egyidejű lekérdezésekor, komplexebb joint tartalmazó kérdések generálása is szükséges lehet. 1.2. A DLog kiterjesztése táblázással A Leíró Logikai kérdések megválaszolása a DLog rendszerben egy hagyományos Prolog végrehajtás során történik. Ennek egyik jellemzője az, hogy a futás során már bebizonyított részcélokat adott esetben újra megpróbáljuk bebizonyítani. A DLog rendszer jelenleg is alkalmaz számos technikát (tömörítés, projekció), amelyek orvosolják a fenti probléma bizonyos előfordulásait. Számos esetben ugyanakkor még mindig feleslegesen foglalkozunk olyan célokkal, amelyek megoldását már korábban kiszámítottuk. Az általános Prolog megoldás, a táblázás, közvetlenül sajnos nem használható, mert a DLog végrehajtás során használt ún. ős-rezolúció eredményekébben egy cél végrehajtása nem környezetfüggetlen, hanem függ attól, hogy milyen ősei vannak a Prolog végrehajtási fában. A munka során meg kell ismerni a létező táblázási megoldásokat és adaptálni kell Prolog és DLog környezethez. 1.3. A DLog párhuzamos és elosztott megvalósításai A Prolog végrehajtás -- a klasszikus imperatív nyelvekkel ellentétben -- könnyen párhuzamosítható. Ráadásul ez _implicit módon_ is elvégezhető, azaz úgy, hogy a Prolog programozónak nem is kell tudnia arról, hogy több processzor hajtja végre a programot. Többféle módon is párhuzamosítható a Prolog: a legismertebbek az ún. vagy-párhuzamosság, amikoris a keresési tér különböző ágait egyszerre dolgozzuk fel, illetve az és-párhuzamosság, amikor egy célsorozat különböző részcéljait futtatjuk párhuzamosan. A munka során elsősorban a vagy-párhuzamosság kiaknázásán dolgozunk a DLog rendszer által generált Prolog kód esetén. Mivel ez sokkal egyszerűbb, mint az általános Prolog programok, számos egyszerűsítésre van lehetőség az ismert Prolog technikákhoz képest. Célunk egy olyan DLog változat elkészítése amely több processzor/mag illetve hálozatba kapcsolt számítógépek felhasználásával lényegesen gyorsabban oldja meg az adatdoboz következtetési feladatokat, mint az egyprocesszoros rendszer. 1.4. A DLog T-doboz következtető komponensének továbbfejlesztése Ezen modul célja, hogy a T-dobozban szereplő axiómákat minél egyszerűbb formájú szabályokká alakítsa. Tesszük ezt azért, hogy a későbbi adatkövetkeztetés során már ne kelljen a T-doboz axiómái közötti összefüggésekkel foglalkozni, és fókuszált, lekérdezés-vezérelt következtetést tudjunk végezni. A munka során meg kell ismerkedni a DLog-ban működő következtetési algoritmussal, mely bizonyos mértékben igényli az elsőrendű rezolúciós tételbizonyítással valamint a leíró logikákhoz kifejlesztett tabló algoritmussal való barátkozást is. Ezután közösen azon dolgozunk, hogy hatékonyabbá tegyük a következtetést: ideálisan úgy, hogy a gép nagyjából azt csinálja, amit egy ember is csinálna. Fontos az érdektelen következtetési ágak minél korábbi felismerése, de bátran elő lehet állni radikálisan új módszerekkel is egyes részfeladatokhoz, vagy akár az egész következtetéshez. A munkának van egy elméleti, matematikai része valamint egy implementációs része, melyhez a Prolog nyelvet használjuk. Az egyetlen igazi követelmény a matematikai gondolkodás iránti hajlandóság és a lelkesedés. 2. Deklaratív nyelvek oktatása Ezek a feladatok a Deklaratív Programozás (DP), ill. a Nagyhatékonyságú Logikai Programozás (NHLP) c. tárgyak oktatásához kapcsolódó kutatás-fejlesztési tevékenységek. 2.1 Hasonlóságvizsgáló eszközök házi feladatok másolásának felderítésére A címben jelzett cél érdekében a DP tárgy oktatása során egyrészt a Match saját fejlesztésű programot, másrészt a 'sim' programot használjuk: . A Match egy olyan (Prolog nyelven készült) program, amellyel viszonylag nagyobb méretű forráskódú programok szerkezetének hasonlóságát lehet megállapítani. A Match rendszert már nyolc éve folyamatosan használjuk a DP nagy házi feladatok másolásának sikeres felderítésére. A 'sim' programot, amely lexikai hasonlóságot vizsgál, a kis házi feladatok esetén használjuk. A hasonlóságvizsgáló eszközök továbbfejlesztése több irányban is kívánatos. Egyrészt szükséges a Match rendszer kibővítése az Erlang nyelvű források esetére, mert a jövőben ezt a funkcionális nyelvet használjuk majd a DP tárgy oktatásában. Ez a kiterjesztés egyrészt egy nyelvi elemző beillesztését, másrészt a rendszer megfelelő hangolását igényli. Másrészt szükséges a 'sim' program fejlesztése is, mert jelenleg ebben egy generikus elemzőt használunk. Azt reméljük, hogy egy Prolog ill. Erlang-specifikus elemző használatával a találati pontosság fokozható. Végül sor kerülhet a két rendszer további fejlesztésére, sőt akár ezek összekapcsolására, illetve új eszközök kidolgozására is. 2.2 Gyakorló rendszer továbbfejlesztése Az elmúlt évek során a Deklaratív Programozás c. tárgyhoz kapcsolódóan kifejlesztettünk egy Elektronikus Tanársegéd (ETS) rendszert (http://dp.iit.bme.hu/ets), amely, többek között a Prolog és SML programozás hallgatói gyakorlását segíti. A munka célja ennek a gyakoroltató rendszernek a továbbfejlesztése: új feladat-típusok és feladatkészletek kidolgozása, a rendszer intelligens értékelő módszerekkel való bővítése, valamint egy segítő alrendszer kidolgozása, amely a hallgatót, az észlelt típushibák alapján a megfelelő anyagrészhez irányítja. A munka viteléhez szükséges a Prolog és/vagy az SML nyelvek ismerete, hasznos az oktatás (és különösen a gépi oktatás) iránti érdeklődés ill. gyakorlat. 2.3 Nagy házi feladatok összehasonlító vizsgálata A DP és NHLP tárgyak oktatásában minden félévben új nagy házi feladatokat tűzünk ki (lásd http://dp.iit.bme.hu, ill. http://www.inf.bme.hu/~szeredi). A munka ezek összegyűjtése, rendszerezése, megoldási módszereik összehasonlítása és elemzése, különös tekintettel a különböző deklaratív nyelvek (SML, Prolog, CLP) által nyújtott lehetőségekre. A munka során ki kell térni a tesztadatok előállítási módszereire, beleértve az automatikus generálást is. Az összegyűlt tapasztalatokra építve a munka során további, nagy házi feladatnak alkalmas problémákat kell azonosítani, a feladatkiírásokat és megoldásokat ki kell dolgozni. A munka viteléhez szükséges az SML és Prolog nyelvek, ill. a Prolog CLP kiterjesztéseinek ismerete. 3. Prolog megvalósítások Ezek a munkák a Prolog nyelv megvalósításához kapcsolódnak. 3.1 Prolog rendszerek összehasonlító vizsgálata 1995-ben készült el az Nemzetközi Szabványosítási Szervezet (ISO) Prolog nyelvre vonatkozó szabványának első része. Azóta számos Prolog rendszert "igazítottak" a szabványhoz. Sajnos több, kisebb-nagyobb kérdésben a magukat ISO-Prolog kompatíbilisnek nevező Prolog rendszerek is eltérnek egymástól. A SICStus Prolog rendszer regresszív tesztkészletéhez korábban elkészült egy program, amely a szabványban levő és további példák futtatásával ellenőrzi az ISO szabványnak való megfelelőséget. A feladat első része ennek a tesztprogramnak az átvitele további Prolog rendszerekre. Ezt követően azonosítani kell a szabvány problematikus döntéseit, és ezeket csoportosítva meg kell kísérelni a különböző Prolog rendszerek osztályozását. Ezután a tesztprogramot tovább kell fejleszteni, hogy segítségével könnyen azonosíthatók legyenek a Prolog megvalósítások. Fontos lehet még a teszt-rendszer kibővítése, pl. a könyvtári eljárások tesztelésére, vagy a különböző Prolog rendszerek (idő-, memória-) hatékonyságának az összehasonlító vizsgálatára. A munka viteléhez szükséges a Prolog nyelv ismerete. 3.2 Prolog rendszerek tárgazdálkodása A feladat a Prolog megvalósítások memória-gazdálkodási módszereinek a vizsgálatával kezdődik, különös tekintettel a hulladékgyűjtési (garbage collection) technikákra. Specifikusan meg kell ismerkedni egy nagyon egyszerű, oktatási célú Prolog megvalósítás, az aProlog rendszer memóriakezelésével. Meg kell tervezni egy az aProloghoz illeszkedő hulladékgyűjtési algoritmust, és implementálni kell C nyelven. A munka viteléhez szükséges a C és Prolog programozási nyelvek ismerete. 3.3 Prolog programok fordítási idejű transzformációja A cél egy olyan, a gyakorlatban alkalmazható Prolog preprocesszálási módszer kifejlesztése, amely nem igényel külön preprocesszor-nyelvet. Ez úgy érhető el, hogy a preprocesszálást úgy tekintjük, mint Prolog forrásprogramok transzformációját. Ez az általános irányzat az ún. parciális evaluáció (http://www.diku.dk/forskning/topps/activities/PartialEvaluation.html), ennek a közelítésmódnak a SICStus Prolog esetére való alkalmazása a Mixtus rendszer (http://www.sics.se/ps/mixtus.html). Ezen, viszonylag általános megközelítések mellett, a SICStus Prolog fejlesztési munkáinak megkönnyítésére készült egy egyszerű előfeldolgozó program, amely fordítási időben végez el egyes redukciós lépéseket (eljáráshívásokat). A munka célja ennek a preprocesszornak a továbbfejlesztése. A munka viteléhez szükséges a Prolog nyelv ismerete.