Re: Java can have coroutines!

[William Ahern <william@...>]

On Mon, Aug 15, 2016 at 08:22:38AM +0100, Emeka wrote:
> Hello Bill,
> 
> Is it possible to pointer to me where your coroutines is used in a code
> base? It looks great , I will like to understand it

The hack that is standard compliant C code relies on the infamous Duff's
Device:

  https://en.wikipedia.org/wiki/Duff%27s_device

Most people know of the Duff's Device through Simon Tatham's web page.

  http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
  
Simon is also author of PuTTY.

Here's an example of mine implementing an iterator over multiple lists:

  https://github.com/wahern/timeout/blob/43a854241b93a85929785b37f45e133bd880690c/timeout.c#L647
   
And implementing a string generator:

  https://github.com/wahern/dns/blob/e4c0182158f7acf699e473855142a660afd16b6e/src/dns.c#L6285

And implementing a state machine for a tiny virtual machine:

  https://github.com/wahern/hexdump/blob/f5302685fccfc8b5ea589368de5ddac502eba630/hexdump.c#L765
  
And implementing a lexer/tokenizer, though this relies solely on computed
gotos, with fallback to a switch statement:

  https://github.com/wahern/json/blob/0fb0b0f4164120f1d197841ffebdce0f4b11772e/src/json.c#L1264  

Computed goto is a GCC extension,

  https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

which has also been adopted by every major C compiler except, AFAIK, Visual
Studio. The raison d'etre for computed gotos in C is to ease the creation of
performant state machines (simple and abstract), so it's use in this context
is not novel. Duff's Device can be used to approximate computed goto in
standard C.

Warning: long rant follows.

You can see how trivial it would be to support this trick directly in a
compiler. A compiler could easily rewrite variable loads and stores to
reference through an implicit or explicit state object, similar to how Lua
rewrites non-lexically bound variable to reference through _ENV. C++,
JavaScript, and Python did this/are doing this, variously named coroutines
or generators but all basically the same inside the implementation. But IMHO
it's a total cop-out. It's easy for a compiler to do because it's relatively
easy for a programmer to do, and so IMO provides little marginal value.
Principally I think it provides a kind of aesthetic satisfication, rounding
away harsh corners visually and providing a sanctioned object type. But it's
not providing a fraction of the power that Lua's coroutines do; the
limitations immediately bleed into the surrounding coding, just like
callbacks do, in terms of forcing programmers to design to the limitations
of the implementationn rather than the requirements of the logical problem.

So-called stackful coroutines--coroutines which transparently encompass the
state of multiple function invocations and thus are naturally implemented
with an underlying thread-like, stack-like data structure--are not easy to
implement at the language level without forethought or serious refactoring.
See, e.g., the Lua authors' paper, Passing a Language Through the Eye of a
Needle.

People conflate stackful coroutines with green threading, like Window's
fibers or Go's goroutines, but that's confusing the means with the end.
Green threading is the least interesting aspect of coroutines. It's a common
and valuable usage scenario, but that's only evidence of their
abstractive/expressive power. It's especially noteworthy that Lua doesn't
provide any help in this area when it comes to I/O--it's standard library
doesn't work with application built green threading solutions. And yet Lua
is still considered an example for the practical benefit of coroutines as a
green threading device. Coroutines are just so useful that the burden goes
unnoticed.

Perl 6's gather/take data structure for lazily iterating lists (e.g.
map/reduce patterns) can also be trivially implemented with stackful
coroutines, and that's how its implemented in MoarVM inside their VM. There
are many patterns that can expressed with stackful coroutines. I think
language designers are missing the forest for the trees when they
conceptualize coroutines as a device for async I/O, list iteration, or
similar specific solutions. They should just all be providing Lua-like
coroutines and let the ecosystem blossom, proving libraries for those
patterns and more.

For example, Rust developers (including the architect of Rust's new futures
construct) claim that Rust's failed green threading experiment is evidence
that stackful coroutines are not a practical or preferable construct for a
language like Rust. But that argument is, IMHO, a mindblowing
misunderstanding of coroutines. Green theading and coroutines are as
different as green threading and functions. All three involve details of how
the call stack is managed and how control flow is passed, but only green
threading required massive changes to their standard library, a dependency
on an event loop, and all the other things that caused that experiment to
rightly and foreseeably fail. Stackful coroutines could have been a zero
cost addition to Rust--irrelevant if you didn't use them but extremely
powerful and efficient when you did.