Önálló labor, TDK és diploma-munka (egységesen: munka) témák Szeredi Péter, SZIT 2010. október 1. Static typing in the Q programming language The aim of this project is to provide tools to statically analyse and type-check program code written in Q, a highly efficient vector-processing functional programming language. The dynamic nature of the language enables fast development of efficient applications. However, the lack of static type checking in the Q interpreter is a recurring source of programming errors. Stricter type checking will help finding errors in corner cases missed by test suites. It is well known in the literature of functional programming languages that a static type system improves the productivity of programmers. This is because, in a typed language, most programming errors result in a type error, reported at compile time. It is often the case that once a program is correct with respect to types, it contains no bugs, i.e. it works correctly. In the absence of static type checking, most errors surface only at runtime, and often only indirectly, through their consequences. Thus the introduction of types produces substantial time savings in the debugging of programs. The project is carried out in close cooperation with Morgan Stanley Business and Technology Centre, Budapest. The tools are implemented in Prolog. The subtasks in which Project Lab work can be carried out in the spring semester 2010 are listed below. 1.1 Development of the type checking algorithm. A type checking algorithm capable of checking the type-correctness of Q functions is developed. The input of the algorithm is a function f in the Q language, the type of f, and the types of any functions invoked from within f. The output of the algorithm is a boolean value reflecting the type-correctness of function f. The algorithm should view its inputs as parse trees (i.e. constructs using the abstract syntax). An abstract syntax for the Q language (extended with types) should be designed as part of this work package. 1.2 Parser implementation. The parser for the Q language extended with types is implemented. It takes a file containing language elements (functions and type declarations) and converts these to abstract syntactic format. 2. 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. 2.1 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. 2.2 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.3 A DLog kiterjesztése hatékony adatbázis interfészekkel (folyamatban) 2.4 A DLog kiterjesztése táblázással (folyamatban) 3. Deklaratív nyelvek oktatása Ezek a feladatok a Deklaratív Programozás (DP), ill. a Nagyhatékonyságú Deklaratív Programozás (NDP) c. tárgyak oktatásához kapcsolódó kutatás-fejlesztési tevékenységek. 3.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 most ezt a funkcionális nyelvet használjuk 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. 3.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. Az elmúlt években a tárgy oktatásában az SML helyett az Erlang nyelvet használjuk. A munka célja ennek a gyakoroltató rendszernek a továbbfejlesztése. Az első, legfontosabb feladat az Erlang nyelv támogatasának kidolgozása. Emellett a rendszer további fejlesztésében sor kerülhet új feladat-típusok és feladatkészletek kidolgozására, a rendszer intelligens értékelő módszerekkel való bővítésére, valamint egy segítő alrendszer kidolgozására, 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 Erlang nyelvek ismerete, hasznos az oktatás (és különösen a gépi oktatás) iránti érdeklődés ill. gyakorlat. 3.3 Nagy házi feladatok összehasonlító vizsgálata A DP és NDP tárgyak (illetve elődtárgyaik) 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.cs.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, Erlang, 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 Erlang, SML és Prolog nyelvek, ill. a Prolog CLP kiterjesztéseinek ismerete. 4. Prolog megvalósítások Ezek a munkák a Prolog nyelv megvalósításához kapcsolódnak. 4.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. 4.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. 4.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.