[E-Lang] Why Not Coroutines? (was: Deadlock-free [was what is good about E?])

[Mark S. Miller]

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 
anyway ;)

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 
(CPS)
http://www.google.com/search?q=%22continuation+passing+style%22&sourceid=opera&num=50

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.

<hypothetical-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.
</hypothetical-argument>

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) 
affects it.

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 
control.

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.


        Cheers,
        --MarkM