Metaprogramação de modelo - Template metaprogramming

Paradigmas de programação

A metaprogramação de modelo ( TMP ) é uma técnica de metaprogramação na qual modelos são usados ​​por um compilador para gerar código-fonte temporário , que é mesclado pelo compilador com o resto do código-fonte e então compilado. A saída desses modelos pode incluir constantes de tempo de compilação , estruturas de dados e funções completas . O uso de modelos pode ser considerado um polimorfismo de tempo de compilação . A técnica é usada por várias linguagens, sendo a mais conhecida C ++ , mas também Curl , D , Nim e XL .

A metaprogramação de template foi, em certo sentido, descoberta acidentalmente.

Algumas outras linguagens suportam recursos de tempo de compilação semelhantes, senão mais poderosos (como macros Lisp ), mas esses estão fora do escopo deste artigo.

Componentes de metaprogramação de template

O uso de modelos como uma técnica de metaprogramação requer duas operações distintas: um modelo deve ser definido e um modelo definido deve ser instanciado . A definição do modelo descreve a forma genérica do código-fonte gerado e a instanciação faz com que um conjunto específico de código-fonte seja gerado a partir da forma genérica no modelo.

A metaprogramação de modelo é Turing-completa , o que significa que qualquer cálculo expressável por um programa de computador pode ser computado, de alguma forma, por um metaprograma de modelo.

Os modelos são diferentes das macros . Uma macro é um pedaço de código que executa em tempo de compilação e executa a manipulação textual do código a ser compilado (por exemplo, macros C ++ ) ou manipula a árvore de sintaxe abstrata sendo produzida pelo compilador (por exemplo, macros Rust ou Lisp ). As macros textuais são notavelmente mais independentes da sintaxe da linguagem que está sendo manipulada, pois elas meramente alteram o texto na memória do código-fonte logo antes da compilação.

Os metaprogramas de modelo não têm variáveis ​​mutáveis - ou seja, nenhuma variável pode alterar o valor depois de inicializada, portanto, a metaprogramação de modelo pode ser vista como uma forma de programação funcional . Na verdade, muitas implementações de modelo implementam controle de fluxo apenas por meio de recursão , como visto no exemplo abaixo.

Usando template de metaprogramação

Embora a sintaxe da metaprogramação de template seja geralmente muito diferente da linguagem de programação com a qual é usada, ela tem usos práticos. Algumas razões comuns para usar modelos são para implementar programação genérica (evitando seções de código que são semelhantes, exceto para algumas variações menores) ou para realizar a otimização de tempo de compilação automática, como fazer algo uma vez em tempo de compilação, em vez de cada vez que o programa é executado - por exemplo, fazendo com que o compilador desenrole loops para eliminar saltos e decréscimos na contagem de loops sempre que o programa for executado.

Geração de classe de tempo de compilação

O que exatamente "programação em tempo de compilação" significa pode ser ilustrado com um exemplo de função fatorial, que em C ++ não-template pode ser escrita usando recursão da seguinte maneira: 

unsigned factorial(unsigned n) {
	return n == 0 ? 1 : n * factorial(n - 1); 
}

// Usage examples:
// factorial(0) would yield 1;
// factorial(4) would yield 24.

O código acima será executado em tempo de execução para determinar o valor fatorial dos literais 0 e 4. Usando a metaprogramação de modelo e a especialização de modelo para fornecer a condição final para a recursão, os fatoriais usados ​​no programa - ignorando qualquer fatorial não usado - podem ser calculado em tempo de compilação por este código: 

template <unsigned N>
struct factorial {
	static constexpr unsigned value = N * factorial<N - 1>::value;
};

template <>
struct factorial<0> {
	static constexpr unsigned value = 1;
};

// Usage examples:
// factorial<0>::value would yield 1;
// factorial<4>::value would yield 24.

O código acima calcula o valor fatorial dos literais 0 e 4 em tempo de compilação e usa os resultados como se fossem constantes pré-calculadas. Para poder usar os modelos desta maneira, o compilador deve saber o valor de seus parâmetros em tempo de compilação, o que tem a pré-condição natural de que o valor fatorial <X> :: só pode ser usado se X for conhecido em tempo de compilação. Em outras palavras, X deve ser um literal constante ou uma expressão constante.

Em C ++ 11 e C ++ 20 , constexpr e consteval foram introduzidos para permitir que o compilador execute código. Usando constexpr e consteval, pode-se usar a definição fatorial recursiva usual com a sintaxe não modelada.

Otimização do código em tempo de compilação

Veja também: Execução da função de tempo de compilação

