www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is instantiabilty of templated types decidable?

reply Manfred Nowak <svv1999 hotmail.com> writes:
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
Nov 11 2012
next sibling parent reply "David Nadlinger" <see klickverbot.at> writes:
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
Nov 11 2012
parent Manfred Nowak <svv1999 hotmail.com> writes:
David Nadlinger wrote:

 a) Instantiability is decidable


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


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
Nov 11 2012
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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.
Nov 11 2012
parent reply evansl <cppljevans suddenlink.net> writes:
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]
Nov 11 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Nov 11 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Nov 11 2012
parent Manfred Nowak <svv1999 hotmail.com> writes:
Nick Sabalausky wrote:

 tell the user he's using an impractical approach

... it is ncurrently ot the duty of the compiler to decide what a practical approach might be. Therefore the coder has to notify this to the compiler. -manfred
Nov 12 2012
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
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.
Nov 11 2012
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
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.
Nov 11 2012
prev sibling next sibling parent "Rob T" <rob ucora.com> writes:
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
Nov 11 2012
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 12 Nov 2012 00:46:06 +0100
Timon Gehr <timon.gehr gmx.ch> wrote:

 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'm not disagreeing with that. But when the question is "Should the compiler loop for days trying to instantiate millions, if not billions of types for a design that's flawed and impractical (due to said explosion of type instantiations)?", or something along those lines, then the question of "undecidable versus unrealistic" becomes irrelevent. If there's laziness techniques that can drastically reduce the number of instantiations the compiler actually needs to analyze/create, then fine, but at some point it *still* has a decision to make of "Geez, we've just created hundreds (thousands?) of recursive instantiations, and in at least this particular case we have no fucking idea how many more we might need, should we continue for a ridiculous amount of time/resources, or just tell the user he's using an impractical approach?" When you're facing that judgement call, it really doesn't matter whether that "ridiculous amount of time/resources" is technically finite or not.
Nov 11 2012
prev sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 12 Nov 2012 08:46:42 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:

 Nick Sabalausky wrote:
 
 tell the user he's using an impractical approach

... it is ncurrently ot the duty of the compiler to decide what a practical approach might be. Therefore the coder has to notify this to the compiler. -manfred

I didn't really mean to claim that it was or wasn't (I can see reasonable points on both sides of that). My only point was just that theoretical decidability wasn't really relevant since it's trumped by practical limitations anyway.
Nov 12 2012