[rust-dev] Language support for external iterators (new for loop)

Niko Matsakis niko at alum.mit.edu
Fri Jun 28 11:23:47 PDT 2013


Specificity is the cost of non-virtual dispatch. However, if it is
truly undesirable in some cases, we can eventually permit you to
return `~Iterator<int>`, once ~-objects work properly.


Niko

On Wed, Jun 26, 2013 at 11:49:07PM +0100, Gareth Smith wrote:
> One downside of external iterators is that they produce function
> signatures that expose implementation details and are harder to
> understand.
> 
> For example, an internal iterator function that loops over odd
> numbers would have a signature like this:
> 
> fn each_odd(ints: &[int], fn(int) -> bool) -> bool;
> 
> The same function written to produce an external iterator would have
> a signature more like this:
> 
> fn iter_odds<'a>(ints: &'a [int]) -> iterator::FilterMapIterator<'a,
> &int, int, vec::VecIterator<'a, int>>;
> 
> This signature is more complicated. It is also likely to change if
> the implementation of iter_odds changes (e.g. to no longer use
> filter_map).
> 
> Gareth
> 
> On 26/06/13 04:44, Daniel Micay wrote:
> >This is a followup from the previous discussion on internal vs. external
> >iterators.[1]
> >
> >Since then, most iterators in the standard library have been converted to
> >external ones. Almost all uses of the `for` loop are now using the `.advance`
> >wrapper, and I don't think there will be any use cases left for the old
> >internal iteration protocol.
> >
> ># External iterators
> >
> >To reiterate the benefits of the external iteration protocol:
> >
> >* It's generic and works well with traits, so functions can be written to work
> >   on any arbitrary `Iterator<A>`. Most adaptors can work for any type `A`,
> >   whether it's a value, reference or mutable reference.
> >
> >* Iteration state is an object, so iterators can be interleaved. This is
> >   required for a generic zip, merge, union, intersect, etc. and is often useful
> >   in an ad-hoc fashion to consume only some of an iterator without
> >   losing it.
> >
> >* In the future, Rust can have generators using a `yield` statement like C#,
> >   compiling down to a fast state machine without requiring context switches,
> >   virtual functions or even closures. This would eliminate the difficulty of
> >   coding recursive traversals by-hand with external iterators.
> >
> ># Alternatives
> >
> >The iteration protocol can't be based on anything requiring virtual method
> >calls, heap allocations or context switches without the performance becoming
> >significantly worse.
> >
> >There have been some suggestions about following the lead of Clojure and using
> >reducers[2], but the implementation suffers from the same limitations of not
> >having an external state.
> >
> >Rust doesn't yet have a way to write data-parallel code, but when it does gain
> >that, containers can just support partitioning themselves into ranges via
> >`Iterator`. It will work for in-place mutation in parallel too.
> >
> ># A new loop
> >
> >I think it's a foregone conclusion that we'll be replacing `for`, so I suggest
> >that we just reuse the current syntax and change the semantics:
> >
> >     for iterator |pattern| { body }
> >
> >This can just be compiled as the following would be:
> >
> >     let mut it = iterator;
> >     loop {
> >         match it.next() {
> >             Some(pattern) => { body }
> >             None => break
> >         }
> >     }
> >
> >A lang item can be added for the Iterator trait requirement.
> >
> >This would avoid the `.advance` tacked onto almost every `for` loop at the
> >moment, and rid us of the problems associated with the current `for`:
> >
> >* The `break` and `return` statements can fail to work, so borrow/liveness
> >   checking can't trust them. A loop body can't take an `&mut` reference and
> >   return it because it could result in grabbing the reference again. This also
> >   seems to be why we forbid `return` inside closures and do statements, since it
> >   would be confusing to have to act differently than `for`.
> >
> >* The function's local variables are upvars in the closure, so using them is
> >   very restricted. It's very obvious that it's not just another block because
> >   of this.
> >
> >* Compiling closures is slow, as they have to broken down by SROA and involve
> >   inlining a function after proving the function pointer is constant. If we
> >   were marking the function pointers as `llvm.invariant` it might stop being a
> >   performance hit, but it would remain a compile time issue.
> >
> ># Iterables
> >
> >The `for` loop above can also be extended to work for *any* `Iterable` in the
> >future, not just iterators themselves.
> >
> >     for iterable |x| { ... } // use the default iterator
> >     for iterable.rev_iter |x| { ... } // use another iterator
> >
> >At the moment, the `Iterable` trait cannot be defined/used because the compiler
> >ignores bounds on trait type parameters, but it would be something like the
> >following:
> >
> >     #[lang = "iterable"]
> >     trait Iterable<A, T: Iterator<A>> {
> >         fn iter(&self) -> T;
> >     }
> >
> >     trait ReverseIterable<A, T: Iterator<A>> {
> >         fn rev_iter(&self) -> T;
> >     }
> >
> >     trait MutableIterable<A, T: Iterator<A>> {
> >         fn mut_iter(&mut self) -> T;
> >     }
> >
> >     trait MutableReverseIterable<A, T: Iterator<A>> {
> >         fn mut_rev_iter(&mut self) -> T;
> >     }
> >
> ># Links
> >
> >[1]: https://mail.mozilla.org/pipermail/rust-dev/2013-June/004364.html
> >[2]: https://github.com/mozilla/rust/wiki/Meeting-weekly-2013-06-25#iterators
> >
> >
> >_______________________________________________
> >Rust-dev mailing list
> >Rust-dev at mozilla.org
> >https://mail.mozilla.org/listinfo/rust-dev
> 

> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev



More information about the Rust-dev mailing list