News for hackers. Stuff that matters.
Re:Zero-cost futures in Rust by wahern on Saturday August 13, 2016 @01:30AM (#12280399)
I've been writing async I/O networking software for about 15 years now. Early on most of that was in C, now it's split about 50/50 between C and Lua. Most of my C I/O code is still in C because I prefer my libraries to be reuseable outside of Lua or any particular event loop, and they often are. Lua's coroutines are usually higher up the stack, juggling more abstract state; and I use them for more than asynchronous I/O or asynchronous tasks.

The thing about async/await is that in a language like C, I can already accomplish much of that with tricks like Duff's Device and macros. It has its limitations, but IME they're not much more onerous than the limitations of async/await, especially in the context of a language lacking GC. I have to manually keep state off the stack (or otherwise copy/restore it), but you do that anyhow when you don't have lexical closures and GC, and often even when you do.

The beautiful thing about coroutines in Lua is that it's based on a threading model, but not one bound to the C stack or a kernel thread, which are completely orthogonal concerns left to the application to deal with or not deal with. And it does this while preserving functions as first-class objects. Neither callers nor callees need to know anything about coroutines. That kind of composability makes coroutines useful and convenient for many more things than simulating green threading or managing CPU parallelism. Among other things, it means I can mix-and-match functional and imperative styles according to the problem, and not whether it will be convenient to then make use of coroutines. It means that I have a single, natural call stack--not an implicit stack and an explicit stack. async/await and futures unify your data stack, but you're still manually managing the call stack through syntactic devices or otherwise formalized calling conventions. However heavily sugared, it will hinder the design of your software no less than if you had to manually manage the data stack, too.

Coroutines that aren't stackful aren't nearly as powerful in terms of problem solving. Without them being stackful, it's a horribly leaky abstraction for non-trivial uses. Most people would agree that the C preprocessor is a mess, and that functions as first-class objects are powerful. So modern languages strive to create templating systems that allow you to construct _real_ functions that are indistinguishable from any another function. But then they introduce monstrosities like futures or async/await, that beautiful symmetry is broken. It's like bringing back C's macro preprocessor--now you have regular functions and these weird things with different syntactic and control follow semantics, whether you wanted it or not. The decision is no longer yours, which means you're bending to the language's deficiencies.

Why even bother with such half-baked solutions? In almost every case it's utterly transparent that these solutions exist for the benefit of the compiler and runtime author, usually because of intentional or unintentional technical debt--a direct or indirect dependency on the C or kernel stack. For C++ it's understandably a difficult dilemma, but for every other language it's a total cop-out.

Then these solutions are sold to the public by prettifying the implementations with fancy terminology and beguiling examples showing how they can be used to implement async I/O or parallel CPU jobs. But few, if any, language features are so narrowly tailored to such specific use cases. Why? Because languages are supposed to provide simple building blocks that compose as seamlessly as possible at a much higher level of abstraction than, e.g., a slightly nicer way to implement HTTP long-polling servers. Such contrivances are as removed from the basic simplicity of the function as C's macros are from first-class functions. In both cases you can implement solutions for a certain subset of problems that superficially look convenient and nice; but in the real world the limitations become swiftly apparent, and you realize a lot of effort was spent in design and implementation for little real-world gain.

With Lua's coroutines, I can implement a futures pattern easily when it's appropriate, and it will be more powerful because the futures themselves can make use of coroutines both internally and externally. But in my use of coroutines in Lua futures are rarely the most natural design pattern. Sometime you want a full-blown CPS solution, sometimes you simply want to be able to arbitrarily swap producer/consumer control flow, for example in a lexer. Often you want a mixture of all of these. Coroutines--stackful coroutines--provide all that and more, seamlessly.

Futures only look nice and elegant in contrast to event loop oriented, callback-style programming. But that's a really, really low bar. Please aim higher, people!

Re:Zero-cost futures in Rust by domenicd on Saturday August 13, 2016 @09:43AM (#12281469)
> Why even bother with such half-baked solutions? In almost every case it's utterly transparent that these solutions exist for the benefit of the compiler and runtime author, usually because of intentional or unintentional technical debt--a direct or indirect dependency on the C or kernel stack.

There is a significant faction of language designers that disagree, and think that keeping coroutines shallow is important for developers writing and reading the code. This post from Dave Herman<(involved in JavaScript and Rust) sums it up: http://calculist.org/blog/2011/12/14/why-coroutines-wont-wor.... (The comment from Tom van Cutsem is also a good rephrasing: http://disq.us/p/9jcee9.) Note that the argument is not as applicable in languages with racy multithreading (like C/C++ or Java).

I don't think it's necessarily a knockout argument, but it at least helps me sleep with what we've chosen for JavaScript.

Re:Zero-cost futures in Rust by gpderetta on Saturday August 13, 2016 @02:57PM (#12282608)
I never understood this argument, it feels to me a post hoc rationalisation. Yes, with toplevel only yield you know all suspension points, but doesn't really buy you anything, as calling an unknown function can potentially mutate any object possibly by invoking user callbacks or other generators. If the function behaviour is well documented, then whether it is a suspension point would be as well.
Re:Zero-cost futures in Rust by domenicd on Sunday August 14, 2016 @07:18PM (#12287772)
The difference is that when you call a function, you can easily know what will happen: the function will execute. You can use your knowledge about the function you are calling (and the functions it calls, etc.) to ensure it does not violate any invariants you set up.

Whereas, if you have an implicit yield point that goes back to the event loop, the event loop can run arbitrary other tasks---not ones you can locally reason about or predict, but simply those that are ready to be executed.

Re:Zero-cost futures in Rust by gpderetta on Monday August 15, 2016 @10:51AM (#12290794)
But if you know what a function does and call you would also know whether it is an implicit yield point or not, right?

Also, I don't know about JS, but many event loops can be reentered recursively, so even with top level only yield all bets are off.

Re:Zero-cost futures in Rust by wahern on Monday August 15, 2016 @05:35PM (#12293661)
Was that a correct link? I feel like it only re-iterates my points.

My point is that thinking about coroutines in the context of green threading is totally the wrong way to think about it. That you can implement something approximating green threads with coroutines is a testament to the power of coroutines, but it's hardly the defining the feature for them.

And coroutines are not sufficient to implement green threading. You still need a way to have multiple outstanding I/O requests. That could have been done with other mechanisms. User code could wrap such mechanisms with coroutines and fashion an event loop if they desired, and no doubt most would have done that. But by leaving that up to the application people could experiment with patterns for addressing concerns regarding concurrency. And I would also note that concurrency problems related to order of operations hardly go away with futures, the preferred solution in JavaScript, or async/await. Stackful coroutines can theoretically be worse when callees can yield from any expression, but don't forget that the real problem is shared mutable state, which you're passing or otherwise making available in equal measures for each option. For that and other reasons the distinction with futures and async/await is, I think, not very meaningful.

For similar reasons, Rust's failed experiment with green threading is not an argument against the practicality of stackful coroutines. Quite the contrary--it's an example of why it's more important to focus on the abstraction and preserving the power of that abstraction than to tailor the solution for specific scenarios. Rust could easily have had stackful coroutines with zero performance cost and negligible cost to the language design. But instead they focused on coroutines as a roundabout way to ease the burden of async I/O, and, worse, they tried to refactor Rust's entire standard I/O library to work with that green threading model. It was a destined for failure, and for good reason.

When discussing coroutines, my favorite example is something like libexpat. libexpat was early on in the history of XML the most widely used XML parser. But it was a push parser. Push parsers are easier to implement and often more performant, but they're more difficult to use. All of those qualities stem from push parsers literally and figuratively pushing the burden onto the application for solving issues related to state management and buffering.

You couldn't easily refactor libexpat into a pull parser because token production relied on automatic variable stack state and internal stack structures. You'd have to copy and buffer everything it produced. No wonder so many people either forked libexpat or just reinvented the wheel.

If C had stackful coroutines, it would be _trivial_ to make libexpat a pull parser. Heck, trivial undersells how simple and elegant it would be. In that context coroutines could have provided the best of every and all worlds, for both libexapt developer(s) and direct and indirect users.

The narrative around coroutines has been poisoned by this narrow focus on async I/O and similar contemporary problems, and conflation and equivocation with fibers, kernel threads, and the low-level details of platforms' C ABIs. It's created lost opportunities for providing stronger language abstractions.

Perl 6 committed a similar sin, IMO. MoarVM technically can support stackful coroutines, but it doesn't because they're only implemented to support Perl's gather/take control structure. That coroutines could have easily been used to implement gather/take entirely within application code, but not vice-versa, should have been a strong hint that coroutines were the stronger abstraction, and gather/take should have been defined as standard API utilizing proper stackful coroutines.

Note to future language designers: coroutines are not about async I/O. Coroutines are not about green threads. Coroutines are not about map/reduce. Don't conflate the means with the ends. Stackful coroutines can be used to implement all of those and more because they're the better abstraction. Lua's stackful coroutines can be used to easily implement green-threading like async I/O, or non-trivial map/reduce patterns, not because the Lua authors bent over backwards to make that possible, but because they preserved their abstractive power; because they modified both the language language design and implementation so stackful coroutines didn't come with needless caveats.