Metaprogramación de plantillas - Template metaprogramming

Paradigmas de programación

La metaprogramación de plantillas ( TMP ) es una técnica de metaprogramación en la que un compilador utiliza las plantillas para generar código fuente temporal , que el compilador fusiona con el resto del código fuente y luego lo compila. La salida de estas plantillas puede incluir constantes en tiempo de compilación , estructuras de datos y funciones completas . El uso de plantillas se puede considerar como polimorfismo en tiempo de compilación . La técnica es utilizada por varios lenguajes, el más conocido es C ++ , pero también Curl , D , Nim y XL .

La metaprogramación de plantillas fue, en cierto sentido, descubierta accidentalmente.

Algunos otros lenguajes admiten instalaciones de tiempo de compilación similares, si no más potentes (como macros Lisp ), pero están fuera del alcance de este artículo.

Componentes de la metaprogramación de plantillas

El uso de plantillas como técnica de metaprogramación requiere dos operaciones distintas: se debe definir una plantilla y se debe crear una instancia de una plantilla definida . La definición de la plantilla describe la forma genérica del código fuente generado, y la instanciación hace que se genere un conjunto específico de código fuente a partir de la forma genérica en la plantilla.

La metaprogramación de plantilla es Turing-completa , lo que significa que cualquier cálculo expresable por un programa de computadora puede ser calculado, de alguna forma, por un metaprograma de plantilla.

Las plantillas son diferentes a las macros . Una macro es un fragmento de código que se ejecuta en tiempo de compilación y realiza una manipulación textual del código que se va a compilar (por ejemplo, macros de C ++ ) o manipula el árbol de sintaxis abstracto que produce el compilador (por ejemplo, macros de Rust o Lisp ). Las macros textuales son notablemente más independientes de la sintaxis del lenguaje que se manipula, ya que simplemente cambian el texto en memoria del código fuente justo antes de la compilación.

Los metaprogramas de plantilla no tienen variables mutables , es decir, ninguna variable puede cambiar el valor una vez que se ha inicializado, por lo tanto, la metaprogramación de plantilla puede verse como una forma de programación funcional . De hecho, muchas implementaciones de plantillas implementan el control de flujo solo a través de la recursividad , como se ve en el siguiente ejemplo.

Usando la metaprogramación de plantillas

Aunque la sintaxis de la metaprogramación de plantillas suele ser muy diferente del lenguaje de programación con el que se utiliza, tiene usos prácticos. Algunas razones comunes para usar plantillas son implementar programación genérica (evitando secciones de código que son similares excepto por algunas variaciones menores) o realizar una optimización automática en tiempo de compilación, como hacer algo una vez en tiempo de compilación en lugar de cada vez que se ejecuta el programa. por ejemplo, haciendo que el compilador desenrolle los bucles para eliminar los saltos y las disminuciones en el recuento de bucles cada vez que se ejecuta el programa.

Generación de clases en tiempo de compilación

Lo que significa exactamente "programar en tiempo de compilación" se puede ilustrar con un ejemplo de una función factorial, que en C ++ sin plantilla se puede escribir usando la recursividad de la siguiente manera: 

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

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

El código anterior se ejecutará en tiempo de ejecución para determinar el valor factorial de los literales 0 y 4. Al usar la metaprogramación de plantilla y la especialización de plantilla para proporcionar la condición final para la recursividad, los factoriales usados ​​en el programa, ignorando cualquier factorial no usado, pueden ser calculado en tiempo de compilación 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.

El código anterior calcula el valor factorial de los literales 0 y 4 en tiempo de compilación y usa los resultados como si fueran constantes precalculadas. Para poder usar plantillas de esta manera, el compilador debe conocer el valor de sus parámetros en el momento de la compilación, lo cual tiene la condición previa natural de que el factorial <X> :: value solo se puede usar si se conoce X en el momento de la compilación. En otras palabras, X debe ser un literal constante o una expresión constante.

En C ++ 11 y C ++ 20 , constexpr y consteval se introdujeron para permitir que el compilador ejecutara código. Usando constexpr y consteval, se puede usar la definición factorial recursiva habitual con la sintaxis sin plantilla.

Optimización de código en tiempo de compilación

Ver también: ejecución de la función en tiempo de compilación

El ejemplo factorial anterior es un ejemplo de optimización de código en tiempo de compilación en el que todos los factoriales utilizados por el programa se compilan previamente y se inyectan como constantes numéricas en la compilación, lo que ahorra tanto la sobrecarga del tiempo de ejecución como la huella de memoria. Sin embargo, es una optimización relativamente menor.

Como otro ejemplo más significativo de desenrollado de bucles en tiempo de compilación , la metaprogramación de plantillas se puede utilizar para crear clases de vectores de longitud n (donde n se conoce en tiempo de compilación). La ventaja sobre un vector de longitud n más tradicional es que los bucles se pueden desenrollar, lo que da como resultado un código muy optimizado. Como ejemplo, considere el operador de suma. Una suma de vectores de longitud n podría escribirse 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;
}

