List/Map in Structure - recursion error

[milan1612]

Code: Select all

Structure Tree
  somedata.i
  List children.Tree() ; or Map
EndStructure

Line 3: Can't do it, it would cause endless recursivity.

Besides the wrong term being used here (it's recursion, not recursivity) I can't really spot the error.

The children list is a list, not a Tree. It's not a recursive structure, unless you initialize the list
and add children to it. The list itself is just a pointer. So why is this prohibited Fred?

[netmaestro]

You can't do anything with a structure containing a dynamic object without first doing InitializeStructure() on it. Once you do that, the list is created automatically for you. In this case, list after endless list as each level of the structure contains a new instance of the object. The error message is correct here as such logic is untenable.

[srod]

Not sure I agree with you there Netmaestro. I don't think that InitializeStructure() is required for a structure variable (only pointers pointing to a chunk of dynamic memory require it etc.)

But even having the list created, the list is empty and so the recursion would not seem to enter into it. I just don't see the recursion any where?

As strange a thing as this is, I'm not sure that it should be flagged as an error; unless PB is simply not intended to support this of course?

[STARGÅTE]

@milan1612
http://www.purebasic.fr/german/viewtopi ... =8&t=22177
i use this code for a childs ...

[netmaestro]

@srod, I know but the InitializeStructure happens on a structured var without the programmer typing it. It doesn't matter if the list is empty, it's an object that exists and even with no elements it uses some memory. This code is endlessly recursive and if an error weren't flagged it would eat all the available memory up in about one second and then hang.

[srod]

I cannot agree in that I see no recursion in this case. Sure, if a structure field which isn't a pointer references the same structure then we indeed have infinite recursion. The same is not true of a pointer field and, in a sense, that is what we have here. The field in question is essentially a pointer to a list.

If I initilaise a structure variable which contains a list then some memory would be reserved for the list. But that is all that happens. I can then add an element to the list and memory for the underlying structure is set aside and placed into the list. This new memory contains a pointer to a new list. I see no recursion.

[netmaestro]

I cannot agree

Sure you can, you're just not trying. You're focusing on semantics here, the point is that if this code were to be allowed to run it would make new lists (or pointers, whatever) until it ran out of memory. How is that good for anything?

[srod]

Guess I am thinking how I would implement this feature in a compiler and, honestly, I see no problem. In my own linked list library I have done this kind of thing without a problem, but then it was all done with pointers. I'd have a structure with a linked list object embedded and within this list I would hold pointers to identical structures, each with their own similar lists. This would never lead to any kind of recursion because lists were added only as required after the individual structues were added and these lists would, in many cases, just sit empty, as they would with Milan's example.

A compiler which implemented lists in this way would be able to work this kind of thing through without any recursion. Of course, a poorly designed program could then instigate the worst case of recursion, but this would be through no fault of the structure definition itself, but through sloppy coding. In principle, a structure defined as Milan has listed above should not need to result in either the compiler or the generated code entering an infinite loop. I am not saying that this will not be the case, but it is dependant on the compiler etc. and is by no means an absolute.

A structure holding a field of the same structure type will lead to infinite recursion - that is an absolute. My point is that it need not be the case with linked lists. It just depends upon the implementation.

[freak]

The limitation was put in place because of arrays. They are dim'ed to the specified number of elements and the elements are initialized on creation, so this would lead to infinite recursion.

Lists and maps are created with zero elements though, so the limit could be removed there.

[milan1612]

Lists and maps are created with zero elements though, so the limit could be removed there.

Absolutely. That would greatly simplify working with tree structures

[srod]

The limitation was put in place because of arrays. They are dim'ed to the specified number of elements and the elements are initialized on creation, so this would lead to infinite recursion.

Lists and maps are created with zero elements though, so the limit could be removed there.

Ah yes, that makes sense.

[Kiffi]

Lists and maps are created with zero elements though, so the limit could be removed there.

Absolutely. That would greatly simplify working with tree structures

+1

Greetings ... Kiffi

[NicTheQuick]

Lists and maps are created with zero elements though, so the limit could be removed there.

Absolutely. That would greatly simplify working with tree structures

+1

[Fred]

Removed for List and Map.

[milan1612]

Removed for List and Map.

Thanks a lot!