Tools4ever Tech Blog

Template meta programming in C++

Ralph Langendam - Sr. Software Engineer | 20 december 2016

Introductie

C++ is niet compleet zonder ondersteuning van de Standard Template Library (STL). Het is dan ook een integraal onderdeel van de C++ standaard en biedt de ontwikkelaar veel generieke functionaliteit. Binnen veel programmeertalen bestaan tegenwoordig constructies om generaliteit en abstractie te bewerkstelligen, maar C++ templates zijn hierin uitzonderlijk. Templates zijn geënt op de generics uit Ada en worden, in tegenstelling tot bijvoorbeeld generics in C# en Java, volledig tijdens compilatie geëvalueerd. Templates laten zich compile-time instantiëren tot alsmaar concretere vorm, totdat uiteindelijk een waarde of een type is bereikt met run-time semantiek.

Net als bijvoorbeeld macro’s en inline assembly vormen templates een Türing complete subtaal binnen C++. Het voert voor deze blogpost veel te ver om het volledige palet aan mogelijkheden van deze taal te belichten. Als vertrekpunt kiezen we dan ook een goed begrip van de STL en C++ templates in zijn algemeenheid. In deze post laat ik enkele template metaprogramming technieken de revue passeren en leg ik de basis voor een eenvoudig uit te breiden template meta programming framework. Een referentie implementatie voor diverse concepten die we behandelen is ook beschikbaar op GitHub: https://github.com/RLangendam/SpecialTMP

Statische polymorfie

Wanneer we het werken met incomplete types combineren met templates ontstaat er de ruimte om generiek gedrag op types te definiëren nog voordat bekend is hoe het type er precies uitziet. Keuzes gebaseerd op deze incomplete types zijn per definitie polymorf van aard. Het ligt daarmee in de lijn der verwachting dat het bijvoorbeeld het dynamisch polymorfisme uit C++ een canonieke transformatie naar compile-tijd toestaat. Beschouw het volgende voorbeeld:

 

Het bovenstaand voorbeeld, op basis van dynamisch polymorfisme, zullen we opnieuw uitschrijven, maar dan op basis van statisch polymorfisme. We maken gebruik van het zogenaamde Curiously Recurring Template Pattern (CRTP), waarbij een base class het afgeleide type als incomplete type in diens definitie meegegeven krijgt.

 

Zoals de naam reeds aangeeft wordt statische polymorfie volledig door de compiler opgelost. Dit in tegenstelling tot dynamische polymorfie. De static_cast in Self is geoorloofd, omdat gegeven T=Insect of T=Arachnid als complete types, het type Animal<T> weet dat ‘this’ een T-pointer is.

Specialisatie

Template Meta ProgrammingNet als instantie biedt template specialisatie de mogelijkheid om templates te concretiseren. In tegenstelling tot instantie echter, leidt specialisatie niet altijd tot concretisering. Bijvoorbeeld, de specialisatie ‘template <> std::vector<bool>’ van de template ‘template <typename T> std::vector<T>’ is een concretisering, terwijl de partiële specialisatie ‘template <typename T> std::is_same<T, T>’ van ‘template <typename T, typename U> std::is_same<T, U>’ slechts een parametrisatie is. Daar waar volledige template specialisatie altijd concretiseert hoeft dit dus niet het geval te zijn voor partiële template specialisatie.

De verzameling van template specialisaties vormt een partiële ordening onder de “meer gespecialiseerd” relatie. Informeel gesproken is een template A meer gespecialiseerd dan een template B als, voor alle types en waardes beschouwd voor instantie, A minder valide kandidaten heeft dan B. Gegeven een combinatie van template parameters voor instantie, dan is de instantie alleen valide indien er precies één meest gespecialiseerde template bestaat. In dat geval is de gekozen template instantie precies de instantie van deze meest gespecialiseerde specialisatie.

In de vorige blogpost over multithreading hebben we in de context van sequencing reeds gekeken naar strikte partiële ordeningen. Een (gewone) partiële ordening daarentegen is een paar (P, ≤) van een verzameling P en een binaire relatie ≤ op P, zodanig dat aan de volgende eigenschappen is voldaan:

  • ≤ is reflexief: ofwel voor alle p ∈ P geldt dat p ≤ p.
  • ≤ is antisymmetrisch: ofwel als voor p, q ∈ P geldt dat p ≤ q en q ≤ p, dan geldt p = q.
  • ≤ is transitief: ofwel als voor p, q, r ∈ P geldt dat p ≤ q en q ≤ r dan geldt p ≤ r.

In de context van template specialisaties neemt ≤ de vorm aan van de “meer gespecialiseerd” relatie. Zij gegeven twee partiële template specialisaties s en t. Om te bepalen welke specialisatie (indien mogelijk) meer gespecialiseerd is worden voor beide specialisaties fictieve overloading templatefuncties f gecreëerd die ieder een instantie van de bijbehorende specialisatie als parameter meekrijgen. Laten we deze respectievelijk fs en ft noemen. Beide templatefuncties participeren vervolgens in König lookup / overload resolutie voor een fictieve type instantie X die voldoet aan beide template instanties. s is meer gespecialiseerd dan t precies als aan de volgende voorwaarden is voldaan.

  • Als template parameter deductie slaagt voor fs(X) dan slaagt deze ook voor ft(X).
  • Als template parameter deductie slaagt voor ft(X) dan slaagt deze niet voor fs(X).

