[E-Lang] E FAQ

[Mark S. Miller]

At 07:16 PM Thursday 9/27/01, Jonathan A Rees wrote:
>   I'm not sure what relevance of "shared state" you have in mind for this 
>   question.
>
>What I mean is that if objects never shared state, in the form of
>mutable variables and data structures, then you'd have a Hewittesque
>world of pure actors, and the notion of "vat" would go away since it
>would coincide with "object" (in E terms, each object would have its
>own vat).  

I believe the issue of shared state is more subtle than I think you may be 
thinking.  Though E has lexically shared state variables in the Scheme 
style, the issue is independent of that.  Shared mutable "data structures", 
ie, objects, is the issue, but Actors have that too.  Consider the following 
session:

    ? def aliceMaker(bob, carol) :any {
    >     def alice() :any {
    >         bob(carol)
    >         carol()
    >     }
    > }
    # value: <aliceMaker>
    
    ? def carolMaker(var counter) :any {
    >     def carol() :any {
    >         counter += 1
    >     }
    > }
    # value: <carolMaker>
    
    ? def carol := carolMaker(3)
    # value: <carol>
    
    ? carol()
    # value: 4
    
    ? def bob(carol) {
    >     carol()
    > }
    # value: <bob>
    
    ? def alice := aliceMaker(bob, carol)
    # value: <alice>
    
    ? alice()
    # value: 6

The call to 'alice()' must return '6' because the synchronous side effects 
caused by Alice's call to 'bob(carol)' must take place before execution 
resumes in Alice.  This is conventional sequential-imperative programming.

To get an Actor-like (or Joule-like, or Concurrent Prolog-like) program, 
replace every immediate call with an eventual send.  Now the arrival order 
of Bob's message to Carol and Alice's message to Carol is non-deterministic. 
This has advantages and disadvantages over conventional 
sequential-imperative programming.  But the fatal disadvantage is a severe 
loss of familiar guarantees, and a consequent need to relearn how to program 
without them.

If Alice's body instead said 'bob <- (carol)', but everything else were the 
same, then the call to 'alice()' would necessarily return '5', since the side 
effects caused by an eventual send are guaranteed not to effect the state 
synchronously accessible from the current turn.  That this mixture of styles 
gives new useful strong guarantees is the one truly new invention of E (due 
to Doug Barnes).

What about simulating conventional sequential-imperative programming in 
Actors using continuation-passing?  After all, Actors invented continuation 
passing, and Scheme got it from there.  We must then make a choice: how to 
translate Alice's body to CPS.  

As I understand the normal Actor style on such matters, since there is no 
statically apparent coupling between the two send-expressions inside Alice, 
we'd translate this to the simultaneous sending (in one event) of two 
concurrent messages.  We would then still have the non-deterministic arrival 
ordering of messages to Carol, and the consequent need to relearn how to 
program.

If, instead, we enclose the second statement in the continuation of the 
first, then we have successfully simulated sequential execution.  However, 
if we do this everywhere, then we've reduced Actors to Scheme and have lost 
all concurrency.

To get our concurrency back, we'd need a notation in the pre-CPS-transform 
language that means "Do this send separately, and don't put the rest of the 
method in the continuation of this invocation."  If we use "<-" for this new 
notation, we're on our way to E.  

I speculate that any program that would be correct in this weaker language 
would also be correct in E, but E, by providing more guarantees (that in 
practice cost nothing), such as the isolation turns from each other, allows 
more useful programs and patterns to be correct.  For example, I don't think 
MarcS' notaryMaker http://www.skyhunter.com/marcs/ewalnut.html#SEC45 could 
be written in Actors without an unreasonable amount of pain.  (When I first 
saw him use this technique, it took me fully by surprise, as I'd gotten used 
to such things being impossible.)


>If an actors partisan looks at E, s/he will want a
>justification of the vat concept (since it limits parallelism and
>makes object relationships non-uniform), and from what I can tell,
>that justification is the assertion that synchronous access to shared
>state is convenient and useful, 

Yup.

>and is somehow stylistically and
>psychologically distinct from message passing 

I hope my example above helps clarify that it's both more similar and more 
different than an actor partisan may have thought.

>and more vulnerable to
>screwups (thus benefiting from the safety of the event loop).

I think this is a strange way to put it.  Actors already use an event loop.  
E merely enlarges an event from a single (post-CPS-transform) method body to 
an entire sequential imperative call chain.  To put it another way, at vat 
granularity, E is a pure actors language, and a vat is a (dynamically 
multi-faceted) pure actor with large internals.

I think the screwups you refer to come from threading, which both systems 
wisely avoid.


>There are probably other frameworks (concurrent prolog??) that could
>replace "actors" in the previous paragraph, so it's not a totally
>arcane question.

I believe all this applies equally well to Actors, Concurrent Prolog, Joule, 
and Toontalk.  We need a name for this category.  If partisans of these 
others don't mind, I propose "Actor-like", since Hewitt did it first and 
almost perfectly.  What other language paradigms are in this category?  How 
would one classify Erlang?  Mozart?


>The question is there mainly because of Henry Lieberman, with whom I
>had several agonizing discussions about E, although Gerry Sussman
>asked it as well.  I feel I still don't have a crisp answer.  Perhaps
>I'm just being a bit slow.

Please forward this thread and invite them to join the list.  Thanks!


        Cheers,
        --MarkM