When I read "Colored function problem" and "make complexity explode" I thought it was some weird NP-complete scheduling issue having to do with graph coloring or something, but it turns out it's just a fancy term for not wanting to add async to everything that calls async. Basically just an ergonomics issue.
First, in Rust this isn't really a problem. You can always turn async calls into blocking ones in Rust by calling block_on [0]. In some languages block_on doesn't exist, like in in-browser js, because here, code is supposed to be async. But in Rust there is no requirement, so there's no colored function problem here.
Second, I don't think it's a big problem in the first place. In one of my projects, I'm using an async library and have isolated the async-ness by creating a dedicated thread that communicates with the library. The thread provides a queue of messages that the remaining code of my project can handle.
the issue is turning blocking calls (or non-async calls) into non-blocking ones, or simply yielding from a callback deep into a callstack (the usual example is turning an internal iterator into an external one).
Of course you can add async to the whole callstack, but it could be third party code and it might require code duplication if async adds a penalty to compared to non-async code.
Ideally the fixed stack size/conversion to state machine would be an optimization that the compiler would apply if it can prove that the coroutine ever yields form top level (or from a well known and fixed stack depth) and resort to dynamic stacks otherwise. I have been thinking a lot about this, and I think the key is reifying the incoming continuation and, as long as it doesn't escape the called coroutine , the optimization can be guaranteed. I believe that rust lifetime machinery might help, but it is something I'm not familiar with.
It's not that hard, it's just pointless. Async is more general, so the optimization would have to go into the opposite direction: everything starts as implicitly async and things that provably don't need to be can just be converted to regular synchronous stackful code as an optimization pass.
that's what many functional programming languages do (or did, I think it went a bit out of syle), but it is expensive and the interoperability story with C is not good.
edit: it also requires heap allocating activation frames in the most general case, which is slow.
After full CPS transformation, you absolutely can allocate the activation frames on the stack. Cf. CHICKEN Scheme that does precisely that, and more generally, uses the stack as the 0-generation. When the stack hits a certain depth, it longjmp's to the GC, copies whatever is alive to the heap and restarts the current continuation on the now-trimmed stack.
yes, you can even use the original C stack as a bump allocator (That's Cheney on the MTA, right?), but then you need GC, which is not appropriate for rust.
If any part of your function depends on the result of a promise then it has to return a promise; this is true whether you use async/await syntax or then(). Unfortunately JS doesn't have something like block_on, which now that I think about it is probably because it's single-threaded, so any block would block the entire app.
Comments
When I read "Colored function problem" and "make complexity explode" I thought it was some weird NP-complete scheduling issue having to do with graph coloring or something, but it turns out it's just a fancy term for not wanting to add async to everything that calls async. Basically just an ergonomics issue.
First, in Rust this isn't really a problem. You can always turn async calls into blocking ones in Rust by calling block_on [0]. In some languages block_on doesn't exist, like in in-browser js, because here, code is supposed to be async. But in Rust there is no requirement, so there's no colored function problem here.
Second, I don't think it's a big problem in the first place. In one of my projects, I'm using an async library and have isolated the async-ness by creating a dedicated thread that communicates with the library. The thread provides a queue of messages that the remaining code of my project can handle.
[0]: https://docs.rs/tokio/0.3.3/tokio/runtime/struct.Runtime.htm...
A viral one, and number-of-possible-states-exploding one at that.
That's not exactly what we're trying to do here.
I must admit I had no idea what that was either and the first thing that came to my mind was some combinatorial explosion thing.
I truly don't care about this issue...
the issue is turning blocking calls (or non-async calls) into non-blocking ones, or simply yielding from a callback deep into a callstack (the usual example is turning an internal iterator into an external one).
Of course you can add async to the whole callstack, but it could be third party code and it might require code duplication if async adds a penalty to compared to non-async code.
Ideally the fixed stack size/conversion to state machine would be an optimization that the compiler would apply if it can prove that the coroutine ever yields form top level (or from a well known and fixed stack depth) and resort to dynamic stacks otherwise. I have been thinking a lot about this, and I think the key is reifying the incoming continuation and, as long as it doesn't escape the called coroutine , the optimization can be guaranteed. I believe that rust lifetime machinery might help, but it is something I'm not familiar with.
It's not that hard, it's just pointless. Async is more general, so the optimization would have to go into the opposite direction: everything starts as implicitly async and things that provably don't need to be can just be converted to regular synchronous stackful code as an optimization pass.
that's what many functional programming languages do (or did, I think it went a bit out of syle), but it is expensive and the interoperability story with C is not good.
edit: it also requires heap allocating activation frames in the most general case, which is slow.
After full CPS transformation, you absolutely can allocate the activation frames on the stack. Cf. CHICKEN Scheme that does precisely that, and more generally, uses the stack as the 0-generation. When the stack hits a certain depth, it longjmp's to the GC, copies whatever is alive to the heap and restarts the current continuation on the now-trimmed stack.
yes, you can even use the original C stack as a bump allocator (That's Cheney on the MTA, right?), but then you need GC, which is not appropriate for rust.
In browser JS can drop down to the old Promise callbacks (.then) to avoid coloring synchronous callers.
If any part of your function depends on the result of a promise then it has to return a promise; this is true whether you use async/await syntax or then(). Unfortunately JS doesn't have something like block_on, which now that I think about it is probably because it's single-threaded, so any block would block the entire app.