Wzorce w C++ są Turing-Complete

tech • 278 słów • 2 minuty czytania

Wzorce języka C++ spełniają wszystkie założenia maszyny Turinga. Przemyślenia i próby udowodnienia tego sformułowania można znaleźć w pracy “C++ Templates are Turing Complete” autorstwa Todda L. Veldhuizena.

Małą ciekawostkę na temat limitów we 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; […]

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 ;)

Dlatego, aby dobrze wyważyć skomplikowanie kodu do czasu jego kompilacji przy wykorzystywaniu 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:

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

Komentarze (2)

lmmilewski avatar
lmmilewski
20081214-155321-lmmilewski

Dobry wpis ;-)

Warto też wspomnieć o wspaniałej książce “Nowoczesne projektowanie w C++”, autor stworzył również bibliotekę Loki.

Jakiś czas temu również pisałem o tym na blogu. Opisałem wtedy jak napisać na szablonach program generujący zbiór Mandelbrota.

Malcom avatar
Malcom
20081214-182708-malcom

Książka Alexandresca fajna, zdarza mi się do niej czasem zerkać, ale jakoś nigdy nie znalazłem czasu, aby ją całą “przerobić”.

Dodaj komentarz

/dozwolony markdown/

/nie zostanie opublikowany/