[E-Lang] Promises, equality and trust

[Mark S. Miller]

These are great questions.  I'll give the quick answers in this message, and 
the longer ones in later messages.

At 02:54 PM Thursday 7/26/01, Mark Seaborn wrote:
>I have some questions about promises.
>
>It seems that promises are given special treatment in E.  When they
>resolve, promises *become* the reference they resolved to, rather than
>just being proxies.  

Correct.

>This has the effects that:
>
> * Immutable circular data structures can be created.  (Though I
>   wonder if this is a hazard, since it means that when traversing a
>   data structure you have to worry about whether it contains cycles.)

Yes, it does mean cycles of immutable data can be created, and it does mean 
that general traversal algorithms must deal with the resulting hazard.  
Since it's at least as hard to prevent cycles as to live with them, it's 
better to live with them because they're more expressive.  In fact, in the 
context of the overall E architecture, I don't think we had a choice.  I 
don't believe we could prevent cyclic data.

It's not all that hard to write traversal algorithms that are cycle 
tolerant, but you need some good examples and some practice.  When people 
don't, because they assume they won't encounter a cycle, or because they 
forgot about the issue, the consequences are normally fail-stop: stack 
exhaustion.

<An aside on VirtualMachineErrors, replay, and persistence>
Note: Stack exhaustion results in the throwing of a 
java.lang.OutOfMemoryError, which, in the current implementation, would 
unwind the stack and run finally clauses (E for unwind-protect) as you'd 
expect.  This is a bug. Instead, from the point of view of E-language code, 
the occurrence of any java.lang.VirtualMachineError must terminate the 
vat-incarnation before any further E-language code gets to run, since the 
computation state following such an error is non-replayable (and has other 
fatal problems as well).  If the vat is persistent, this is a vat-crash that 
may very well result in the automatic revival from previous checkpointed 
state.  Speculating now, part of configuring a vat's persistence may be to 
say how many time the same revival should be attempted in the face of 
repeated crashes that prevent us from reaching the next checkpointable state.
</An aside on VirtualMachineErrors, replay, and persistence>


> * Once resolved to an object, a promise stays resolved to that
>   object.  

Correct.

>This is useful for efficiency in terms of cacheing, and in
>   terms of reducing latency (if a resolved promise is passed to
>   another vat, the other vat gets the object the promise resolved to,
>   not a proxy).  It also seems useful from a correctness point of
>   view -- the object a promise is resolved to can't change underneath
>   you.  

All correct.

>This advantage seems to be thrown away by using the Miranda
>   method whenResolved for detecting resolution, 

