Can a Python data structure reference itself?

By Vasudev Ram

As part of some Python work, I was tinkering with the built-in globals() function of Python, when I noticed this:

>>> g = globals()
>>> g
{'a': 'A', 'A': 'C', 'C': 4, 'b': 'a', 'g': {...}, '__builtins__': <
module '__builtin__' (built-in)>, 'k': '__doc__', '__package__': None, '__name__
': '__main__', '__doc__': None}
>>> # The variable g seems to have got stored inside of itself!
>>> id(g)
31298152L
>>> id(globals())
31298152L
>>> g['g'] == g
True
>>> g['g']['g'] == g
True
>>> g['g']['g']['g'] == g
True
>>> id(g['g']['g']['g']) == id(g)
True

The above does make a kind of sense, when you remember that the globals() function returns a dict representing the current global symbol table, i.e. all the currently defined attributes (objects) in the global scope.

So when I said g = globals(), the variable g got created in the global scope; so when I next print g, it should contain g itself, i.e. g (a list) contains itself as a list item (of g).

But on further thought, it seems like this should depend on the order of the evaluation of the statement g = globals():

Case 1) If the variable g is created first (and hence the global symbol table now contains it), and if only after that is the globals() function called, and its return value assigned to g, then things should work as shown in the above interpreter output.

Case 2) But if the evaluation works in a different order, i.e. the globals() function is first called (before the variable g is created), then at this point its return value (the dict) should not contain the item with key 'g' (and value g), and it is this dict that should get assigned to the variable g. Hence when we print g, we should not see g again within it.

Considering the above output, it seems like Case 1 is what actually happens. Also, I realized that if the globals() function is returning a copy of the dict that represents the global state, the above output should not work. But it seems to be returning the original dict itself, as shown by this:

>>> id(g) == id(globals())
True

To explore this further, I thought of trying to create a similar self-referential structure, but without using globals():

lis = []
lis.append(1)
print 'lis:', lis
print 'id(lis):', id(lis)
lis.append(lis)
print 'lis:', lis
print 'id(lis):', id(lis)
print 'id(lis[1]):', id(lis[1])
print lis == lis[1]
print lis[1] == lis[1][1]

And the output again seems to indicate that the list lis now references itself, that is, contains itself as an item.

I then thought of testing my Python function to flatten an arbitrarily nested list, with the above definition of lis, as the input argument. As expected, it terminated with a run-time error about recursion limit exceeded. See the post linked in the previous sentence for the flatten function - and some variations on it, in the comments on that post.

I'll write more about this in a following post, after fixing the flatten function to handle this case. On first thought, the fix seems straightforward: at any level in the recursion, check if id(lis) == id(lis[i]) - for any i, and if so terminate with an error about this being a self-referential list - but I'll write and test it first, then blog the results.

The more interesting question is whether this is a known Python feature, or an undocumented one (seems unlikely), or a bug (unlikely), and also whether similar behavior exists in other languages. Interested to hear what others think / know about this.

Update:

I looked in the official Python Language Reference, at the Section 3. Data model:

https://docs.python.org/2/reference/datamodel.html

and saw this excerpt:

[ CPython implementation detail: CPython currently uses a reference-counting scheme with (optional) delayed detection of cyclically linked garbage, which collects most objects as soon as they become unreachable, but is not guaranteed to collect garbage containing circular references. ]

Not sure whether it is relevant to the topic at hand, since, on the one hand, it uses the words "cyclically linked", but on the other, it says "garbage collection".

The image at the top of the post is of an ouroboros, which is "ancient symbol depicting a serpent or dragon eating its own tail", according to Wikipedia. Sort of appropriate, I guess, because Python :)

- Vasudev Ram - Online Python and Linux training and programming

Dancing Bison Enterprises

Signup to hear about new products or services that I create.

Posts about Python  Posts about xtopdf

Contact Page

Share |