Elosztott rendszerekre implementált funkcionális nyelvek - PRML projekt Király Roland, Hernyák Zoltán 2008. március 18.
Kivonat Sok funkcionális nyelv rendelkezik telekommunikációs rendszerek fejlesztésére alkalmas nyelvi elemekkel, melyek támogatják a párhuzamos, több processzoros, vagy klaszterekre írt programok fejlesztését. mint az Erlang, és vannak, melyek inkább a gyors, nagy pontosságú számítások és adatkezelés területén nyújtanak több lehet®séget, de az elosztottságot és a konkurrens rendszerek készítését nem támogatják. Ezen projekt célja egy olyan programozási nyelv megalkotása, amely nagy sebesség¶, nagy pontosságú matematikai számítások porgramozását teszi lehet®vé egyszer¶, könnyen tanulható módon. A végs® cél egy olyan funkcionális nyelv megalkotása, amelyen megírt programok futtathatók helyben, vagy elosztott módon egy grid rendszer¶ számítógéphálózatban. A PRML project keretében kísérletet teszünk arra, hogy bemutassunk az általunk tervezett funkcionális nyelvet, és annak futtató rendszerét, mely támogatja a nagy pontosságú és sebesség igény¶ számítások programozását, valamint konkurrens rendszerek fejlesztésére alkalmas. A rendszer képes számítógépek halmazát egységként (klaszter) kezelni automatikusan, vagy programozói beavatkozással. Mindezt teszi úgy, hogy a lehet® legoptimálisabban kezeli a rendelkezésre álló er®forrásokat. A nyelvhez jelenleg megalkottuk a nyelv szintaxisát, szintaktikai és szemantikai elemz® programját. A futtató környezet implementációja folyamatos fejlesztés alatt áll. A futtató rendszerben választható, hogy .NET köztes kódra alakítva a Framework 3.5-öt, vagy Erlang futtatókörnyezetet használjon az elosztottság megvalósítására. Az el®adás keretében az eddigi eredményeket és ötleteket próbáljuk meg bemutatni, és megismertetni ezt a nyílt forráskódú rendszert a jöv®beli, lehetséges fejleszt®ivel.
1
1. PRML pro jekt A PRML project keretében kísérletet teszünk arra, hogy bemutassunk egy általunk tervezett funkcionális nyelvet, és annak futtató rendszerét, mely támogatja a nagy pontosságú és sebesség igény¶ számítások gyors elvégzését és az elosztottságot, mely az el®z® tulajdonság szinte elengedhetetlen feltétele. A nyelv futtató rendszere képes számítógépek halmazát egységként (klaszter) kezelni úgy, hogy a lehet® legoptimálisabban használja ki a rendelkezésre álló er®forrásokat. A projekt keretében megterveztük a nyelv szintaxisát, melyet a kés®bbiekben ismertetünk, valamint a szemantika meghatározó részét.
A futtató rendszer
jelenlegi verziója a CSharp nyelvre támaszkodva valósítja meg az elosztottságot, de céljaink között van a saját környezet kialakítása. A jelenlegi egyik legjobb ilyen rendszer, a Beowulf [8] mintájára, vagy ezt a rendszert felhasználva szeretnénk az elosztott rendszert és a hozzá tartozó middleware-t kidolgozni.
2. PRML nyelv 2.1. Funkcionális nyelvi jellemz®k A funkcionális program típus, osztály és függvényde níciókból és egy kezdeti kifejezésb®l áll. A program végrehajtása a kezdeti kifejezés kiértékeléséb®l áll, vagyis azonos a kifejezésben szerepl® függvények szövegszer¶ behelyettesítésével. A végrahjtási modell minden esetben egy átíró rendszer mely kon uens, tehát a részkifejezések átírásának sorrendje nincs hatással a végeredményre.
Ilyen
kon uens rendszer a Lamda kalkulus. A gráf átírása során a kifejezések kiértékelése és behelyettesítése lényegesen gyorsabbá tehet®, ha a nagy er®forrásigény¶ kódrészeket több processzoron és memóriával, szerencsés esetben párhuzamosan tudjuk végrehajtani. Az általunk kidolgozott nyelvnek rendelkeznie kell az elosztottság támogatásával már nyelvi szinten is, valamint meg kell felelnie a funkcionális nyelveknél felsorolt alapelveknek.
2.2. A nyelv szintaxisa A PRML rendelkezik az alább felsorolt lehet®ségek mindegyikével.
•
Hivatkozási helyfüggetlenség (referential transparency). A függvények de niálásan sorredje nincs hatással a végeredményre.
•
Válozók csak egyszer kapnak értéket, állandók.
•
Szigorú statikus típusosság - A típus levezet® rendszer mindig meg tudja határozni a típust valamely környezetfügg® nyelvtan segítségével.
•
Megengedett a magasabb rend¶ függvények használata.
•
A futtatórendszer alkalmazhatja a Curry módszert - részleges függvényalkalmazást.
•
Rekurzív függvényhívásokkal valósítja meg az iterációt.
2
•
Lusta és mohó kiértékelés egyaránt használható a rendszerben.
•
A Zermelo Fraenkel halmazkifejezést tartalmazza a nyelv - lista kifejezés
A nyelv nem csak az elejét®l a végéig megírt programok futtatására alkalmas, hanem támogatja a lépésenkénti végrehajtást, valamint a komolyabb matematikai számítások keredményét szöveges formában is képes megjeleníteni.
2.3. Típusok a nyelvben A PRML nyelv támogatja a funkcionális nyelveknél megszokott típusok mellet a nagy pontosságú számításokhoz szükséges nagy méret¶ valós számok használatát, valamint a szám típusokoz megadható azok pontossága. A nyelvben speciális típusok is helyet kaptak.
Van saját szerkezet a pro-
cesszek azonosítására és a mobil kód célbajuttatására.
::= | "vector" "of" vektor | "{}" üres rendezett n-es | "{" "}" rendezett n-es | "[]" üres lista | "[" "]" lista | union | "->" fügvény | "(" ")" csoport | <processID> processz azonosító | "stream" [] mobil csatorna | [] rekord
"int" <pontossag> | "bool" | "char" | "string" [] | "word" <pontossag> | "float" <pontossag> ...
A típusok pontossága változtatható a futtatórendszerben.
A lebeg®pon-
tos számítások elvégzéséhez az elosztott rendszer optimális kihasználása mellett nagy mennyiség¶ memória vonható össze. A több processzor egyidej¶ kihasználásával a számítási kapacitás is nagy mértékben növelhet®. Az aktuálisan elvégzend® számítások er®forrás igényéhez mérten az er®források mértéke dinamikusan növelhet®, vagy csökkenthet®.
2.4. Kifejezések nyelvtana A nyelv kifejezés rendszere magában foglalja a funkcionális nyelvi jellemz®ket, de nem használja a monadikus input-output kezelést. A hagyományos elemek mellett megtalálható benne az üzenetküldésre, processzek közti adatfolyamok kezelésére és a mobil kód küldésére alkalmas utasítások.
3
A dinamikus és generatív kódok írására a template-ek használhatóak, valamint van lehet®ség a makrók támogatása el®fordító segítségével. Az el®fordítás során a standard C, C++ preprocesszort kívánjuk alkalmazni, mivel ebben megvan minden szükséges tudás a PRML elemeinek el®fordítására. A függvények hívása és de níciója egyaránt lehet rekurzív, vagy több klózból felépített. A több klóz esetén mindig a hívási mintára illeszked® ág fut le. A rekurzió kétféle változatát kihasználva egyaránt írható iteratív és normál rekurzív program. Az alábbiakban bemutatott néhány soros program megmutatja a nyelv lehet®ségeit. (az alábbi kódot a nyelv szintaktikai ellen®rz®je helyesnek fordította.)
module test import file1; //imported files import file2; export ft,fz;//exported functions fx :: int -> int<64> //from int to int64 fx a = a + 2; tupple :: int int int-> {} //create tuple contains integers tuple x y z = {x,y,z}; add::int int -> int add x y = x + y; fb::int -> int fb a = case a of 10 -> a, 20 -> a+2, _ -> fb a end; //this section starts some expressions start= 3 + 2; start= acker 3 2; start = fx 10; start=fx 3; acker::int acker 0 j acker i 0 acker i j
int -> int = j + 1 = acker (i - 1) 1 = acker (i - 1) (acker i (j - 1));
A forráskódban megtalálható függvény de níció, függvények hívása, néhány ismert függvény de níciója, valamint egyszer¶ kifejezések változók és kommentek.
4
3. Futtató rendszer Az elosztott futtatás alapja az a rendszer, mely a számítógépes hálózatból megfelel® mértékben vonja be a rendelkezésre álló számítási csomópontokat. A számítási halmaz lokális hálózatban (LAN) egymással összekapcsolt számítógépek halmaza
gk
Σhgi i (klaszter).
A klasztert egy központi vezérl® csomópont
irányítja, mely a számítási m¶veletek kiosztásáért és az eredmény feldolgo-
zásáért felel®s.
• Cluster = hΣhgi ii + gk • gi = hCP Ui , RAMi i • i = 1..n • gk = centralu A központi
gk számítógép
rendekezik karakteres, vagy gra kus felülettel, me-
lyet a programozó kezelhet közvetlenül, vagy egy küls® számítógépre telepített alkalmazással, ahol a programjait írja és futtatja. A központi gép gra kus felületen képes megmutatni a rendelkezésre álló számítási csomópontok számát, a memória méretét, a processzorok mennyiségét a gépekben, vagy összességében, valamint a terheltséget és az aktuális kihasználtságot. A számítási csomópontok valamely ismert operációs rendszert futtatják. Az operációs rendszeren fut a PRML midleware, mely egységessé és transzparensé teszi a futtató renszer számára a klasztert, és kommunikál a töbi entitással. A számítógépek szabvány kommunikációt használnak az üzenetek továbbításához, de magasabb szinten saját protokolljuk van az üzenetek feldolgozására. A központi gép egy hálózati kapcsoló segítségévelés kapcsolódik a számíási halmazhoz, valamint ez a kapcsoló biztosítja az összeköttetést a LAN számítógépei között. A klaszter felett áll a programozási nyelv futtató rendszere, mely a magasszint¶ funkcionális nyelvet képes értelmezni, s az elosztó rendszert®l független¶l alkalmazni az abban leírt utasításokat. A programozó közvetlenül beavatkozhat az elosztottság kezelésébe, vagyis utasításokat adhat a rendszer konkurrens részének, de írhat úgy is programot, hogy az alsóbb rétegekre bízza az er®források bevonását, vagy gyelmen kívül hagyását.
3.1. Köztes kód A PRML nyelv jelenlegi verziójában a magasszint¶ funkcionális nyelvet .NET [9] kódra, vagy Erlang [4] kódra tudjuk konvertálni, majd az említett nyelvek futtató rendszerének lehet®ségeit kihasználva hajtjuk végre a rogramokat. Az elosztottság megvalósítását végz® middleware hiányzik, valamint a gráfátíró rendszer is csak részben kidolgozott, vagyis jelenleg nem futtatható. A szintaktikai ellen®rz® program a kész kódot közvetlen¶l normál CSharp kódra, CSharp IL kóra vagy Erlang kódra konvertálja, majd meghívva az adott nyelv futtatóját el®állítja és futtatja a kész programot.
5
Ebben az állapotában a nyelv tesztelhet®, de a hatékonysága csak részben és nem pontosan mérhet®, viszont megmutatja a nyelv lehet®ségeit és ötletek ad a továbfejlesztéshez.
3.2. Parser és lexer A nyelvtani ellen®rz® program szabvány LALR(1). A nyelvtanból generálódik a lexikális elemz®, vagyis a nyelvi elemek leírásának megváltoztatását a lexikális és a szintaktikus elemz® képes követni. A szintaktikát XML, vagy egyéb jól strukturált sémájú fájlba tárolhatjuk. Az elemz®k a fájlban tárolt szintaxis alapján újra és újra legenerálhatóak, így elég csak a nyelvtani leírást megváltoztatni és újrageneráltatni az elemz®ket a nyelv változásainak követésére. A szemantikus ellen®rz® több apró programból áll, a programokat egy konténer fogja össze, és mindíg azokat az elemz® programokat futtatja csak le, amelyek a lefordítandó fájlban alkalmazott nyelvtani formulák elemzéséhez szükségesek. Ez az eljárás más rendszerekben is el®fordul.
Ilyen módon épül fel egyes
refaktoring eszközök elemz®je, mint a RefactorErl [3] [6] [7], valamint az összes Lex, Yacc, Bison, Yecc, Leex és egyéb parser generátorokkal el®állított elemz®k. Ezeknek a rendszereknek a nagy el®nye az, hogy minden változtatás, ami a nyelvet érinti könnyen korrigálható az újrafordítás során.
3.3. A framework A teljes rendszer tehát több szintb®l áll, melyek független¶l cserélhet®ek, átalakíthatóak, így alkalmazkodóvá teszik a nyelvet. Az konkurrens rész dinamikusan fel tudja használni a több processzor és memória nyújtotta lehet®ségeket úgy, hogy mindezt elfedi a programozó el®l. A teljes rendszer dinamikus és bármely pontján megváltoztatható, így könnyen fejleszthet®.
4. Párhuzamos munkák A funkcionális nyelvek világában találhatók hasonló elemz® és fordító-futtató rendszerek, melyek sok esetben jobban és hatékonyabban valósítják meg az itt bemutatottakat. A matematikai számítások terén nyújt támogatást, a konkurrencia megvalósításában az Erlang [4], az IO kezelésében a Clean kiemelked®.
Vannak a
generikusok használatát támogató funkcionális nyelvek, és a párhuzamosságot támogató rendszerek is, mint a Distributed Clean [2], vagy a Hume [1]. A PRML projekt kutatási célokkal készül lehet®séget adva feljeszt®knek és kutatókak egyaránt, hogy nem éles ipari, de ellen®rzött környezetben próbálhassák ki ötleteiket, programjaikat és tudásukat. A feljesztés teljes mértékben nyitott, minden használható kifejlesztett, vagy fejlesztés alatt álló komponens beépítésre kerülhet a résztvev®k és a projekt vezet®inek jóváhagyása mellett.
6
Hivatkozások [1] Gudmund Grov, Robert Pointon, Greg Michaelson, and Andrew Ireland. Coordination Models, Languages and Applications Track of the 23rd Annual ACM Symposium on Applied Computing, 2008. To appear. [2] ZSÓK VIKTÓRIA, HERNYÁK ZOLTÁN, HORVÁTH ZOLTÁN Designing Distributed Computational Skeletons in D-Clean and D-Box, in.: Lecture Notes in Computer Science, Horváth Zoltán(ed.) in.: Central European Functional Programming School (The First Central European Summer School, CEFP 2005, Budapest, Hungary, July 4-15, 2005), Revised Selected Lectures. , ISSN 0302-9743 [3] Microsoft http://plc.inf.elte.hu/erlang [4] Erlang http://www.erlang.org [5] PORKOLÁB ZOLTÁN, KIRÁLY ROLAND, KURTI ILIR Supporting Generic Programming in CORBA IDL, in.: Proceedings of the 7th International Conference on Applied Informatics (ICAI) [6] HORVáTH ZOLTáN, LöVEI LáSZLó, KOZSIK TAMáS, VíG ANIKó, NAGY TAMáS Refactoring Erlang Programs. Abstract, in.:
Conference
of PhD Students in Computer Science, CSCS 2006, Volume of extended abstracts [7] LöVEI LáSZLó, HORVáTH ZOLTáN, KOZSIK TAMáS, KIRáLY ROLAND, VíG ANIKó, NAGY TAMáS Refactoring in Erlang, a Dynamic Functional Language, Dig Danny, Cebulla Michael(ed.) in.: Proc. of 1st Workshop on Refactoring Tools (WRT'07), ECOOP 2007 , ISSN 1436-9915 [8] Beowulf project http://www.debian.org/ports/beowulf/ [9] msdn.microsoft.com/netframework/
7
