A yield construct in the vein of C#

@thestinger

Issue by bstrie
Friday Jul 12, 2013 at 13:46 GMT

For earlier discussion, see rust-lang/rust#7746

This issue was labelled with: A-an-interesting-project, E-hard, I-wishlist in the Rust repository

@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.

I believe yield conveys pretty much the same meaning in other languages, including Python, Ruby and Lua. I think it's very appropriate to remove "C#" from the title.

@errordeveloper

@errordeveloper: It's not implemented with a compile-time state machine in Python and Ruby. C# in the title is definitely appropriate, because (AFAIK) there isn't another language with a comparable feature. The proposal is not about generators / coroutines built on context switches.

@thestinger

@thestinger sure, I didn't fully realise that.

A decently in depth discussion of yield support in C++: http://isocpp.org/files/papers/N4134.pdf

@sfackler

@sfackler great find!

If Am I understanding correct that someone needs to make a pull-request with an actual RFC write-up, and if so, has anyone here already started on that or at least intending to do so?

@errordeveloper

@errordeveloper #53

@errordeveloper

@errordeveloper I have started thinking about the implications of a 'yield' construct for borrow checking, which is something that past proposals have sort of glossed over. I haven't been too anxious to write up an RFC, because there is no chance that it will be considered before 1.0.

Is the fact that it's implemented as a compile-time state machine significant? The usage pattern to the developer is the same as in any other language, albeit with explicit typing.

It is, as it makes this feature most useful. State machines generated at
build time can be validated/safety-checked as well as optimised by the
compiler plugin that implements it.

On Wed, 19 Nov 2014 20:46 Lucretiel notifications@github.com wrote:

Is the fact that it's implemented as a compile-time state machine
significant? The usage pattern to the developer is the same as in any other
language, albeit with explicit typing.

—
Reply to this email directly or view it on GitHub
#388 (comment).

That is an interesting bunch of libraries there! It looks like your monad macro has bind as a primitive like Haskell's. I wonder if performance could be improved by using map and join alone as primitives to remove some "administrative lambdas".

