>>>>> "CT" == Christian Tismer <tismer@tismer.com> writes:
CT> Vladimir Marangozov wrote:
>> While I'm at it, maybe the same recursion control logic could be
>> used to remedy (most probably in PyObject_Compare) PR#7:
>> "comparisons of recursive objects" reported by David Asher?
CT> Hey, what a good idea.
CT> You know what's happening? We are moving towards tail recursion.
CT> If we do this everywhere, Python converges towards Stackless
CT> Python.
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.
I have tried to come up with a solution in the same style as the repr
solution. repr maintains a list of objects currently being repred.
If it encounters a recursive request to repr the same object, it just
prints "...". (There are better solutions, but this one is fairly
simple.) I always get hung up on a cmp that works this way because at
some point you discover a recursive cmp of two objects and you need to
decide what to do. You can't just print "..." :-).
So the real problem is defining some reasonable semantics for
comparison of recursive objects. I checked what Scheme and Common
Lisp, thinking that these languages must have dealt with the issue
before. The answer, at least in Scheme, is infinite loop. R5RS
notes: "'Equal?' may fail to terminate if its arguments are circular
data structures. "
http://www-swiss.ai.mit.edu/~jaffer/r5rs_8.html#SEC49 For eq? and eqv?, the answer is #f.
The issue was also discussed in some detail by the ANSI commitee
X3J13. A summary of the discussion is at here:
http://www.xanalys.com/software_tools/reference/HyperSpec/Issues/iss143-writeup.html The result was to "Clarify that EQUAL and EQUALP do not descend any
structures or data types other than the ones explicitly specified
here:" [.both descend for cons, bit-vectors, and strings; equalp has
some special rules for hashtables and arrays]
I believe this means that Common Lisp behaves the same way that Scheme
does: comparison of circular data structures does not terminate.
I don't think an infinite loop is any better than a core dump. At
least with the core dump, you can inspect the core file and figure out
what went wrong. In the infinite loop case, you'd wonder for a while
why your program doesn't terminate, then kill it and inspect the core
file anway :-).
I think the comparison ought to return false or raise a ValueError.
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:
Object equality is not a concept for which there is a uniquely
determined correct algorithm. The appropriateness of an equality
predicate can be judged only in the context of the needs of some
particular program.
So, in the end, I propose ValueError.
Jeremy