2009.12_Metaprogramowanie algorytmy wykonywane w czasie kompilacji_[Programowanie C C++].pdf

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.

Dowiesz się:

• Jak tworzyć programy działające w czasie

kompilacji;

• Jak używa się kolekcji typów;

• Jak wykorzystać kontenery i algorytmy do-

starczane przez bibliotekę boost::mpl.

Powinieneś wiedzieć:

• Jak pisać proste programy w C++;

• Co to są szablony.

tu rzeczywistego. Szablonu tego używa się za-

miast funkcji kwadratowej, Power<2>(x) do-

starcza funkcji x*x , P ower<3>(x) dostarcza

x*x*x itd. Szablon ten, przedstawiony na Li-

stingu 3, po pierwsze skraca zapis, po drugie

kod jest bardziej czytelny, po trzecie kod wy-

konuje się szybciej niż implementacja algoryt-

mu potęgowania wykonywana w czasie działa-

nia programu, dostarczana przez std::power ,

która zawiera pętlę wykonującą wielokrotne

mnożenie.

Jeżeli wykładnik jest dużą liczbą całkowi-

tą (co zdarza się na przykład przy kodowaniu

RSA), to algorytm potęgowania przez wielo-

krotne mnożenie, przedstawiony na Listingu 3,

jest mało wydajny. Wielkość kodu wynikowego

może znacznie wzrosnąć, ponieważ utworzo-

na w czasie kompilacji funkcja jest długa. Nedo-

godności powyższe możemy usunąć, korzysta-

jąc z faktu, że w szablonach można implemen-

tować złożenia funkcji. Ponieważ x n , dla n=2 m

(gdy n jest potęgą dwójki, tzn. n=1,2,4,8,16,

itd.) można obliczać jako m krotne podnosze-

nie do kwadratu, czyli x n =(...((x 2 ) 2 )...) 2 , jeże-

li podnoszenie do kwadratu oznaczymy jako

sqr, to x n =sqr × sqr × … × sqr(x), gdzie × ozna-

cza złożenie funkcji. Używając tego sposobu

dla n=1024, wykonamy tylko m=10 operacji

podnoszenia do kwadratu, a nie 1024 mnoże-

nia. Potęgę dla dowolnej liczby całkowitej do-

Poziom

trudności

nywalnego, dostarczeniu stałej równej N! , po-

nieważ wartość składowej value dla tego szablo-

nu jest obliczana w czasie kompilacji. Szablon

Silnia nadaje znaczenie stałej, więc kod jest

bardziej czytelny, nie musimy obliczać warto-

ści funkcji narzędziem zewnętrznym, unikamy

pomyłek związanych z umieszczaniem w pro-

gramie wartości obliczonych poza nim.

Algorytm obliczający silnię (Listing 1) zo-

stał zdefiniowany rekurencyjnie i wykorzy-

stuje specjalizację szablonów. Rekurencja jest

techniką bardzo powszechną w tego typu pro-

gramach, ponieważ metaprogramy mogą wy-

korzystywać jedynie byty dostępne w czasie

kompilacji (stałe całkowite, typy itd.), nie mo-

żemy użyć zmiennej ani tworzyć pętli. Meta-

programy są podobne do programów tworzo-

nych w językach funkcyjnych. Program po-

kazany na Listingu 2 (zaczerpnięty z książki

Abrahams, Gurtovoy, Język C++, metaprogra-

mowanie za pomocą szablonów) pozwala zapi-

sywać stałe całkowite w kodzie dwójkowym, co

zwiększa czytelność, jeżeli to bity są istotne.

nia w C++ jest preprocesor oraz me-

chanizm szablonów, mechanizmy te

dostarczają instrukcji wyższego rzędu , które po-

zwalają na manipulacje kodem źródłowym.

Mechanizm szablonów oferuje większe moż-

liwości i wygodniejszą składnię niż makrode-

finicje preprocesora, szablony są lepiej wspie-

rane przez kompilator, dlatego są częściej uży-

wane do tworzenia metaprogramów i my także

będziemy z nich korzystać, pomijając możliwo-

ści tworzenia takich rozwiązań przez preproce-

sor. Szablony umożliwiają implementację do-

wolnego algorytmu, z punktu widzenia teorii

automatów są one równoważne maszynie Tu-

ringa. Algorytmy te są wykonywane w czasie

