Metaprogramowanie szablonów — Template metaprogramming

Paradygmaty programowania

Metaprogramowanie szablonów ( TMP ) to technika metaprogramowania , w której kompilator wykorzystuje szablony do generowania tymczasowego kodu źródłowego , który jest łączony przez kompilator z resztą kodu źródłowego, a następnie kompilowany. Dane wyjściowe tych szablonów mogą zawierać stałe czasu kompilacji , struktury danych i kompletne funkcje . Używanie szablonów można traktować jako polimorfizm w czasie kompilacji . Technika ta jest używana przez wiele języków, z których najbardziej znany to C++ , ale także Curl , D , Nim i XL .

Metaprogramowanie szablonów zostało w pewnym sensie odkryte przypadkowo.

Niektóre inne języki obsługują podobne, jeśli nie bardziej zaawansowane funkcje czasu kompilacji (takie jak makra Lisp ), ale są one poza zakresem tego artykułu.

Składniki metaprogramowania szablonów

Użycie szablonów jako techniki metaprogramowania wymaga dwóch odrębnych operacji: należy zdefiniować szablon i utworzyć instancję zdefiniowanego szablonu . Definicja szablonu opisuje rodzajową formę wygenerowanego kodu źródłowego, a tworzenie instancji powoduje wygenerowanie określonego zestawu kodu źródłowego z formy ogólnej w szablonie.

Metaprogramowanie szablonu to Turing-complete , co oznacza, że ​​wszelkie obliczenia wyrażalne przez program komputerowy mogą być obliczone, w pewnej formie, przez metaprogram szablonu.

Szablony różnią się od makr . Makro to fragment kodu, który jest wykonywany w czasie kompilacji i albo wykonuje tekstową manipulację kodem, który ma zostać skompilowany (np. makra C++ ), albo manipuluje abstrakcyjnym drzewem składni tworzonym przez kompilator (np. makra Rust lub Lisp ). Makra tekstowe są znacznie bardziej niezależne od składni manipulowanego języka, ponieważ zmieniają jedynie tekst znajdujący się w pamięci kodu źródłowego tuż przed kompilacją.

Metaprogramy szablonów nie mają zmiennych zmiennych — to znaczy żadna zmienna nie może zmienić wartości po jej zainicjowaniu, dlatego metaprogramowanie szablonów może być postrzegane jako forma programowania funkcjonalnego . W rzeczywistości wiele implementacji szablonów implementuje kontrolę przepływu tylko poprzez rekursję , jak widać w poniższym przykładzie.

Korzystanie z metaprogramowania szablonów

Chociaż składnia metaprogramowania szablonów jest zwykle bardzo różna od języka programowania, z którym jest używany, ma praktyczne zastosowania. Niektóre typowe powody używania szablonów to implementacja programowania generycznego (unikanie sekcji kodu, które są podobne, z wyjątkiem kilku drobnych zmian) lub przeprowadzanie automatycznej optymalizacji czasu kompilacji, takiej jak robienie czegoś raz w czasie kompilacji, a nie za każdym razem, gdy program jest uruchamiany — na przykład dzięki temu, że kompilator rozwinie pętle, aby wyeliminować skoki i zmniejszenie liczby pętli za każdym razem, gdy program jest wykonywany.

Generowanie klas w czasie kompilacji

Co dokładnie oznacza "programowanie w czasie kompilacji" można zilustrować przykładem funkcji silni, która w nieszablonowym C++ może być napisana przy użyciu rekurencji w następujący sposób: 

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

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

Powyższy kod zostanie wykonany w czasie wykonywania w celu określenia wartości silni literałów 0 i 4. Używając metaprogramowania szablonu i specjalizacji szablonu w celu dostarczenia warunku końcowego rekursji, silnia użyte w programie — ignorując nieużywaną silnię — może być obliczone w czasie kompilacji za pomocą tego kodu: 

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.

Powyższy kod oblicza wartość silni literałów 0 i 4 w czasie kompilacji i używa wyników tak, jakby były wstępnie obliczonymi stałymi. Aby móc używać szablonów w ten sposób, kompilator musi znać wartość swoich parametrów w czasie kompilacji, co ma naturalny warunek wstępny, że factorial<X>::value może być używany tylko wtedy, gdy X jest znane w czasie kompilacji. Innymi słowy, X musi być literałem stałym lub wyrażeniem stałym.

W C ++ 11 i C ++ 20 , constexpr i consteval zostały wprowadzone do niech kompilator wykonanie kodu. Używając constexpr i consteval, można użyć zwykłej definicji silni rekurencyjnej z nieszablonową składnią.

Optymalizacja kodu w czasie kompilacji

Zobacz też: Wykonywanie funkcji w czasie kompilacji

Powyższy przykład silni jest jednym z przykładów optymalizacji kodu w czasie kompilacji, w którym wszystkie silnie używane przez program są wstępnie kompilowane i wstrzykiwane jako stałe liczbowe podczas kompilacji, co oszczędza zarówno narzut w czasie wykonywania, jak i zużycie pamięci. Jest to jednak stosunkowo niewielka optymalizacja.

Jako inny, bardziej znaczący przykład rozwijania pętli w czasie kompilacji , metaprogramowanie szablonów może być użyte do tworzenia klas wektorów o długości n (gdzie n jest znane w czasie kompilacji). Zaletą w porównaniu z bardziej tradycyjnym wektorem o długości n jest to, że pętle mogą być rozwijane, co skutkuje bardzo zoptymalizowanym kodem. Jako przykład rozważmy operator dodawania. Dodawanie wektora o długości n można zapisać jako 

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;
}

