MalDevBlog

Wzorce języka C++ spełniają wszystkie założenia maszyny Turinga.

Przemyślenia i próby udowodnienia powyższego sformułowania można znaleźć w pracy „C++ Templates are Turing Complete” autorstwa Todd L. Veldhuizen.

Małą ciekawostkę na temat limitów w wzorcach możemy znaleźć na końcu artykułu:

[...] the C++ standards committee allows conforming compilers to limit the depth of „recursively nested template instantiations,” with a recommended minimum limit of 17. Compilers have adopted this limit, many with an option to increase it.

This limit does not translate into any reliable time or space bound on compiles, though; it is straightforward to construct C++ programs which instantiate k^17 templates (i.e. within the recommended limit) for any arbitrarily large k; [...]

Poniżej przykład wzorca (pochodzący z w/w dokumentu) z k=5, który wygeneruje 5^17 = 762 939 453 125 instancji wzorca:

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;

Kompilacja tego kodu może być długa i męcząca :P

Aby dobrze wyważyć skomplikowanie kodu do czasu jego kompilacji w kontekście wykorzystania wzorców, należy dogłębnie poznać tajniki i idiomy programowania i metaprogramowania z ich wykorzystaniem.

Na stronie autora w/w dokumentu dowodzącego kompletności Turinga dla wzorców, można znaleźć kilka ciekawych artykułów poruszających wykorzystanie wzorców w programowaniu:

• Template Metaprograms
• Expression Templates
• C++ Templates as Partial Evaluation

Zgromadzone tam informacje mogą okazać się bardzo przydatne dla początkujących adeptów sztuki metaprogramowania i wykorzystania wzorców, natomiast średniozaawansowanym zapewne będą znane przedstawione tam techniki, triki i idiomy.