The case of Sequence in Hylo

[kyouko-taiga]

Background: Swift's Sequence protocol

As I was thinking about the traits required by consuming for loops (see #1080), I wondered about the role of a Swift-like Sequence trait in Hylo.

Motivation for a Sequence-like trait:

Often, one may want to iterate over the elements of a container to apply some form of transformation. If that container isn't needed after the iteration, the latter should be able to take ownership of each element. Concrete examples include map, filter, and reduce:

fun filter<E, S: Strawman>(_ s: sink S, _ is_included: inout [E](S.Element) inout -> Bool) -> Array<S.Element> {
  // Note: could be a consuming for loop.
  var g = s.make_iterator()
  var r = Array<S.Element>()
  while let e = &g.next() where &is_included(e) {
    &r.append(e) // note: ownership of `e` is transferred here
  }
  return r
}

Note that no copy occurs in the above implementation of map.

Starting from Swift:

It would be pretty simple to model a consuming generator with the following trait, shamelessly copying Swift's design:

public trait IteratorTrait {
  type Element
  fun next() inout -> Optional<Element>
}

public trait Sequence {
  type Iterator: IteratorTrait
  fun make_iterator() sink -> Iterator // note: this is a `sink` method
}

Relationship to Collection:

In Swift, Collection is a refinement of Sequence. We could make the same choice in Hylo but synthesizing Sequence's requirements from a conformance to Collection would only be possible when Self.Element is Copyable:

public trait Collection: Sequence { ... }

public extension Collection where Element: Copyable {
  public typealias Iterator = DefaultIterator<Self>
  public fun make_iterator() sink -> { .new(self) }
}

public type DefaultIterator<Base: Collection>: IteratorProtocol {
  public let base: Base
  var position: Base.Index
  public init(_ base: Base) {
    &self.base = base
    &self.position = base.start_index()
  }
  public fun next() inout -> Optional<Element> {
    if position == base.end_index() { return None() }
    defer { &position = base.index(after: position) }
    return base[position].copy()
  }
}

The constraint Self.Element: Copyable makes it annoying to implement Collection on arbitrary types. Further, DefaultIterator is not even a very efficient implementation. It doesn't really satisfies the spirit of the trait, which is supposed to let the client efficiently (i.e., without unnecessary copies) consume the elements of a container in order, one at a time.

So I'm not convinced that Collection should refine Sequence in Hylo. Instead, I would lean toward having just Iterator and optionally another trait ConvertibleToIterator.

Be more generic?

One other way to look at this issue would be to design a kind of maximally generic adapter that can take ownership of a base collection only when necessary. I think it would be interesting to think about what such a type would look like, but it would require quite some work on the design of remote types and polymorphic effects. So I think that is out of scope for a 1.0 version of Hylo.

[dabrahams]

Some scattered thoughts:

Just for posterity: the reason to distinguish Sequence from Iterator in this model is because the iterator may require additional state. The iterator for an Array is an example; it would need a next_index. But actually that is a poor example, because as you suggest above, Array<T> should not conform to this Sequence thing, whatever we end up calling it. I am starting to see them as separate things.

There is in general no way to pop elements off the front of a Collection, which is what you would need for Sequence conformance. A trait to represent that capability (PopFirstable strawman) might be a very good idea, though: Deque, Lists, all kinds of sets and maps, and ReversedCollection<T> where T: PopLastable are all obvious candidates.

If I had a non-PopFirstable Collection of copyable elements and needed a consuming iterator, there are 2 cases:

• I'm done with the Collection, in which case I can sink it into a OwningCopyingIterator that copies elements out on demand.
• I'm not done, in which case I can project it into a non-owning CopyingIterator that copies elements out on demand.

This obviously screams out for remote parts: then you just have one CopyingIterator<T: Collection where T.Element: Copyable> where the you get the 2nd case if T is remote. But that also makes me want to do both cases with the sink and let clauses of a single projection; that isn't expressible in the type system as currently designed. Sigh.

I don't love that the filter implementation you wrote there always consumes its argument. I suppose we could end up with a method bundle that also filters without consuming. But I guess we said “if the function has to escape (part of) its parameter, it should sink that parameter, and the caller should copy if needed.” Now here's the rub: copying just the elements to be escaped could be a lot cheaper than copying the whole collection. This is a case where the CopyingIterator above is sub-optimal. You only want to copy the element once you know it passes the predicate. You just want to read the original element in-place for predicate purposes.

I'm beginning to think that filter on a Collection should be explicitly and always be a projected lazy collection. You then get the option to copy the element on the back end, e.g. c.elements[satisfying: some_predicate]. If you want a copy, you can pass that to an Array constructor (or whatever).

synthesizing Sequence's requirements from a conformance to Collection would only be possible when Self.Element is Copyable:

I think in some sense that is only true if we don't have remote parts. But then your filter implementation would require Copyable to store the element based on the remote part in the Optional, so it just moves the requirement around.

(@kyouko-taiga this post may have evolved a lot since you read it last).

[dabrahams]

(Aside) doesn't IteratorTrait need to at least be Deinitializable? I would think Movable also just because I can't think of a case where it couldn't be. Am I missing something?

[kyouko-taiga]

Deinitializable is necessary to ensure that a consuming for-loop will never complain about the iterator being indestructible. That would be a confusing error message as it would relate to synthesized code. So I think that requiring Deinitializable is justified.

I don't think Movable is necessary but I also don't have a use case for an immovable iterator on the top of my head. The larger (non-rhetorical) question is: should we always ask Regular on the abstractions of the standard library unless we have compelling use cases for weaker requirements?

[dabrahams]

Yes, as I mentioned in #1619 we should be working hard to avoid granular concepts. Grouping operations as much as possible before you call something a concept is an important and often-overlooked part of the generic programming process.

[kyouko-taiga]

It's not quite the same problem. If we have already decided that P and Q deserve to be separate concepts, with Q a refinement of P, we already accepted that the granularity was justified by some other argument. We're no longer evaluating whether P is a worthy concept on its own.

So then, if an operation can be expressed in terms of just P, it is worth wondering whether we're not pushing ourselves in a corner by requiring Q prematurely.

[dabrahams]

We discussed the idea that a consuming iterator should be called Stream, but Generator might be better.

I am convinced by your arguments that Collection should not refine this thing.