[E-Lang] Why Not Coroutines? (was: Deadlock-free [was what is good
Mark S. Miller
Wed, 18 Jul 2001 13:36:38 -0700
At 04:45 PM Tuesday 7/17/01, Dan Moniz wrote:
>So, in as much as my motive is to inform, I'd like to have more people
>consider coroutines. I'm not sure if they make sense for E (I would
>initially tend to doubt it, since Java already provides threads, but seeing
>as how this discussion arose out of possible changes to Java thread support,
>I suppose it's germane), but they do make sense in many other places where
>threads just seem to be too much bother than their worth.
Apologies for a long answer to a simple question. The issues raised are
hard (for me at least) to explain well, but important enough to explain
One of E's ancestors, Tclio/Webmart http://www.agorics.com/webmart.html
http://www.sun.com/960201/cover/webmart.html was based coroutine scheduling.
On the liveness vs corruption vs expressiveness tradeoff, a pure
coroutine-based system falls somewhere between a pre-emptive multi-threaded
system and a pure event-loop system, but closer to the event-loop system.
Indeed, one can transform a code written for a coroutine system (like
WebMart) into code for a pure event-loop system (like E). As is often the
case with such "equivalence" preserving transforms, the transformation is
our best means for understanding how these systems do and don't differ.
This particular transformation is already well documented, though in a
different context. It is the transformation to continuation-passing style
Anywhere a method calls one of the coroutining primitives that may cause it
to block, transform it instead to put the rest of the method in a when-catch
block to be scheduled when the coroutine call would have returned. Of
course, you must likewise transform all callers of this method, and all
their callers in turn.
The seeming cost of the above transformation is a non-issue. Compilers for
various lambda languages similar to E (eg, Scheme, ML) often choose to
transform all code to continuation passing style early in compilation, and
the jury is still out over whether this is a net win or lose on quality of
the resulting code.
Rather, the issue is expressiveness, but in a surprising way. Let's start
by arguing expressiveness in the other direction, and then seeing what's
wrong with the argument.
Since this transformation is possible and correctness preserving, by not
providing it, E makes the programmer transform their continuations by
hand. They could write such a tool to transform their own programs, and so
get the expressiveness of the continuation notation, while still living
within the E framework. Since they can do this, and the result would be
more expressive, E may as well provide coroutines itself. Whether E
provides them by transformation or primitively (but equivalently to the
result of the transformation) then becomes a mere implementation matter.
There are two things wrong with this argument:
A) It identifies "expressiveness" with notational convenience.
By making the programmer manually write in the when/catch (or continuation
passing) style around possible blockage points, the notation of E programs
thereby captures a crucial distinction: *When may the state change out from
under you?* Zooko writes about Multi-Threaded Hell:
>when looking at the source code of an object, you have to imagine that two or
>more threads could be accessing the object's state at the same time. Therefore
>you can rely on very little in the way of "known facts about the state" while
>trying to debug a piece of code.
This fits very well with the Hayekian explanation of the concurrency problem
on http://www.erights.org/elib/concurrency/event-loop.html as one of plan
interference, and the resulting punch line "Avoid stale stack frames!".
When coding, I, and I believe most programmers, need a strong convention
about what boundaries in a program represent places where they need to
recheck assumption, because things can change since "they" last looked. (Or
rather, when the narrative in their head about what the program is doing last
looked.) Our naive intuitions from sequential programming are mostly
inarticulate, but go something like:
1) On entry to a function/method, assume state invariants are intact, but
within those constraints anything may have changed. (For "internal" calls,
you can't even assume state invariants are intact, but you should at least
be able to be locally aware of this delicate issue. This should also be
less of an issue for E for reasons I can explain if there's interest.)
2) From one instruction/expression/statement to the next, assume that the
immediately accessible world is only affected in the ways I (this code)
3) Between a call and a return, assume that the callee only affects the world
in way I can understand. (This is strengthened in a pointer-safe language,
and especially in a capability language, in that we may have a principled
basis for reasoning about the what state the callee may and may not affect.)
Advocates of pre-emptive shared-memory multithreading would have us relearn
#2 and #3. I say #2 is too valuable and relearning it is too hard, so forget it.
Advocates of coroutines would let us keep #2, but have us relearn #3. We
see by the hypothetical transformation, combined with a coroutine-based
scheduler, that the programmer using such a hypothetical transformer is now
writing source code that confuses #1 and #3. Put another way, since the
transformer silently turns #3 into #1, on return from a call, we would now
have to be as assumption-free about the current state as we normally are on
entry to a method.
Traditional pure event-loop languages (Actors...Toontalk) have not had
call/return, but are faithful to intuitions #1 and #2.
E is faithful to all three intuitions.
"So why doesn't a when-catch body look like the function definition it is?"
Well, I tried to do so, for the above reasons, but the notation was clunky.
However, to emphasize that the body is done *later* (ie, when assumptions
may have changed), I put the "->" in the syntax between the immediate part
(on the left) and the eventual part (or the right). I also made the right
hand side look approximately like a nested function definition it gets
transformed into. We'll see if these are good enough reminders.
The other thing wrong with the hypothetical argument?
B) Our hypothetical programmer has no means to transform clients he doesn't
When a Scheme compiler does a CPS transform, it transforms the whole program
-- meaning all code in the transitive call graph. While our hypothetical
programmer can write and apply a hypothetical transformer to his own code,
so that he can write in E-with-coroutines. He cannot transparently cause
this transformation to be applied to callers of his that he didn't write and
doesn't control. Therefore, although he can chose to knowingly endanger
himself by obscuring #1 and #3 in his notation, he cannot endanger anyone
else without their knowledge.