Metaprogramação em C++

Introdução

Toda a gente que conhece minimamente a linguagem C++ já ouviu falar em templates. O conceito inovador de template foi oficialmente introduzido no standard de implementação em 1998 e trouxe uma lufada de ar fresco, tanto ao C++, como a um número de outras linguagens mais recentes (por exemplo, também linguagens como o Java ou C# foram enriquecidas com as suas próprias técnicas de programação genérica). Neste artigo, iremos rever os templates, bem como as suas propriedades, e explorar algumas das possibilidades raramente consideradas com templates.

O que são e o que fazem templates

O verdadeiro potencial dos templates é que nem sempre foi evidente. Mas isso mudou com o tempo. Em primeiro lugar, vejamos com o próximo exemplo, uma utilização clássica de templates, com base nas suas capacidades de parametrização.

template<class T>
T max(const T &a, const T &b)
{ return a > b ? a : b; }
 
template<class T>
T sqr(const T &a)
{ return a*a; }
 
...
 
int n = 2, m = 5;
max<int>(n,m);   // Devolve 5
 
double x = 0.67, y = 2.71828;
max(x,y);        // Devolve 2.71828
 
int r = 12;
sqr(r);          // Devolve 144

O que está em cima são dois típicos exemplos de livro teórico de templates de funções e respectivas instanciações. Essencialmente, o que um template faz é permitir escrever uma função de forma parametrizada, isto é, antes de saber de que tipo são as variáveis envolvidas. Isto é bastante útil no sentido em que de uma só vez se garantiu a implementação das funções max e sqr para qualquer tipo de variável (a variável genérica T). É de salientar outra característica importante dos templates: o seu mecanismo de instanciação. Um template de uma função não é uma função, mas um protótipo. Isto é, o compilador verifica a sintaxe, mas ignora a validade lógica de um template. Isto até que o template seja chamado no código. Por exemplo, a função max não existe em parte alguma do código antes de ser instanciada ao chamarmos max<int>. E novamente, ao chamarmos max<double>. Ou seja, o compilador tomou o protótipo da função max e de cada vez que o programador pediu uma nova forma da função, utilizou-o para criar uma nova função max em overload. Como devem ter reparado, podemos chamar max<double> sem especificar o tipo double, porque o compilador é capaz de deduzir que versão do template deve ser usada a partir dos argumentos da função. Apenas exigimos para esta função que ambos os argumentos sejam do mesmo tipo T.

Para além de templates de funções, existem templates de classes. E, similarmente, cumprem a mesma tarefa que os templates de funções: permitem declarar uma classe de forma genérica. A classe genérica Sequencia implementada neste exemplo revela a sintaxe a que poderíamos recorrer para parametrizar uma classe em função do tipo de variável do conteúdo.

template<class T = double>
class Sequencia
{
  private:
    long quant;
    T *p;
  public:
    Sequencia(const long n = 10)
    { quant = n; p = new T[n]; }
    virtual ~Sequencia()
    { delete[] p; }
};
 
...
 
Sequencia<double> s1;
Sequencia<unsigned long> s2;
 
Sequencia s3;   // Instanciação automática a double
 
Sequencia<Sequencia> s4;  // possível

O que este template de classe tem de interessante é o valor automático para o tipo. Isto quer dizer que se omitirmos o parâmetro de tipo na declaração do template, o compilador seguirá a indicação dada de que por omissão, o conteúdo é do tipo double. Outro pormenor interessante é que até é possível criar um objecto Sequencia de objectos Sequencia. Tal é a flexibilidade dos templates.

Propriedades dos templates

Até agora, não temos visto nada de especial, a não ser uma funcionalidade que até pode vir a dar jeito para certos tipos de funções e estruturas. É agora altura de reflectir sobre as propriedades dos templates:

  • Aceitam como parâmetros tipos genéricos (class ou typename), apontadores para funções, ou constantes literais inteiras ou booleanas (ou seja, desde que o valor seja conhecido aquando da compilação).
  • Ao serem instanciados, os parâmetros-tipo são verificados contra o código utilizado.
  • Podem utilizar qualquer número de parâmetros, e estes podem ser deduzidos.
  • Podem ser instanciados recursivamente.

Estas propriedades são muito interessantes. Na prática, um mecanismo de instanciação que permite utilizar valores inteiros, e ainda para mais, recursivamente, é o mesmo que uma linguagem de programação em si. Este resultado abre portas a uma infinidade de possibilidades: o mecanismo de instanciação dos templates é funcionalmente similar a uma máquina de Turing. Por outras palavras, os templates podem levar um compilador de C++ a comportar-se como um interpretador! Isto demonstrar-se-á na próxima secção.

Um primeiro metaprograma

Sabendo agora que um template também aceita inteiros (atenção, constantes literais) como parâmetro, e sabendo da sua recursividade, vamos experimentar um pouco o conceito de metaprogramação fazendo o compilador calcular o factorial de um número.

template<int N>
class Factorial
{
  public:
    static inline int valor()
    { return N*Factorial<N-1>::valor(); }
};
 
// Isto é uma especialização:
template<>
class Factorial<1>
{
  public:
    static inline int valor()
    { return 1; }
};
 
...
 
Factorial<6>::valor();
// Devolve 6! (ou seja, 720)

O aspecto interessante neste exemplo é que uma vez compilado o código, o método estático Factorial<6>::valor() não faz qualquer chamada a funções, e limita-se a devolver a constante 720. O compilador instanciou 6 classes Factorial<N>, uma para cada valor de N. Cada classe forçou o compilador a criar a classe de ordem inferior, decrementando o N sucessivamente até à última especialização Factorial<1>. Durante a compilação, os valores N, N-1, … , 1 são sucessivamente multiplicados dando finalmente origem ao valor 720 como uma constante literal. O factorial é calculado durante a compilação.

Aplicações de templates

Sejamos sinceros, por muito engraçado que seja coagir o compilador a calcular um factorial ou a gerar números primos, é óbvio que fazê-lo no compilador não tem grande utilidade prática. Nesse caso, perguntar-se-ão muitos, para que mais servirão templates, afinal? Como é possível prever no exemplo dado anteriormente, um template de uma classe ou estrutura pode ser tratado como um programa que gera código durante a compilação. Através da especialização, é por exemplo possível criar classes cuja implementação depende da plataforma ou de um parâmetro do sistema, de uma forma mais elegante que utilizando macros: ao invés de se limitarem a fazer substituição de texto, os templates passam argumentos e verificam os tipos.

template<typename T, bool Windows_Vista>
class AMinhaClasse
{
  private:
    T _idAlgumaCoisa
  public:
    ...
};
 
// As especializações verificam a versão:
template<typename T>
class AMinhaClasse<T,true>
{
  private:
    T _idAlgumaCoisa
  public:
    const bool Especifico()
    {
      // Código específico para Vista...
      // ... ou 7, claro ;)
    }
};
 
template<typename T>
class AMinhaClasse<T,false>
{
  private:
    T _idAlgumaCoisa
  public:
    const bool Especifico()
    {
      // Código genérico para XP...
    }
};
 
...
 
// Em qualquer versão de Windows:
const bool is_vista = 	(VERSAO_WIN >= 6);
// Isto compila sse is_vista é constante!
AMinhaClasse amc<long,is_vista>;
amc.Especifico();

Olhando para este pedaço de código, que é possível obter o mesmo comportamento com macros de #if, podemo-nos perguntar quanto à sua relevância. Ora bem, a verdade é a instanciação de AMinhaClasse até “consultou” uma macro para saber que especialização usar… mas por outro lado, a parametrização em T certifica-se de que a classe não será compilada no executável a não ser que seja utilizada, e simultaneamente, quando esta for compilada, a implementação propícia ao sistema será escolhida. Mas pensemos ainda em melhores exemplos do uso de parâmetros que não são tipos: e se eu tivesse por exemplo em mente uma classe de buffer genérico, que faz conversão automática, em função do tamanho do tipo de variável que recebe? Poderíamos por exemplo, ter uma classe que utiliza uma sintaxe semelhante a algo como OMeuBuffer<char,sizeof(double)>.

A propósito deste último exemplo, esta técnica, de tornar classes transparentes aos tipos utilizados tem um nome: traits. Normalmente, uma trait envolve uma conversão ou um typedef para tornar o código do programador de uma classe completamente agnóstico dos tipos utilizados e devolvidos. Outro conceito útil de metaprogramação é o de policies. Similarmente a uma trait, uma policy filtra o código em função dos tipos utilizados, mas neste caso, faz uma decisão de que algoritmo usar. Imaginemos o exemplo seguinte que refina a nossa anterior classe Sequencia com uma policy:

template<typename T, bool Is_Small=true>
struct EscolheAlgoritmo
{
    static void sort(T *p)
    {
       ... // Fazer um InsertionSort
    }
};
 
template<typename T>
struct EscolheAlgoritmo<T,false>
{
    static void sort(T *p)
    {
       ... // Fazer um QuickSort
    }
};
 
template<int N, class T = double>
class OutraSequencia
{
private:
  T *dados;
  ...
public:
  void sort()
  {
    EscolheAlgoritmo<T,(N<20)>::sort(dados);
  }
  ...
};
 
...
 
// Depois, é uma questão de usar com:
OutraSequencia a<15,double>;
OutraSequencia b<30,char>;
a.sort(); // Faz um InsertionSort
b.sort(); // Faz um QuickSort

Note-se que, se só se tivesse utilizado a primeira ou a segunda instância de OutraSequencia, um dos algoritmos teria sido excluído da própria compilação. Neste caso, o interessante é ver como uma classe se pode assim adaptar a diversas condições, sem interferir no código do programador. É claro que é fácil imaginar exemplos muito melhores, como por exemplo, aplicações em singletons, mas a ideia é tornar claro como os templates são uma valiosa ferramenta para construir bibliotecas, da qual é um bom exemplo a Standard Template Library. Algumas aplicações avançadas de templates fazem parte da implementação de apontadores inteligentes (tradicionalmente, este tipo de classe tem uma designação com o sufixo _ptr). Apontadores inteligentes são apontadores que fazem a sua própria gestão de memória, e como tal, utilizam combinações de traits e policies para determinar o seu comportamento em determinadas situações. Desta forma, ajudam a impedir bastantes erros subtis no código. Utilizando templates, há diferentes tipos de ponteiros inteligentes: alguns proíbem a cópia, outros incluem técnicas de reference counting. Os apontadores podem ser origem de muitas dores de cabeça, e toda a ajuda é pouca!

Uma grande porção das aplicações de templates cai na área da computação numérica. Em cálculo numérico, os templates ajudam a reduzir redundâncias de código, minimizando chamadas a métodos virtuais e removendo ambiguidades (através do célebre Barton-Nackman trick, em que uma classe base é recursivamente parametrizada em função das derivadas). No que diz respeito a cálculo, o exemplo mais interessante, contudo, são os templates de expressões. Estes requerem alguma prática e envolvem alguma complexidade. Como tal, é mais razoável dar apenas um curto exemplo do que templates de expressões fazem sem entrar em detalhes, antes de concluir esta discussão.

Imaginemos, portanto, uma típica classe de vector, e um operator+ global que soma dois objectos da mesma classe usando um ciclo for.

template<typename T>
class Vector
{
   ...
};
 
template<typename T>
const Vector<T>& operator+
  (const Vector<T> &a,
   const Vector<T> &b)
{
  const int s = a.size();
  Vector temp(s);
  for(int i = 0; i < s; ++i)
    a[i] + b[i];
  return temp;
}
 
...
 
Vector<double> a,b,c,d;
...
d = a + b + c;  // usando o operador
...
for(int i = 0; i < d.size(); ++i)   // metodo “a la C”
  d[i] = a[i] + b[i] + c[i];

O que se passa com este código é que, enquanto o operador torna a sintaxe agradável ao programador, esta operação é extremamente ineficiente! A primeira alternativa corre pelo menos três ciclos for e cria pelo menos dois vectores temporários. Torna-se preferível escrever o ciclo explicitamente! Ou seja, seria interessante convencer o compilador a gerar um único ciclo for, com um único vector temporário na pior das hipóteses, independentemente do número de termos somados. Vejamos esta solução através da aplicação de templates…

template<typename T>
class Vector
{
  private:
    T *_ptr;
    int _num;    
  public:
  ...
    template<typename Expr>
    const Vector& operator= (const Expressao<T,Expr> &expr)
    {
      for(int i = 0; i < _num; ++i) // ciclo de acesso indirecto
        _ptr[i] = expr[i]; 
    } 
};
 
...
 
template<typename T, typename Expr>
class Expressao
{ 
  private: 
    Expr e;
  public:
    inline const T& operator[](int i) // Membro acedido a partir de Vector
    { return e[i]; }
};
 
template<typename T, typename OpEsq, typename OpDir> // Os operandos estão parametrizados
class Adicao
{
  private:
    OpEsq esq;
    OpDir dir;
  public:
    inline const T& operator[](int i)
    { return esq[i]+dir[i]; }
};
 
...
 
Vector<double> a,b,c,d;
...
d = a + b + c;  // Um único ciclo

Lendo de baixo para cima, podemos ver que o compilador começa a interpretar a expressão pela esquerda devido à igual precedência. O desenrolar iterativo à medida que os templates são instanciados é ilustrado na figura seguinte.

Metaprogramação em C++: templates

d é afectado por um objecto Expressao, consistindo de um objecto Adicao. Este objecto Adicao, por sua vez, é instanciado com um operando Vector a e com outro objecto Adicao (que representa a soma b+c). Se lermos a definição de Adicao, vemos que tem um operator[], tal como supomos que Vector tem. A soma é resolvida em três passagens de referência: o compilador passa o acesso aos elementos das Vectors ao objecto Expressao (através do seu próprio operator[]). Finalmente, o operator= passa o resultado a d. Deste modo, a soma foi efectuada dentro de um único ciclo for. Obviamente, o processo cria objectos intermédios de classes auxiliares para passar as referências aos elementos dos vectores, mas permite efectuar de forma eficiente uma soma num vector longo, e tudo isto sem sacrificar o conforto de uma sintaxe intuitiva. Esta técnica de implementação de objectos eficientes para computação numérica foi inventada independentemente por Todd Veldhuizen e Daveed Vandevoorde.

Conclusões

Ficou muita coisa por explorar, mas com certeza a ideia das interessantes aplicações de templates no desenho de bibliotecas ficou patente através dos exemplos dados. Os templates de C++ têm uma capacidade impressionante de permitir polimorfismo estático, determinado aquando da compilação, ao ponto de permitir liberdades extremas de compilação condicional. Também permitem construir autênticos idiomas alternativos da linguagem, e tudo isto com um impacto mínimo na eficiência no código compilado. Infelizmente, actualmente este poder sobre a linguagem vem com um custo associado em termos de complexidade, levando a complexidades extremas só para permitir definições intuitivas que tornem classes parametrizadas úteis. Argumentativamente, esta dificuldade só é sentida por quem desenha as bibliotecas para benefício dos programadores que as utilizam, mas erros de compilação difíceis de ler, que se obtêm quando se usam determinados parâmetros em erro, nunca ajudaram ninguém. Obviamente, há soluções que estão a ser implementadas para melhorar esta situação (inclusivamente tornando alguns dos truques aqui mencionados obsoletos), mas isso será abordado num futuro artigo sobre a nova especificação de C++: o C++0x.

Bibliografia

  • Ulrich W. Eisenecker: Generative Programming: Methods, Tools, and Applications, Addison-Wesley
  • David Vandervoorde, Nicolai M. Josuttis: C++ Templates: The Complete Guide, Addison-Wesley
  • http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.html
  • Todd Veldhuizen: Using C++ template metaprograms, C++ Report, Vol. 7, No. 4 (May 1995), pp. 36-43
  • John J. Barton, Lee R. Nackman: Scientific and Engineering C++: An Introduction with Advanced Techniques and Examples, Addison-Wesley

Publicado na edição 20 (PDF) da Revista PROGRAMAR.