Exchanging the actual subtrees (crossover.subtree)

[cgarcia-UCO]

The problem

crossover.subtree.do_crossover looked for the exchanging subtrees by means of method index (lines 279, 293, 307, and 308). However, the instruction pX.children.index(tX) returned the index of the subtree with the same content (I suppose that for which Tree.eq returns True), but perhaps that is not the right subtree.

Example:

p0.children = ['whatever_1', 'Yes', 'whatever_2', 'Yes'] t0 = p0.children[3] # i.e. str(0) == 'Yes'

p0.children.index(t0) # this returns 1, but the actual index of t0 is 3

Implications

Since the trees are not exchanging the right subtrees, the new trees share nodes. But not nodes with the same content, but actually the same objects in memory. The problem is that subsequent modification in Tree A may produce modifications in another expected independent Tree B, because they share the same node-objects.

Final comment

I am not sure if this is significant in other problems (/ grammars / linear operators / ...). It was in my case, since I am using some operators for prunning the trees in the context of classification with decision trees (a grammar similar to the if_else_classifier.bnf). In particular, due to the interaction between my prunning operators and the aforementioned fact, I was getting some trees that did not point to their parents, which actually contained them in property children, and viceversa, some trees pointing to parent nodes that did not contained them in property children. In case it was interesting, I noticed that Tree B changed when changing A, afterwards I noticed that there were trees sharing the same objects, and finally, I detected that behaviour in the method index.

Best regards.

[jmmcd]

Thanks @mfjoneill for checking it out!