Very perceptive, and more correct than not.  This is an ugly issue in the 
language, and I'm not at all confident I've ended up in the right place.  I 
believe the behavior seen by the "normal" programmer when interacting with 
"normal" programs is correct.  Here, I define a "normal" program as one that 
never uses the experimental Plumbing expression, and that never overrides 
whenMoreResolved and whenBroken.  (As of the next release, the old 
"whenResolved" message has transmuted into "whenMoreResolved" for reasons 
I'll be explaining.)  In any case, I'd consider a change here that preserves 
this "normal" behavior, and so would be "practically upwards compatible."  
If we figure out such an improvement, it should be relatively painless to 
shift to it, so it's good you're raising this issue now.  I'll postpone 
further discussion of this topic to another message.


>(Incidentally, what is the origin of the term `Miranda method'?
>Presumably it doesn't come from the language Miranda.)

In the U.S., one's Miranda rights include "If you cannot afford a 
lawyer, one will be provided for you".  They're named after this case:
http://www.thecapras.org/mcapra/miranda/rights.html .

If you don't provide a Miranda method from yourself, one will be provided 
for you.  


>Does a holder of a promise always get told about the promise's
>resolution, or does this information only come through the call to an
>observer passed to a whenResolved message, with the local proxy for
>the promise wrapping the observer passed in whenResolved so that it
>detects the resolution too?  (Giving whenResolved special treatment in
>this way does not seem very elegant.)

The latter.  The holder of a promise never gets told simply by virtue of 
holding. Rather, the holder of a promise can arrange to find out by means of 
the various "when..." constructs you already know about.  The holder of a 
promise can also check (ie, poll) by use of "Ref isResolved(expr)".

Your description of the implementation is essentially correct.  It doesn't 
seem very elegant to me either, but I've never come across or been able to 
think up anything better.  Suggestions would be great.


>Presumably promise references are tagged as being promises when they
>are sent in messages.  This would mean that promises cannot be
>implemented in the E language.  Is that right?

It used to simply be right.  Now it's half right.  The integrity of the 
state transition diagrams on 
http://www.erights.org/elib/concurrency/refmech.html are still guaranteed by 
the language kernel, but the comm system that stretches capabilities between 
address spaces no longer need be in the kernel -- these can now be written 
in normal E.  In fact, eventually I expect to replace the Java-written comm 
system with one written in E and given least authorities, so we can analyze 
our risks from the possibility of comm system bugs.  By the same token, it 
should be possible to have several comm systems of different design 
coexisting in the same vat.  Multiple coexisting comm systems of course 
raises various new complexities, which I'll postpone thinking about for now.

In order to do this, it needed to be possible for non-privileged code to 
supply the encoding and forwarding over the wire behavior behind an eventual 
ref.  This is provided by 
http://www.erights.org/elib/concurrency/refmech.html .  See 
http://www.eros-os.org/pipermail/e-lang/2001-April/005226.html , but keep in 
mind that Redirector was renamed ProxyResolver and RefHandler was renamed 
ProxyHandler.


>If the invocation of observers passed in whenResolved messages is the
>way promises get resolved to values, wouldn't that mean promises can
>get resolved to different values in different vats?  A promise that
>started out being equal to itself would end up splitting into
>inconsistent values.

Yes, but I believe this issue can't be fixed.  The rationale for the current 
design rests on that unproven belief, so there's definitely something to 
talk about.  More later.


>Another concern I have:  If Alice passes to Carol her reference to Bob,
>Carol's vat will have to establish a connection to Bob's vat in order
>to send messages to Bob (assuming all three live in different vats).
>Assuming Bob and Bob's vat are in collusion, Bob will be able to
>distinguish between messages from Alice and messages from Carol.
>
>If Bob doesn't want Alice to delegate Bob's authority to Carol,
>obviously Bob will not be able to stop this, but if Alice's default
>behaviour is to leave Carol to establish a new connection with Bob,
>Bob will be able to recognise this, and silently let Carol's reference
>to Bob do something different to Alice's reference to Bob.
>
>Should the default behaviour be to provide proxies to delegate
>authority unless we explicitly trust vats to play nice and ensure that
>a reference works the same regardless of what connection it is used
>through?
>
>I'm assuming the network is not anonymous, which I think is
>reasonable, but even if that's not the case, the
>connection-orientedness of E's protocol could lead to different
>behaviours of the same reference over different connections.


Fascinating.  What you're proposing is what E-Speak2.2 planned to do: have 
the default case be not to shorten paths (the case actually implemented), 
and then have a path shortening Granovetter introduction be something a 
program can explicitly request (AFAIK, their plan for this was sound, but it 
never got implemented).  I remember arguing with Alan over this years ago 
(remember Alan?), but yours is the first rationale for the E-Speak position 
I understand.

I still think default shortening is the right engineering decision, because 
the price of not shortening is too high, and the above price of shortening 
will IMO usually not be a practical issue.  Note that the issue is only 
defaults.  As in the planned E-Speak2.2, in E both are possible. It's just 
that the default is on the other foot.  Alice can always easily introduce 
Bob to a forwarder for Carol running in VatA.  Using the experimental 
PlumbingExpr for a moment,

    bob <- foo(def _ delegate { carol })

would do it.  The reason the PlumbingExpr is considered experimental, 
discouraged for now, and not even present in the language by default, is 
because of the need to settle exactly the kinds issues you raise earlier: 
What does it mean when an object overrides or doesn't implement Miranda 
methods involved in reference resolution?


        Cheers,
        --MarkM