GTL Graphical Template Library

E¨otv¨os Lor´and Tudom´anyegyetem Informatikai Kar Programoz´asi Nyelvek ´es Ford´ıt´oprogramok Tansz´ek

GTL Graphical Template Library Vatai Emil V. ´eves Programtervez˝o Matematikus hallgat´o T´emavezet˝o:

Dr. Porkol´ ab Zolt´ an egyetemi docens E¨otv¨os Lor´and Tudom´anyegyetem - Informatikai Kar Programoz´asi Nyelvek ´es Ford´ıt´oprogramok Tansz´ek

Budapest, 2007. m´ajus 31.

Kivonat A Graphical Template Library (GTL) [2], egy olyan k´ıs´erleti generikus C++ sablon-k¨onyvt´ar, ami a C++ Standard Template Library (STL) alap¨otlet´et pr´ob´alja ´atvinni a grafikus feladatok k¨or´ebe. A GTL-t 1999-ben k´esz´ıtette el Kisteleki R´obert (ELTE programtervez˝o matematikus hallgat´o) ´es Dr. Porkol´ab Zolt´an. Eredetileg, a feladat, egy rajzol´o program megval´os´ıt´asa lett volna, amely a GTL-re t´amaszkodik ´es a GTL ´altal ny´ ujtott alakzatokat tudja kirajzolni ´es ezeken a GTL algoritmusait, m˝ uveleteit tudja v´egrehajtani. A program fejleszt´ese sor´an, kiz´ar´olag a generikus programoz´as eszk¨ozeire kellet haszn´alni, az ¨or¨okl˝od´est ´es a virtu´alis f¨ uggv´enyek haszn´alat´at teljesen mell˝ozve. A program elk´esz´ıt´ese folyam´an, komoly probl´em´akba u ¨tk¨ozt¨ unk, melyeket a GTL, vagyis ´altal´anosan, a generikus programoz´as korl´atai okoztak. ´Igy a feladat b˝ov¨ ult, ezen probl´em´ak ´es korl´atok felt´ar´as´aval ´es annak a bizony´ıt´as´aval, hogy ezek a korl´atok, az elv´art megszor´ıt´asok (dinamikus polimorfizmus mell˝oz´ese) mellet nem ker¨ ulhet˝oek meg. V´eg¨ ul adunk egy becsl´est arra, hogy mi lenne az kompromisszum az objektum orient´alt ´es a generikus programoz´as k¨oz¨ott, amely ´el mindk´et paradigma eszk¨ozeivel ´es a legjobb eredm´enyt ny´ ujtva, azaz hogyan kellene enyh´ıteni a felt´eteleket, hogy egy kell˝oen hat´ekony ´es eleg´ans megold´ast kapjunk.

1.

Egy k´ ezenfekv˝ o megold´ as – ¨ or¨ okl˝ od´ es

Ha az ember geometriai alakzatokat rajzol´o ´es manipul´al´o programot akar ´ırni, akkor azt objektum orient´alt megk¨ozel´ıt´es, vagyis az ¨or¨okl˝od´es j´o v´alaszt´asnak t˝ unik. A tipikus p´elda, az ¨or¨okl˝od´es ´es az objektum orient´alt programoz´as szeml´eltet´es´ere pontosan az ilyen rajzol´o programok implement´aci´oja. Egy Shape b´azis-oszt´alyb´ol induln´ank ki ´es ebb˝ol sz´armaztatn´ank a Polygon, Circle ´es hasonl´o oszt´alyokat. A Shape oszt´alyban deklar´aljuk a virtu´alis draw, move, rotate, stb. met´odusokat, majd a sz´armaztatott oszt´alyokban defini´aljuk ˝oket ´es egy Shape* t´ıpus´ u, azaz alakzatokra mutat´o mutat´okat tartalmaz´o t¨ombbe pakoljuk a rajzlap tartalm´at. Ilyen megold´assal er˝osen t´amaszkodunk az ¨or¨okl˝od´esre ´es a dinamikus polimorfizmusra. A Java els˝o kiad´asai ezt a megk¨ozel´ıt´est alkalmazt´ak a szabv´anyos t´arol´ok megval´os´ıt´as´ahoz. J´av´aban minden t´ıpus az Object t´ıpusb´ol sz´armazik, azaz J´av´aban minden objektum t´ıpus´ u [4]. ´Igy k´ezenfekv˝o volt az a megold´as, hogy az ArrayList, a List, a Set ´es a Map kont´enerek Object t´ıpus´ u elemeket (pontosabban referenci´akat) t´arolnak. Ennek egy´ertelm˝ u h´atr´anya volt, hogy a t´arol´ok u ´gymond nem tudtak” a t´arolt elemek t´ıpus´ar´ol semmit. ” 1

