This code implements sort of an unary counter:

class Elem( size_t mynumber) {
  Elem!( mynumber +1)* next;
}
void main(){
  auto unaryCounter= new Elem!0;
}

Although only `Elem!0' has to be instantiated dmd 2.060 on
windows shouts:
  Error: template instance Elem!(500u) recursive expansion

This is the reason for the subject. Because:

a) Instantiability is decidable
Why does the compiler stop with the evaluation at that randomly
choosen and apparently hard coded value of 500 recursive
expansions?

b) Instantiability is not decidable
Why does the compiler even try to instantiate more than the
indeed needed type `Elem!0'?

I miss the rationale for this behaviour.

-manfred

On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:
> a) Instantiability is decidable
> Why does the compiler stop with the evaluation at that randomly
> choosen and apparently hard coded value of 500 recursive
> expansions?

You are right, it is just an arbitrary limit, but useful to give the user at least somewhat useful diagnostics instead of just hitting a stack overflow eventually.

> b) Instantiability is not decidable
> Why does the compiler even try to instantiate more than the
> indeed needed type `Elem!0'?

The other types _are_ needed to be known (e.g. for TypeInfo generation, and generally because the fields are always typed internally). You might be confusing this with knowing the _size_ of Elem!(n + 1) when calculating the size of Elem!(n) due to the recent discussion, which is indeed not necessary.

David

On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:
> a) Instantiability is decidable
> Why does the compiler stop with the evaluation at that randomly
> choosen and apparently hard coded value of 500 recursive
> expansions?

It's not decidable. Consider use of static if. It's Turing complete. I can give an example if you like.


> b) Instantiability is not decidable
> Why does the compiler even try to instantiate more than the
> indeed needed type `Elem!0'?
>
> I miss the rationale for this behaviour.

As David says, it's needed for TypeInfo etc.

On 11/11/12 06:49, Peter Alexander wrote:
> On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:
>> a) Instantiability is decidable
>> Why does the compiler stop with the evaluation at that randomly
>> choosen and apparently hard coded value of 500 recursive
>> expansions?
> 
> It's not decidable. Consider use of static if. It's Turing complete. I can give an example if you like.
> 

I'd like.  An example might help me better understand why it's
undecidable.
[snip]

On Sunday, 11 November 2012 at 13:40:45 UTC, evansl wrote:
> On 11/11/12 06:49, Peter Alexander wrote:
>> On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:
>>> a) Instantiability is decidable
>>> Why does the compiler stop with the evaluation at that randomly
>>> choosen and apparently hard coded value of 500 recursive
>>> expansions?
>> 
>> It's not decidable. Consider use of static if. It's Turing complete. I
>> can give an example if you like.
>> 
>
> I'd like.  An example might help me better understand why it's
> undecidable.
> [snip]

Collatz sequence.

struct Collatz(int n)
{
    enum next = n % 2 == 0 ? n / 2 : 3 * n + 1;
    Collatz!(next)* foo;
}

It's an unsolved problem in mathematics whether or not this instantiates an infinite number of templates.

David Nadlinger wrote:

>> a) Instantiability is decidable
> an arbitrary limit, but useful

I doubt the usefullness of any value `v' ( here  `v == 500') because the recursive definition might come to an end at value `v +1'. Especially in the case, that the coder knows of such a limit, the limit should be adjustable---but an option for adjusting the limit is missing.

>> b) Instantiability is not decidable
> The other types _are_ needed to be known
It is useless to force the compiler to know anything about a type for which the instantiability is not decided---and it is a prerequisite, that the instantiability is not decidable.

If the coder doesn't know the instantantiability either or simply wants the compiler to stop at some point with the expansions, the language should give the coder an oportunity to declare those points.

For example: an attribute named `Undecided' can be used to express such a declaration in the example given in the OP:

class Elem( size_t mynumber) {
  Undecided( Elem!( mynumber +1)*) next;
}

Where the attribute `Undecided( T)' replaces `T' until its instantiation by a type with similar meaning as "NaN" or `null', for example `TypeWithUndecidedExistence' or `TWUE'. Of course: although `TWUE' has `typeinfo' etc., `TWUE' poisons every type constructing operation by that the result is again `TWUE'

-manfred

On 11/11/2012 03:45 PM, Peter Alexander wrote:
> On Sunday, 11 November 2012 at 13:40:45 UTC, evansl wrote:
>> On 11/11/12 06:49, Peter Alexander wrote:
>>> On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:
>>>> a) Instantiability is decidable
>>>> Why does the compiler stop with the evaluation at that randomly
>>>> choosen and apparently hard coded value of 500 recursive
>>>> expansions?
>>>
>>> It's not decidable. Consider use of static if. It's Turing complete. I
>>> can give an example if you like.
>>>
>>
>> I'd like.  An example might help me better understand why it's
>> undecidable.
>> [snip]
>
> Collatz sequence.
>
> struct Collatz(int n)
> {
>      enum next = n % 2 == 0 ? n / 2 : 3 * n + 1;
>      Collatz!(next)* foo;
> }
>
> It's an unsolved problem in mathematics whether or not this instantiates
> an infinite number of templates.

The possible inputs are finite, so the property is decidable.

On Sun, 11 Nov 2012 19:37:45 +0100
Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 11/11/2012 03:45 PM, Peter Alexander wrote:
> >
> > Collatz sequence.
> >
> > struct Collatz(int n)
> > {
> >      enum next = n % 2 == 0 ? n / 2 : 3 * n + 1;
> >      Collatz!(next)* foo;
> > }
> >
> > It's an unsolved problem in mathematics whether or not this instantiates an infinite number of templates.
> 
> The possible inputs are finite, so the property is decidable.

Technically, yea, but I think upwards of ~4 billion template instantiations is quite unrealistic, to the point of being effectively undecidable.

On Sunday, 11 November 2012 at 20:40:35 UTC, Nick Sabalausky wrote:
>> The possible inputs are finite, so the property is decidable.
>
> Technically, yea, but I think upwards of ~4 billion template
> instantiations is quite unrealistic, to the point of being effectively
> undecidable.

My thoughts exactly. Using the template system in this way looks like abuse rather than being practical. There must be alternative methods to get the same results for whatever you may be attempting.

What we could do is set a practical limit of some default number. 500 appears to be the default limit right now, although in reality without an official written spec we have nothing specific to expect and rely on.

I do agree with manfred that the limit is arbitrary and there may be a few valid use cases where the number should be user adjustable.

--rt

On 11/11/2012 09:40 PM, Nick Sabalausky wrote:
> On Sun, 11 Nov 2012 19:37:45 +0100
> Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> On 11/11/2012 03:45 PM, Peter Alexander wrote:
>>>
>>> Collatz sequence.
>>>
>>> struct Collatz(int n)
>>> {
>>>       enum next = n % 2 == 0 ? n / 2 : 3 * n + 1;
>>>       Collatz!(next)* foo;
>>> }
>>>
>>> It's an unsolved problem in mathematics whether or not this
>>> instantiates an infinite number of templates.
>>
>> The possible inputs are finite, so the property is decidable.
>
> Technically, yea, but I think upwards of ~4 billion template
> instantiations is quite unrealistic, to the point of being effectively
> undecidable.
>

Undecidability has a precise definition in theoretical computer science. It means that there is no algorithm that implements the given predicate. It is a lot stronger than impracticality of implementation.

I claim that the following, very simple algorithm decides whether or not the template above terminates instantiation without errors with the given parameter:

bool collatzTerminates(int n){ return true; }

Therefore, a conforming D compiler implementation could evaluate the template above lazily.