kompilacji, wyniki ich działania są umieszcza-

ne w kodzie wynikowym.

Szybki start

Aby uruchomić przedstawione przykłady,

należy mieć dostęp do kompilatora C++

oraz edytora tekstu. Niektóre przykłady

korzystają z udogodnień dostarczanych

przez bibliotekę boost::mpl, warunkiem

ich uruchomienia jest instalacja biblio-

tek boost (w wersji 1.36 lub nowszej) Na

wydrukach pominięto dołączanie odpo-

wiednich nagłówków oraz udostępnianie

przestrzeni nazw, pełne źródła dołączono

jako materiały pomocnicze.

Obliczenia w czasie kompilacji

Dostarczając algorytmy, które wykonują się

w czasie kompilacji, przyspieszamy działa-

nie programów, ponieważ część przetwarza-

nia będzie wykonywana w czasie kompilacji,

co w pewnych przypadkach zwiększa wiel-

kość kodu. Metaprogramy mogą używać frag-

mentów kodu, a nie tylko stałych, co pokaza-

no na przykładzie szablonu Power dostarcza-

jącego funkcji potęgi całkowitej dla argumen-

Zwiększanie czytelności kodu

Jednym z powodów tworzenia metaprogra-

mów jest chęć zwiększenia czytelności i ela-

styczności kodu. Metaprogram tego typu, po-

kazany na Listingu 1, oblicza wartość funkcji

silnia podczas kompilacji. Konkretyzacja sza-

blonu Silnia<N> (gdzie N jest liczbą całkowi-

tą dodatnią) jest równoważna, dla kodu wyko-

12/2009

N arzędziami do metaprogramowa-

Metaprogramowanie

datniej n można uzyskać, wykorzystując po-

kazany powyżej sposób, jeżeli n zapiszemy bi-

narnie n=b m *2 m + b (m-1) *2 (m-1) + ... + b 1 *2 + b 0

= (b m b (m-1) ...b 1 b 0 ) 2 , to x n jest iloczynem skład-

ników, które będziemy wielokrotnie podno-

sić do kwadratu, na przykład x 35 = x (32+2+1) =

((((x 2 ) 2 ) 2 ) 2 ) 2 *(x 2 )*x. Na Listingu 4 przedstawio-

no szablon funkcji Pow , która realizuje przedsta-

wioną koncepcję, generując w czasie kompilacji

wyrażenie, które oblicza potęgę.

Metaprogramy mogą dostarczać przy-

bliżenia funkcji matematycznych z założo-

ną dokładnością. Przykładowo funkcja wy-

kładnicza może być przybliżana szeregiem

Listing 1. Metaprogram obliczający wartość funkcji silnia

template < unsigned int n > struct Silnia {

static const unsigned int value = n * Silnia < n - 1 >:: value ;

};

template <> struct Silnia < 0 > { //specjalizacja, kończy rekurencję

static const unsigned int value = 1 ;

};

unsigned int i = Silnia < 0 >:: value ; //przykład użycia, równoważne i = 1

i = Silnia < 5 >:: value ; //równoważne i = 120

Listing 2. Metaprogram, który pozwala używać stałych zapisanych binarnie

template < unsigned long n > struct Binary { //stałe binarne

static const unsigned long value = Binary < n / 10 >:: value << 1 — n % 10 ;

};

template <> struct Binary < 0 > { //stop dla rekurencji

static const unsigned long value = 0 ;

};

//przykład użycia

const int FLAGS = Binary < 1100 >:: value ; //zamiast 12 lub 0xC

więc dostarczając szablon, można obliczać ją

z założoną precyzją; patrz Listing 5.

Kod tworzony przez metaprogramy często

wykorzystuje się w bibliotekach numerycz-

nych, na przykład do mnożenia czy odwraca-

nia macierzy. Obliczenia wykonywane w czasie

kompilacji dostarczają stałych lub funkcji, które

możemy obliczyć lub wyprowadzić za pomocą

innych narzędzi (na przykład ręcznie), a następ-

nie umieścić je w programie. Stosowanie meta-

programów zwiększa elastyczność dostarcza-

nych rozwiązań oraz zmniejsza ryzyko popeł-

nienia pomyłki, jest też bardziej czytelne, po-

nieważ nazwa szablonu zawiera informacje o