O exemplo fatorial acima é um exemplo de otimização de código em tempo de compilação em que todos os fatoriais usados ​​pelo programa são pré-compilados e injetados como constantes numéricas na compilação, economizando sobrecarga de tempo de execução e espaço de memória. É, no entanto, uma otimização relativamente pequena.

Como outro exemplo mais significativo de desdobramento de loop em tempo de compilação , a metaprogramação de template pode ser usada para criar classes de vetor de comprimento n (onde n é conhecido em tempo de compilação). O benefício sobre um vetor length- n mais tradicional é que os loops podem ser desenrolados, resultando em um código muito otimizado. Como exemplo, considere o operador de adição. Uma adição de vetor de comprimento n pode ser escrita como 

template <int length>
Vector<length>& Vector<length>::operator+=(const Vector<length>& rhs) 
{
    for (int i = 0; i < length; ++i)
        value[i] += rhs.value[i];
    return *this;
}

Quando o compilador instancia o modelo de função definido acima, o seguinte código pode ser produzido: 

template <>
Vector<2>& Vector<2>::operator+=(const Vector<2>& rhs) 
{
    value[0] += rhs.value[0];
    value[1] += rhs.value[1];
    return *this;
}

O otimizador do compilador deve ser capaz de desenrolar o forloop porque o parâmetro do modelo lengthé uma constante em tempo de compilação.

No entanto, tome cuidado e tenha cuidado, pois isso pode causar inchaço do código, uma vez que um código separado desenrolado será gerado para cada 'N' (tamanho do vetor) com o qual você instanciar.

Polimorfismo estático

O polimorfismo é um recurso de programação padrão comum onde os objetos derivados podem ser usados ​​como instâncias de seu objeto base, mas onde os métodos dos objetos derivados serão chamados, como neste código 

class Base
{
public:
    virtual void method() { std::cout << "Base"; }
    virtual ~Base() {}
};

class Derived : public Base
{
public:
    virtual void method() { std::cout << "Derived"; }
};

int main()
{
    Base *pBase = new Derived;
    pBase->method(); //outputs "Derived"
    delete pBase;
    return 0;
}

onde todas as invocações de virtualmétodos serão aquelas da classe mais derivada. Esse comportamento dinamicamente polimórfico é (normalmente) obtido pela criação de tabelas de consulta virtuais para classes com métodos virtuais, tabelas que são percorridas em tempo de execução para identificar o método a ser chamado. Assim, o polimorfismo de tempo de execução necessariamente acarreta sobrecarga de execução (embora em arquiteturas modernas a sobrecarga seja pequena).

No entanto, em muitos casos, o comportamento polimórfico necessário é invariável e pode ser determinado em tempo de compilação. Em seguida, o Curiously Recurring Template Pattern (CRTP) pode ser usado para atingir o polimorfismo estático , que é uma imitação do polimorfismo no código de programação, mas que é resolvido no tempo de compilação e, portanto, elimina as pesquisas de tabela virtual em tempo de execução. Por exemplo: 

template <class Derived>
struct base
{
    void interface()
    {
         // ...
         static_cast<Derived*>(this)->implementation();
         // ...
    }
};

struct derived : base<derived>
{
     void implementation()
     {
         // ...
     }
};

Aqui, o modelo da classe base aproveitará o fato de que os corpos das funções de membro não são instanciados até depois de suas declarações e usará membros da classe derivada em suas próprias funções de membro, por meio do uso de a static_cast, portanto, na compilação, gerando um objeto composição com características polimórficas. Como um exemplo de uso no mundo real, o CRTP é usado na biblioteca do iterador Boost .

Outro uso semelhante é o " truque de Barton-Nackman ", às vezes referido como "expansão de modelo restrita", onde a funcionalidade comum pode ser colocada em uma classe base que é usada não como um contrato, mas como um componente necessário para reforçar o comportamento de conformidade, minimizando redundância de código.

Geração de tabela estática

O benefício das tabelas estáticas é a substituição de cálculos "caros" por uma operação simples de indexação de matriz (para exemplos, consulte a tabela de pesquisa ). Em C ++, existe mais de uma maneira de gerar uma tabela estática em tempo de compilação. A listagem a seguir mostra um exemplo de criação de uma tabela muito simples usando estruturas recursivas e modelos variados . A mesa tem um tamanho de dez. Cada valor é o quadrado do índice. 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

/**
 * Variadic template for a recursive helper struct.
 */
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };

/**
 * Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
 */
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
  static constexpr std::array<int, TABLE_SIZE> table = { D... };
};

constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;

enum  {
  FOUR = table[2] // compile time use
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // run time use
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

A ideia por trás disso é que o Helper de estrutura herda recursivamente de uma estrutura com mais um argumento de modelo (neste exemplo calculado como INDEX * INDEX) até que a especialização do modelo termine a recursão em um tamanho de 10 elementos. A especialização simplesmente usa a lista de argumentos variáveis ​​como elementos para a matriz. O compilador produzirá um código semelhante ao seguinte (retirado de clang chamado com -Xclang -ast-print -fsyntax-only). 

template <int INDEX = 0, int ...D> struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> {
};
template<> struct Helper<0, <>> : Helper<0 + 1, 0 * 0> {
};
template<> struct Helper<1, <0>> : Helper<1 + 1, 0, 1 * 1> {
};
template<> struct Helper<2, <0, 1>> : Helper<2 + 1, 0, 1, 2 * 2> {
};
template<> struct Helper<3, <0, 1, 4>> : Helper<3 + 1, 0, 1, 4, 3 * 3> {
};
template<> struct Helper<4, <0, 1, 4, 9>> : Helper<4 + 1, 0, 1, 4, 9, 4 * 4> {
};
template<> struct Helper<5, <0, 1, 4, 9, 16>> : Helper<5 + 1, 0, 1, 4, 9, 16, 5 * 5> {
};
template<> struct Helper<6, <0, 1, 4, 9, 16, 25>> : Helper<6 + 1, 0, 1, 4, 9, 16, 25, 6 * 6> {
};
template<> struct Helper<7, <0, 1, 4, 9, 16, 25, 36>> : Helper<7 + 1, 0, 1, 4, 9, 16, 25, 36, 7 * 7> {
};
template<> struct Helper<8, <0, 1, 4, 9, 16, 25, 36, 49>> : Helper<8 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 8 * 8> {
};
template<> struct Helper<9, <0, 1, 4, 9, 16, 25, 36, 49, 64>> : Helper<9 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 64, 9 * 9> {
};
template<> struct Helper<10, <0, 1, 4, 9, 16, 25, 36, 49, 64, 81>> {
  static constexpr std::array<int, TABLE_SIZE> table = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
};

Desde C ++ 17, isso pode ser escrito de forma mais legível como: 

 
#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

constexpr std::array<int, TABLE_SIZE> table = [] { // OR: constexpr auto table
  std::array<int, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = i * i;
  }
  return A;
}();

