Programowanie C++
Metaprogramowanie
algorytmy wykonywane w czasie kompilacji
Metaprogramowaniem nazywa się tworzenie programów, które
w wyniku działania dostarczają programów. Metaprogramy stosujemy
aby zwiększyć szybkość działania programów oraz ich czytelność,
a także aby unikać powielania kodu, wtedy gdy te same operacje
chcemy wykonać dla grupy typów.
tu rzeczywistego. Szablonu tego używa się za-
Dowiesz się: Powinieneś wiedzieć: miast funkcji kwadratowej, Power<2>(x) do-
" Jak tworzyć programy działające w czasie " Jak pisać proste programy w C++; starcza funkcji x*x, Power<3>(x) dostarcza
kompilacji; " Co to sÄ… szablony. x*x*x itd. Szablon ten, przedstawiony na Li-
" Jak używa się kolekcji typów; stingu 3, po pierwsze skraca zapis, po drugie
" Jak wykorzystać kontenery i algorytmy do- kod jest bardziej czytelny, po trzecie kod wy-
starczane przez bibliotekę boost::mpl. konuje się szybciej niż implementacja algoryt-
mu potęgowania wykonywana w czasie działa-
nia programu, dostarczana przez std::power,
nywalnego, dostarczeniu stałej równej N! , po- która zawiera pętlę wykonującą wielokrotne
nieważ wartość składowej value dla tego szablo- mnożenie.
Poziom nu jest obliczana w czasie kompilacji. Szablon Jeżeli wykładnik jest dużą liczbą całkowi-
trudności Silnia nadaje znaczenie stałej, więc kod jest tą (co zdarza się na przykład przy kodowaniu
bardziej czytelny, nie musimy obliczać warto- RSA), to algorytm potęgowania przez wielo-
ści funkcji narzędziem zewnętrznym, unikamy krotne mnożenie, przedstawiony na Listingu 3,
pomyłek związanych z umieszczaniem w pro- jest mało wydajny. Wielkość kodu wynikowego
arzędziami do metaprogramowa- gramie wartości obliczonych poza nim. może znacznie wzrosnąć, ponieważ utworzo-
nia w C++ jest preprocesor oraz me- Algorytm obliczający silnię (Listing 1) zo- na w czasie kompilacji funkcja jest długa. Nedo-
Nchanizm szablonów, mechanizmy te stał zdefiniowany rekurencyjnie i wykorzy- godności powyższe możemy usunąć, korzysta-
dostarczają instrukcji wyższego rzędu, które po- stuje specjalizację szablonów. Rekurencja jest jąc z faktu, że w szablonach można implemen-
zwalajÄ… na manipulacje kodem z
ródłowym. techniką bardzo powszechną w tego typu pro- tować złożenia funkcji. Ponieważ xn, dla n=2m
Mechanizm szablonów oferuje większe moż- gramach, ponieważ metaprogramy mogą wy- (gdy n jest potęgą dwójki, tzn. n=1,2,4,8,16,
liwości i wygodniejszą składnię niż makrode- korzystywać jedynie byty dostępne w czasie itd.) można obliczać jako m krotne podnosze-
finicje preprocesora, szablony są lepiej wspie- kompilacji (stałe całkowite, typy itd.), nie mo- nie do kwadratu, czyli xn=(...((x2)2)...)2, jeże-
rane przez kompilator, dlatego są częściej uży- żemy użyć zmiennej ani tworzyć pętli. Meta- li podnoszenie do kwadratu oznaczymy jako
wane do tworzenia metaprogramów i my także programy sÄ… podobne do programów tworzo- sqr, to xn=sqr × sqr × & × sqr(x), gdzie × ozna-
będziemy z nich korzystać, pomijając możliwo- nych w językach funkcyjnych. Program po- cza złożenie funkcji. Używając tego sposobu
ści tworzenia takich rozwiązań przez preproce- kazany na Listingu 2 (zaczerpnięty z książki dla n=1024, wykonamy tylko m=10 operacji
sor. Szablony umożliwiają implementację do- Abrahams, Gurtovoy, Język C++, metaprogra- podnoszenia do kwadratu, a nie 1024 mnoże-
wolnego algorytmu, z punktu widzenia teorii mowanie za pomocą szablonów) pozwala zapi- nia. Potęgę dla dowolnej liczby całkowitej do-
automatów są one równoważne maszynie Tu- sywać stałe całkowite w kodzie dwójkowym, co
ringa. Algorytmy te są wykonywane w czasie zwiększa czytelność, jeżeli to bity są istotne.
Szybki start
kompilacji, wyniki ich działania są umieszcza-
Aby uruchomić przedstawione przykłady,
ne w kodzie wynikowym. 0bliczenia w czasie kompilacji
należy mieć dostęp do kompilatora C++
Dostarczając algorytmy, które wykonują się
oraz edytora tekstu. Niektóre przykłady
Zwiększanie czytelności kodu w czasie kompilacji, przyspieszamy działa-
korzystają z udogodnień dostarczanych
Jednym z powodów tworzenia metaprogra- nie programów, ponieważ część przetwarza-
przez bibliotekÄ™ boost::mpl, warunkiem
mów jest chęć zwiększenia czytelności i ela- nia będzie wykonywana w czasie kompilacji, ich uruchomienia jest instalacja biblio-
tek boost (w wersji 1.36 lub nowszej) Na
styczności kodu. Metaprogram tego typu, po- co w pewnych przypadkach zwiększa wiel-
wydrukach pominięto dołączanie odpo-
kazany na Listingu 1, oblicza wartość funkcji kość kodu. Metaprogramy mogą używać frag-
wiednich nagłówków oraz udostępnianie
silnia podczas kompilacji. Konkretyzacja sza- mentów kodu, a nie tylko stałych, co pokaza-
przestrzeni nazw, pełne z
ródła dołączono
blonu Silnia (gdzie N jest liczbą całkowi- no na przykładzie szablonu Power dostarcza-
jako materiały pomocnicze.
tą dodatnią) jest równoważna, dla kodu wyko- jącego funkcji potęgi całkowitej dla argumen-
24 12/2009
Metaprogramowanie
datniej n można uzyskać, wykorzystując po-
Listing 1. Metaprogram obliczający wartość funkcji silnia
kazany powyżej sposób, jeżeli n zapiszemy bi-
narnie n=bm*2m + b(m-1)*2(m-1) + ... + b1*2 + b0 template struct Silnia {
= (bmb(m-1)...b1b0)2, to xn jest iloczynem skład- static const unsigned int value = n*Silnia::value;
ników, które będziemy wielokrotnie podno- };
sić do kwadratu, na przykład x35 = x(32+2+1) = template<> struct Silnia<0> { //specjalizacja, kończy rekurencję
((((x2)2)2)2)2*(x2)*x. Na Listingu 4 przedstawio- static const unsigned int value = 1;
no szablon funkcji Pow, która realizuje przedsta- };
wioną koncepcję, generując w czasie kompilacji unsigned int i = Silnia<0>::value; //przykład użycia, równoważne i = 1
wyrażenie, które oblicza potęgę. i = Silnia<5>::value; //równoważne i = 120
Metaprogramy mogą dostarczać przy-
Listing 2. Metaprogram, który pozwala używać stałych zapisanych binarnie
bliżenia funkcji matematycznych z założo-
ną dokładnością. Przykładowo funkcja wy- template struct Binary { //stałe binarne
kładnicza może być przybliżana szeregiem static const unsigned long value = Binary::value << 1  n % 10;
};
template <> struct Binary<0> { //stop dla rekurencji
static const unsigned long value = 0;
};
więc dostarczając szablon, można obliczać ją //przykład użycia
z założoną precyzją; patrz Listing 5. const int FLAGS = Binary<1100>::value; //zamiast 12 lub 0xC
Kod tworzony przez metaprogramy często
Listing 3. Metaprogram dostarczający funkcji do potęgowania (wykładnik całkowity dodatni)
wykorzystuje siÄ™ w bibliotekach numerycz-
nych, na przykład do mnożenia czy odwraca- template inline double Power(double x) {
nia macierzy. Obliczenia wykonywane w czasie return x * Power(x); //rekurencyjna definicja funkcji
kompilacji dostarczają stałych lub funkcji, które }
możemy obliczyć lub wyprowadzić za pomocą template <> inline double Power<0>(double x) {
innych narzędzi (na przykład ręcznie), a następ- return 1.0; //specjalizacja kończy rekurencję
nie umieścić je w programie. Stosowanie meta- }
programów zwiększa elastyczność dostarcza-
Listing 4. Szablon generuje wyrażenie obliczające potęgę o wykładniku całkowitym
nych rozwiązań oraz zmniejsza ryzyko popeł-
nienia pomyłki, jest też bardziej czytelne, po- template double Pow(double x) {
nieważ nazwa szablonu zawiera informacje o return Pow<2>( Pow(x) )*Pow(x);
znaczeniu. }
//specjalizacje dla kwadratu i innych warunków brzegowych
Kolekcje typów template <> double Pow<2>(double x) { return x*x;}
Metaprogramy, których argumentami są ty- template <> double Pow<1>(double x) { return x;}
py, pozwalają wyrażać pojęcia trudne do opisu template <> double int_power<0>(double x) { return 1.0;}
innymi technikami, na przykład pozwala wy-
Listing 5. Szablon generuje wyrażenie obliczające wartość funkcji wykładniczej z założoną
konywać podobne operacje na grupie wskaza-
precyzjÄ…
nych typów. W takich przypadkach wykorzy-
stujemy kolekcje typów, które można utwo- template inline double Exp(double x) {
rzyć za pomocą szablonów. Przykład takiej ko- //wykorzystuje szablony z Listingu 1 oraz Listingu 4
lekcji, przechowującej typy w liście jednokie- return Exp(x) + Pow(x)/Silnia::value;
runkowej (propozycja opisana w książce An- }
dreia Alexandrescu Nowoczesne projektowanie template <> inline double Exp<0>(double x) {
w C++), pokazuje Listing 6. return 1.0;
Poszczególne elementy listy przechowu- }
jÄ… dowolne typy, natomiast ostatni element
Szablony przypomnienie
Szablony (templates) dostępne w języku C++ umożliwiają implementację generycznych, to znaczy niezależnych od typów, algorytmów oraz
struktur danych. Przykładowy szablon swap, pokazany poniżej, zamienia zawartość dwu obiektów, możemy go wołać dla dowolnych obiektów
tego samego typu, jeżeli dostarczają one konstruktora kopiującego i operatora przypisania.
template void swap(T& a, T& b) {
T tmp = a;
a = b;
b = tmp;
}
Podczas kompilacji następuje konkretyzacja szablonu, co oznacza generowanie kodu dla właściwych typów. Kod generowany na podstawie szablonów
nie różni się od kodu tworzonego ręcznie, nie ma żadnych narzutów pamięciowych i czasowych, jedyną niedogodnością jest dłuższy czas kompilacji.
Specjalizacja to wersja szablonu, która będzie użyta do generacji kodu zamiast wersji ogólnej, gdy parametrami będą odpowiednie typy.
12/2009 www.sdjournal.org 25
Programowanie C++
jest zawsze typu NullType (lista z wartow- du na konieczność rekurencyjnego zagłębiania la przechowywać dowolną liczbę typów, różnią
nikiem). Za pomocą tak zdefiniowanej li- tych szablonów. Biblioteka boost::mpl dostar- się one pewnymi właściwościami, na przykład
sty możemy utworzyć kolekcję typów o do- cza kolekcji typów oraz operacji, zwalnia ona mpl::set usuwa kolejne wystąpienia tego sa-
wolnej długości, na Listingu 6 pokazano li- programistę z konieczności implementacji wła- mego typu w kolekcji. Najczęściej używa się ko-
stę przechowującą trzy typy: short, int oraz snych rozwiązań. Kolekcje typów dostarczane lekcji mpl::vector, natomiast pozostałe wyko-
long. Listing 7 pokazuje operację obliczania przez tę bibliotekę mają interfejs zbliżony do ze- rzystuje się wtedy, gdy odpowiednie właściwo-
długości kolekcji (liczba elementów listy). stawu metod oferowanych przez kolekcje z bi- ści okażą się przydatne. Dostarczane są operacje
blioteki standardowej, ponadto biblioteka do- modyfikacji tych kolekcji, to znaczy dodawania
boost starcza zbiór przydatnych metafunkcji, pozwa- i usuwania elementów, badania właściwości ko-
metaprogramming library (MPL) lając unikać zapisów rekurencyjnych. Kolekcje lekcji, badania występowania danego typu, sto-
Tworzenie listy typów za pomocą szablonu typów to szablony: mpl::vector, mpl::list, sowania pewnej operacji dla każdego z typów w
TList jest niewygodne i nieczytelne, ze wzglę- mpl::set oraz mpl::map, każdy z nich pozwa- kolekcji, tworzenie nowych typów na podsta-
wie typów przechowywanych w kolekcji. Przy-
kład użycia kolekcji został pokazany na Listin-
Listing 6. Kolekcja typów zdefiniowana rekurencyjnie
gu 8. Każda z operacji zakłada, że wynik, któ-
template struct TList { // lista rekurencyjna ry jest typem, jest składową type, natomiast wy-
typedef H Head; nik, który jest wartością jest dostępny jako skła-
typedef T Tail; dowa type::value. Oczywiście algorytmy wy-
}; konujÄ… siÄ™ w czasie kompilacji.
struct NullType { }; //typ kończący listę Algorytm mpl::for_each jest nietypowy, wo-
//przykładowa kolekcja typów ła on dostarczoną funkcję lub dostarczony funk-
typedef TList > > Integers; tor (obiekt klasy, która dostarcza operatora wo-
łania funkcyjnego) dla każdego typu, który jest
Listing 7. Badanie długości listy typów
przechowywany w kolekcji. Specyfika tego al-
template struct Size { gorytmu polega na tym, że tworzy on kod, któ-
static const int value = Size::value + 1; ry jest wykonywany w czasie działania, patrz Li-
}; sting 9, gdzie pokazano rozwiÄ…zanie (a raczej
template <> struct Size< NullType> { szkic rozwiązania), które wykorzystuje bibliote-
static const int value = 0; kę mpl do rejestracji klas w fabryce obiektów.
}; Biblioteka mpl jest używana przez wiele in-
nych bibliotek dostarczanych przez boost, na
Listing 8. Przykład operacji na kontenerach z biblioteki mpl
przykład przez biblioteki tworzące obiekty funk-
typedef mpl::vector Types; // przykładowa kolekcja cyjne bind, bibliotekę dostarczającą variant
typedef mpl::push_back::type NewTypes; // modyfikacja (obiekt, który przechowuje jedną z wybranych
cout << mpl::size::type::value; // wydrukuje wartość 5 wartości, podobnie jak union w C) czy bibliote-
//algorytm count zlicza wystąpienia danego typu w kolekcji kę spirit, służącą do generowania gramatyk.
cout << mpl::count::type::value; //drukuje liczbÄ™ 2
Podsumowanie
Listing 9. Przykład wykorzystania algorytmu for_each z biblioteki mpl
Metaprogramowanie umożliwia przetwarza-
//mamy hierarchiÄ™ klas, gdzie klasÄ… bazowÄ… jest Figure nie informacji podczas kompilacji. Techniki
class Square : public Figure { //przykładowa klasa konkretna te pozwalają zmniejszać rozmiar kodu, zwięk-
public: szając jego czytelność, oraz sprawiać, że progra-
//klasa konkretna dostarcza metodÄ™ statycznÄ… create my wykonujÄ… siÄ™ szybciej. Metaprogramowa-
static Figure* create() { return new Square; } nie znalazło wiele zastosowań zwłaszcza przy
static int id_; //klasa konkretna przechowuje identyfikator tworzeniu ogólnych, przenośnych i efektyw-
}; nych rozwiązań. Zostanie ono wsparte w no-
struct Factory { //fabryka figur konkretnych, przedstawiony kod bardzo uproszczony wej wersji standardu C++0x.
public:
typedef Figure* (*CreateFig)(); //typ funkcji tworzÄ…cej obiekty
static Factory& getInstance(); //dostęp do obiektu fabryki
W Sieci
int registerFig(CreateFig fun); //metoda rejestracji, dostarcza funkcjÄ™
tworzÄ…cÄ… obiekt, zwraca id
" http://www.boost.org  dokumentacja
}; bibliotek boost;
" http://www.open-std.org  dokumen-
struct RegisterFigure { //szablon użyty do rejestracji
ty opisujÄ…ce nowy standard C++.
template void operator()(T){
T::id_ = Factory::getInstance().registerFig( T::create );
}
}; R0BERT N0WAK
typedef mpl::vector Types; // kolekcja typów dla klas Adiunkt w Zakładzie Sztucznej Inteligencji Instytu-
konkretnych tu Systemów Elektronicznych Politechniki Warszaw-
mpl::for\_each(RegisterFigure()); //woła w czasie wykonania operację dla skiej, zainteresowany tworzeniem aplikacji dla biolo-
każdego typu gii i medycyny, programuje w C++ od ponad 10 lat.
Kontakt z autorem:[e-mail]
26 12/2009