Méně známé skutečnosti o C++: šablony jsou Turingovsky úplné

Oproti Java Generics či C# Generics (které jsou vlastně pouze typově parametrizované třídy) jsou šablony v C++ velice mocný nástroj - o tom určitě nikdo nepochybuje. Co se ale ví už méně, tak je to, že tento prvek jazyka C++ je turingovsky úplný (Turing-complete), čili, lidově řečeno, pomocí něj lze vyjádřit libovolný výpočet. Z toho plyne zajímavý důsledek, který bych chtěl uvést v tomto příspěvku.

"Důkaz" toho, že C++ šablony jsou Turingovsky úplné, je uveden v tomto článku. Proč píšu "důkaz" v uvozovkách? Odpověď se nachází hned na začátku článku - je to kvůli tomu, že pro rigorózní důkaz by bylo třeba přesně definovat sémentiku instanciace šablon, což zatím nikdo neudělal. Další potenciální problém může být ten, že standard C++98 umožňuje překladačům omezit hloubku rekurzivního zanoření při instanciaci šablon (minimální limit je 17 zanoření - zajímalo by mě, jak k tomuto číslu dospěli :)), takže ono tvrzení o úplnosti C++ šablon je platné pouze za předpokladu toho, že hloubka instanciace nebude omezena (pro šťouraly: ano, paměť současných počítačů je konečná, tedy hloubka instanciace bude vždy také omezená množstvím paměti, ale v debatách ohledně Turingovské úplnosti se toto zanedbává a model se považuje za Turingovsky úplný tehdy, pokud by měl nekonečnou paměť a byl by Turingovsky úplný).

Této vlastnosti jazyka se využívá v tzv. šablonovém metaprogramování (template metaprogramming), o kterém byla vydána i samostatná kniha, mohutně se využívá v knihovně Blitz pro numerické výpočty a dokonce jsem našel i maďarský kurz (C++ Template Metaprogramming), který je na toto zaměřen. Nalézt lze samozřejmě i spoustu internetových článků, z nichž bych chtěl zmínit alespoň tento, který je nejznámější.

Jaký důsledek tedy ona úplnost má? Pokud budeme uvažovat neomezenou hloubku instanciace šablon, pak není možné sestrojit překladač pro jazyk C++, který by byl pro každý zdrojový kód schopen v konečném čase říct, zda se jedná o platný C++ zdrojový kód :). Redukcí lze snadno dokázat, že pokud bychom byli takoví překladač schopni sestrojit, pak bychom byli schopni vyřešit problém zastavení, což je asi nejznámější problém, který není rozhodnutelný. Jelikož totiž jsou šablony Turingovsky úplné, tak během kompilace se může provádět potenciálně nekonečný program, který nemusí nikdy skončit. Jen si to představte - nemusíte se dočkat konce překladu :).

Pro zajímavost - ve výše uvedeném článku je uveden krátký příklad, při jehož překladu proběhne 5^17 (762 939 453 125) instanciací dané šablony (počítá se v něm s možným limitem 17 zanoření při instanciaci šablon). Schválně si můžete zkusit, kolik hodin potrvá překlad na vašem stroji :).

template<int Depth, int A, typename B>
struct K17 {
    static const int x =
        K17 <Depth+1, 0, K17<Depth,A,B> >::x
        + K17 <Depth+1, 1, K17<Depth,A,B> >::x
        + K17 <Depth+1, 2, K17<Depth,A,B> >::x
        + K17 <Depth+1, 3, K17<Depth,A,B> >:x
        + K17 <Depth+1, 4, K17<Depth,A,B> >::x;
};
 
template <int A, typename B>
struct K17 <16,A,B> {
    static const int x = 1;
};
 
static const int z = K17 <0,0,int>::x;
 
int main(void) { }