We beschouwen std::is_same als voorbeeld ter illustratie van dit principe:

 

Ofschoon onze bovengenoemde partiële specialisatie niet zou compileren voor instantie met twee verschillende types geeft dit geen compiler error. Deze ‘overload’ wordt in plaats daarvan uit de kandidatenlijst geschrapt. Dit principe heeft de naam Substitution Failure Is Not An Error (SFINAE) en wordt binnen STL veelvuldig gebruikt om uniciteit binnen de partiële ordening van specialisaties te realiseren.

Het is mede vanwege de intrinsieke afbeelding van template specialisaties op overloading dat het combineren van templatefunctie specialisatie en overloading wordt ontraden. Voor meer informatie over de mogelijke problemen en onduidelijkheden die dit met zich meebrengt kunt u eens kijken naar de ‘Barton-Nackman trick’ en de volgende bijdrage van Herb Sutter (http://www.gotw.ca/publications/mill17.htm)

In deze blogpost zullen wij ons voor de eenduidigheid louter beperken tot template specialisatie van types. Omdat types niet overloaden is niet alleen het begrip van de beoogde specialisaties eenvoudiger, maar ook van meet af aan eenduidig. Dat dit geen wezenlijke beperking van onze vrijheden is illustreren we hierbij aan de hand van twee semantisch identieke voorbeelden.

 

Template Meta Programming - traits clasess

Traits classes

De parameters in een template definitie zijn altijd van een van de volgende drie soorten:

  • Compile-time constante heeltallige waarden
  • Types
  • Templates

Indien er sprake is van een type of een template als soort voor een template parameter afhankelijke naam (dependent name), dan dient deze soort expliciet gespecificeerd te worden met respectievelijk het ‘typename’ of ‘template’ keyword. Bijvoorbeeld:

 

Bovenstaand voorbeeld illustreert nog een belangrijk principe. Namelijk, dat alle soorten template parameters ook met slechts één parameter van het soort ‘type’ kunnen worden doorgegeven aan een template. Het type X vervult hier de functie van een zogenaamde traits class. Het gedrag van de instantie S<X> wordt immers beïnvloed door de eigenschappen (traits) van X.

Het specialiseren op basis van dergelijke dependent traits verschilt niet veel van gewone specialisatie.

 

Trait slicing

Template Meta Programming - Trait slicingIn het werken met traits classes in generieke constructies gebruikt men vaak nodeloos veel template instanties. Deze instanties kosten niet alleen compilatietijd om te bepalen, maar dragen ook bij aan de omvang van de translation unit waar deze in terecht komen. In het optimaliseren van template instanties kan trait slicing uitkomst bieden. Beschouw eerst het volgende voorbeeld:

 

 

Ofschoon Container<T> wezenlijk niets anders representeert in beide expliciete template instanties, worden er desalniettemin toch twee nieuw types voor geïnstantieerd. Om dit te voorkomen kunnen we de traits voor Array op maat ‘snijden’ voor instantie van Container.

 

Interessanter wordt de constructie als we de specifieke traits voor Container ook in andere templates willen hergebruiken. We kunnen dan beter, in plaats van een ContainerFactory, een traits factory beschouwen en de instantie van Container met deze herbruikbare traits overlaten aan de specifieke situatie:

 

Trait generalisatie

De keuze voor Traits is hier natuurlijk nogal arbitrair is slecht herbruikbaar. We zijn op deze manier immers gedwongen om nieuwe traits classes te definiëren voor elke bundeling van eigenschappen voor een class. Bovendien kunnen deze eigenschappen niet alleen waarden, maar ook types of templates zijn. Zelfs variadic templates zijn niet rijk genoeg om al deze combinaties in een keer te ondersteunen. Tenminste, zo lijkt het nu.

Het volgende dient om aan te tonen dat we voldoende hebben aan slechts één traits class. Het idee is om zowel waardes, types als templates getrouw om te vormen tot types, en tuples van dergelijke types op te vatten als de traits class waarop specialisatie mogelijk is.

Als wij zouden slagen in deze poging, dan kunnen alle template definities in C++ gereduceerd worden tot template types met slechts één template parameter: de traits class. Dan hebben alle templates de metasignatuur: template <typename> class. Het transformeren van een dergelijke template naar een type is nu eenvoudig:

 

Omdat types reeds types zijn, rest ons nog slechts de transformatie van waardes naar types. Gelukkig is ook dit niet ingewikkeld.

 

Nu alle soorten template parameters kunnen worden beschreven als types blijft slechts het bundelen van deze types tot één traits class over. Hiertoe gebruiken we het principe van een tuple.

 

Met uitzondering van de drie voorgenoemde constructies (Value, Template en Tuple) zijn alle template types bewijsbaar te schijven als unaire metafuncties. Hieruit concluderen we dat onze aanname terecht was.

Trait slicing als vorm van duck typing is met deze constructies weliswaar niet langer mogelijk, maar specialisatie wordt daarentegen een stuk eenvoudiger. Beide technieken kennen hun specifieke toepassingsdomein. Bestaande templates kunnen eenvoudig verpakt worden om compatible met deze techniek te zijn:

 

Meta algoritmen

Template Meta Programming - Meta algoritmenDaar waar duck typing technieken goed werken in losse templatecomponenten zonder veel omgevingskennis werkt de generalisatie van traits tot incomplete types veelal beter in een algoritmische context. De rest van dit blog zullen wij ons richten op de ontwikkeling van meta algoritmiek gebruik makend van trait generalisatie.

We beginnen met een stukje logica en we introduceren een macro voor het definiëren van een metafunctie.

 

 

De definities voor de andere logische en aritmetische operatoren laten we als oefening over aan de lezer. In de kern van veel algoritmiek zit uiteraard iteratie. Iteratie kunnen we realiseren door bijvoorbeeld de elementen van een tuple stapsgewijs te doorlopen. Hiertoe introduceren we enkele hulpfuncties.

 

Met iteratie tot onze beschikking komt het karakter van template metaprogramming in C++ als volwassen functionele subtaal steeds beter tot uitdrukking. Vrijwel alle STL-algoritmen uit <algorithm> en <numeric> kunnen uitgeschreven worden in termen van dergelijke left folds. Ook dit laten wij als oefening aan de lezer.

Compositie

Template Meta Programming - compositieEen template in C++ kan beschouwd worden als een metafunctie tussen types. Immers een template <typename> class F associeert met een type T een type F<T> door applicatie. Een meta metafunctie is logischerwijs een associatie tussen metafuncties. Bijvoorbeeld, een unaire meta metafunctie is een template <template <typename> class> class M die aan iedere metafunctie F een metafunctie M<F> toekent. Dergelijke functies zijn voorbeelden van functoren. Binnen ons framework blijkt hier reeds in voorzien te zijn, aangezien we alle templates een metasignatuur template <typename> class kunnen geven. Ter illustratie beschrijven we de meta metafunctie Compose als metafunctie:

 


Currying

Template Meta Programming - curryingWe brengen in herinnering dat currying de transformatie beschrijft van de evaluatie van een functie op meerdere argumenten naar de achtereenvolgende evaluatie van meerdere functies op steeds een argument. Bijvoorbeeld, we kunnen de functie

f : V1 × ... × Vn → W : (v1, ..., vn) ↦ w = f(v1, ..., vn)

beschouwen als een geneste reeks van functies

V1 → (V2 → (... → (Vn → W) ... )) : v1 ↦ (v2 ↦ ... (vn ↦ w) ... )

Binnen ons framework valt currying eenvoudig te realiseren. Immers, alleen wanneer een metafunctie met precies de juiste (hoeveelheid) elementen in een Tuple wordt geïnstantieerd zal er mogelijk een compleet type ontstaan waarop evaluatie mogelijk is. Dat wil zeggen, een type waarop de inferentie ::Type is toegestaan. Hiertoe breiden we Apply uit met een extra specialisatie en introduceren we een hulpfunctie Concat.

 

Binding

Waar het tot C++ 11 nog slechts mogelijk was om binaire functies te binden kunnen we nu functies van willekeurige ariteit binden met std::bind. De introductie van variadische templates speelde een cruciale rol in de realisatie hiervan. Dat ditzelfde principe nu ook te realiseren valt op metafuncties is dan ook geen verrassing.

 

We laten het als uitdagende oefening over aan de lezer om bovenstaande code uit te breiden voor geneste bind expressies.

Slotwoord

Na al deze bootstrapping moge het duidelijk zijn dat de mogelijkheden van deze functionele programmeertaal binnen C++ net zo onbegrensd zijn als andere functionele programmeertalen. In tegenstelling tot andere functionele programmeertalen echter, bestaan alle constructies alleen gedurende compilatie en dus zijn template metaprogramming oplossingen per definitie globaal stateless.

Statelessness wordt in andere functionele programmeertalen ofwel opgegeven, dan wel verhuld door gebruik te maken van monades. Het voert voor nu te ver om hier in detail op in te gaan. Mogelijk komen we hier in een toekomstige blogpost nader op terug. Voor nu zou ik willen afsluiten met een opmerkelijke eigenschap van default template argumenten. Beschouw de volgende code:

 

Blijkbaar zijn we zelfs met alleen incomplete types in staat om functionele operaties uit te voeren. Jammer genoeg kunnen we default template argumenten niet gebruiken op partiële template specialisaties. We zouden dan immers alle voorgaande bootstrapping kunnen vereenvoudigen tot alleen maar incomplete types; op de uiteindelijke evaluatie (concretisering) na.

De C++ standaard is hier duidelijk over: 14.5.5/8: "The template parameter list of a specialization shall not contain default template argument values." De bijbehorende voetnoot getuigt mijns inziens dan ook slechts van een gebrek aan fantasie: "There is no way in which they could be used."