Templatmetaprogrammering

**Templatmetaprogrammering (TMP)** er en metaprogrammeringsteknikk hvor templater blir brukt av kompilatoren til å generere midlertidig kildekode som slås sammen med resten av kildekoden og kompilert videre. Templatene produserer «compile-time constants» (kompileringstidskonstanter), datastrukturer og funksjoner. Teknikken ble oppdaget tilfeldig i programmeringsspråket C++ ved at man fant ut at templater var turingkomplett, som betyr at et hvert beregnbart problem som kan uttrykkes i et program kan beregnes ved hjelp av templatmetaprogrammering. Senere har ideen spredt seg til også andre programmeringsspråk som Curl, D og XL. 

## Teknisk overblikk
Bruken av templater i metaprogrammering skiller seg gjerne inn i to distinkte operasjoner. En template må bli definert, og en template som er definert må også instansieres. Definisjonen beskriver den generiske formen av koden som blir generert, mens instansieringa genererer koden beskrevet i definisjonen. Templatmetaprogrammer har ingen muterbare variabler som betyr at ingen variabler kan bli forandra etter at de har blitt initialisert. Det finnes ingen løkker, kun rekursjon. Derfor kan templatmetaprogrammering anses som en form for ren funksjonell programmering.

Et klassisk eksempel er fakultetsfunksjonen som i vanlig C++ kan skrives som en rekursiv funksjon.
```c++
unsigned int faktultet(unsigned int n) {
    return n == 0 ? 1 : n * faktultet(n - 1);
}

// fakultet(3) vil gi 6
// fakultet(5) vil gi 120
```
Denne funksjonen vil bli beregnet under kjøretid. Samme algoritme kan uttrykkes i templatmetaprogrammering og i stedet bli beregnet under kompilering. Følgende er et eksempel på en rekursiv metafunksjon som uttrykker samme algoritme.
```c++
template <unsigned N>
struct fakultet {
    static const unsigned int resultat = N * fakultet<N-1>::resultat;
};

template <>
struct fakultet<0> {
    static const unsigned int resultat = 1;
};

// fakultet<3>::resultat gir 6
// fakultet<5>::resultat gir 120
```
Ved rekursive metafunksjoner uttrykker man gjerne basistilfellet (i dette tilfellet 0) som en «template specialization» (templatspesialisering). Denne metafunksjonen vil beregnes ved kompilering og resultatet vil behandles som en prekalkulert konstant i programmet. Det vil si at alle tilfeller av for eksempel fakultet::resultat vil i det kjørbare programmet erstattes med verdien selv. En viktig observasjon er også at siden dette blir kalkulert under kompilering, krever det at argumentet til metafunksjonen er kjent under kompilering. Med andre ord kan argumentet kun være et konstantuttrykk eller et «constant literal» (i dette tilfellet alle naturlige heltall uten variabelbinding). Merk også at dette betyr at alle uttrykk deklarert som constexpr kan gis som argument, siden disse omfatter konstantuttrykk fra og med versjonsstandarden C++11.  

Templatmetaprogrammering kan også brukes til å representere mer avanserte konsepter enn bare funksjoner innen programmering, som for eksempel kontrollflyt og ulike evalueringsstrategier. 

## Kjente metaprogrammeringsteknikker

### Statisk polymorfisme
Polymorfisme er når deriverte objekter (barna i et klassehierarki) kan brukes som instanser av deres foreldre, men hvor det deriverte objektets metoder blir kjørt i stedet for foreldrens, som i denne kodesnutten (merk at dette er ved bruk av C++14)
```c++
#include <memory>
#include <iostream>

class Forelder {
public:
    virtual void metode() {
        std::cout << "Metode fra foreldreklassen";
    }
};

class Barn : public Forelder {
public:
    virtual void metode() {
        std::cout << "Metode fra barneklassen";
    }
};

int main() {
    std::unique_ptr<Forelder> f = std::make_unique<Barn>();
    f->metode();
    
    return 0;
}
```
Alle kjøringer av virtuelle metoder vil kjøre den mest deriverte metoden (metoden lengst ned i klassehierarkiet). Dette er polymorfi som er dynamisk hvor det vil lages virtuelle søketabeller som traverseres for å finne den mest deriverte metoden i hierarkiet.

