View mode: basic / threaded / horizontal-split · Log in · Help
November 08, 2012
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" <rob@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.
November 08, 2012
Re: Recursive data structure using template won't compile
On Thursday, 8 November 2012 at 21:50:02 UTC, Nick Sabalausky 
wrote:
> On Fri, 09 Nov 2012 01:26:44 +0400
> Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
>> 
>> Just coming up with an idea how it may fail, not arguing for 
>> it being correct ;)
>
> Right. Point is, it's a compiler bug.

For D, as opposed to C/C++, my understanding was that specifying 
forward references to deal with out-of-order difinitions, or 
situations like the one I'm experiencing, was not required, so I 
have to agree it's a "bug" rather than just a limitation of the 
language and compiler. There's no reason why the compiler should 
fail in either case, other than due to a less-than-adequate 
method of evaluating the different structs.

--rt
November 08, 2012
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
November 08, 2012
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" <rob@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).
November 08, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On 11/9/12, Nick Sabalausky <SeeWebsiteToContactMe@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..
November 08, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Thursday, 8 November 2012 at 23:05:33 UTC, Nick Sabalausky 
wrote:
> 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.

Clearly.

> 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).

The T* pointers don't seem to be the problem, it's the T payload. 
If I switch to T* payload it all works OK, but I'll have to 
perform allocations on each instance of payload which is not 
desirable. I may still get away with it in my case, but I'm very 
concerned that it will start eating up memory needlessly because 
the GC appears to come with a ton of issues yet to be resolved.

--rt
November 09, 2012
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
November 09, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
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.

One way to see the recursion in the problem given is to evaluate the 
exact types of the three entities starting with `(d_list!R).(node!
R)'---yes, `node' is templated implicitely---and yes, not starting 
names of types with upper case might confuse the senses.

Reaching `R' one might see, that
 `typeof( R)'
must be equal to
 `typeof( int x &( R x &( (d_list!R).(node!R))^2)^2 )'

where `T x U' is equívalent to put types `T' and `U' into a record,
     `&T' is an adress of some variabkle of type `T' and
     `T^2' is short hand for `T x T'.

If there is no such `R' for which this equality holds, then recursion 
is not avoidable.

Please guess what I believe.

-manfred
November 09, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 01:17:09 +0000 (UTC)
Manfred Nowak <svv1999@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./
November 09, 2012
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
1 2 3 4 5 6 7
Top | Discussion index | About this forum | D home