Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)

Nick Sabalausky SeeWebsiteToContactMe at semitwist.com
Thu Nov 8 18:13:57 PST 2012


On Fri, 9 Nov 2012 01:17:09 +0000 (UTC)
Manfred Nowak <svv1999 at 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./



More information about the Digitalmars-d-learn mailing list