View mode: basic / threaded / horizontal-split · Log in · Help
November 11, 2012
Is instantiabilty of templated types decidable?
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
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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.
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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]
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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.
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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.
November 11, 2012
Re: Is instantiabilty of templated types 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.
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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
November 11, 2012
Re: Is instantiabilty of templated types decidable?
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.
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home