Tov´abb´a amikor haszn´alt´ak a kont´ener elemeit, akkor azok mivel Object t´ıpus´ uak voltak, ez´ert fut´asiidej˝ u, dinamikus t´ıpuskonverzi´ot kellet rajtuk v´egrehajtani ami valamilyen m´ert´ekben rontotta a program teljes´ıtm´eny´et. Ezt ki lehetett ker¨ ulni u ´j, t´ıpus-tudatos” oszt´alyok l´etrehoz´as´aval. Ilyen ” lehetne p´eld´aul a ShapeArray oszt´aly, amelyhez meg´ırhatjuk a megfelel˝o DrawAll(ShapeArray sa) ´es RotateAll(ShapeArray sa, float r) f¨ uggv´enyeket.

2.

Generikus programoz´ as ´ es az STL

A kont´enereket ´es a rajtuk v´egrehajtand´o algoritmusokat C++-ban nagyon eleg´ans m´odon oldott´ak meg, oszt´aly-sablonok ´es f¨ uggv´enyek-sablonok seg´ıts´eg´evel. A C++ STL k¨onyvt´ar´aban (Standard Template Library), a kont´enerek mint p´eld´aul a vector, a list, a set stb. mind oszt´aly-sablonok, melyeket a t´aroland´o elemek t´ıpus´aval param´eterez¨ unk. Ezek mell´e, az STL m´eg a megfelel˝o algoritmusokat is biztos´ıtja, mint p´eld´aul a sort vagy a find. Az algoritmusok f¨ uggv´eny sablonk´ent vannak implement´alva, ´es iter´atorokon kereszt¨ ul kommunik´alnak” a kont´enerekkel. Az STL-nek megk¨ozel´ıt´ese sz´amos ” el˝onye van az Objecteket t´arol´o kont´enerrel szemben: • T´ıpus biztons´agos: A ford´ıt´o mindent elv´egez helyett¨ unk. Ford´ıt´asiid˝oben p´eld´anyos´ıtja a oszt´aly-sablonokat ´es f¨ uggv´eny-sablonokat, ´es a megfelel˝o t´ıpus ellen˝orz´eseket is elv´egzi. Teh´at kisebb a hiba lehet˝os´eg. • Hat´ekony: A sablonok seg´ıts´eg´evel a ford´ıt´o mindent a ford´ıt´asi id˝oben kisz´amol, leellen˝oriz ´es behelyettes´ıt – minden a ford´ıt´askor eld˝ol semmit sem hagy fut´asi-id˝ore. • Egyszer˝ ubb b˝ov´ıteni ´es programozni: ak´ar u ´j algoritmusokkal, ak´ar u ´j kont´enerekkel egyszer˝ uen b˝ov´ıthetj¨ uk a k¨onyvt´arat, csak a megfelel˝o iter´atorokat kell implement´alni ´es a megfelel˝o konvenci´okat (concepteket) k¨ovetni. Az utobbib´ol az is ad´odik, hogy ha van m t´ıpusunk ´es n m˝ uvelet¨ unk, akkor az objektum orient´al hozz´a´all´assal ellent´etben, ahol minden t´ıpus minden (virtu´alis) met´odus´at, azaz O(n ∗ m) f¨ uggv´enyt kell implement´alni, generikus programoz´assal viszont el´eg O(n + m), vagyis k¨ ul¨on-k¨ ul¨on implement´alnunk kell a t´ıpusokat (´es iter´atoraikat) ´es k¨ ul¨on az algoritmusokat. Ezek az el˝ony¨oket, az STL oly m´odon k´epes megval´os´ıtani, hogy egy´altal´an nem megy a programoz´o rov´as´ara, vagyis nem kell bonyolultabb k´odot ´ırni, s˝ot, kevesebb k´odot kell ´ırni, ami kevesebb hib´aval j´ar. A C++ sablonok, ford´ıt´askor manipul´alj´ak a k´odot, ´es egy csom´o rutin munk´at elv´egeznek 2

a programoz´o helyett. Ebben az esetben, ahelyett, hogy mi ´ırjuk meg k¨ ul¨onk¨ ul¨on a IntVector-t ´es a FloatVectort, a sablonok ezt automatikusan megteszik helyett¨ unk, ugyanis l´enyeg´eben ugyan azt a k´odot kell meg´ırni, csak m´as t´ıpussal.

3.

Sablon m´ agia – Template Metaprogramming

