èablonovΘ metaprogramovßnφ (template metaprogramming) je velice zajφmavß technika, vhodnß p°edevÜφm pro tvorbu knihoven a optimalizaci k≤du. Jejφ poΦßtky se datujφ p°ibli₧n∞ do roku 1994 a od tΘ doby se postupn∞ vyvinula v pou₧iteln² a nad∞jn² prost°edek, kter², alespo≥ pokroΦil²m, urΦit∞ stojφ za seznßmenφ...
Rozvφjejφcφ se standard C++ umo₧nil n∞co, o Φem se d°φve nikomu ani nesnilo: p°idat do jazyka C++ kvalitativn∞ novou vrstvu û metaprogramovßnφ. Prost°edkem jsou Üablony (templates), kterΘ zmi≥ovan² standard znaΦn²m zp∙sobem rozÜφ°il. Pomocφ Üablon lze emulovat zßkladnφ konstrukce programovacφch jazyk∙, jako v∞tvenφ (if-then-else, switch) nebo smyΦky (for, do-while, while). Ukß₧eme si, jak na to.
Metatypy
Prom∞nn²mi v ÜablonovΘm metaprogramovßnφ jsou typy a celß Φφsla (p°esn∞ji °eΦeno vÜechno, co m∙₧e b²t argumentem Üablony). Vzhledem k tomu, ₧e metaprogram je provßd∞n b∞hem kompilace, musφ b²t Φφsla z pohledu klasickΘho C++ konstanty. I v ÜablonovΘm metaprogramovßnφ lze rozliÜit prom∞nnΘ, konstanty a literßly. ZaΦneme s jednoduch²mi p°φklady:
const int N = 1;
template <int M> class A {};
void funkce()
{
A<N> a; // zde p°i°adφme M = N
}
Zde N je metakonstanta, M je metaprom∞nnß, 1 je celoΦφseln² metaliterßl (p°edpony meta majφ naznaΦit vztah k metaprogramu). Samoz°ejm∞, N je zßrove≥ konstanta a 1 je celoΦφseln² literßl. A nynφ pro zm∞nu typy:
typedef int X;
template <class T> class B {};
void funkce()
{
B<X> b; // zde p°i°adφme T = X
}
Jde o analogii p°edchozφho p°φkladu: X je (typovß) metakonstanta, T je (typovß) metaprom∞nnß, int je (typov²) metaliterßl. I bez slo₧it²ch definic by m∞lo b²t jasnΘ, co je co.
Metaoperace
Uka₧me si te∩, jak pomocφ Üablon zapsat n∞kterΘ jednoduchΘ metaoperace. ZaΦneme u nßsobenφ:
template <int M, int N> struct MetaMUL
{
static cont int RETURN = M*N;
};
Pou₧φt to m∙₧eme t°eba takto:
template <int M, int N> class Matice // matice M x N
{
// ... uvedeno jen to podstatnΘ
static const int PocetPrvku()
{
return MetaMUL<M, N>::RETURN;
}
};
Metoda PocetPrvku() vrßtφ poΦet prvk∙ matice, tj. M*N. M∙₧ete namφtnout, ₧e to je zbyteΦn∞ slo₧itΘ a mφsto metaoperace MetaMUL by zde Ülo pou₧φt klasickou operaci nßsobenφ. JednoduchΘ smysluplnΘ p°φklady metaprogramovßnφ se vÜak t∞₧ko hledajφ a musφme se zatφm spokojit s t∞mi mΘn∞ smyslupln²mi.
Ostatnφ operace s cel²mi Φφsly lze definovat analogicky. Uvedeme jeÜt∞ jeden p°φklad û porovnßnφ:
template <int M, int N> struct MetaEQ
{
static const bool RETURN = (M == N);
};
Porovnßnφ je operace, kterou m∙₧eme implementovat i pro typy. V tomto p°φpad∞ musφme ale pou₧φt ΦßsteΦnou specializaci Üablon:
template <class T1, class T2> struct MetaEQTYPE
{
static const bool RETURN = false;
}
template <class T> struct MetaEQTYPE<T, T>
{
static const bool RETURN = true;
}
Smyslupln² p°φklad pou₧itφ se sem bohu₧el nevejde, tak alespo≥ to nejjednoduÜÜφ, co lze napsat:
MetaEQTYPE<int, double>::RETURN; // v²raz 1
MetaEQTYPE<int, int>::RETURN; // v²raz 2
Pokud p°ekladaΦ narazφ na v²raz 1, pou₧ije nespecializovanou Üablonu, a tudφ₧ hodnotu false. Pro v²raz 2 se pou₧ije specializovanß Üablona a hodnota true.
Metafunkce
Od metaoperacφ je jen kr∙Φek k metafunkcφm. Uka₧me si vyu₧itφ rekurze v hodnotovΘm parametru Üablony na klasickΘm p°φkladu v²poΦtu faktorißlu. Faktorißl nezßpornΘho celΘho Φφsla n je definovßn rekurzivn∞ takto:
0! = 1
n! = n.(n-1)!
A nynφ v Üablonßch:
template <int N> struct MetaFactorial
{
static const int F = N*MetaFactorial<N-1>::F;
};
// explicitnφ specializace, ukonΦenφ rekurze
template <> struct MetaFactorial<0>
{
static const int F = 1;
};
Co na to p°ekladaΦ? Pokud narazφ na v²raz MetaFactorial<N>::F, pokusφ se vyΦφslit jeho hodnotu takto:
if (N == 0)
{
pou₧ij specializovanou t°φdu MetaFactorial<0>
MetaFactorial<0>::F = 1
}
else // N > 0
{
pou₧ij nespecializovanou t°φdu MetaFactorial<N>
je t°eba urΦit MetaFactorial<N-1>::F,
a proto pou₧ij rekurzivn∞ tento postup pro N-1
prove∩ nßsobenφ N*cFaktorial<N-1>::F
}
Pokud v programu napφÜeme cFaktorial<4>::F, p°ekladaΦ to nahradφ v dob∞ p°ekladu konstantou 24 û v²poΦet faktorißlu tedy nenφ zßle₧itostφ b∞hu programu, ale p°ekladaΦe! V²poΦet faktorißlu byl op∞t tφm nejjednoduÜÜφm p°φkladem. M∙₧eme ovÜem vyΦφslovat i mnohem komplikovan∞jÜφ funkce, dokonce i odmocniny:
template <int SIZE, int LOW = 1, int HIGH = SIZE>
struct MetaRoot;
{
static const int mean = (LOW+HIGH)/2;
static const bool down = (mean*mean >= SIZE);
static const int root =
MetaRoot<SIZE, (down ? LOW : mean+1),
(down ? mean : HIGH)>::root;
};
// ΦßsteΦnß specializace
template <int SIZE, int MID>
struct MetaRoot<SIZE, MID, MID>
{
static const int root = MID;
};
V²raz sRoot<N>::root je ekvivalentem v²razu std::ceil(std::sqrt(N)), tj. je to hornφ celß Φßst odmocniny z N; lze jej pou₧φt na mφst∞, kde je oΦekßvßna konstanta, nap°. p°i deklaraci statickΘho pole:
const int N = 10;
int tabulka[sRoot<N>::root];
JeÜt∞ poznßmka: Tento p°φklad, aΦkoliv je zcela v souladu se standardem jazyka C++, v mΘm p°ekladaΦi (C++ Builder 4.0) nefunguje. ProblΘm je v deklaraci prvnφ Üablony. P°ekladaΦ si nedokß₧e poradit s implicitnφm argumentem u ÜablonovΘho parametru HIGH (tj. int HIGH = SIZE). Ohlßsφ vnit°nφ chybu a skonΦφ. Doufejme, ₧e v nov∞jÜφch p°ekladaΦφch u₧ to bude lepÜφ.
Meta-if
V∞tvenφ pat°φ mezi zßkladnφ programovΘ konstrukce a v metaprogramovßnφ mß takΘ svΘ mφsto. Vytvo°φme primßrnφ Üablonu t°φdy
template <bool B> struct MetaIF {};
a explicitnφ specializaci pro argumenty true a false:
template <> struct MetaIF<true>
{
static void Neco();
};
template <> struct MetaIF<false> {};
Toto je implementace ne·plnΘho meta-if (kde chybφ sekce else). P°φklad pou₧itφ:
MetaIF<(sizeof(int) > 2)>::Neco();
ZapiÜme schematicky, co chceme od p°ekladaΦe
if (sizeof(int) > 2)
{
pou₧ij t°φdu MetaIF<true>
zavolej metodu MetaIF<true>::Neco()
}
else
{
pou₧ij t°φdu MetaIF<false>
metoda MetaIF<false>::Neco() nenφ definovanß
ohlaÜ chybu
}
Pokud bychom cht∞li emulovat ·plnΘ meta-if, staΦφ dodefinovat metodu MetaIF<false>::Neco(). Poznamenejme jeÜt∞, ₧e pro pou₧itφ MetaIF<B> je nutnΘ, aby B byl v²raz vyΦφsliteln² v dob∞ p°ekladu a p°evoditeln² na typ bool.
Meta-switch
Na podobnΘm principu funguje i emulace konstrukce switch. Vytvo°φme primßrnφ Üablonu t°φdy MetaCASE. Ta pak bude slou₧it jako sekce default v p°φkazu switch.
template <int I> struct MetaCASE
{
static int NecoDelej() {return 0;}
};
Nynφ pro ka₧dou hodnotu, kterß by se vyskytla v nßv∞Ütφ case, vytvo°φme explicitnφ specializaci.
Emulace smyΦek je zalo₧ena na rekurzi v hodnotovΘm parametru Üablony. PoΦet pr∙chod∙ smyΦkou musφ b²t znßm v dob∞ p°ekladu. Klasicky by to mohlo vypadat takto:
void funkce(int i)
{
std::cout << i; // n∞jakß akce
}
const int N = 10;
for (int i = 0 ; i <= N ; i++) funkce(i);
A nynφ pomocφ Üablon:
template <int I> struct MetaLOOP
{
static void loop()
{
MetaLOOP<I-1>::loop(); // rekurze
std::cout << I; // n∞jakß akce
}
};
// explicitnφ specializace, ukonΦφ rekurzi
template <> struct MetaLOOP<0>
{
static void loop()
{
std::cout << 0; // n∞jakß akce
}
};
Uka₧me si, co se stane, kdy₧ p°ekladaΦ narazφ na konstrukci MetaLOOP<N>::loop(), kde N je konstanta znßmß v dob∞ p°ekladu:
if (N == 0)
{
pou₧ij specializovanou t°φdu MetaLOOP<0>
zavolej metodu MetaLOOP<0>::loop()
(naÜe metoda vypφÜe na obrazovku hodnotu 0)
}
else // N > 0
{
pou₧ij nespecializovanou t°φdu MetaLOOP<N>
zavolej metodu MetaLOOP<N>::loop()
v metod∞ MetaLOOP<N>::loop()
je t°eba zavolat metodu MetaLOOP<N-1>::loop(),
proto pou₧ij rekurzivn∞ tento postup pro N-1
potom prove∩ dalÜφ instrukce v metod∞
MetaLOOP<N>::loop()
(naÜe metoda vypφÜe na obrazovku hodnotu N)
}
To v praxi znamenß, ₧e p°φkaz MetaLOOP<2>::loop() vypφÜe na obrazovku °et∞zec "012". Nejd°φve se zavolß MetaLOOP<2>::loop(), ta zavolß MetaLOOP<1>::loop() a ta zavolß MetaLOOP<0>::loop(). Zde dojde k v²pisu hodnoty 0. Vracφme se do funkce MetaLOOP<1>::loop(), kde dojde k v²pisu hodnoty 1. Nakonec se vrßtφme do MetaLOOP<2>::loop(), kde se vypφÜe hodnota 2. Pokud bychom cht∞li obrßtit sled hodnot, staΦφ zam∞nit po°adφ rekurze a "akce" v metod∞ MetaLOOP<I>::loop():
template <int I> struct MetaLOOP
{
static void loop()
{
std::cout << i; // n∞jakß akce
MetaLOOP<I-1>::funkce(); // rekurze
}
};
Nynφ by p°φkaz MetaLOOP<2>::loop() vypsal na obrazovku °et∞zec "210". A nynφ se dostßvßme k nevφdan²m mo₧nostem optimalizace: Pokud budou metody deklarovßny jako vlo₧enΘ, tj. deklarovßny s pou₧itφm klφΦovΘho slova inline nebo definovßny uvnit° t°φdy (jako zde), nebude p°ekladaΦ volat funkce, ale p°φmo tam vlo₧φ k≤d. Navφc je to ud∞lßno rekurzivn∞, tak₧e p°ekladaΦ v p°φpad∞ p°φkazu MetaLOOP<2>::loop() vygeneruje nßsledujφcφ k≤d (pro p∙vodnφ vzestupnou verzi):
std::cout << 0;
std::cout << 1;
std::cout << 2;
Ani zmφnka o n∞jakΘ smyΦce Φi volßnφ funkce! V angliΦtin∞ se to oznaΦuje jako loop transformation, tedy transformace smyΦky do jednosm∞rnΘ posloupnosti p°φkaz∙. Tφmto zp∙sobem je mo₧nΘ donutit p°ekladaΦ optimalizovat na rychlost: odstranφ se smyΦka (testovßnφ v²razu, skok na zaΦßtek nebo na konec smyΦky) i volßnφ funkcφ (ulo₧enφ a odstran∞nφ parametr∙ v zßsobnφku, skok do funkce a nßvrat z funkce).
Podmφnkou ovÜem je, aby poΦet opakovßnφ smyΦky byl znßm v dob∞ p°ekladu a byl mal² (viz zßv∞reΦnΘ poznßmky). Proto tento p°φstup nelze pou₧φt v₧dy. Velice vhodn² je pro tzv. "malΘ" vektory a matice. O co jde? M∞jme za ·kol naprogramovat knihovnu pro prßci s vektory (samoz°ejm∞ pomocφ Üablon). Vytvo°φme Üablonu t°φdy cVektorA tak, jak nßs to uΦφ uΦebnice C++:
template <class TYP> class cVektorA
{
public:
cVektorA(int velikost)
: Velikost(velikost), Data(new TYP [velikost]) {}
~cVektorA() {delete [] Data;}
// ... uvedeny jsou jen d∙le₧itΘ v∞ci
TYP operator *(cVektorA<TYP> & v); // skalßrnφ souΦin
private:
TYP * Data;
int Velikost;
};
// p°etφ₧en² operßtor *, skalßrnφ souΦin
template <class TYP>
TYP cVektorA<TYP>::operator *(cVektorA<TYP> & v)
{
// problΘm 1: nelze provΘst pro odliÜnΘ velikosti
if (Velikost != v.Velikost)
{
throw std::logic_error("* nelze provΘst pro vektory"
"odliÜnΘ velikosti");
}
// problΘm 2: neefektivnφ pro "male Velikosti"
TYP suma = 0;
for (int i = 0 ; i < Velikost ; i++)
{
suma += Data[i] * v.Data[i];
}
return suma;
}
V definici p°etφ₧enΘho operßtoru nßsobenφ jsou naznaΦeny n∞kterΘ problΘmy. NaÜφm cφlem je co nejrychlejÜφ k≤d, tak₧e pro malΘ vektory to zkusφme jinak û s pou₧itφm ÜablonovΘho metaprogramovßnφ. Novß t°φda cVektor bude parametrizovßna takΘ velikostφ vektoru.
template <class TYP, int VELIKOST> class cVektor
{
public:
cVektor() : Data(new TYP [VELIKOST]) {}
~cVektor() {delete [] Data;}
// ... uvedeny jsou jen d∙le₧itΘ v∞ci
TYP operator *(cVektor<TYP, VELIKOST> & v);
private:
TYP * Data;
};
// pomocnΘ t°φdy pro implementaci skalßrnφho souΦinu
template <class TYP, int VELIKOST> struct MetaDOT
{
static inline TYP apply(const TYP * a, const TYP * b)
Jak vidφte, je skalßrnφ souΦin dvou vektor∙ p°ekladaΦem p°etransformovßn do tvaru
Data[0]*v.Data[0] + Data[1]*v.Data[1] + ... +
Data[VELIKOST-1]*v.Data[VELIKOST-1]
co₧ je tΘm∞° optimßlnφ tvar. Stejn∞ tak m∙₧eme optimalizovat sΦφtßnφ, odΦφtßnφ, inicializaci, kopφrovßnφ atd. Na Chip CD (viz infotipy) naleznete mj. zdrojov² soubor metaloop_02.cpp, ve kterΘm je dopln∞n jednoduch² test rychlosti. Pro VELIKOST==2 je metak≤d asi Φty°icetkrßt (!) rychlejÜφ ne₧ p∙vodnφ implementace pomocφ smyΦek. Pro rostoucφ VELIKOST tento pom∞r klesß.
N∞kolik poznßmek na konec
Metak≤d je mo₧no zapsat r∙zn²mi zp∙soby. V p°edchozφm jsme vÜechny operace implementovali pomocφ Üablon t°φd (struct, class) a jejich statick²ch atribut∙ a metod. N∞kte°φ auto°i obΦas pou₧φvajφ i Üablony funkcφ nebo mφsto statick²ch atribut∙ pou₧φvajφ v²ΦtovΘ typy (enum).
Pou₧itφ funkcφ nenφ zrovna nejchyt°ejÜφ. Statickß metoda t°φdy poskytuje v podstat∞ totΘ₧ co funkce. Navφc do t°φdy je mo₧no vlo₧it mnoho dalÜφch d∙le₧it²ch informacφ, nap°. o typu vracenΘ hodnoty, kterΘ je mo₧nΘ v metak≤du vyu₧φt.
V²ΦtovΘ typy p°edstavujφ alternativu statick²ch atribut∙. Ale pozor: P°i pou₧itφ v²Φtov²ch typ∙ i statick²ch atribut∙ jsem narazil na zßva₧nΘ problΘmy v n∞kter²ch p°ekladaΦφch (Borland C++ Builder 4.0); rozhodn∞ se v₧dy vyplatφ pßr pokus∙ p°edem.
DalÜφ omezenφ se mohou vyskytnout v souvislosti se smyΦkami. Nejde toti₧ o nic jinΘho ne₧ o rekurzivnφ vytvß°enφ instancφ Üablon. Norma doporuΦuje tv∙rc∙m p°ekladaΦ∙ podporovat hloubku rekurze minimßln∞ 17. R∙znΘ p°ekladaΦe se ovÜem mohou liÜit. Borland C++ Builder 4.0 dovolφ v n∞kter²ch p°φpadech dosßhnout hloubky rekurze v∞tÜφ ne₧ 1000 (!), jindy zase nejvφce 86 û prost∞ poka₧dΘ je to jinak (viz infotipy û ukßzky program∙ na Chip CD). Proto znovu p°ipomφnßm, ₧e je t°eba experimentovat.
Zßv∞r
Hlavnφ v²znam ÜablonovΘho metaprogramovßnφ spoΦφvß v optimalizaci v²slednΘho k≤du z hlediska rychlosti. Z p°ekladaΦe se tak vlastn∞ stßvß interpret, kter² podle naÜich instrukcφ (metaprogramu) nejd°φve vygeneruje tΘm∞° optimßlnφ k≤d a ten pak p°elo₧φ. Metaprogram nenφ nic jinΘho ne₧ chyt°e vytvo°enΘ deklarace Üablon t°φd a jejich specializacφ. Rychlost v²slednΘho k≤du je pak srovnatelnß s rychlostφ po ruΦnφ optimalizaci.
SouΦasnΘ p°ekladaΦe ovÜem zatφm majφ s n∞kter²mi konstrukcemi problΘmy. Nenφ se co divit û v∞tÜina z nich jeÜt∞ pln∞ neimplementuje Üablony tak, jak to vy₧aduje standard, a nßpis na krabici "Full ANSI/ISO template implementation" Φasto vyjad°uje spφÜe p°ßnφ ne₧ skuteΦnost.
Knihovny napsanΘ pomocφ ÜablonovΘho metaprogramovßnφ lze nalΘzt na internetu. Mezi nejlepÜφ pat°φ Blitz++ a Matrix Template Library, kterΘ p°edstavujφ implementaci lineßrnφ algebry a n∞kter²ch numerick²ch algoritm∙. Tam takΘ hledejte dalÜφ, praktiΦt∞jÜφ p°φklady konstrukcφ, kterΘ jsme si zde p°edstavili.
Optimalizace pomocφ Üablon samoz°ejm∞ nekonΦφ u mal²ch vektor∙. Optimalizovat lze takΘ operace provßd∞nΘ s velk²mi vektory, o tom vÜak snad n∞kdy p°φÜt∞.
Jaroslav Fran∞k
infotipy
Standard C++:
International standard ISO/IEC 14882, Programming languages û C++. 1998-09-01.