Gdy kompilator tworzy wystąpienie szablonu funkcji zdefiniowanego powyżej, może zostać wygenerowany następujący kod: 

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

Optymalizator kompilatora powinien być w stanie rozwinąć forpętlę, ponieważ parametr szablonu lengthjest stałą w czasie kompilacji.

Należy jednak zachować ostrożność i zachować ostrożność, ponieważ może to spowodować rozdęcie kodu, ponieważ dla każdego elementu „N” (rozmiar wektora) zostanie wygenerowany osobny rozwinięty kod.

Polimorfizm statyczny

Polimorfizm to powszechna standardowa funkcja programowania, w której obiekty pochodne mogą być używane jako instancje ich obiektów bazowych, ale w których metody obiektów pochodnych będą wywoływane, jak w tym kodzie 

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;
}

gdzie wszystkie wywołania virtualmetod będą wywołaniami klasy najbardziej pochodnej. To dynamicznie polimorficzne zachowanie jest (zazwyczaj) uzyskiwane przez utworzenie wirtualnych tabel przeglądowych dla klas z metodami wirtualnymi, które są przeszukiwane w czasie wykonywania w celu zidentyfikowania metody, która ma zostać wywołana. W związku z tym polimorfizm w czasie wykonywania z konieczności pociąga za sobą koszty wykonania (chociaż w nowoczesnych architekturach koszty te są niewielkie).

Jednak w wielu przypadkach wymagane zachowanie polimorficzne jest niezmienne i można je określić w czasie kompilacji. Następnie wzorzec Curiously Recurring Template Pattern (CRTP) może zostać użyty do uzyskania statycznego polimorfizmu , który jest imitacją polimorfizmu w kodzie programistycznym, ale który jest rozwiązywany w czasie kompilacji, a tym samym eliminuje wyszukiwania tabel wirtualnych w czasie wykonywania. Na przykład: 

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

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

Tutaj szablon klasy bazowej będzie korzystał z faktu, że ciała funkcji składowych są tworzone dopiero po ich deklaracjach, i użyje składowych klasy pochodnej w ramach własnych funkcji składowych, poprzez użycie a static_cast, a więc przy kompilacji generującej obiekt kompozycja o cechach polimorficznych. Jako przykład użycia w świecie rzeczywistym, CRTP jest używany w bibliotece iteratorów Boost .

Innym podobnym zastosowaniem jest „ sztuczka Bartona-Nackmana ”, czasami określana jako „ograniczone rozszerzanie szablonów”, gdzie powszechną funkcjonalność można umieścić w klasie bazowej, która nie jest używana jako kontrakt, ale jako niezbędny składnik do wymuszenia zgodnego zachowania przy minimalizacji nadmiarowość kodu.

Generowanie tabeli statycznej

Zaletą tabel statycznych jest zastąpienie "kosztownych" obliczeń prostą operacją indeksowania tablic (przykłady patrz tabela przeglądowa ). W C++ istnieje więcej niż jeden sposób generowania statycznej tabeli w czasie kompilacji. Poniższa lista przedstawia przykład tworzenia bardzo prostej tabeli przy użyciu struktur rekurencyjnych i szablonów variadic . Stół ma rozmiar dziesięciu. Każda wartość to kwadrat indeksu. 

#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;
}

Ideą tego jest to, że struct Helper rekursywnie dziedziczy ze struktury z jeszcze jednym argumentem szablonu (w tym przykładzie obliczanym jako INDEX * INDEX), dopóki specjalizacja szablonu nie zakończy rekurencji w rozmiarze 10 elementów. Specjalizacja po prostu używa listy zmiennych argumentów jako elementów tablicy. Kompilator wygeneruje kod podobny do poniższego (pobrany z clang wywołanego z -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};
};

Od C++17 można to bardziej czytelnie zapisać jako: 

 
#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;
}

Aby pokazać bardziej wyrafinowany przykład, kod w poniższym listingu został rozszerzony o pomoc do obliczania wartości (w przygotowaniu do bardziej skomplikowanych obliczeń), offset specyficzny dla tabeli oraz argument szablonu dla typu wartości tabeli (np. 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;
  }
}

Co można napisać w następujący sposób przy użyciu 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;
  }
}

Koncepcje

Standard C++20 przyniósł programistom C++ nowe narzędzie do programowania meta-szablonów, koncepcji.

Koncepcje pozwalają programistom określić wymagania dla typu, aby umożliwić tworzenie instancji szablonu. Kompilator szuka szablonu z koncepcją, która ma najwyższe wymagania.

Oto przykład słynnego problemu z buzzem Fizza, który został rozwiązany za pomocą Template Meta Programming. 

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

Zalety i wady metaprogramowania szablonów

Kompromis między czasem kompilacji a czasem wykonania
Jeśli używa się dużej ilości metaprogramowania szablonów.
Programowanie ogólne
Metaprogramowanie szablonów pozwala programiście skupić się na architekturze i przekazać kompilatorowi generowanie dowolnej implementacji wymaganej przez kod klienta. W ten sposób metaprogramowanie szablonów może zapewnić prawdziwie ogólny kod, ułatwiając minimalizację kodu i lepszą konserwację.
Czytelność
W odniesieniu do C++ przed C++11 składnia i idiomy metaprogramowania szablonów były ezoteryczne w porównaniu z konwencjonalnym programowaniem C++, a metaprogramy szablonów mogą być bardzo trudne do zrozumienia. Ale począwszy od C++11 składnia metaprogramowania obliczania wartości staje się coraz bardziej podobna do „normalnego” C++, z coraz mniejszą utratą czytelności.

Zobacz też

Bibliografia

Linki zewnętrzne