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

[Jonathan S. Shapiro]

> Dan Moniz writes:
>
> Those 2 web pages describe coroutines, but Mark is talking about
> coroutine *threads* aka user or cooperative threads.
> Different things.  Eg, unless I'm really missing something, one cannot
> have one coroutine blocked on I/O while another coroutine is busy.

We are running into a fundamental confusion about the meaning of the term
"thread".
When we speak of threads, we actually are talking about two separate things:
a continuation and an activity (there is no common term for the second; I
will use "activity" here, following the conventions of Chorus).

Let me make an attempt to confuse matters further by attempting a more
precise description of what is going on with coroutines vs. threading. I
hope that Jonathan Rees will correct anything that I mess up, for reasons
that will become obvious.

First, we need to be clear about how instruction execution works for
purposes of this discussion. An instruction is an atomic unit whose effects
on the state of the machine either happen or they do not. [I'm going to
ignore instructions like S/370 string move, which are restartable in
intermediate states, so those of you who know too much about architecture
should take "instruction" here to mean "unit of operation" in the sense of
the S/360 or S/370 PrincOps and lets leave that confusion out of things.]

What it means for an instruction to execute is that the processor has
accepted (as input) one continuation and has generated (as output) a second
continuation by performing the operation named by the instruction pointer of
the input continuation. The state transformation from the first continuation
to the second is determined by the particular instruction that is executed.

At this point, I need to introduce a new term: "activity". An "activity" is
the "motivating force" behind the execution. A continuation makes progress
(i.e. executes instructions) if there is an activity associated with that
continuation.

When we introduce co-routines in the traditional language-oriented
mechanism, what we have really done is to introduce the possibility of
multiple, *named* continuations in the machine, and introduced an
instruction whose effect is to re-bind a particular activity with some other
continuation. The general form of instruction execution is now as follows:

1. Perform the operation designated by the active continuation, yielding a
new continuation.
2. rebind the activity to some new continuation, usually, but not
necessarily, the result of step (1).

[I have not addressed the notion of execution stream names or side-effecting
the bindings of these, but I don't think these are relevant to the
discussion at hand.]

So far, note, we have no operation that raises the possibility of multiple
*activities* simultaneous in a given system.

I believe that the description given above fully characterizes the execution
model of E vats (insofar as I understand them). The key point is that so
long as there is exactly one activity, execution remains sequential and
deterministic.  You can cheat slightly by borrowing ideas from dataflow
computation. It is not necessary that the actual computation be purely
deterministic. It is sufficient that the detectable state of the computation
correspond to the state of the deterministic computation.

In KeyKOS and EROS, the behavior of CALL and RETURN can also be captured
within the formulation I have given above. The SEND primitive (KeyKOS fork)
introduces a new operation: the ability to introduce a new "activity". In
EROS (KeyKOS), a SEND (FORK) operation proceeds as follows:

    The sending continuation executes an instruction
    The sending activity remains bound to the
        sending continuation
    A new activity is created that becomes bound to the
        receiving continuation, and begins executing
        instructions there.

[I have again skipped some details concerning message transfer. If you are
familiar with CPS-based compilation, you'll remember that continuations
accept a value, which is how messages get passed.]

Actually, it doesn't matter formally which activity ends up on which
continuation, as the only state of an activity in the formalism is the
identity of the continuation it interprets. The important point is that when
it's all over you have a new activity and you have two continuations that
are executing.

[In an operating system, it matters alot, as the activity is the fundamental
unit of scheduling, and there is a question about whether the sender should
be preempted in favor of the recipient.]


And finally, let me bring this back to the "threads" terminology.

In EROS/KeyKOS, when we say that "a domain is occupied by a thread", we mean
that there is an activity causing the instructions of the domain's
continuation to be interpreted.

POSIX unfortunately has other semantics associated with threads, but the
basic idea once again is that you have two (or more) continuations motivated
by distinct activities. [Note that the continuations can share state in
their closures. Thus threads can share address spaces.]


At the risk of self-promotion, one of the unusual ideas (inadequately)
expressed in my dissertation is the notion that an entire operating system
can be viewed as a virtual machine in the same way that a microprocessor
implements a virtual machine. It is this degree of precise specifiability
that makes the security of the EROS/KeyKOS rigorously analyzable. E, I
think, shares this property. It's all a rather natural idea in the languages
community, but fairly alien to the way that OS people think.


Jonathan