Cuando el compilador crea una instancia de la plantilla de función definida anteriormente, se puede producir el siguiente código: 

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

El optimizador del compilador debería poder desenrollar el forciclo porque el parámetro de plantilla lengthes una constante en el momento de la compilación.

Sin embargo, tenga cuidado y sea precavido, ya que esto puede causar que el código se sobrecargue, ya que se generará un código desenrollado por separado para cada 'N' (tamaño de vector) con el que cree una instancia.

Polimorfismo estático

El polimorfismo es una instalación de programación estándar común donde los objetos derivados se pueden usar como instancias de su objeto base, pero donde se invocarán los métodos de los objetos derivados, como en este 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;
}

donde todas las invocaciones de virtualmétodos serán las de la clase más derivada. Este comportamiento dinámicamente polimórfico se obtiene (normalmente) mediante la creación de tablas de búsqueda virtuales para clases con métodos virtuales, tablas que se recorren en tiempo de ejecución para identificar el método que se invocará. Por lo tanto, el polimorfismo en tiempo de ejecución implica necesariamente una sobrecarga de ejecución (aunque en las arquitecturas modernas la sobrecarga es pequeña).

Sin embargo, en muchos casos el comportamiento polimórfico necesario es invariante y se puede determinar en el momento de la compilación. Luego, el patrón de plantilla curiosamente recurrente (CRTP) se puede utilizar para lograr un polimorfismo estático , que es una imitación del polimorfismo en el código de programación, pero que se resuelve en tiempo de compilación y, por lo tanto, elimina las búsquedas de tablas virtuales en tiempo de ejecución. Por ejemplo: 

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

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

Aquí, la plantilla de la clase base aprovechará el hecho de que los cuerpos de las funciones miembro no se instancian hasta después de sus declaraciones, y usará miembros de la clase derivada dentro de sus propias funciones miembro, mediante el uso de a static_cast, por lo tanto en la compilación generando un objeto composición con características polimórficas. Como ejemplo de uso en el mundo real, el CRTP se usa en la biblioteca de iteradores de Boost .

Otro uso similar es el " truco de Barton-Nackman ", a veces denominado "expansión de plantilla restringida", donde la funcionalidad común se puede colocar en una clase base que no se usa como un contrato sino como un componente necesario para hacer cumplir el comportamiento conforme mientras se minimiza Redundancia de código.

Generación de tablas estáticas

El beneficio de las tablas estáticas es el reemplazo de cálculos "costosos" con una operación simple de indexación de matrices (para ver ejemplos, consulte la tabla de búsqueda ). En C ++, existe más de una forma de generar una tabla estática en tiempo de compilación. La siguiente lista muestra un ejemplo de cómo crear una tabla muy simple usando estructuras recursivas y plantillas variadas . La mesa tiene un tamaño de diez. Cada valor es el cuadrado del í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;
}

La idea detrás de esto es que el struct Helper hereda recursivamente de una estructura con un argumento de plantilla más (en este ejemplo calculado como INDICE * INDEX) hasta que la especialización de la plantilla finaliza la recursividad en un tamaño de 10 elementos. La especialización simplemente usa la lista de argumentos de la variable como elementos para la matriz. El compilador producirá un código similar al siguiente (tomado de clang llamado con -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, esto se puede escribir de manera más legible 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 un ejemplo más sofisticado, el código de la siguiente lista se ha ampliado para tener un ayudante para el cálculo del valor (en preparación para cálculos más complicados), un desplazamiento específico de la tabla y un argumento de plantilla para el tipo de los valores de la tabla (por ejemplo, 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 podría escribirse de la siguiente manera 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;
  }
}

Conceptos

El estándar C ++ 20 trajo a los programadores de C ++ una nueva herramienta para la programación de metaplantillas, conceptos.

Los conceptos permiten a los programadores especificar requisitos para el tipo, para hacer posible la creación de instancias de la plantilla. El compilador busca una plantilla con el concepto que tenga los requisitos más altos.

Aquí hay un ejemplo del famoso problema de buzz de Fizz resuelto con la Meta Programación de Plantillas. 

#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>
*/
}

Beneficios e inconvenientes de la metaprogramación de plantillas

Compensación de tiempo de compilación versus tiempo de ejecución
Si se utiliza una gran cantidad de metaprogramación de plantillas.
Programación genérica
La metaprogramación de plantillas permite al programador centrarse en la arquitectura y delegar en el compilador la generación de cualquier implementación requerida por el código del cliente. Por lo tanto, la metaprogramación de plantillas puede lograr un código verdaderamente genérico, facilitando la minimización del código y una mejor capacidad de mantenimiento.
Legibilidad
Con respecto a C ++ antes de C ++ 11, la sintaxis y los modismos de la metaprogramación de plantilla eran esotéricos en comparación con la programación C ++ convencional, y los metaprogramas de plantilla podían ser muy difíciles de entender. Pero a partir de C ++ 11 en adelante, la sintaxis para la metaprogramación de cálculo de valores se vuelve cada vez más similar a C ++ "normal", con cada vez menos problemas de legibilidad.

Ver también

Referencias

enlaces externos