Opened 7 years ago
Closed 6 years ago
#16676 closed defect (fixed)
Cardinality of infinite sets loops forever
Reported by: | defeo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | sets infinite_loop |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This was reported in Ask question http://ask.sagemath.org/question/23467.
Most operations on Sets have their cardinality()
method defined by
return len(list(self))
This obviously fails on infinite sets which Sage does not know of:
sage: Set(ZZ).difference(Set()).cardinality()
Change History (12)
comment:1 Changed 7 years ago by
comment:2 follow-up: ↓ 3 Changed 7 years ago by
Looping forever is always a bug in my opinion. The class Set_object_difference
knows in advance that the loop is not going to stop when the first set is infinite, thus it could avoid the computation. This only solves the first layer of the problem, though.
Obviously the problem is undecidable. A properly designed system should only start the enumeration when it knows the set is finite. This is best implemented with three-way logic, a topic that resurfaces often in discussion threads.
The semi-decidable algorithm could still be run by a call to is_finite(try_hard=True)
, then Set_object_difference
could be smart and run it only when self.__X.is_finite(try_hard=True)
returns true.
However this would require a thorough redesign of the Set
API, which I do not have time to start right now. I was merely reporting the bug for reference.
By the way, the fix you suggest would clash on the following bug of is_finite()
:
sage: Set(ZZ).difference(Set()).is_finite() ... RuntimeError: maximum recursion depth exceeded while calling a Python object
This is a different problem and an easy fix, though, as long as we agree that False
means "I don't know".
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 7 years ago by
This is a different problem and an easy fix, though, as long as we agree that
False
means "I don't know".
I do not agree.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 7 years ago by
Replying to vdelecroix:
This is a different problem and an easy fix, though, as long as we agree that
False
means "I don't know".I do not agree.
Me neither. So I guess someone must step up and add three-way logic to the Set API. A grep for Unknown
in Sage src shows three-way logic is used almost nowhere inside Sage, and certainly not in sets.
comment:5 in reply to: ↑ 4 Changed 7 years ago by
This is a different problem and an easy fix, though, as long as we agree that
False
means "I don't know".I do not agree.
Me neither. So I guess someone must step up and add three-way logic to the Set API. A grep for
Unknown
in Sage src shows three-way logic is used almost nowhere inside Sage, and certainly not in sets.
Sage (for now) says True
only if we know for sure it is true, otherwise False
. One would have to have a discussion on sage-devel otherwise - and of course that is a long thing to implement. The problem is, among others, that lots of symbolic expressions might or might not be zero, and the question is how much computation to invest in trying to discern this...
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 6 years ago by
Hello,
Actually, it is "solved" in #18159 as
sage: X = Set(QQ) sage: Y = Set(Primes()) sage: B = Set(X.difference(Y)) sage: B.cardinality() Traceback (most recent call last): ... NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of all prime numbers: 2, 3, 5, 7, ... not yet implemented
... (needs review) ...
comment:8 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-6.7
comment:9 follow-up: ↓ 11 Changed 6 years ago by
- Milestone changed from sage-6.7 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
Now #18159 is closed and we will have
sage: Set(ZZ).difference(Set()).cardinality() +Infinity sage: Set(QQ).difference(Set(ZZ)).cardinality() NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of elements of Integer Ring not yet implemented
I suggest to close this ticket as won't fix. Or do you think it is worth to add a doctest for these?
Vincent
comment:10 Changed 6 years ago by
I do not think a doctest is needed. I'll compile #18159 as soon as I have a little spare time, and close this ticket if everything looks ok.
comment:11 in reply to: ↑ 9 Changed 6 years ago by
- Status changed from needs_review to positive_review
sage: Set(ZZ).difference(Set()).cardinality() +Infinity sage: Set(QQ).difference(Set(ZZ)).cardinality() NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of elements of Integer Ring not yet implemented
Perhaps we should start adding parentheses in those error messages. Something like
computation of cardinality of (Set-theoretic difference of Set of elements of Rational Field) and (Set of elements of Integer Ring) not yet implemented.
But then we would eventually end up with the more lisp-looking message
computation of cardinality of (Set-theoretic difference of Set of elements of (Rational Field)) and (Set of elements of (Integer Ring)) not yet implemented.
Sigh... :-P
Nathann
comment:12 Changed 6 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Hi,
This is not a bug. Deciding if an iterator is finite is semi-decidable and I do not want that because only half of the answer is known we do not give it a try. There are many problems which are known to be undecidable (like equality of symblolic stuff, or the word problem in fg groups). But it is worth it to design the best algorithm that answer most of the cases.
One way to "fix" this non-problem would be to through a warning before we start the enumeration:
Vincent