[Pitch] Make Collection Super-Convenient and Retire Sequence

Dave's answer quoted below implies that trapping is valid behavior. That would actually be better than an infinite loop IMO.

I don't think so. We are looking for a way to express the precondition that the input must have a size small enough to allow each element to be processed in practice. Several people have made the observation that this precondition is easily satisfied for all instances of container types.

The trouble comes when we want algorithms that process every element to also work with types that produce elements on demand. There isn't a precise way to distinguish 0..<5 from 0..<Int.max at runtime let alone compile time.

I think it is important to distinguish streams like random number generators from streams like user input. The former are able to produce the next element any time a program requests it. The latter have inverted control: the next event is produced and provided to the program when an external event occurs. "Stream" should only have one of these meanings in Swift. The discussion of streams-as-single-pass-sequences clearly implies streams which are able to produce the next element on demand.

This might be considered pedantic, but I think it is more accurate to say something like "the output cannot be repeated unless the stream has value semantics and a copy is made prior to iteration when multiple passes are necessary".

3 Likes

If I understand this correctly, trap here means stack overflow. I don’t see anything you can lift from here into types to get any static analysis support from compiler... I don’t get your point.

See my reply to Erica above. Streams which produce elements on demand are very different from "reactive streams".

1 Like

I see.

I interpret it to mean that if we allow infinite collections and all instances of a given conforming type have infinite elements it would be reasonable to implement count by calling fatalError(). What would be the point of entering an infinite loop in that case?

For the sake of discussion let's consider a protocol ContainedCollection which has a semantic requirement that conforming types must store their elements internally. All of the algorithms that have the finite precondition could instead require Self: ContainedCollection. The compiler obviously cannot verify whether a conformance meets this semantic requirement, but that is true of many semantic requirements. But the fact that the compiler cannot verify this does not mean it is not useful! If that were true we would not need refined protocols such as RandomAccessCollection which exist to encode complexity requirements.

There are very good reasons ContainedCollection is not the design we have but it is certainly possible and sometimes very useful (see RandomAccessCollection) to encode semantic requirements like this.

The one point I can see in its favor is that it doesn’t bring down the other threads in your process.

That might make sense in some cases right now but I think the balance would be strongly in favor of trapping if (when?) we have a concurrency model that includes isolation (something like Swift Concurrency Manifesto ¡ GitHub).

1 Like

Can we stop using “generalized existentials” as excuses to kick the can down the road? Not just to you specifically but i feel like every discussion on swift evolution these days ends with “well there’s no point in doing X until Some Type System Feature arrives”

5 Likes

I don't think so; at least, I never intended to write something like that into law—it can't even be precisely specified. Strictly speaking, there's no need to explicitly document where infinite collections are allowed, given that we document algorithmic complexity. You just expect an O(N) algorithm on an infinite collection not to terminate. Furthermore, I don't think I'd want to outlaw the use of O(N) algorithms on infinite collections. I lost the battle long ago against side-effectful parameters to algorithms like reduce, which is one reason we have .lazy (there are other good reasons too, though). Given that we're not re-litigating that question, I have no problem with someone calling reduce in a thread on a potentially infinite collection of messages from another process, and using its side-effects to do whatever they want.

3 Likes

Fair enough. Should the documentation be updated to reflect this?

There is a difference between not having a problem with a particular use if the design supports it and believing the use case should actually influence the deisgn. IMO the use case you described falls into the former category in this context. Do you believe this use case should actually influence the design (given the constraints on the design space)?

What changes did you have in mind?

Yes, only because it was explicitly decided (before Swift 1) that using these algorithms for their side-effects was legitimate and it is therefore currently and intentionally supported, including on infinite Sequences. Making that use case officially illegal is not something that can happen as a byproduct of other design choices.

Obviously updating the section you mentioned earlier:

Moreover, a collection’s indices form a finite range of the positions of the collection’s elements. The fact that all collections are finite guarantees the safety of many sequence operations, such as using the contains(_:) method to test whether a collection includes an element.

But also updating the documentation for algorithms where it currently says "the sequence must be finite" to both caution against "finite but very large" as well as acknowledge use cases like the ones you described above.

Would you consider a design that doesn't make it illegal but might require small source changes for valid use cases of using these algorithms with infinite sequences / collections?

Not obvious at all; I'm not the one who mentioned it. Of course if we're going to lift restrictions on Collection so as to allow them to be infinite, we'd need to update the documentation accordingly… but that seems so “obvious” :wink: that I think I must be misunderstanding your question.

As for your “design that doesn't make it illegal” I guess that depends on the proposal. I really can't imagine what you have in mind.

1 Like

I'm still working through the details but do have something in mind. I'll try to get far enough to post something in the next few days. I don't believe it has come up in the prior discussions (and am reviewing the previous threads right now).

Just chiming in with the observation that you can't call these things a Stream. That name is already taken by the bridging of NSStream (and NSInputStream and NSOutputStream) in to Swift.

1 Like

Which raises the question..........why on earth was that done? Does anyone still use NSStream? I refactored all my code that used it years ago...

Sorry I wasn't trying to be annoying but I am concerned that a better collection library design would use generalised existentials extensively. In the ideal world many methods like filter, map, or slice would return AnyCollection<T>, which is only possible after type system improvements.

Therefore we would be making changes now onely to have to go back and revisit collection changes again, so my suggestion of sitting on theses changes is to prevent too much churn in everyones code.

I am assuming that generalised existentials will happen soon though, if they are 12 months away then I would go with changes now.

I mostly agree with this. I don't think we should wait to START designing it, but we may want to make the changes all at once, which might mean differing the actual implementation until at least the ownership stuff has been defined.

We should definitely start thinking about the design now though, since it is going to take awhile, and my least favorite additions have been the ones where we have rushed...

1 Like

FWIW, although that may look attractive on the surface, if you dig deeper into the implications, including performance, static type safety, and the extent of implied code breakage, I am convinced it will turn out to be wrong. I don’t have anything against speculative discussion of possible redesigns based on language features we don’t yet have, but IMO further discussion of this direction, if people want to pursue it, would be better in a separate thread. :wink:

5 Likes