Ilyen sok probl´em´at megoldani, ilyen hat´ekonyan szinte m´agi´anak t˝ unhet. Sok´aig annak is t˝ unt ´es ez arra ¨oszt¨onz¨ott p´ar C++ programoz´ot, hogy kicsit jobban megvizsg´alj´ak a sablonok ´altal ny´ ujtott lehet˝os´egeket. ´Igy t¨ort´ent, hogy 1994-ben Erwin Unruh bemutatta a C++ szabv´any bizotts´ag el˝ott az els˝o sablon-metaprogramot, amely, igaz nem fordult le, de viszont a hiba¨ uzenetek pr´ımsz´amok voltak. Felismerv´en a C++-ba be´agyazott sablonmechanizmus Turing-teljess´eg´et, mint (ford´ıt´as idej˝ u) nyelv, megfogant a C++ sablon-metaprogramoz´as (template metaprogramming) fogalma. A sablonok, egy a rekurz´ıv f¨ uggv´eny h´ıv´ashoz hasonl´o elveken m˝ uk¨odik. A r´eszben specializ´alt sablonok, f¨ uggv´eny h´ıv´ashoz hasonl´ıtanak ´es a teljes specializ´aci´ok pedig termin´alj´ak a rekurzi´ot. Ezt nagyon j´ol szeml´elteti a k¨ovetkez˝o p´elda: // factorial.cpp #include template struct Factorial { enum { value = N * Factorial::value }; }; template <> struct Factorial<1> { enum { value = 1 }; }; // example use int main() { const int fact15 = Factorial<15>::value; std::cout << fact15 << endl; return 0; } Mi is fog t¨ort´enni amikor a ford´ıt´o leford´ıtja a programunkat? A fact15 egy N = 15-vel p´eld´anyos´ıtott oszt´aly-sablon, amelynek a value tagja egyenl˝o a 3

Factorial::value-vel, azaz a p´eld´anyos´ıt´as rekurz´ıvan” megh´ıv´odik, ” eg´esz addig am´ıg a Factorial<1>-n´el nem termin´al. Nagyon fontos ´eszre venni, hogy ez mind ford´ıt´as id˝oben t¨ort´enik, ´es fut´as id˝oben a fact15 v´altoz´o, m´ar a 1307674368000 liter´alt kapja ´ert´ek¨ ul. Vagyis nem ´ırhatjuk a k¨ovetkez˝ot: int main() { int fact; std::cin >> fact; std::cout << fact << endl; return 0; } ugyan is a nem tal´alhatja ki a ford´ıt´o program, milyen sz´amot fog a felhaszn´al´o bevinni. Term´eszetesen jogos az ´eszrev´etel, hogy minek az ossz vesz˝od´es, hogy ´ırjunk egy eleve nehezen ´erthet˝o ´es tal´an f´elrevezet˝o sablon-metaprogramot ha egy egyszer˝ u kalkul´ator programmal, vagy ak´ar pap´ıron kisz´amolhatjuk, hogy 15! = 1307674368000 ´es az el˝oz˝o p´elda programunkat a k¨ovetkez˝o, elvileg azonos programra: int main() { int fact = 1307674368000; // == 15! std::cout << fact << endl; return 0; } Ennek t¨obb oka is lehet. Els˝o sorban, ha t¨obbsz¨or akarn´ank olyan konstansokat haszn´alni a programunkban, ami egy pozit´ıv eg´esz faktori´alisa, akkor egy´ertelm˝ u, hogy a t¨obbsz¨or¨os sz´amol´as ´es t¨obbsz¨or¨os hiba elker¨ ul´ese v´eget, azaz pontoss´agi, helyess´egi ´es k´enyelmi szempontok miatt is meg´eri egy ilyen kis metaprogram meg´ır´asa. Ez lehet, hogy a faktori´alisra nem t´ ul s˝ ur˝ un lesz sz¨ uks´eg¨ unk, de p´eld´aul ahogy a C++ nem csak ´e´a˝ou ´u ˝´ou ¨

Hivatkoz´ asok [1] Bjarne Stroustrup: A C++ programoz´ asi nyelv, Kiskapu, 2001, [1305], ISBN 963 9301 17 5 ¨o [2] Zolt´an Porkol´ab, R´obert Kisteleki: Alternative Generic Libraries, ICAI’99 4th International Conference on Applied Informatics, Ed: Em˝od Kov´acs et al., Eger-Noszvaj, 1999, [79-86] 4

[3] David Abrahams, Aleksey Gurtovoy: C++ Template Metaprogramming - Consepts, Tools, and Techniques from Boost and Beyond, Addison Wesley Professional, 2004, ISBN 0-321-22725-5 [4] Bruce Eckel, Thinking in Java (3rd Edition) , Prentice Hall PTR, 2002, [1119], ISBN-10: 0131002872 [5] Boost Meta Template Library

5