Java can have coroutines!

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Java can have coroutines!

Stefan Reich
Reply | Threaded
Open this post in threaded view
|

Re: Java can have coroutines!

William Ahern
On Fri, Aug 12, 2016 at 11:25:21PM +0200, Stefan Reich wrote:
> Like Lua has. :-)
>
> https://medium.com/@stefanreich/java-can-have-coroutines-e469dc91c15a
> http://www.ai1.lol
>

Not really.

1) Coroutines as added to most languages require adorning the function
definition and/or invocation.

2) Coroutines in most languages are a special kind of function, thus point
#1. Coroutines in Lua are an abstraction around a thread. In Lua you can
yield from nested function calls, without intermediate function invocations
having to know about coroutine semantics. In most other languages you either
have to chain invocations with special decorators like await, or you have to
use a special function type. In both cases you're violating functions as
first-class values as now you have at least two entirely distinct function
types.

As a classic example, Lua's coroutines can be used to emulate green
threading. But just as importanly it means complex iterators are easier to
create because you can easily implement the logic of the iterator across
multiple functions, most or even all of which can be ignorant of coroutine
semantics. Whereas in other languages you're either going to have to
shoe-horn everything into a single function, or you're going to have to
mix-and-match regular functions with coroutine-specific functions.

That's not to say that the more limited form of coroutines in other
languages isn't useful. But they're not nearly as useful and convenient as
in Lua.

I can implement functions-as-coroutines in C using the preprocessor[1].
There are limitations to what you're allowed to do from the function. But
there are limitations to coroutines in other languages. And that's my point:
Lua's coroutines really stand out wrt their level of abstraction.


[1] Here's the most recent implementation I wrote, which is pure ANSI C.
I've used this pattern or something like it dozens of times, and it's so
simple it's not really worth turning into a library.

/*
 * Application code should define SM_RESTORE and SM_SAVE, and the
 * local variable pc.
 */
#define SM_ENTER \
        do { \
        static const int pc0 = __LINE__; \
        SM_RESTORE; \
        switch (pc0 + pc) { \
        case __LINE__: (void)0

#define SM_SAVE_AND_DO(do_statement) \
        do { \
                pc = __LINE__ - pc0; \
                SM_SAVE; \
                do_statement; \
                case __LINE__: (void)0; \
        } while (0)

#define SM_YIELD(rv) \
        SM_SAVE_AND_DO(return (rv))

#define SM_EXIT \
        do { goto leave; } while (0)

#define SM_LEAVE \
        leave: (void)0; \
        SM_SAVE_AND_DO(break); \
        } \
        } while (0)

If you can use computed goto extensions (supported by every major compiler
except Visual Studio), you can implement a faster version with fewer
limitations. One obvious limitation to the above is that you cannot yield
from a nested switch statement. But for implementing iterators (the purpose
for which cooroutines are most often sold in other languages) the above is
adequate for even complex cases. I also use the above in C code to simplify
using asynchronous I/O, another use case coroutines are used for in other
languages.

Reply | Threaded
Open this post in threaded view
|

Re: Java can have coroutines!

Emeka

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

On Aug 13, 2016 12:45 AM, "William Ahern" <[hidden email]> wrote:
On Fri, Aug 12, 2016 at 11:25:21PM +0200, Stefan Reich wrote:
> Like Lua has. :-)
>
> https://medium.com/@stefanreich/java-can-have-coroutines-e469dc91c15a
> http://www.ai1.lol
>

Not really.

1) Coroutines as added to most languages require adorning the function
definition and/or invocation.

2) Coroutines in most languages are a special kind of function, thus point
#1. Coroutines in Lua are an abstraction around a thread. In Lua you can
yield from nested function calls, without intermediate function invocations
having to know about coroutine semantics. In most other languages you either
have to chain invocations with special decorators like await, or you have to
use a special function type. In both cases you're violating functions as
first-class values as now you have at least two entirely distinct function
types.

As a classic example, Lua's coroutines can be used to emulate green
threading. But just as importanly it means complex iterators are easier to
create because you can easily implement the logic of the iterator across
multiple functions, most or even all of which can be ignorant of coroutine
semantics. Whereas in other languages you're either going to have to
shoe-horn everything into a single function, or you're going to have to
mix-and-match regular functions with coroutine-specific functions.

That's not to say that the more limited form of coroutines in other
languages isn't useful. But they're not nearly as useful and convenient as
in Lua.

I can implement functions-as-coroutines in C using the preprocessor[1].
There are limitations to what you're allowed to do from the function. But
there are limitations to coroutines in other languages. And that's my point:
Lua's coroutines really stand out wrt their level of abstraction.


[1] Here's the most recent implementation I wrote, which is pure ANSI C.
I've used this pattern or something like it dozens of times, and it's so
simple it's not really worth turning into a library.

/*
 * Application code should define SM_RESTORE and SM_SAVE, and the
 * local variable pc.
 */