enum  {
  FOUR = table[2] // compile time use
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // run time use
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

Para mostrar um exemplo mais sofisticado, o código na lista a seguir foi estendido para ter um auxiliar para cálculo de valor (em preparação para cálculos mais complicados), um deslocamento específico de tabela e um argumento de modelo para o tipo de valores de tabela (por exemplo, uint8_t, uint16_t, ...). 

                                                                
#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

/**
 * Template to calculate a single table entry
 */
template <typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE INDEX>
struct ValueHelper {
  static constexpr VALUETYPE value = OFFSET + INDEX * INDEX;
};

/**
 * Variadic template for a recursive helper struct.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, int N = 0, VALUETYPE ...D>
struct Helper : Helper<VALUETYPE, OFFSET, N+1, D..., ValueHelper<VALUETYPE, OFFSET, N>::value> { };

/**
 * Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE ...D>
struct Helper<VALUETYPE, OFFSET, TABLE_SIZE, D...> {
  static constexpr std::array<VALUETYPE, TABLE_SIZE> table = { D... };
};

constexpr std::array<uint16_t, TABLE_SIZE> table = Helper<uint16_t, OFFSET>::table;

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table[i] << std::endl;
  }
}

Que pode ser escrito da seguinte maneira usando C ++ 17: 

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

template<typename VALUETYPE, VALUETYPE OFFSET>
constexpr std::array<VALUETYPE, TABLE_SIZE> table = [] { // OR: constexpr auto table
  std::array<VALUETYPE, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = OFFSET + i * i;
  }
  return A;
}();

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table<uint16_t, OFFSET>[i] << std::endl;
  }
}

Conceitos

O padrão C ++ 20 trouxe aos programadores C ++ uma nova ferramenta para a programação de meta templates, conceitos.

Os conceitos permitem que os programadores especifiquem os requisitos para o tipo, para tornar possível a instanciação do modelo. O compilador procura um modelo com o conceito que possua os requisitos mais elevados.

Aqui está um exemplo do famoso problema Fizz buzz resolvido com a meta-programação de modelo. 

#include <boost/type_index.hpp> // for pretty printing of types
#include <iostream>
#include <tuple>

/**
 * Type representation of words to print
 */
struct Fizz {};
struct Buzz {};
struct FizzBuzz {};
template<size_t _N> struct number { constexpr static size_t N = _N; };

/**
 * Concepts used to define condition for specializations
 */
template<typename Any> concept has_N = requires{ requires Any::N - Any::N == 0; };
template<typename A> concept fizz_c = has_N<A> && requires{ requires A::N % 3 == 0; };
template<typename A> concept buzz_c = has_N<A> && requires{ requires A::N % 5 == 0;};
template<typename A> concept fizzbuzz_c = fizz_c<A> && buzz_c<A>;

/**
 * By specializing `res` structure, with concepts requirements, proper instantation is performed
 */
template<typename X> struct res;
template<fizzbuzz_c X> struct res<X> { using result = FizzBuzz; };
template<fizz_c X> struct res<X> { using result = Fizz; };
template<buzz_c X> struct res<X> { using result = Buzz; };
template<has_N X> struct res<X> { using result = X; };

/**
 * Predeclaration of concentrator
 */
template <size_t cnt, typename... Args> 
struct concatenator;

/**
 * Recursive way of concatenating next types
 */
template <size_t cnt, typename ... Args>
struct concatenator<cnt, std::tuple<Args...>> 
{ using type = typename concatenator<cnt - 1, std::tuple< typename res< number<cnt> >::result, Args... >>::type;};

/**
 * Base case
 */
template <typename... Args> struct concatenator<0, std::tuple<Args...>> { using type = std::tuple<Args...>;};

/**
 * Final result getter
 */
template<size_t Amount>
using fizz_buzz_full_template = typename concatenator<Amount - 1, std::tuple<typename res<number<Amount>>::result>>::type;

int main()
{
	// printing result with boost, so it's clear
	std::cout << boost::typeindex::type_id<fizz_buzz_full_template<100>>().pretty_name() << std::endl;
/*
Result:
	std::tuple<number<1ul>, number<2ul>, Fizz, number<4ul>, Buzz, Fizz, number<7ul>, number<8ul>, Fizz, Buzz, number<11ul>, Fizz, number<13ul>, number<14ul>, FizzBuzz, number<16ul>, number<17ul>, Fizz, number<19ul>, Buzz, Fizz, number<22ul>, number<23ul>, Fizz, Buzz, number<26ul>, Fizz, number<28ul>, number<29ul>, FizzBuzz, number<31ul>, number<32ul>, Fizz, number<34ul>, Buzz, Fizz, number<37ul>, number<38ul>, Fizz, Buzz, number<41ul>, Fizz, number<43ul>, number<44ul>, FizzBuzz, number<46ul>, number<47ul>, Fizz, number<49ul>, Buzz, Fizz, number<52ul>, number<53ul>, Fizz, Buzz, number<56ul>, Fizz, number<58ul>, number<59ul>, FizzBuzz, number<61ul>, number<62ul>, Fizz, number<64ul>, Buzz, Fizz, number<67ul>, number<68ul>, Fizz, Buzz, number<71ul>, Fizz, number<73ul>, number<74ul>, FizzBuzz, number<76ul>, number<77ul>, Fizz, number<79ul>, Buzz, Fizz, number<82ul>, number<83ul>, Fizz, Buzz, number<86ul>, Fizz, number<88ul>, number<89ul>, FizzBuzz, number<91ul>, number<92ul>, Fizz, number<94ul>, Buzz, Fizz, number<97ul>, number<98ul>, Fizz, Buzz>
*/
}

Benefícios e desvantagens da metaprogramação de modelo

Troca de tempo de compilação versus tempo de execução
Se uma grande quantidade de metaprogramação de template for usada.
Programação genérica
A metaprogramação de modelo permite que o programador se concentre na arquitetura e delegue ao compilador a geração de qualquer implementação exigida pelo código do cliente. Assim, a metaprogramação de template pode realizar um código verdadeiramente genérico, facilitando a minimização do código e melhor manutenibilidade.
Legibilidade
Com relação ao C ++ anterior ao C ++ 11, a sintaxe e os idiomas da metaprogramação de modelo eram esotéricos em comparação com a programação C ++ convencional, e os metaprogramas de modelo podiam ser muito difíceis de entender. Mas do C ++ 11 em diante, a sintaxe para a metaprogramação de cálculo de valor torna-se cada vez mais semelhante ao C ++ "normal", com cada vez menos penalidade de legibilidade.

Veja também

Referências

links externos