znaczeniu.

Listing 3. Metaprogram dostarczający funkcji do potęgowania (wykładnik całkowity dodatni)

template < unsigned n > inline double Power ( double x ) {

return x * Power < n - 1 > ( x ); //rekurencyjna deinicja funkcji

}

template <> inline double Power < 0 > ( double x ) {

return 1.0 ; //specjalizacja kończy rekurencję

}

Listing 4. Szablon generuje wyrażenie obliczające potęgę o wykładniku całkowitym

template < unsigned n > double Pow ( double x ) {

return Pow < 2 > ( Pow < n / 2 > ( x ) ) * Pow < n % 2 > ( x );

}

//specjalizacje dla kwadratu i innych warunków brzegowych

template <> double Pow < 2 > ( double x ) { return x * x ;}

template <> double Pow < 1 > ( double x ) { return x ;}

template <> double int_power < 0 > ( double x ) { return 1.0 ;}

Kolekcje typów

Metaprogramy, których argumentami są ty-

py, pozwalają wyrażać pojęcia trudne do opisu

innymi technikami, na przykład pozwala wy-

konywać podobne operacje na grupie wskaza-

nych typów. W takich przypadkach wykorzy-

stujemy kolekcje typów, które można utwo-

rzyć za pomocą szablonów. Przykład takiej ko-

lekcji, przechowującej typy w liście jednokie-

runkowej (propozycja opisana w książce An-

dreia Alexandrescu Nowoczesne projektowanie

w C++ ), pokazuje Listing 6.

Poszczególne elementy listy przechowu-

ją dowolne typy, natomiast ostatni element

Listing 5. Szablon generuje wyrażenie obliczające wartość funkcji wykładniczej z założoną

precyzją

template < unsigned int N > inline double Exp ( double x ) {

//wykorzystuje szablony z Listingu 1 oraz Listingu 4

return Exp < N - 1 > ( x ) + Pow < N > ( x ) / Silnia < N >:: value ;

}

template <> inline double Exp < 0 > ( double x ) {

return 1.0 ;

}

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<typename T> 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.

www.sdjournal.org

Programowanie C++

jest zawsze typu NullType (lista z wartow-

nikiem). Za pomocą tak zdefiniowanej li-

sty możemy utworzyć kolekcję typów o do-

wolnej długości, na Listingu 6 pokazano li-

stę przechowującą trzy typy: short , int oraz

long . Listing 7 pokazuje operację obliczania

długości kolekcji (liczba elementów listy).

du na konieczność rekurencyjnego zagłębiania

tych szablonów. Biblioteka boost::mpl dostar-

cza kolekcji typów oraz operacji, zwalnia ona

programistę z konieczności implementacji wła-

snych rozwiązań. Kolekcje typów dostarczane

przez tę bibliotekę mają interfejs zbliżony do ze-

stawu metod oferowanych przez kolekcje z bi-

blioteki standardowej, ponadto biblioteka do-

starcza zbiór przydatnych metafunkcji, pozwa-

lając unikać zapisów rekurencyjnych. Kolekcje

typów to szablony: mpl::vector , mpl::list ,

mpl::set oraz mpl::map , każdy z nich pozwa-

la przechowywać dowolną liczbę typów, różnią

się one pewnymi właściwościami, na przykład

mpl::set usuwa kolejne wystąpienia tego sa-

mego typu w kolekcji. Najczęściej używa się ko-

lekcji mpl::vector , natomiast pozostałe wyko-

rzystuje się wtedy, gdy odpowiednie właściwo-

ści okażą się przydatne. Dostarczane są operacje

modyfikacji tych kolekcji, to znaczy dodawania

i usuwania elementów, badania właściwości ko-

lekcji, badania występowania danego typu, sto-

sowania pewnej operacji dla każdego z typów w

kolekcji, tworzenie nowych typów na podsta-

wie typów przechowywanych w kolekcji. Przy-

kład użycia kolekcji został pokazany na Listin-

gu 8. Każda z operacji zakłada, że wynik, któ-

ry jest typem, jest składową type , natomiast wy-

nik, który jest wartością jest dostępny jako skła-

dowa type::value . Oczywiście algorytmy wy-

konują się w czasie kompilacji.

Algorytm mpl::for_each jest nietypowy, wo-

ła on dostarczoną funkcję lub dostarczony funk-

