Recursive nested instantiations don't make sense to me

Hi,

From an interesting article regarding C++ as a Turing Machine, I have found some code that I totally do not understand. It is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<int Depth, int A, typename B>
struct K17
{
	static constexpr 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<2, A, B>
{
	static constexpr int x = 1;
};


static constexpr int z = K17<0, 0, int>::x;


Now this seems to me a sure stack overflow. I (probably incorrectly) understand the code similar to the following runtime recursive call:

1
2
3
4
5
6
7
8
9
10
11
12
int f(int depth, int a, int m)
{
	if (depth == 2)	return 1;

	return f(depth + 1, 0, f(depth, a, m)) +
		f(depth + 1, 1, f(depth, a, m));
}

int main()
{
  autor ret = f(0,0,1);
}


And the execution of main above gives a compiler stack overflow as expected. Compilation of the template code does not give stack overflow in Visual Studio 2017 15.5.2, but rather for values greater than 8 (the recursive stop) gives out of heap memory. The fact that it does not give stack overflow does not make sense to me. Maybe I am understanding what is going on incorrectly and my runtime function is not at all equivalent to the compile template code.

Any insights greatly appreciated!!

Regards,
Juan Dent
Unless K17<Depth,A,B> is not evaluated... after all we do not ask for its x value!

??

Yes.
There is no requirement here that K17<Depth,A,B> must be a completely defined type.

Implicit instantiation
When code refers to a template in context that requires a completely defined type, or when the completeness of the type affects the code, and this particular type has not been explicitly instantiated, implicit instantiation occurs.
http://en.cppreference.com/w/cpp/language/class_template
Registered users can post here. Sign in or register to post.