View mode: basic / threaded / horizontal-split · Log in · Help
November 10, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 20:57:42 +0000 (UTC)
Manfred Nowak <svv1999@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.
November 10, 2012
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
November 10, 2012
Re: Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
On Fri, 9 Nov 2012 14:04:26 +0000 (UTC)
Manfred Nowak <svv1999@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.
November 10, 2012
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
November 10, 2012
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" <rob@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.
November 10, 2012
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
November 10, 2012
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
November 10, 2012
Re: Recursive data structure using template won't compile
Rob T wrote:

> I want to create a simple recursive data structure as follows:
> 
> struct R
> {
>     int value;
>     d_list!R Rlist;
> }

I do not see any usage for the member `d_list!R Rlist'.

Please explain.

-manfred
November 10, 2012
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
November 10, 2012
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
1 2 3 4 5 6 7
Top | Discussion index | About this forum | D home