Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 13/11/12 06:51, Rob T wrote: On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic wrote: On 11/12/12, Andrej Mitrovic andrej.mitrov...@gmail.com wrote: On 11/12/12, Don Clugston d...@nospam.com wrote: Yeah. Though note that 1000 bug reports are from bearophile. Actually only around 300 remain open: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Oh wait, that's only for DMD. It's 559 in total: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Issue 8990 and 6969, both related to this thread and unresolved, are not in the list, so I suspect there's a lot more missing too. PS: I could not figure out how to make a useful report using that bug report tool either. --rt I recommend deskzilla lite. D is on its list of supported open-source projects. It maintains a local copy of the entire bugzilla database, so you're not restricted to the slow and horrible html interface.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/13/12, Don Clugston d...@nospam.com wrote: I recommend deskzilla lite. D is on its list of supported open-source projects. It maintains a local copy of the entire bugzilla database, so you're not restricted to the slow and horrible html interface. Wow, I had no idea they had this. I've added a note about it here: http://prowiki.org/wiki4d/wiki.cgi?D__Tutorial/BugReports Thanks!
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Tue, 13 Nov 2012 11:56:57 +0100 Don Clugston d...@nospam.com wrote: I recommend deskzilla lite. D is on its list of supported open-source projects. It maintains a local copy of the entire bugzilla database, so you're not restricted to the slow and horrible html interface. Awesome! I wish GitHub had something like that. (Hell, I wish every web app had something like that.) Although, $189 for anything with 2k issues or anything non-OSS? Geez that's expensive, what are they, Adobe?
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 10/11/12 08:53, Rob T wrote: On Saturday, 10 November 2012 at 06:09:41 UTC, Nick Sabalausky wrote: I've gone ahead and filed a minimized test case, and also included your workaround: http://d.puremagic.com/issues/show_bug.cgi?id=8990 I didn't make that one struct nested since that's not needed to reproduce the error. Thanks for filing it. Looking at the bug reports, there's 2000+ unresolved? Yikes. --rt Yeah. Though note that 1000 bug reports are from bearophile.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Yeah. Though note that 1000 bug reports are from bearophile. Well, at least he's persistent. -- Using Opera's revolutionary email client: http://www.opera.com/mail/
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/12/12, Don Clugston d...@nospam.com wrote: Yeah. Though note that 1000 bug reports are from bearophile. Actually only around 300 remain open: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophilecomponent=DMDproduct=D
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/12/12, Andrej Mitrovic andrej.mitrov...@gmail.com wrote: On 11/12/12, Don Clugston d...@nospam.com wrote: Yeah. Though note that 1000 bug reports are from bearophile. Actually only around 300 remain open: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Oh wait, that's only for DMD. It's 559 in total: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic wrote: On 11/12/12, Andrej Mitrovic andrej.mitrov...@gmail.com wrote: On 11/12/12, Don Clugston d...@nospam.com wrote: Yeah. Though note that 1000 bug reports are from bearophile. Actually only around 300 remain open: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Oh wait, that's only for DMD. It's 559 in total: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Issue 8990 and 6969, both related to this thread and unresolved, are not in the list, so I suspect there's a lot more missing too. PS: I could not figure out how to make a useful report using that bug report tool either. --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic wrote: On 11/12/12, Andrej Mitrovic andrej.mitrov...@gmail.com wrote: On 11/12/12, Don Clugston d...@nospam.com wrote: Yeah. Though note that 1000 bug reports are from bearophile. Actually only around 300 remain open: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile Oh wait, that's only for DMD. It's 559 in total: http://d.puremagic.com/issues/buglist.cgi?query_format=advancedemailreporter2=1emailtype2=substringorder=Importancebug_status=UNCONFIRMEDbug_status=NEWbug_status=ASSIGNEDbug_status=REOPENEDbug_status=VERIFIEDemail2=bearophile NM, you were talking about bugs reported by bearophile. Back to sleep ... --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/13/12, Rob T r...@ucora.com wrote: PS: I could not figure out how to make a useful report using that bug report tool either. You will need to register, and then use this page: http://d.puremagic.com/issues/enter_bug.cgi?product=D Then select a component (usually DMD, druntime, or Phobos). D2 is selected by default, all that's left is to write a summary and description. You can also click on Show Advanced Fields (top left), and in the Keywords field (way down) you can add things like accepts-invalid, or rejects-valid. The list of keywords is here: http://d.puremagic.com/issues/describekeywords.cgi
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Nick Sabalausky wrote: *but* head and tail are merely pointers to node Thank you. I do recognize now, that my flow of thought stopped at the same point at which the flow of control of the compiler stopped. -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Timon Gehr wrote: In theory yes, but [...] What a pity. Because in the code given only the types Elem!0 and Elem!1 must be indeed initialized. The fact, that the specification of the template describes a family of types with an infinite number of members should not force the front end to check wether all those members are initializable. If the executable is not allowed to build new types, which seems to be canonically, it is sufficient for the front end to check the initializability of those members, for which an initialization is imperative. This polishes my claim in digitalmars.D.learn:40939. For me now it appears as a bug, when the front end assumes, that the executable is allowed to build new types. -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Nick Sabalausky wrote:
I really don't see the relevance
Please look at the definition of R:
struct R
{
int value;
d_list!R Rlist;
}
If no recursion was wanted the OP should have written:
d_list!(R*) Rlist;
In digitalmars.D.learn:40990 I already asked for an explanation.
-manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Rob T wrote: and the problem I'm experiencing is definitely a compiler bug I do not see that. Please work on my messages digitalmars.D.learn:40990 and digitalmars.D.learn:40991. -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Nick Sabalausky wrote: But the OP was never trying to do anything like that. See digitalmars.D.learn:40991 -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Sat, 10 Nov 2012 10:33:39 + (UTC)
Manfred Nowak svv1...@hotmail.com wrote:
Nick Sabalausky wrote:
I really don't see the relevance
Please look at the definition of R:
struct R
{
int value;
d_list!R Rlist;
}
If no recursion was wanted the OP should have written:
d_list!(R*) Rlist;
Ok, I see what you're saying, but you're mistaken: That line d_list!R
Rlist; is not a problematic recursion.
Imagine if d_list had been defined like this:
struct d_list(T)
{
int i;
}
Then would this still be problematic recursion?:
struct R
{
d_list!R Rlist;
}
No, because R is never actually used anywhere in that d_list (only
int is used). In this case, R is nothing more that part of the *name* of
a particular instantiation of the d_list template.
And indeed, just like the above example, the OP's definition of d_list
also does *not* use R:
struct d_list( T )
{
node* head;
node* tail;
}
Now, yes, that node type does use R (instead of R*), *but* head
and tail are merely pointers to node, so it's ok.
In digitalmars.D.learn:40990 I already asked for an explanation.
Actually, my newsreader is kinda shitty, and (AFAIK) doesn't give me
any way to lookup a message by ID, so I'm not really sure which message
you're referring to :/
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/10/2012 10:12 AM, Manfred Nowak wrote: Timon Gehr wrote: In theory yes, but [...] What a pity. Because in the code given only the types Elem!0 and Elem!1 must be indeed initialized. ... In this specific case, yes. But as this is an undecidable property in general, detecting and exploiting it would merely be an optimization that cannot generally be relied upon. Depending on how powerful it is, it would slow down analysis most of the time. Furthermore, I do not see use cases. I'll look into it when the front end is finished though.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Timon Gehr wrote: But as this is an undecidable property in general I do not see, that the compiler has to solve the general case--- at least when compiling monolithic code and the executable is only allowed to use types which are initialized at compile time. Upon using several modules the modules might follow some restrictions and I am currently not able to specify that restrictions. -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/09/12 23:45, Timon Gehr wrote: On 11/09/2012 10:24 PM, Philippe Sigaud wrote: Timon: The D front end I am developing can already handle it. Developed in D, I suppose? Yes. Public? License? URL? artur
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Nick Sabalausky wrote: So ok: s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ recursion here./ That's one correection only. Several more are to come. Sorrily no one seems to have recognized this sentence in digitalmars.D.learn:40918: Because `R' can recurse infinitely over `Ancor' a mooring and a way to that mooring is needed. In regex-parlor this meens, that `( R!Ancor!)*' is the type the compiler should be able to handle according to the template definitions given. But the compiler currently can only handle types with a finite length of description on instantiation. For me it is in doubt that this restriction can be declared as a bug. -manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Friday, 9 November 2012 at 14:04:26 UTC, Manfred Nowak wrote: Nick Sabalausky wrote: So ok: s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ recursion here./ That's one correection only. Several more are to come. Sorrily no one seems to have recognized this sentence in digitalmars.D.learn:40918: Because `R' can recurse infinitely over `Ancor' a mooring and a way to that mooring is needed. In regex-parlor this meens, that `( R!Ancor!)*' is the type the compiler should be able to handle according to the template definitions given. But the compiler currently can only handle types with a finite length of description on instantiation. For me it is in doubt that this restriction can be declared as a bug. -manfred I'm not sure if you commented on why the non-templated version compiled. Since it does compile as I expected it would, it means that the templates operate in another dimension from what I was expecting, i.e., there's two languages in D, one for templates and another for non-temnplate code. My understanding of D from what I read, was that templates are supposed to work in the same way as regular code. The (T) is only there to introduce a type, so that code can be reused over multiple types. What is happening however, is that the templates are not doing what would be expected if the type was introduced manually, and to me this is plain wrong, or at best very unfortunate for D. --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/09/2012 02:17 PM, Manfred Nowak wrote: Rob T wrote: The above template definitions define exactly the same structure as the original No, they implement not _exactly_ the same structure, because they supply more freedom than the original templates version. The original version forced a recursion onto every implementation, whereas this new templates version allows non-recursive implementations. It might be helpfull to reintroduce the forced recursion using the new template definitions. Hint: start with | alias d_list!node00 d_list00; | d_list00 var; and publish whether it is possible to compile this line: | alias R!d_list00 R0; -manfred The example definitely exposes a bug in DMD. The D front end I am developing can already handle it.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Timon: The D front end I am developing can already handle it. Developed in D, I suppose?
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Timon Gehr wrote:
The example definitely exposes a bug in DMD.
The D front end I am developing can already handle it.
May I guess, that your front end is also able to handle this code:
struct Elem( size_t myNumber) {
Elem!( myNumber +1)* next;
}
void main(){
Elem!0 list;
list.next= new Elem!1;
}
-manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/09/2012 10:32 PM, Manfred Nowak wrote:
Timon Gehr wrote:
The example definitely exposes a bug in DMD.
The D front end I am developing can already handle it.
May I guess, that your front end is also able to handle this code:
struct Elem( size_t myNumber) {
Elem!( myNumber +1)* next;
}
void main(){
Elem!0 list;
list.next= new Elem!1;
}
-manfred
In theory yes, but it takes a long time and uses a lot of memory,
especially on a 64 bit build. This is a very different example from the
OT's though.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/09/2012 10:24 PM, Philippe Sigaud wrote: Timon: The D front end I am developing can already handle it. Developed in D, I suppose? Yes.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Friday, 9 November 2012 at 21:32:01 UTC, Manfred Nowak wrote:
Timon Gehr wrote:
The example definitely exposes a bug in DMD.
The D front end I am developing can already handle it.
May I guess, that your front end is also able to handle this
code:
struct Elem( size_t myNumber) {
Elem!( myNumber +1)* next;
}
void main(){
Elem!0 list;
list.next= new Elem!1;
}
-manfred
With the unmodified template as posted, I get a very specific
error about recusive expansion, but I can see why using that
form of template - it will expand into multiple types forever
Elem!(0), Elem!(1), Elem!(2) ... Elem!(infinity).
Now take note that with the modified code below, it works fine,
and exactly as I would expect:
struct Elem(T) {
Elem* next;
}
My attempt to mess up the compiler did not succeed, the code
below still compiles as expected.
struct Elem(T) {
Elem!(T)* next;
}
If it works above, then it should also work with the code I
introduced in the OP because it's the exact same scenario, only
much more simplified. The type expansion should stop at the
pointers, and the error message indicates that it does (there's
no recursive expansion message), but it fails to evaluate all the
types correctly (forwarded reference message).
I think this example clears the matter up nicely, and the problem
I'm experiencing is definitely a compiler bug. I'd like to see
this problem resolved, so I'll file a bug report.
BTW, thanks for all the attention to this matter, I've learned a
lot more about D templates, such as the recusivness of templates
demonstrated by manfred, and the dialogue in here helped me to
find a reasonable work-a-round for my particular application.
--rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 20:57:42 + (UTC) Manfred Nowak svv1...@hotmail.com wrote: Rob T wrote: What is happening however, is that the templates are not doing what would be expected if the type was introduced manually The expectations might be wrong. With Templates one is able to introduce recursive definitions of types into the type system. As with recursive functions, the feedom, thereby generated, can introduce relaxation as well as strain. One is indeed *able* to do that with templates, but the OP never actually did so, so I really don't see the relevance.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Friday, 9 November 2012 at 20:57:42 UTC, Manfred Nowak wrote: Rob T wrote: What is happening however, is that the templates are not doing what would be expected if the type was introduced manually The expectations might be wrong. With Templates one is able to introduce recursive definitions of types into the type system. As with recursive functions, the feedom, thereby generated, can introduce relaxation as well as strain. -manfred I agree that you can introduce recursive definitions into a template, and you have demonstrated that ability rather well, however the definitions in my template does not do this, and so far I have not seen a demonstration of how it could be doing so. The type expansion is definitely finite, there's several posts following through with the expansion, and they all show that the compiler must stop expanding at the pointers. All of the pointers are of a known finite size (standard pointer type) and the type they represent for dereferencing is definitely knowable. The problem appears to be with the compiler failing to evaluate all of the type definitions fully, and as a result it inappropriately fails with a forwarded reference error. I've seen a somewhat related problem with functions that return auto. If the body conatins something that needs to know the return value, the compiler may fail with a forwarded reference error. There's absolutely no valid reason why the compiler should be doing this, and it exposes a weakness in the way it does type evaluations (in at least that case). On the other hand, I've seen the compiler do very good work evaluating out-of-order type definitions that are all over the place. If I'm to take the D specification (what little of it there is) at face value, out-of-order type definitions are always perfectly legal provided that they are legal definitions of course, so when the compiler fails on them, then it's a bug that needs to be fixed. --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 14:04:26 + (UTC)
Manfred Nowak svv1...@hotmail.com wrote:
Sorrily no one seems to have recognized this sentence in
digitalmars.D.learn:40918:
Because `R' can recurse infinitely over `Ancor' a mooring and a way
to that mooring is needed.
In regex-parlor this meens, that `( R!Ancor!)*' is the type the
compiler should be able to handle according to the template
definitions given.
But the compiler currently can only handle types with a finite length
of description on instantiation. For me it is in doubt that this
restriction can be declared as a bug.
But all of the OP's types *do* have a finite length of description.
I do understand what you are trying to doing with the mooring (although
I admit I wasn't familiar with the word mooring until this
discussion), and I definitely understand what that technique is used
for. But it's not relevant to the OP's example, as he's not trying to
do anything that for which that mooring is actually needed.
Note that the following structs do NOT require mooring and *already*
work perfectly fine with DMD:
struct S1 { S1* s; }
struct S2(T) { S2!(T)* s; }
Those work perfectly fine, even once you actually instantiate S2. The
OP's example follows the same pattern as those.
If, OTOH, there had been something like this:
struct S3(T) { S3!(S3)* s; }
Then *that* would require the mooring you described. But the OP was
never trying to do anything like that.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
If anyone is interested, here's my current work-a-round ...
// original code that fails ...
struct R
{
int value;
d_list!R Rlist;
}
// d-linked list with templated payload
struct d_list( T )
{
struct node
{
T payload;
node* pred;
node* succ;
}
node* head;
node* tail;
}
// modified code that works ...
// no changes made
struct R
{
int value;
d_list!R Rlist;
}
// definition moved out of d_list
struct node( T )
{
T payload;
node* pred;
node* succ;
}
// Added default type N = node!(T)
struct d_list( T, N = node!(T) )
{
N* head;
N* tail;
}
Thanks again for all your help!
--rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Sat, 10 Nov 2012 06:29:02 +0100 Rob T r...@ucora.com wrote: If anyone is interested, here's my current work-a-round ... // original code that fails ... [...] // modified code that works ... [...] Thanks again for all your help! I've gone ahead and filed a minimized test case, and also included your workaround: http://d.puremagic.com/issues/show_bug.cgi?id=8990 I didn't make that one struct nested since that's not needed to reproduce the error.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Saturday, 10 November 2012 at 06:09:41 UTC, Nick Sabalausky wrote: I've gone ahead and filed a minimized test case, and also included your workaround: http://d.puremagic.com/issues/show_bug.cgi?id=8990 I didn't make that one struct nested since that's not needed to reproduce the error. Thanks for filing it. Looking at the bug reports, there's 2000+ unresolved? Yikes. --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Manfred Nowak wrote:
or `T' itself must take the lead.
`T' was given as:
| struct R
| {
| int value;
| d_list!R Rlist;
| }
... and using the given changes as well as D-parlor `T' becomes:
| struct R {
| int value;
| Ancor!R list;
| }
Because `R' can recurse infinitely over `Ancor' a mooring and a way
to that mooring is needed. Let the mooring be, when there are no more
`Ancor' to expect, i.e. the way to that mooring leads from some
height down to zero.
That means `R' has to know its height. `R' roughly becomes:
| struct R( int height) {
| int value;
| Ancor!R( height-1) list;
| }
That describes the way. Of course the mooring is still missing:
| struct R( int height)
| if( height 0) {
| int value;
| Ancor!R( height-1) list;
| }
| struct R( int height)
| if( height = 0) {
| int value;
| }
That's it. Only missing some testing:
import std.stdio: writeln;
void main(){
alias R!(1) First;
First elem;
elem.value= 1;
writeln( elem);
alias Ancor!First.Node Node;
Node n;
n.payload= elem;
n.pred= null;
n.succ= null;
writeln( n);
alias Ancor!First Ancor1;
Ancor1 ancor;
ancor.head= n;
ancor.tail= n;
writeln( ancor);
}
-manfred
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thursday, 8 November 2012 at 20:39:29 UTC, Manfred Nowak wrote:
Manfred Nowak wrote:
or `T' itself must take the lead.
`T' was given as:
| struct R
| {
| int value;
| d_list!R Rlist;
| }
... and using the given changes as well as D-parlor `T' becomes:
| struct R {
| int value;
| Ancor!R list;
| }
Because `R' can recurse infinitely over `Ancor' a mooring and a
way
to that mooring is needed. Let the mooring be, when there are
no more
`Ancor' to expect, i.e. the way to that mooring leads from some
height down to zero.
That means `R' has to know its height. `R' roughly becomes:
| struct R( int height) {
| int value;
| Ancor!R( height-1) list;
| }
That describes the way. Of course the mooring is still missing:
| struct R( int height)
| if( height 0) {
| int value;
| Ancor!R( height-1) list;
| }
| struct R( int height)
| if( height = 0) {
| int value;
| }
That's it. Only missing some testing:
import std.stdio: writeln;
void main(){
alias R!(1) First;
First elem;
elem.value= 1;
writeln( elem);
alias Ancor!First.Node Node;
Node n;
n.payload= elem;
n.pred= null;
n.succ= null;
writeln( n);
alias Ancor!First Ancor1;
Ancor1 ancor;
ancor.head= n;
ancor.tail= n;
writeln( ancor);
}
-manfred
I still don't follow what you are trying to point out.
I use this form of structure in real world applications, and they
work just fine as-is.
If you mean by 'anchor' a way to end the recursion, that's a
trivial problem already solved - the recursion ends when the list
is empty. Of course I've left out the associated logic that does
the necessary work, since that is not relevant to the problem at
hand and clutters the issue.
No matter if there's merit to what you are describing, or not,
the structure as-is should be legally definable as a template. In
fact, I can define the structure just fine provided that I do not
use a template.
--rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thursday, 8 November 2012 at 21:15:17 UTC, Manfred Nowak wrote: Rob T wrote: In fact, I can define the structure just fine provided that I do not use a template. .. and if one uses a template one can get an infinite recursion, because templates include recursion. This is the case in your code. The code I gave elimates that infinite recursion. The code compiles although it uses a template. Not seeing e recursion does not mean that there is none. Not every recursion is as simple to see as: | alias X Y; | alias Y X; -manfred I think I'm starting to understand what you are doing, however we're operating on two separate planes of existence. What you are describing, is a different structure than what I want. The template creates two separate struct types for R, one with a list and one without (R1 R2), but I want only one type R, otherwise it will introduce a ton of complications in the form of me having to make just about eveything that uses these two different structures a template and/or duplicated overloaded functions. Perhaps I just don't understand the in's and out's of D templates, but it's just not doing what I want. So is there a way to retain identical struct types for R by disabling the not-so-useful-in-my-case template recursion? --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thu, 08 Nov 2012 22:46:46 +0100 Rob T r...@ucora.com wrote: So is there a way to retain identical struct types for R by disabling the not-so-useful-in-my-case template recursion? There is no template recursion in your code (you have *exactly* 3 concrete types even after all template instantiations), see my reply to Manfred.
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thursday, 8 November 2012 at 21:47:55 UTC, Nick Sabalausky wrote: It is *not* the case in his code. He has three actual instantiated structs: R -- 1. int value (4 bytes) 2. d_list!R Rlist (size: TBD) d_list!R -- // **JUST POINTERS** 1. (d_list!R).node* head (4 bytes, assuming -m32) 2. (d_list!R).node* tail (4 bytes, assuming -m32) (d_list!R).node -- 1. (d_list!R)* outer (4 bytes, assuming -m32) 2. R payload (size: TBD) 3. (d_list!R).node* (4 bytes, assuming -m32) 4. (d_list!R).node* (4 bytes, assuming -m32) What other concrete types are there? *None*. Just those three. Now, let's expand *all* of the aggregate value types: R -- 1. int value (4 bytes) 2. d_list!R Rlist (size: 8 bytes) 2.1. (d_list!R).node* head (4 bytes, assuming -m32) 2.2. (d_list!R).node* tail (4 bytes, assuming -m32) Total: 4+8 == 12 bytes d_list!R -- // *JUST POINTERS* 1. (d_list!R).node* head (4 bytes, assuming -m32) 2. (d_list!R).node* tail (4 bytes, assuming -m32) Total: 4+4 == 8 bytes (d_list!R).node -- 1. (d_list!R)* outer (4 bytes, assuming -m32) 2. R payload (size: 12 bytes) 2.1. int value (4 bytes) 2.2. d_list!R Rlist (size: 8 bytes) 2.2.1. (d_list!R).node* head (4 bytes, assuming -m32) 2.2.2. (d_list!R).node* tail (4 bytes, assuming -m32) 3. (d_list!R).node* (4 bytes, assuming -m32) 4. (d_list!R).node* (4 bytes, assuming -m32) Total: 4+12+4+4 == 24 bytes Now there are NO MORE aggregate types left to be expanded, and ALL 3 types have an exact, FINITE size. There *IS NO RECURSION* here. Nice description! You have described *exaclty* how I expected the template evaluations to work their way out. I'm very much interested in learning how manfred understands the process will unfold. It could be that the template system simply does not operate as we expect, which IMO would be unfortunate because it will describe a system somewhat unrelated to actual coding (a problem C++ templates are infamous for), or that it is a manifestation of the problem where the out-of-order instantiations are not being evaluated in a way that works for all *legal* cases, which in that case can be considered a bug, esp since D is supposed to allow for out-of-order definitions. Even when we remove the templates, it was noted that it can still fail if the node struct is defined inside the list, but that situation should be easily resolvable. So it seems we have at least one bug, and possibly two, or one bug and a template system that works as expected, but operates in a different dimension. --rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thu, 08 Nov 2012 23:28:05 +0100 Rob T r...@ucora.com wrote: It could be that the template system simply does not operate as we expect, which IMO would be unfortunate because it will describe a system somewhat unrelated to actual coding (a problem C++ templates are infamous for), or that it is a manifestation of the problem where the out-of-order instantiations are not being evaluated in a way that works for all *legal* cases, which in that case can be considered a bug, esp since D is supposed to allow for out-of-order definitions. Historically, DMD tended to have a lot of trouble actually resolving forward references according to spec (perhaps due to it's C/C++ roots?). Most of big glaring problems have been fixed since then, but unfortunately there's still a number of edge cases yet to be ironed out. It *is* possible to construct types in a way that is inherently ambiguous, and cannot be correctly handled by the compiler even in theory. So naturally those cases will end up being forward reference, or perhaps more accurately circular definition. But your example is definitely not such a case, so however the compiler is currently processing it, it needs to be fixed. FWIW, you should be able to work around the issue by making some of the pointers void*. You'll lose some type safety and have to remember to cast things correctly, but it should at least make it compile (although I haven't tried it).
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/9/12, Nick Sabalausky seewebsitetocontac...@semitwist.com wrote:
FWIW, you should be able to work around the issue by making some of the
pointers void*. You'll lose some type safety and have to remember to
cast things correctly, but it should at least make it compile (although
I haven't tried it).
Perhaps another possible workaround is to use 'alias this'.
struct R
{
struct Data
{
int value;
}
Data data;
alias data this;
d_list!Data Rlist;
}
May not work in all cases though..
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Interestingly, this is a workaround that may be workable somehow.
I've even been able to expand it so that the R.value type is
determined by a temnplate.
struct node( P )
{
P payload;
node* pred;
node* succ;
}
struct R( V )
{
V value;
alias node!R N;
d_list!N Rlist;
}
struct d_list( N )
{
N* head;
N* tail;
// even this works
ref typeof(N.payload) getFirstValue(){
return head.payload;
}
}
--rt
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 01:17:09 + (UTC)
Manfred Nowak svv1...@hotmail.com wrote:
Nick Sabalausky wrote:
ALL 3 types have an exact, FINITE size.
There *IS NO RECURSION* here.
This conclusion is wrong. Otherwise one can conclude that `s' is not
recursing on itself in this code:
struct S{ S* next;}
S s;
s.next= s;
... because `s' has a fixed and finite size.
Wait a minute, are you or are you not saying that the OP's original
example is impossible (due to recursion)?
Because struct S{ S* next;} is *not* an example of an impossible data
structure. It works perfectly fine because of the indirection
introduced by the pointer. The OP's original example is also perfectly
possible for the same reason reason as struct S{ S* next;}.
There are two forms of recursion that can render a type impossible:
// Recursive data layout:
struct S
{
int i; // -- Seed
S s; // -- Kaboom!
}
Or:
// Recursive symbols (impossible in D, not sure about ML):
alias S!int Foo; // -- Light the fuse...
struct S(T)
{
S!(typeof(this))* s; // -- Kaboom!
}
Neither of those two bad recursions occur in the OP's original
example. It only has the perfectly benign struct S{ S* next;} form of
recursion. So the OP is using a perfectly legit, perfectly feasible
data structure. DMD just happens to mishandle it and then chokes.
So ok:
s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ recursion here./
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
There is clearly no recursion in the struct, it terminates at the
pointers, therefore it is of finite and knowable size during
compile time.
R looks like this if value is int
dlist!R = struct{ struct*, struct* }
R = struct{ int, struct{ struct*, struct* } }
node!R = struct{ struct{ int, struct{ struct*, struct* } },
struct*, struct* }
The the structs are now fully defined.
I will argue that there's actually no recursion in the definition
when the definition is looked at from the POV of what the
compiler should be seeing.
struct R =
{
int = int; // STOP
d_list!R =
{ node!(R)* = pointer; // STOP
node!(R)* = pointer; // STOP
} // STOP d_list is now 100% defined
We still need to know what node!R is in order to dereference the
node!(R)* pointers inside d_list.
struct node!(R) =
{
R = R; // STOP, R is fully defined already.
node* = pointer; // STOP
node* = pointer; // STOP
} // STOP node!(R) is 100% defined.
We now know the size and contents of R, d_list!R, and node!R, and
we have all the information required to dereference the pointers
properly.
How is the recursion in the definition stoping the compiler from
doing its job?
Finally, take note that this altenate recursive definition
compiles and works as expected:
struct node( P )
{
P payload;
node* pred;
node* succ;
}
struct R( V )
{
V value;
alias node!R N;
d_list!N Rlist;
}
struct d_list( N )
{
N* head;
N* tail;
// even this works
ref typeof(N.payload) getFirstValue(){
return head.payload;
}
}
The above template definitions define exactly the same structure
as the original, it's just done in a different way, by supplying
the entire node definition to the d_list instead of just the
payload type.
Why should this version work and not the other?
--rt
