New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve handling of finite iterables #24757
Comments
comment:1
Why is the finiteness so important? For me, an iterable is just an iterable. Trying to figure out the length of arbitrary iterables is not possible, so why bother? |
comment:2
There's been lots of debate about this in the Python community in the past. Of course finiteness is important. If you do something like |
comment:3
Replying to @embray:
What's your point? If the user writes bad code, then bad things can happen. That's a basic axiom of programming. We don't "protect" the user from running
Of course, it can often be nice to check the input given by the user. That's what exceptions are for. But here we have the problem that we want to accept certain input where we cannot a priori determine whether it's good (finite) or bad (infinite). So there are two "solutions":
|
comment:4
The problem with iterators, and especially generators, is that their behavior can be extremely obscured. If you have an explicit This discussion led in part to the creation of Of course, given some arbitrary code it's impossible to know if it will always terminate, but there are definitely common cases where we can do better than nothing.
Like what? Also, I'll note, there are lots of places in my Python 3 branch where for now I just accept arbitrary iterables where it's possible to. But this is a concession to the fact that there's often no better way to check finiteness. The point of this ticket was to talk about adding some simple checks for common cases. E.g. if it were possible with the |
comment:5
Replying to @embray:
Generators. |
comment:6
I'm not sure what you mean. I'm not proposing anything that would break using arbitrary generators. Though it's a shame Python doesn't provide a way to attach a length hint to generators--or at least something along the lines of "this is expected to terminate". |
comment:7
Replying to @embray:
OK, then what are you proposing? I don't understand anymore... Maybe you should give a concrete example of some bad iterable that you want to catch. |
comment:8
I'm not proposing anything specific here. This ticket is intended mostly for brainstorming. I think it does matter whether or not an iterable is finite, but the problem is much of Python doesn't seem to care and I'm wondering out loud if there's anything we can do to improve that situation for places where it matters. I see it as a quality issue... |
comment:9
Thanks for the clarification. Still, I don't really what could be done. Surely, the problem cannot be solved for all iterables because of the Halting Problem. And there are almost no cases where an iterable is known to be infinite. So either you know that it's finite or you don't know anything. I think that we should always assume the best and treat the unknown cases as finite. So you end up with zero information. |
comment:10
Related: #13556 |
comment:11
Obviously we can't always say with absolute certainty that some calculation will terminate, but when implementing iterators, even generators, we can say "this should terminate". |
comment:12
Just to give an example, say iterables had some flag on them like Then, for example, a I get your point that if we said "okay, this function will reject any inputs that don't have Anyways, this isn't necessarily a problem that Sage alone can solve. |
comment:13
Replying to @embray:
OK, now I understand what you mean. This one sentence explains everything. Still, that sounds like something for a PEP, not something that Sage can fix. |
comment:14
It seems to me that a wholesale replacement of these new (py3-only) iterators (e.g. filter()) by iterables (e.g. lists) is not a good idea, as it prevents potential performance optimisations. Why not just wrapping them with list() or tuple() instead? It is much less work, and it does not remove the opportunity to optimise later on, if desired. |
comment:16
See also https://bugs.python.org/issue33939 |
comment:17
Interesting. I'm curious, how did you stumble on that? |
There is a general problem throughout much of Sage where code checks if some argument is a
list
ortuple
(e.g.isinstance(x, (list, tuple))
) where really it should be able to accept any argument which, depending on the context, implements either theSequence
protocol, or even just theIterable
protocol.This especially becomes a problem on Python 3 where common built-ins like
map()
andfilter()
now return lazily-evaluated iterators instead oflist
s.In many cases we've addressed this by replacing
map
/filter
calls with list comprehensions and that works fine. But really also ought to make many of these interfaces more flexible in what types they accept.For some cases simply replacing
(list, tuple)
withSequence
is sufficient (basically, this is any object that implements__iter__
as well as__len__
and__getitem__
). Unfortunately, there are other cases where we don't need the fullSequence
protocol, and in fact would like to take any iterable (likemap
).The problem with the latter case is that in most cases what we really want is finite iterables. We don't want to write code that can be passed an infinite generate and hang. To some extent this is the user's responsibility but we should try as much as possible to prevent it. If an iterable implements
__len__
then no problem, butmap
andfilter
do not (since they can wrap any iterable(s), finite or not).An even bigger problem is that Python's interface does not allow us to easily introspect
map
orfilter
to see if the iterable's they're wrapping are finite. In some sense there's no general way to do this with certainty, if you have arbitrarily nested iterables (though I feel that that's a shortcoming in Python). But for most cases we should be able to check if amap
orfilter
is finite by looking directly at the iterable(s) they were passed as arguments, so it might be nice to have a C-level helper for that.Component: python3
Issue created by migration from https://trac.sagemath.org/ticket/24757
The text was updated successfully, but these errors were encountered: