Comparison of cyclic objects (was RE: [Python-Dev] trashcan and PR#7)

[Tim Peters]

[Jeremy Hylton]>
> It doesn't seem like tail-recursion is the issue, rather we need to
> define some rules about when to end the recursion.  If I understand
> what is being suggest, it is to create a worklist of subobjects to
> compare instead of making recursive calls to compare.  This change
> would turn the core dump into an infinite loop; I guess that's an
> improvement, but not much of one.
>
> ...
>
> So the real problem is defining some reasonable semantics for
> comparison of recursive objects.

I think this is exactly a graph isomorphism problem, since Python always
compares "by value" (so isomorphism is the natural generalization).

This isn't hard (!= tedious, alas) to define or to implement naively, but a
straightforward implementation would be very expensive at runtime compared
to the status quo.  That's why "real languages" <wink> would rather suffer
an infinite loop.  It's expensive because there's no cheap way to know
whether you have a loop in an object.

An anal compromise would be to run comparisons full speed without trying to
detect loops, but if the recursion got "too deep" break out and start over
with an expensive alternative that does check for loops.  The later requires
machinery similar to copy.deepcopy's.

> ...
> I think the comparison ought to return false or raise a ValueError.

After

   a = []
   b = []
   a.append(a)
   b.append(b)

it certainly "ought to be" the case that a == b in Python.  "false" makes no
sense.  ValueError makes no sense either unless we incur the expense of
proving first that at least one object does contain a loop (as opposed to
that it's just possibly nested thousands of levels deep) -- but then we may
as well implement an isomorphism discriminator.

> I'm not sure which is right.  It seems odd to me that comparing two
> builtin lists could ever raise an exception, but it may be more
> Pythonic to raise an exception in the face of ambiguity.  As the
> X3J13 committee noted:

Lisps have more notions of "equality" than Python 1.6 has flavors of strings
<wink>.  Python has only one notion of equality (conveniently ignoring that
it actually has two <wink>).  The thing the Lisp people argue about is which
of the three or four notions of equality to apply at varying levels when
trying to compute one of their *other* notions of equality -- there *can't*
be a universally "good" answer to that mess.  Python's life is easier here.

in-concept-if-not-in-implementation-ly y'rs  - tim