tor (obiekt klasy, która dostarcza operatora wo-

łania funkcyjnego) dla każdego typu, który jest

przechowywany w kolekcji. Specyfika tego al-

gorytmu polega na tym, że tworzy on kod, któ-

ry jest wykonywany w czasie działania, patrz Li-

sting 9, gdzie pokazano rozwiązanie (a raczej

szkic rozwiązania), które wykorzystuje bibliote-

kę mpl do rejestracji klas w fabryce obiektów.

Biblioteka mpl jest używana przez wiele in-

nych bibliotek dostarczanych przez boost, na

przykład przez biblioteki tworzące obiekty funk-

cyjne bind , bibliotekę dostarczającą variant

(obiekt, który przechowuje jedną z wybranych

wartości, podobnie jak union w C) czy bibliote-

kę spirit , służącą do generowania gramatyk.

boost

metaprogramming library (MPL)

Tworzenie listy typów za pomocą szablonu

TList jest niewygodne i nieczytelne, ze wzglę-

Listing 6. Kolekcja typów zdeiniowana rekurencyjnie

template < class H , class T > struct TList { // lista rekurencyjna

typedef H Head ;

typedef T Tail ;

};

struct NullType { }; //typ kończący listę

//przykładowa kolekcja typów

typedef TList < short , TList < int , TList < long , NullType > > > Integers ;

Listing 7. Badanie długości listy typów

template < class TList > struct Size {

static const int value = Size < typename TList :: Tail >:: value + 1 ;

};

template <> struct Size < NullType > {

static const int value = 0 ;

};

Listing 8. Przykład operacji na kontenerach z biblioteki mpl

typedef mpl :: vector < int , char , long , int > Types ; // przykładowa kolekcja

typedef mpl :: push_back < Types , int >:: type NewTypes ; // modyikacja

cout << mpl :: size < NewTypes >:: type :: value ; // wydrukuje wartość 5

//algorytm count zlicza wystąpienia danego typu w kolekcji

cout << mpl :: count < Types , int >:: type :: value ; //drukuje liczbę 2

Podsumowanie

Metaprogramowanie umożliwia przetwarza-

nie informacji podczas kompilacji. Techniki

te pozwalają zmniejszać rozmiar kodu, zwięk-

szając jego czytelność, oraz sprawiać, że progra-

my wykonują się szybciej. Metaprogramowa-

nie znalazło wiele zastosowań zwłaszcza przy

tworzeniu ogólnych, przenośnych i efektyw-

nych rozwiązań. Zostanie ono wsparte w no-

wej wersji standardu C++0x.

Listing 9. Przykład wykorzystania algorytmu for_each z biblioteki mpl

//mamy hierarchię klas, gdzie klasą bazową jest Figure

class Square : public Figure { //przykładowa klasa konkretna

public :

//klasa konkretna dostarcza metodę statyczną create

static Figure * create () { return new Square ; }

static int id_ ; //klasa konkretna przechowuje identyikator

};

struct Factory { //fabryka igur konkretnych, przedstawiony kod bardzo uproszczony

public :

typedef Figure * ( * CreateFig )(); //typ funkcji tworzącej obiekty

static Factory & getInstance (); //dostęp do obiektu fabryki

int registerFig ( CreateFig fun ); //metoda rejestracji, dostarcza funkcję

tworzącą obiekt, zwraca id

W Sieci

• http://www.boost.org – dokumentacja

bibliotek boost;

• http://www.open-std.org – dokumen-

ty opisujące nowy standard C++.

};

struct RegisterFigure { //szablon użyty do rejestracji

template < typename T > void operator ()( T ){

T :: id_ = Factory :: getInstance (). registerFig ( T :: create );

}

};

typedef mpl :: vector < Square , Circle , Rectangle > Types ; // kolekcja typów dla klas

konkretnych

mpl :: for \ _each < Types > ( RegisterFigure ()); //woła w czasie wykonania operację dla

każdego typu

ROBERT NOWAK

Adiunkt w Zakładzie Sztucznej Inteligencji Instytu-

tu Systemów Elektronicznych Politechniki Warszaw-

skiej, zainteresowany tworzeniem aplikacji dla biolo-

gii i medycyny, programuje w C++ od ponad 10 lat.

Kontakt z autorem:rno@o2.pl

12/2009

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: