digitalmars.D - Is instantiabilty of templated types decidable?
- Manfred Nowak (20/20) Nov 11 2012 This code implements sort of an unary counter:
- David Nadlinger (10/17) Nov 11 2012 You are right, it is just an arbitrary limit, but useful to give
- Manfred Nowak (24/28) Nov 11 2012 I doubt the usefullness of any value `v' ( here `v == 500')
- Peter Alexander (4/12) Nov 11 2012 It's not decidable. Consider use of static if. It's Turing
- evansl (4/13) Nov 11 2012 I'd like. An example might help me better understand why it's
- Peter Alexander (9/25) Nov 11 2012 Collatz sequence.
- Timon Gehr (2/25) Nov 11 2012 The possible inputs are finite, so the property is decidable.
- Nick Sabalausky (5/19) Nov 11 2012 Technically, yea, but I think upwards of ~4 billion template
- Rob T (14/19) Nov 11 2012 My thoughts exactly. Using the template system in this way looks
- Timon Gehr (10/29) Nov 11 2012 Undecidability has a precise definition in theoretical computer science....
- Nick Sabalausky (18/47) Nov 11 2012 I'm not disagreeing with that. But when the question is "Should the
- Manfred Nowak (5/6) Nov 12 2012 ... it is ncurrently ot the duty of the compiler to decide what
- Nick Sabalausky (6/16) Nov 12 2012 I didn't really mean to claim that it was or wasn't (I can see
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
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
David Nadlinger wrote: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.a) Instantiability is decidablean arbitrary limit, but usefulIt 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' -manfredb) Instantiability is not decidableThe other types _are_ needed to be known
Nov 11 2012
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
On 11/11/12 06:49, Peter Alexander wrote:On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:I'd like. An example might help me better understand why it's undecidable. [snip]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.
Nov 11 2012
On Sunday, 11 November 2012 at 13:40:45 UTC, evansl wrote:On 11/11/12 06:49, 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.On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:I'd like. An example might help me better understand why it's undecidable. [snip]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.
Nov 11 2012
On 11/11/2012 03:45 PM, Peter Alexander wrote:On Sunday, 11 November 2012 at 13:40:45 UTC, evansl wrote:The possible inputs are finite, so the property is decidable.On 11/11/12 06:49, 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.On Sunday, 11 November 2012 at 12:33:25 UTC, Manfred Nowak wrote:I'd like. An example might help me better understand why it's undecidable. [snip]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.
Nov 11 2012
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:Technically, yea, but I think upwards of ~4 billion template instantiations is quite unrealistic, to the point of being effectively undecidable.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
On Sunday, 11 November 2012 at 20:40:35 UTC, Nick Sabalausky wrote: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. --rtThe 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
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: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.On 11/11/2012 03:45 PM, Peter Alexander wrote:Technically, yea, but I think upwards of ~4 billion template instantiations is quite unrealistic, to the point of being effectively undecidable.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
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: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.On Sun, 11 Nov 2012 19:37:45 +0100 Timon Gehr <timon.gehr gmx.ch> wrote: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.On 11/11/2012 03:45 PM, Peter Alexander wrote:Technically, yea, but I think upwards of ~4 billion template instantiations is quite unrealistic, to the point of being effectively undecidable.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
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
On Mon, 12 Nov 2012 08:46:42 +0000 (UTC) Manfred Nowak <svv1999 hotmail.com> wrote:Nick Sabalausky wrote: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.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