Blog post series: Alternative type constructors and HKT

So, at Rust Belt Rust, @aturon, @withoutboats, and I spent a lot of time talking over ATC and HKT and how they interact and compare. I’ve been trying to write up some of the stuff we said. I’ve just posted the first post here:

http://smallcultfollowing.com/babysteps/blog/2016/11/02/associated-type-constructors-part-1-basic-concepts-and-introduction/

This first post is mostly background, though it does touch briefly on the “big idea” of associated type constructors. I will have more posts coming over the next several days; I have several written already but just didn’t want to blast people with too much stuff all at once. =)

Anyway, I’m opening this thread for comments and to talk things over.

22 Likes

Your “old iterator blog post” link is borked (this one: http://smallcultfollowing.com/blog/2016/02/19/parallel-iterators-part-1-foundations/).

Thanks, will fix!

EDIT: Should be fixed. FTR, correct URL is http://smallcultfollowing.com/babysteps/blog/2016/02/19/parallel-iterators-part-1-foundations/.

1 Like

This part seems to be missing a self :

We could also imagine writing impls for other types, like Vec in the standard library: fn iterate<'iter>(&'iter) -> slice::Iter<'self, T> { self.iter() }

1 Like

type Iter: Iterator<Item=T>;

Shouldn't this actually be Iterator<Item=&'iter T>, in the definition of Collection trait ?

And so, the "associated-type constructor" version would be

type Iter<'iter>: Iterator<Item=&'iter T>;

So, it already reveals the issue with this trait when trying to define it, even before trying to implement it.

Great article nonetheless!

Thanks for the writeup @nikomatsakis! Somewhat recently I wanted to have an Iterator impl which forced the returned Item type to be dropped before the next one could be obtained. Basically that would mean a next() signature which looked like this:

fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>

But without ATC this cannot be done using the Iterator trait. This method is perfectly valid if it’s implemented directly on some iterator-like thing without it actually being an Iterator. However, doing so means losing out on iterator sugar like for item in iterator. Without the sugar, consuming it becomes something like

while let Some(item) = iterator_like_thing.next() {
    // ...
}

While not bad, it’s not nearly as nice as the sugar we get with a real Iterator impl. With that background out of the way, I’d like to ask, will the current plans for ATC be able to apply to the current Iterator trait, or will something like StreamingIterator (as discussed in RFC 1598) be required? Would the for-loop sugar still work in that case?

This still won’t work, because Iterator::Item doesn’t have a lifetime parameter.

Yes, true. =) Maybe I can adjust the text a bit.

Yes, this is usually so that the iterator can "generate" data as it goes, using some internal storage. And yeah, this needs a new trait. I don't think you could do it with the current Iterator trait even if we had ATC. And certainly not backward compatibly.

This is sort of an interesting use case though. I hadn't thought it out before. So, imagine that we had this trait:

trait GenIterator {
    type Item<'iter>;
    fn next<'iter>(&'iter mut self) -> Self::Item<'iter>;
}

Obviously, this trait lets you do what you wanted to do. It has some kind of subtle effects, however, on people who want to write generic code over iterators. In particular, they can no longer assume that the data they produce will outlive the iterator (that is, indeed, the whole point!).

Now, one of the key things that the current iterator design supports is the ability to have one iterator trait supplying &T, &mut T, or T, as you need it (i.e., iter(), iter_mut(), and into_iter()).

It is not entirely obvious whether ATC would also support that pattern. I haven't gotten to this part yet in the series, but one of the restrictions that we are considering for ATC (at least for now) is to limit how the lifetime/type parameters can be used. This would be to preserve forwards compatibility with an HKT-like system, if we want that. One part of these rules would be that every parameter must be used exactly once, and in the same order as they appear.

So for example, a definition like this would be disallowed:

