Meta-programare cu template-uri

Cosmin Negruseri
19 august 2008

Radu Berinde, care vara asta face un internship la VMware, va scrie un guest post despre programarea templateurilor in C++. Despre Radu am mai vorbit aici si aici .

Am inceput sa citesc o carte interesanta - "Modern C++ Design", numita si "the crack book" din motive ce devin evidente inca de prin capitolul 2. Intamplator, e scrisa chiar de un roman, Andrei Alexandrescu, care e unul dintre cei mai mari experti pe C++ din lume. Cartea arata cum se pot face lucruri foarte interesante si/sau ciudate cu template-uri. Mi-am amintit de ceva ce am auzit acum mult timp: despre cineva care facuse un program C++ care nu compila, dar mesajele de eroare aratau numerele prime. Mi se parea ceva de-a dreptul bolnav, insa - comparativ cu ce se intampla prin cartea mentionata - acum pare trivial un astfel de program. Si de fapt chiar este destul de simplu, asa ca m-am gandit sa fac un mic "tutorial" in care sa explic cum se face.

Principiul de baza

Poate stiti ca in STL exista o implementare generala pentru vector, insa exista si o implementare speciala numai pentru vector<bool>, care foloseste doar cate un bit pentru fiecare valoare. Idioma C++ care permite asa ceva este "template specialization" si este un mecanism foarte puternic (mult mai puternic decat vom vedea aici). Practic, compilatorul are mai multe definitii din care alege una anume. Folosind acest lucru putem sa "trucam" compilatorul in a face un "if".

De exemplu, sa zicem ca vrem sa facem o asertie la timpul compilarii. Avem o expresie statica (care poate fi calculata la compilare) si vrem sa primim o eroare daca aceasta expresie nu se evalueaza la true. Putem sa folosim aceasta idee de template specialization:

template<bool> struct CompileTimeError {};
template<> struct CompileTimeError<true> { enum { Cool = 1 }; };

Am definit un tip CompileTimeError care in general este gol. Insa daca parametrul bool se intampla sa fie true, compilatorul foloseste definitia specializata a tipului. Daca avem o expresie expr, sa ne gandim la urmatoarea expresie:

CompileTimeError<expr>::Cool

Daca expr = true, s-ar evalua la 1. Insa daca este false, vom avea o eroare de compilare - definitia generala nu include identificatorul Cool. Am reusit sa facem compilatorul sa evalueze doua lucruri diferite in functie de o expresie - un "if" daca vreti.

Recursivitate

Pentru ca tipurile sunt prin definitie imutabile, nu vom putea face compilatorul sa ruleze algoritmi iterativi - nu avem cum sa il facem sa mentina o stare. Va trebui sa convertim orice lucru iterativ in ceva recursiv, cum am face la un limbaj functional (in stil lisp). Cum determinam daca un numar este prim fara sa mentinem stare? Putem sa definim o "functie" HasDivisors cu doi parametri, N si K. HasDivisors returneaza true daca vreun numar intre 2 si K il divide pe N. Astfel, un numar este prim daca HasDivisors este true pentru parametrii N si N-1. Putem implementa aceasta idee cu template-uri:

template <int N, int K>
struct HasDivisors
{
    enum { Result = (N % K == 0) || HasDivisors<N, K-1>::Result };
};

template <int N>
struct HasDivisors<N, 1>
{
    enum { Result = 0 };
};

template <int N>
struct IsPrime
{
    enum { Result = !HasDivisors<N, N-1>::Result };
};

Observam recursivitatea din HasDivisors; conditia de oprire este implementata prin specializarea partiala HasDivisors<$N$, 1>

Putem combina acestea cu definitiile de mai sus pentru a genera erori pentru numerele prime:

template <int N>
struct PrimeErrors
{
    enum { Result = CompileTimeError<!IsPrime<N>::Result>::Cool +
                      PrimeErrors<N-1>::Result };
};

template <>
struct PrimeErrors<1>
{
    enum { Result = 0 };
};

Prima parte a expresiei din PrimeErrors este doar o asertie la timpul compilarii. Operatia de adunare e folosita doar pentru recursivitate. Din nou, specializarea ne da voie sa definim conditia de oprire a recursivitatii. In final nu mai avem nevoie decat de o instructiune care sa faca compilatorul sa evalueze PrimeErrors:

PrimeErrors<100>::Result x;

Daca compilam acest program, vom primi erori ca mai jos (am taiat din liniile repetitive):

templates.cpp: In instantiation of 'PrimeErrors<2>':
templates.cpp:25:   instantiated from 'PrimeErrors<3>'
templates.cpp:25:   instantiated from 'PrimeErrors<4>'
templates.cpp:25:   instantiated from 'PrimeErrors<5>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'
templates.cpp: In instantiation of 'PrimeErrors<3>':
templates.cpp:25:   instantiated from 'PrimeErrors<4>'
templates.cpp:25:   instantiated from 'PrimeErrors<5>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'
templates.cpp: In instantiation of 'PrimeErrors<5>':
templates.cpp:25:   instantiated from 'PrimeErrors<6>'
templates.cpp:25:   instantiated from 'PrimeErrors<7>'
...
templates.cpp:34:   instantiated from here
templates.cpp:25: error: 'Cool' is not a member of
'CompileTimeError<false>'

Daca filtram doar liniile cu In instantiation of ..., vedem frumos rezultatul dorit:

root@slack ~# gcc templates.cpp 2>&1 | grep "In in" 
templates.cpp: In instantiation of 'PrimeErrors<2>':
templates.cpp: In instantiation of 'PrimeErrors<3>':
templates.cpp: In instantiation of 'PrimeErrors<5>':
templates.cpp: In instantiation of 'PrimeErrors<7>':
templates.cpp: In instantiation of 'PrimeErrors<11>':
templates.cpp: In instantiation of 'PrimeErrors<13>':
templates.cpp: In instantiation of 'PrimeErrors<17>':
templates.cpp: In instantiation of 'PrimeErrors<19>':
templates.cpp: In instantiation of 'PrimeErrors<23>':
templates.cpp: In instantiation of 'PrimeErrors<29>':
templates.cpp: In instantiation of 'PrimeErrors<31>':
templates.cpp: In instantiation of 'PrimeErrors<37>':
templates.cpp: In instantiation of 'PrimeErrors<41>':
templates.cpp: In instantiation of 'PrimeErrors<43>':
templates.cpp: In instantiation of 'PrimeErrors<47>':
templates.cpp: In instantiation of 'PrimeErrors<53>':
templates.cpp: In instantiation of 'PrimeErrors<59>':
templates.cpp: In instantiation of 'PrimeErrors<61>':
templates.cpp: In instantiation of 'PrimeErrors<67>':
templates.cpp: In instantiation of 'PrimeErrors<71>':
templates.cpp: In instantiation of 'PrimeErrors<73>':
templates.cpp: In instantiation of 'PrimeErrors<79>':
templates.cpp: In instantiation of 'PrimeErrors<83>':
templates.cpp: In instantiation of 'PrimeErrors<89>':
templates.cpp: In instantiation of 'PrimeErrors<97>':

Dragut, nu?