Semantics of ==

[Axel Boldt]

Erik Max Francis <max at alcyone.com> wrote
> Axel Boldt wrote:

> >   >>> l=[1]
> >   >>> s=l
> >   >>> l.append(s)
> >   >>> w=[1]
> >   >>> r=[1,w]
> >   >>> w.append(r)
> >   >>> s
>  [1, [...]]
> >   >>> w
>  [1, [1, [...]]]
> >   >>> s==w
> >   True

> If you try running through the
> element-wise algorithm that Python uses to determine equality of lists,
> you'll see that they are in fact equal at this point.

I couldn't find that algorithm in the language reference, only in 5.9:
"Tuples and lists are compared lexicographically using comparison of
corresponding elements. This means that to compare equal, each element
must compare equal and the two sequences must be of the same type and
have the same length."

That definition doesn't seem to fully specify equality of list values:
to determine whether s==w, I first note that they both have length 2
and both have 1 as their first element, the second element of s is a
pointer to s, the second element of w is a two-element list, with
first element 1 and second element a pointer to w. So now I have to
determine whether s is equal to the two element list with first
element 1 and second element a pointer to w. They both have two
elements, they both share the first element 1, the second element of s
is a pointer to s, the second element of the other list is a pointer
to w. Now I'm back where I started: I have to test whether s==w. So
the definition in the language reference is circular and both
conclusions s==w and s!=w are consistent with it. I hope that the
actual result received, i.e. s==w, is not implementation dependent?

It now appears to me that there are four levels of equality in Python:

a is b => pickle.dumps(a)==pickle.dumps(b) => repr(a)==repr(b) => a==b

and none of the arrows can be reversed in general. I suppose I had
naively assumed the last three to be equivalent. Is there a string
function analogous to pickle.dumps or repr which only takes values
into account, not internal structure? Such a function could be useful
for hashing the values of mutables.

Axel