A `yield` construct in the vein of C#

[bstrie]

@thestinger has mentioned this several times as a wishlist item. This is a feature that greatly simplifies the implementation of external iterators by allowing them to be compiled to state machines at compile time (did I get that right?). See http://msdn.microsoft.com/en-us/library/vstudio/9k7k7cf0.aspx for reference.

While we shouldn't expect this for 1.0, it might be prescient to reserve the keyword right now.

Nominating for far-future milestone.

[Sod-Almighty]

Seconded. Hopefully not too far in the future.

[bstrie]

@Sod-Almighty far-future milestone just means that it would not be a priority for the primary developers until after 1.0. It leaves open the possibility that a volunteer could implement it themselves, and such a patch could be accepted regardless of the current milestone.

[Kimundi]

This could probably not be done with a syntax extension, because it needs to do some serious rewriting, typechecking, inference etc. Using some mockup syntax you'd have:

yield fn foo(m: uint) -> pub struct FooIterator {
    loop {
        yield 1;
        yield 2;
        yield m;
    }
}

Which would get rewritten into something like this:

pub struct FooIterator {
    priv state: uint,
    priv m: uint
}

impl Iterator<uint> for FooIterator {
    fn next(&mut self) -> Option<uint> {
        let (new_state, ret) = match self.state {
            0 => (1, 1) 
            1 => (2, 2) 
            2 => (0, self.m)
            _ => fail!()
        };
        self.state = new_state;
        ret
    }
}

fn foo(m: uint) -> FooIterator {
    FooIterator{ state: 0, m: m }
}

[flying-sheep]

It's pretty much the only option we have to make our new external iterators as nice as the internal ones can be in situations where external ones usually suck.

[thestinger]

This would be really nice to have, because manually hoisting out the state into a struct gets tiresome. The only case where it's truly painful to write an external iterator is a recursive traversal where you have to build a stack of the state you hoisted out.

Context switches for each iteration aren't acceptable so the solutions used by Ruby (to_enum) and Python (generators) aren't a good model. C#'s state machine generator is a killer feature, but would likely take a lot of effort to implement correctly.

[flying-sheep]

Also yield is very awesome for lexers: yield some tokens, delegate to a subparser, and yield more is trivial to do and leads to very elegant code.

[graydon]

Interesting. I'd recommend digging up a formal description of the rewriting algorithm, and doing a patent search to ensure it's safe to prototype. Happy to reserve the keyword though

[bstrie]

Given that #5633 was assigned to Far-Future and was closed in favor of this bug, I'm assigning that milestone here.

[JulianBirch]

It would probably be desirable to support await as well, maybe clojure async style. I believe the state machine generation is fairly similar between the two cases.

[erickt]

@bstrie: coincidentally enough, @huonw and I have been chatting about if we could support a syntax extension that can build state machines which compile down into computed gotos. This would be really handy for my ragel parser generator fork, and would probably help make yields as fast as possible. So if this issue goes forward, please try to leave some hooks available for general purpose state machines.

[Kimundi]

I thought a bit about this today. One problem with providing yield syntax is that while it makes writing Iterator impls easy to write...

yield fn zero2ten() -> struct Zero2TenIter {
    let mut x = 0;
    while x <= 10 {
        yield x;
        x += 1;
    }
}

...DoubleEndedIterator impls nevertheless still require defining a struct and writing next() and next_back() manually:

fn zero2ten() -> Zero2TenIter { Zero2TenIter { start: 0, end: 10 } }
struct Zero2TenIter { start: uint, end: uint }
impl Iterator<uint> for Zero2TenIter {
    fn next(&mut self) -> Option<uint> {
        if self.start <= self.end {
            let v = self.start;
            self.start += 1;
            Some(v)
        } else {
            None
        }
    }
}
impl DoubleEndedIterator<uint> for Zero2TenIter {
    fn next_back(&mut self) -> Option<uint> {
        if self.start <= self.end {
            let v = self.end;
            self.end -= 1;
            Some(v)
        } else {
            None
        }
    }
}

As you can see, the problem with that is that now upgrading a existing yield function to a DoubleEndedIterator becomes even more work than if it started as a regular struct+impl to begin with, which means users will be less likely to do that, and just live with one-ended ones even if double-ended ones would make perfect sense and potentially improve re usability of the iterator.

So, as a solution, how about just making the yield syntax optionally a bit more complicated, with the ability to write both Iterator and DoubleEndedIterator impls more easily than in the manual "constructor fn + struct + trait impls" way:

yield fn zero2ten() -> struct Zero2TenIter {
    let mut start = 0;
    let mut end   = 10;
} front {
    while start <= end {
        yield start;
        start += 1;
    }
} back {
    while start <= end {
        yield end;
        end -= 1;
    }
}

The idea here is to give the user three code blocks to fill out: initialization, which contains all the setup code for the iterator and any variable declarations that are shared state for both Iterator impls, and two code blocks corresponding to the two iterator impls. A user of this syntax would still have to take care of checking that both code blocks play nice together and properly recognize that the ranges meet in the middle, but they could do so more easily than in the manual implementation way.

[Sod-Almighty]

@Kimundi: Sounds good, but should be optional. Original syntax for single-ended iterators.