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

Od Petr Zemek, 2009-03-26

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) { }
Obsah tohoto pole je soukromý a nebude veřejně zobrazen.

Filtrované HTML (využíváno)

  • Povolené HTML značky: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <table>
  • Zvýraznění syntaxe kódu lze povolit přes následující značky: <code>, <blockcode>, <bash>, <c>, <cpp>, <haskell>, <html>, <java>, <javascript>, <latex>, <perl>, <php>, <python>, <ruby>, <rust>, <sql>, <text>, <vim>, <xml>, <yaml>.
  • Řádky a odstavce se zalomí automaticky.
  • Webové a e-mailové adresy jsou automaticky převedeny na odkazy.
CAPTCHA
3 + 1 =
Vyřešte tento jednoduchý matematický příklad a vložte výsledek. Např. pro 1+3 vložte 4.
Nějak se mi tady rozmohl spam, takže poprosím o ověření.

Díky za velmi zajímavý příspěvek, to, že C++ šablony jsou Turing-complete jsem už někde zaslechl, ale nikdy nic konkrétnějšího (a ani jsem to nikdy ani zdaleka nevyužil). Na léto (či někdy jindy) mám připravenu knihu Moderní programovaní v C++, takže doufám, že se tam toho dozvím více. Jinak ještě malé rýpnutí: místo toho, že HP není rozhodnutelný bych spíš preferoval formulaci, že je nerozhodnutelný (některým lidem se ten rozdíl může zdát důležitý ;-) ).

Jo, ta kniha je fajn a člověk z ní získá úplně jiný pohled na využití šablon :). Jen je škoda, že v českém překladu tam překládali i zdrojové kódy...

K tomu HP: Já jsem formulaci, že HP je nerozhodnutelný (schválně, tj. přemýšlel jsem nad tím) nepoužil proto, protože existuje ještě částečná rozhodnutelnost a HP je právě částečně rozhodnutelný. A tudíž někteří lidé věří (a já k nim zatím patřím, dokud mě někdo nepřesvědčí o opaku), že je "správnější" říct, že HP není rozhodnutelný, než že je nerozhodnutelný. Takže tak :).