impl GenIterator for vec::IntoIter<T> {
    type Item<'a> = T;  // illegal: `'a` is not used
}

But let's say we don't apply that restriction. In that case, the above iterator could work, so in a sense this iterator trait is strictly more expressive.

I was then starting to think about the generic functions that use the iterator trait. If you want to write a function that works over any iterator today, you might write:

fn first<I, T>(t: I) -> Option<T>
    where I: Iterator<Item=T>
{
    i.next()
}

What's kind of interesting about this is that the code above could be rewritten to use GenIterator sort of like this:

fn first<I, T>(t: I) -> Option<T>
    where I: GenIterator<Item<'iter>=T>

The key point here is that, because T is bound outside of the scope of 'iter, we know that if the where-clause is satisfied, I::GenIterator<'foo> must not be dependent on 'foo. Kind of interesting.

It'd be a good exercise to try and work out this example more, so as to see how generic adapters like Map wind up looking. e.g., map normally takes a function F where F: FnMut(Self::Iter), but it'd have to be something like F: for<'iter> FnMut(Self::Item<'iter>) instead. I haven't tried to work this through to see if any problems arise.

I guess I just want to use into_iterator as my example :slight_smile:

Nit: type Iter<'iter>: Iterator<Item=T>; should be type Iter<'iter> where for<'iter> Iter<'iter>: Iterator<Item=T>;, yes? (or &'iter T as mentioned above.`)

Would you ever want type Iter<'iter>: Iterator<Item=&'iter T>; to mean anything other than for<'iter> Iter<'iter>: Iterator<Item=&'iter T>?

There are some unresolved questions about syntax here.

1 Like

should be type Iter<'iter> where for<'iter> Iterator<Item=&'iter T>;

That would be a slightly weird syntax as you're introducing the lifetime 'iter and then immediately shadowing it with for<'iter> (which introduces a new lifetime) without ever using it.

TBH, I think it's a little weird that the syntax introduces a new named lifetime at all, when it's often not used - it only makes sense if you consider the trait bound to be inside the universal quantifier, eg. for<'iter> (type Iter<'iter>: Iterator<Item=&'iter T>)

As opposed to using a placeholder lifetime: type Iter<'_> where for<'iter> Iter<'iter>: Iterator<Item=&'iter T>

This interpretation precludes placing bounds on a concrete substitution, so there's no way to express: type Iter<'iter> where Iter<'static>: Foo Because when rewritten, you get: for<'iter> (type Iter<'iter> where Iter<'static>: Foo) Which doesn't make much sense.

No, I at least wouldn't =)

I think that:

type Iter<'iter>: Iterator<Item=T>

and

type Iter<'iter> where for<'iter> Self::Iter<'iter>: Iterator<Item=T>
//                                ^^^^^^ you forgot this part, I think

would be equivalent, presuming we allow where clauses to be attached to types and not just traits. (Do we? Honestly I forget.)

But, yes, if iterator is to yield up references to the elements, then I should have written type Iter<'iter>: Iterator<Item=&'iter T>. Just imagine it was the iterator that results from into_iterator instead (I should patch up the post; didn't have time today).

I think this restriction would be unfortunate. At in least some of the cases where I’ve wanted ATC, some of the impls would not use the type parameter. (And non-generic code that uses such an impl should have values of the constructed associated type not borrow the lifetime.)

But then I have not thought through all the consequences of allowing this in the language.

3 Likes

Not according to the RfC, which explicitly mentions this :smile: . But it's possible y'all have changed the design since then.

I agree that the restriction is unfortunate. The problem is this: a type constructor is actually a lambda term. If we allow type constructors as parameters to types, we have higher order lambdas in our generics system (this is what higher kinded polymorphism means after all). If the type constructors you’re allowed to use here are unconstrained, Rust’s generics system becomes a lambda calculus evaluator, and you can accidentally describe types which are non-terminating programs.

ATCs alone sidestep this problem by not making it possible to define a higher order type constructor, so the generics language isn’t so trivially turing complete.

What this means is that there is a trade off here: we can have “full HKT” or we can have unconstrained ATCs. The idea is to start with constrained ATCs, then we can get more insight into which limitation it would be more helpful to remove.

But Rust’s type system has been Turing complete for ages (and it gets easier with specialization); you just have to use different encodings, typically involving associated types. (So (f x) is represented as something like <(F, X) as Apply>::Out, or Apply<F, X> with a type alias; you can’t get F<X> which this would allow, at least if F is a variable rather than a fixed ‘function’, but I don’t think that makes much difference.)