I mange tilfeller vil polymorfisk oppførsel heller kunne bestemmes under kompilering. Da kan et idiom kalt CRTP (Curiously Recurring Template Pattern) brukes for å få statisk polymorfi, som illustrert i dette eksempelet.
```c++
template <class Derivert>
struct Forelder {
    void grensensitt() {
    // ...
    static_cast<Derivert*>(this)->implementering();
    }
    // ...
};

struct Barn : Forelder<Barn> {
    void implementering() {
        // ...
    }
};
```
Via grensesnittet til forelderen kan man finne den mest deriverte metoden. Alt skjer under kompilering, og vil ikke kreve noen form for virtuelle søketidstabeller.

### «Expression templates» (uttrykkstemplater)
Det finnes etablerte teknikker som kan gjøre templatmetaprogrammer svært mer effektive enn om det skulle vært programmert i det opprinnelige språket. Et eksempel på det er uttrykkstemplater som er mye brukt i mattebiblioteker når det ofte blir store midlertidige variabler som må lagres ved å evaluere sammensatte uttrykk. Et eksempel er addisjon av tre matriser. I ordinære programmeringsspråk vil først addisjonen av de to første matrisene lagres i en midlertidig variabel før det adderes med den siste matrisen. Dette vil allokere minne minst to ganger. En løsning på dette problemet er en spesiell implementering av lat evaluering ved templatmetaprogrammering. Det blir implementert ved at man lar operator+ returnere et objekt av en brukerdefinert type som skal representere et uevaluert subuttrykk, for eksempel addisjon av to matriser. Ved evaluering av større uttrykk bygger man opp et «parse tree» av disse objektene som representerer de uevaluerte subuttrykkene. Treet evalueres kun når strukturen som representerer treet blir tildelt en variabel. For å få til den effekten definerer man da operator=. Vær oppmerksom på at evaluering krever at man traverserer treet, som i seg selv er en kostbar operasjon. Men alt i alt vil dette kun kreve en minneallokering, om det implementeres riktig.

Kort oppsummert implementerer uttrykkstemplater lat evaluering ved bruk av «parse trees» som kun eksisterer under kompilering. 

## Fordeler og ulemper ved bruk
Selv om templatmetaprogrammering ofte er svært annerledes fra programmeringsspråket som det brukes med, har det flere bruksområder. Før var templatmetaprogrammering den eneste måten å utføre beregninger under kompilering på. Med C++11 kom constexpr som gjorde det lettere å gjøre beregninger under kompilering, hvor man ikke er avhengig av funksjonelle programmeringsteknikker som i templatmetaprogrammering. Det blir uansett brukt som følge av at mange er avhengig av tidligere versjonsstandarder og at constexpr har begrensninger i C++11 (de har forøvrig blitt lettet mye på med C++14). En fordel med å utføre beregninger under kompilering enn ved kjøretid er at man slipper å utføre beregninga hver gang programmet skal kjøres. I stedet gjør man det under kompilering. Til gjengjeld tar det lengre tid å kompilere. I C++ er templatmetaprogrammering den eneste måten du kan gjøre beregninger med typer på, dette gjør det ofte særlig relevant for utviklere av biblioteker. Templatmetaprogrammering er veldig utbredt i C++ sitt standardbibliotek. 

Et av problemene knyttet til templatmetaprogrammering er at det kan være svært vanskelig å skrive og lese kode. Det er en konsekvens av at det var ingen som designet teknikken, den ble i stedet oppdaget ved en tilfeldighet. Man har i stedet tatt skritt for å tilpasse templatmetaprogrammering inn i C++ med de nyere versjonsstandardene, siden det viser seg å være en så kraftig teknikk. Kompilering kan også bli veldig tregt om mye templatmetaprogrammering brukes. Graden av hvor tregt det kan bli vil være veldig avhengig av hvordan det har blitt brukt.  

## Se også
* Templater
* Templatspesialisering
* Metaprogrammering

## Referanser