#define SM_ENTER \
        do { \
        static const int pc0 = __LINE__; \
        SM_RESTORE; \
        switch (pc0 + pc) { \
        case __LINE__: (void)0

#define SM_SAVE_AND_DO(do_statement) \
        do { \
                pc = __LINE__ - pc0; \
                SM_SAVE; \
                do_statement; \
                case __LINE__: (void)0; \
        } while (0)

#define SM_YIELD(rv) \
        SM_SAVE_AND_DO(return (rv))

#define SM_EXIT \
        do { goto leave; } while (0)

#define SM_LEAVE \
        leave: (void)0; \
        SM_SAVE_AND_DO(break); \
        } \
        } while (0)

If you can use computed goto extensions (supported by every major compiler
except Visual Studio), you can implement a faster version with fewer
limitations. One obvious limitation to the above is that you cannot yield
from a nested switch statement. But for implementing iterators (the purpose
for which cooroutines are most often sold in other languages) the above is
adequate for even complex cases. I also use the above in C code to simplify
using asynchronous I/O, another use case coroutines are used for in other
languages.

Reply | Threaded
Open this post in threaded view
|

Re: Java can have coroutines!

Philipp Janda
Am 15.08.2016 um 09:22 schröbte Emeka:
> 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

If I were you, I'd start here[2] or here[3]. If you want to see real
world code, apparently Putty[4] uses this hack in its implementation.

Philipp

   [2]: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
   [3]: http://dunkels.com/adam/pt/expansion.html
   [4]:
https://github.com/Yasushi/putty/blob/20458bcedb5935f5e8cd629c8398a29f71cfcd9d/ssh.c#L413 
(unofficial mirror!)


> On Aug 13, 2016 12:45 AM, "William Ahern" <[hidden email]>
> wrote:
>
>> On Fri, Aug 12, 2016 at 11:25:21PM +0200, Stefan Reich wrote:
>>> Like Lua has. :-)
>>>
>>> https://medium.com/@stefanreich/java-can-have-coroutines-e469dc91c15a
>>> http://www.ai1.lol
>>>
>>
>> Not really.
>>
>> 1) Coroutines as added to most languages require adorning the function
>> definition and/or invocation.
>>
>> 2) Coroutines in most languages are a special kind of function, thus point
>> #1. Coroutines in Lua are an abstraction around a thread. In Lua you can
>> yield from nested function calls, without intermediate function invocations
>> having to know about coroutine semantics. In most other languages you
>> either
>> have to chain invocations with special decorators like await, or you have
>> to
>> use a special function type. In both cases you're violating functions as
>> first-class values as now you have at least two entirely distinct function
>> types.
>>
>> As a classic example, Lua's coroutines can be used to emulate green
>> threading. But just as importanly it means complex iterators are easier to
>> create because you can easily implement the logic of the iterator across
>> multiple functions, most or even all of which can be ignorant of coroutine
>> semantics. Whereas in other languages you're either going to have to
>> shoe-horn everything into a single function, or you're going to have to
>> mix-and-match regular functions with coroutine-specific functions.
>>
>> That's not to say that the more limited form of coroutines in other
>> languages isn't useful. But they're not nearly as useful and convenient as
>> in Lua.
>>
>> I can implement functions-as-coroutines in C using the preprocessor[1].
>> There are limitations to what you're allowed to do from the function. But
>> there are limitations to coroutines in other languages. And that's my
>> point:
>> Lua's coroutines really stand out wrt their level of abstraction.
>>
>>
>> [1] Here's the most recent implementation I wrote, which is pure ANSI C.
>> I've used this pattern or something like it dozens of times, and it's so
>> simple it's not really worth turning into a library.
>>
>> /*
>>  * Application code should define SM_RESTORE and SM_SAVE, and the
>>  * local variable pc.
>>  */
>> #define SM_ENTER \
>>         do { \
>>         static const int pc0 = __LINE__; \
>>         SM_RESTORE; \
>>         switch (pc0 + pc) { \
>>         case __LINE__: (void)0
>>
>> #define SM_SAVE_AND_DO(do_statement) \
>>         do { \
>>                 pc = __LINE__ - pc0; \
>>                 SM_SAVE; \
>>                 do_statement; \
>>                 case __LINE__: (void)0; \
>>         } while (0)
>>
>> #define SM_YIELD(rv) \
>>         SM_SAVE_AND_DO(return (rv))
>>
>> #define SM_EXIT \
>>         do { goto leave; } while (0)
>>
>> #define SM_LEAVE \
>>         leave: (void)0; \
>>         SM_SAVE_AND_DO(break); \
>>         } \
>>         } while (0)
>>
>> If you can use computed goto extensions (supported by every major compiler
>> except Visual Studio), you can implement a faster version with fewer
>> limitations. One obvious limitation to the above is that you cannot yield
>> from a nested switch statement. But for implementing iterators (the purpose
>> for which cooroutines are most often sold in other languages) the above is
>> adequate for even complex cases. I also use the above in C code to simplify
>> using asynchronous I/O, another use case coroutines are used for in other
>> languages.
>>
>>
>



Reply | Threaded
Open this post in threaded view
|

Re: Java can have coroutines!

William Ahern
In reply to this post by Emeka
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.


Reply | Threaded
Open this post in threaded view
|

Re: Java can have coroutines!

Sam Putman


On Mon, Aug 15, 2016 at 4:02 PM, William Ahern <[hidden email]> wrote:


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.



Have you brought this detailed argument to the Rust community? 

They're smart, very responsive, and *really like* zero-cost abstractions.