On Thursday, 8 November 2012 at 18:45:08 UTC, Manfred Nowak wrote:
> Rob T wrote:
>
>> I want to be clear that I'm trying to define a recursive data structure
> [...]
>> so correct me if there's a reasonable way to get this job done
>
> A recursive data structure needs a mooring ... and such a mooring is
> missing in the code given.
>
> -manfred
>
> 

I'm afraid I don't follow what you mean by mooring and anchor given the example at hand.

The structure as described allows for the implementation of a real-world useful structure, such as a property tree, where a value may have an associated list of sub-values, (recursive) forming a tree of values. The list of associated values is of arbitrary length and a d-list is not necessarily required, so long as it's a list.

This is a simple yet very usefull structure, which I can define apparently legally in D so long as I do not make use of a template. If I can define it legally without a template, then I expected to be able to define it with a template.

Obviously infinite recursive structs cannot be allowed, and dmd does detect these cases. In my case, the struct that implements the list contains nothing but pointers, therefore it should allow for lists of lists, and indeed it does, but only if I do not use templates OR I use templates but also change the payload to be a pointer.

Why the difference in ability to compile as a template vs a non-template if the all of the template structures can be completely resolved into defined states during compile time - just as it would be if I hard coded the same types?

--rt

Before I forget, it is important to note that the structure consists of two parts, the value with a list of associated sub-values, along with the list.

struct R
{
   int value;
   d_list!R Rlist;
}

struct d_list( T )
{
   struct node
   {
      T payload;
      node* pred;
      node* succ;
   }
   node* head;
   node* tail;
}

--rt

On Thu, 08 Nov 2012 19:19:52 +0400
Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:

> 11/8/2012 10:39 AM, Rob T пишет:
> > I want to create a simple recursive data structure as follows:
> >
> > struct R
> > {
> >     int value;
> >     d_list!R Rlist;
> > }
> 
> Not possible - you don't know the size of R at this point. So determine it compiler looks inside of d_list, and then encounters _node_. It naturally sees T which is R and starts this loop anew.
> 

That's incorrect behavior. The size of R is NOT needed to determine the size of "d_list!R":

Note that "d_list!R" has exactly 2 data members, and BOTH of them are pointers. Therefore, the size of "d_list!R" is trivially determined *regardless* of its template parameter or "nested" type: Two pointers == 8 bytes on 32-bit, 16 bytes on 64-bit, *regardless* of what the pointers point to.

Also note that "node" is not actually a *data* member of d_list, and does not contribute to the size or internal structure of d_list.


> To break this chain make node a separate templated struct outside of d_list. Then peeking inside of d_list compiler shouldn't go crazy.
> 

No, I tried that, and it still fails. This is definitely a compiler bug.

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

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

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

11/9/2012 12:35 AM, Nick Sabalausky пишет:
> On Thu, 08 Nov 2012 19:19:52 +0400
> Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
>
>> 11/8/2012 10:39 AM, Rob T пишет:
>>> I want to create a simple recursive data structure as follows:
>>>
>>> struct R
>>> {
>>>      int value;
>>>      d_list!R Rlist;
>>> }
>>
>> Not possible - you don't know the size of R at this point. So
>> determine it compiler looks inside of d_list, and then encounters
>> _node_. It naturally sees T which is R and starts this loop anew.
>>
>
> That's incorrect behavior. The size of R is NOT needed to determine
> the size of "d_list!R":
>
> Note that "d_list!R" has exactly 2 data members, and BOTH of them are
> pointers. Therefore, the size of "d_list!R" is trivially determined
> *regardless* of its template parameter or "nested" type: Two pointers
> == 8 bytes on 32-bit, 16 bytes on 64-bit, *regardless* of what the
> pointers point to.
>
> Also note that "node" is not actually a *data* member of d_list, and
> does not contribute to the size or internal structure of d_list.

Yeah, that's all good and well, I mean that I can calculate the size. But well I'm far smarter then DMD :)

And most like the problem is not size. I was mistaken as it must be template instantiation itself.

Basically:
to analyze R -> inst-te d_list!R ---during which---> (in fact) inst-te node!R ---during which---> inst-te d_list!R -> ...

and d_list!R is not yet ready since we analyze node!R

Now it could probably improve on it to handle this somehow. I dunno how general it can be or special cased it will be.


Now the extra fun - 2 snippets.

First one dies with forward ref.
Probably because inside of node it issues forward reference to R and inside of R forward reference for d_list and it wasn't finished because of node waiting on forward reference to R?
Just coming up with an idea how it may fail, not arguing for it being correct ;)

struct d_list
{
struct node
{
      R payload;
      node* pred;
      node* succ;
}

    node* _head;
    node*  _tail;
}

struct R
{
   int value;
   d_list Rlist;
}

void main(){
	R r;	
}


But this one doesn't.

struct node
{
      R payload;
      node* pred;
      node* succ;
}

struct d_list
{
    node* _head;
    node*  _tail;
}

struct R
{
   int value;
   d_list Rlist;
}

void main(){
	R r;	
}


-- 
Dmitry Olshansky

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

On Thu, 8 Nov 2012 21:15:17 +0000 (UTC)
Manfred Nowak <svv1999@hotmail.com> 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.
> 

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.

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.