Either way (as pipes will contain FnOnces even if the core monad parts don't), it would be nice if there was some way to add an #[inline] to the function the once closure sugar desguars into. Maybe that might help with code locality.

Here the latest Kohlhoff paper "Resumable Expressions", a new lower-level c++ alternative to await that allows implementing yield at the library level and combines stackless and stackfull coroutines:
http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/n4453.pdf

I can't claim to be much of a fan of this proposal. He completely ignores what I think is the major advantage of the await/async (in python: yield from/coroutine) model: explicit control flow shifts. One of the major side benefits to single-threaded asynchronous design, as opposed to multithreaded synchronous, is that the control flow is only ever in one place at once. This means that a lot of the state-sync and atomicity issues in multithreaded design can be avoided. Compounding this advantage is the fact that, with await/yield from, all context shifts are explicit. In effect this means the developer can guarantee that between this await and that one, no other coroutine will touch any shared state. As an example, I used this to my advantage when writing an IRC-like chat room using python asyncio, where I had the list of logged in users as a dict mapping user ids to connection objects. Because I could guarantee exclusive access to this object in a given coroutine' between yield froms, I didn't have to worry about locking it, creating a local copy of it, or anything like that. Unfortunately, in the proposed resumable model, this advantage is lost. Any function could conceivably result in a context switch. The situation is slightly improved by the fact that such functions are explicitly tagged "resumable", but because merely calling the function can cause it to begin running or suspending, there's no way to separate the act of instantiating the function with that of stepping through it.

Worth noting: Python's PEP process just accepted an async/await PEP: https://www.python.org/dev/peps/pep-0492/

PEP 492 is pretty cool, I'm excited to try the next pre-release of Python 3.5.

In addition to generators and async functions in Javascript, there's also some work being done on async generators as well: https://github.com/jhusain/asyncgenerator. The author gave a talk about some related concepts in this talk, though the syntax is hidden on the last slide and not really explained: https://www.youtube.com/watch?v=gawmdhCNy-A.

@DemiMarie

@DemiMarie @gnzlbg
The point about dsts may be pointless anyway, because according to the book you can't have one in a variable. I don't know for sure, but I can't figure out how you get one on the stack to start with and the internet is widely saying this isn't possible or at least very difficult in safe Rust. They don't make sense in stack variables because they don't have compile-time sizes. I'm basically certain you can't return them from functions directly. Etc. Can you show code that works now that you think might not work in a generator?

The thing is that someone has to know the size eventually. Even with Box, the thing that goes into Box::new is always sized. Assuming there is no counterexample, therefore, the generator has the same limitations as the stack anyway, and you can always convert it to a struct with a state field and a known size.

I'm not understanding why you can't know the size of a generator/coroutine at compile time? Assuming it's non-recursive, of course. If it makes function calls, those can just live on the normal call stack since they'll only be invoked when control is inside the generator. If it invokes other generators/coroutines, those would just live in the static memory of the coroutine itself. Circular dependencies would be detected the same way they're detected in structs. The size of a coroutine would just be pessimistically the minimum size needed to hold all the variables in the local control flow stack, excluding function calls.

My understanding is it'd look something like this:

// Pseudocody
gen fn my_generator(flag: bool) -> i32 {
    let val1: i32 = 10;
    let val2: i32 = 20;
    if flag {
        let val3: i64 = 30;
        yield val1; yield val2; yield val3 as i32;
    } else {
        let val3: i16 = 30;
        yield val1; yield val2; yield val3;
    }
    // The stack space for this function call isn't part of my_generator's
    // storage, because it can only be invoked when control flow is here.
    let val4 = function_returning_i32();
    yield val4;

    // The storage required for this generator IS part of the storage, though.
    let mut sub_gen = my_sub_generator();
    for value in sub_gen {
        yield value;
    }
}

In this example, the storage required for this generator (before compiler optimizations, and ignoring alignments) would be:

i32 + i32 + max(i64, i16) + i32 + sub_gen + value

Plus a small, fixed amount of extra space to store where the last yield was so we can resume iteration.

So I don't understand the argument that we can't know the size of a generator at compile time. It's true that the size of a generator might be large at compile time, to account for deeply-nested but non-recursive generators, but that's no different than the deeply nested struct that would be required to implement the same pattern.

I've elided ownership & lifetime concerns here, but I don't see any obvious reasons in principle that it would be different than a lambda or a struct.

@Lucretiel

@Lucretiel
That's it, yes. That's why I'm kind of confused as well. The only thing which can break it is if you actually can get a DST on the stack somehow. Admittedly there's alloca (the Linux function, not the LLVM op), but other than that the size is known and the transformation is safe.

Now, the really fun part: work is going on to eliminate unused variables. I think your example might actually only have to include one of val1 through val3. At the very least, val4 shouldn't ever exist in the storage. SO the best case is even better than that, potentially by a whole lot in some cases.

I'm starting to think I should throw an RFC out which does what we can do and leaves room for streaming in future whenever we get HKT.

I'm also looking at LLVM, and probably it's best to do this as LLVM coroutines if we can. There's a pretty long todo list, however, including a few things which might be deal breakers (specifically alignment being ignored by the allocation/freeing intrinsics). This documentation isn't currently very good, but it looks like the pointer for the dynamically allocated frame is supplied by you, not just made by LLVM. So probably it could be worked out such that Rust generates a struct with a [u8; sizeof(coroutine's frame)] in it for that case,. Alternatively, maybe Rust would need a new kind of type internally to make this work.

Actually I take that back. I bet you can't move the frame once you allocate it, which would sadly make this heap only in some cases. The only saving grace is that you can tell beforehand.

I bet you can't move the frame once you allocate it

Sure, because of dangling pointers, but that's how everything in Rust is, right? Like, that's the whole point of the ownership / borrow / mutable borrow system. It's no different than being unable to move a stack-allocated struct once you've allocated it on the stack; you can move it by bitwise copy, but only when there are no living borrows of that struct in existence. The point is that a generator "frame" is essentially the same thing as a struct, in terms of ownership, lifetime, and sizing constraints.

The only problem I can see is that there might be some interior references, like this:

gen fn my_gen() -> int {
    let i = 10;
    let ri = &i;
    ...
}

Which would make it impossible to move the struct in a way that the borrow will accept (again, before compiler optimizations or a potentially more relaxed borrow checker).

But it's still essentially syntax sugar over a struct. The challenge will be communicating borrow checker violations to the user in a useful way, but I don't see any reasons in principle that it's different than a struct frame.

Yikes. Sounds like any borrows of stack allocated variables at a yield
site would cause the transformation to fail.

Obviously, this would be a major usability problem.

On Oct 6, 2016 3:35 PM, "Lucretiel" notifications@github.com wrote:

The only problem I can see is that there might be some interior
references, like this:

gen fn my_gen() -> int {
let i = 10;
let ri = &i;
...
}

But it's still essentially syntax sugar over a struct. The challenge will
be communicating borrow checker violations to the user in a useful way, but
I don't see any reasons in principle that it's different than a struct
frame.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#388 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/AGGWB-aTdDU9dwEaVO7ctUSTXUWn0vyeks5qxU2VgaJpZM4CtyWG
.

I'm betting that you can't even move LLVM coroutines by bitwise copy safely. The implementation assumes that you allocate the pointer for it in some cases, but doesn't seem to allow you to set the pointer if it changes. I.e. if you use alloca for it either directly or indirectly it can only live as long as the stack frame that made it, even if it's a case wherein the struct would live longer. I.e. you maybe can't return a generator from a function using Rust's model if you use the LLVM coroutine intrinsics because it invalidates a pointer you can't set. Or store them in a struct that gets passed around, for that matter. This needs further investigation.

This is fixable if you just allocate the frame on the heap, but having Rust language features allocate implicitly is way against the language's philosophy, imho.

In terms of references, What doesn't work is specifically borrowing a variable on the "stack" of the generator and then yielding the reference. You can borrow them all you want, you just can't yield the reference. This is the streaming iterator problem, and the latest RFC is #1598.

As for borrow checker errors, you do that first as well. If the coroutine tries to yield anything with a lifetime less than the return type of the coroutine, you error. And then you make the lifetime elision rules apply like it's a function. I.e. you're allowed to yield references to/from any argument to the generator, but not from inside the generator.

In general, you do any safety checks before lowering the generator to a struct and iterator implementation.

We might need to wait for #1598, though, if only because hitting the non-streaming case and the streaming case at the same time might be necessary. I sort of favor dedicated syntax for a streaming generator: we can implicitly detect that it needs to be streaming but the difference would be one tiny change in the code, anywhere at all. This would lead to cryptic errors that are hard to fix.

offtopic: The cppcon2016 video about LLVM coroutines is up: https://www.youtube.com/watch?v=8C8NnE1Dg4A

I want to breathe some fresh air into this RFC, with my yield function to state machine (as an iterator) concept. Gist. It's not very good - it was quickly hacked together, but it actually compiles - you can play around with it!

Explanation: The commented-out function foo at the top is our yielding function / coroutine. All the other code below, is what could be generated by the compiler. It's similar to what Roslyn (C#) would do, I think. The return type of the coroutine becomes the data type of the values which the coroutine yields.
FooStack is a container for all the stack variables declared in the coroutine.
YieldsFnFoo is the actual iterator generated by the compiler.
The main function shows how the coroutine can be called.

I didn't follow this RFC much, but it appears that the current discussion is mostly about LLVM's built in coroutine support. I guess my concept could be considered an opposite to LLVM coroutines, since my concept could be implemented at a very high compiler level, possibly even procedural macros.

Feedback very welcome!

Experimental RFC #2033 has been accepted and implemented in nightly.

Closing in favor of rust-lang/rust#43122

+1

…

On Sun, 7 Oct 2018, 8:42 am Mazdak Farrokhzad, ***@***.***> wrote: Closing in favor of rust-lang/rust#43122 <rust-lang/rust#43122> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#388 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAPWS80F_HlVsD55ir-nBzB5NcqsVwDQks5uibBagaJpZM4CtyWG> .

Navigation Menu

Repository navigation

A `yield` construct in the vein of C# #388

47 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

A yield construct in the vein of C# #388

Description

Activity

errordeveloper commented on Oct 12, 2014

thestinger commented on Oct 12, 2014

errordeveloper commented on Oct 12, 2014

sfackler commented on Oct 14, 2014

errordeveloper commented on Oct 14, 2014

errordeveloper commented on Oct 14, 2014

sinistersnare commented on Oct 14, 2014

zwarich commented on Oct 14, 2014

Lucretiel commented on Nov 19, 2014

errordeveloper commented on Nov 25, 2014

Ericson2314 commented on Nov 30, 2014

gnzlbg commented on Apr 17, 2015

Lucretiel commented on Apr 17, 2015

steveklabnik commented on May 6, 2015

ryanhiebert commented on May 6, 2015

47 remaining items

ahicks92 commented on Oct 5, 2016

Lucretiel commented on Oct 5, 2016

ahicks92 commented on Oct 6, 2016

ahicks92 commented on Oct 6, 2016

Lucretiel commented on Oct 6, 2016

Lucretiel commented on Oct 6, 2016

DemiMarie commented on Oct 7, 2016

ahicks92 commented on Oct 7, 2016

gnzlbg commented on Oct 10, 2016

haudan commented on May 23, 2017

mbrubeck commented on Sep 28, 2017

Centril commented on Oct 7, 2018

errordeveloper commented on Oct 8, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

A `yield` construct in the vein of C# #388