[E-Lang] Progress & Non-Progress Report

Dean Tribble tribble@e-dean.com
Sun, 20 May 2001 09:41:19 -0700


>So a statement like:
>
>      0 > i
>
>would not answer the question: "Is i a negative integer?". "i" could be 
>anything and can answer the question in any way it chooses.

Correct; it answers the question, "Is i less than 0", and does not imply 
anything about integer-hood.  This is to support user-extensible coercion 
for magnitudes.  Thus, if I have defined objects that implement infinities, 
Conway numbers, matrices, complex numbers, fractions, infinite precision 
reals, etc. they can interoperate transparently with the "built in" 
integers, floats, etc.

>What happens if "y" does not have a method named "lessThanFrom/2"?

Then it doesn't meet the contract of a number, and the default behavior 
associated with the definition of the "lessThanFrom" contract is 
invoked.  This default behavior is typically to throw a 
"NoSuchMethodError", but in this case would thrown a "NotANumberError".  If 
there was a more useful default behavior (like reveal "false"), that could 
be implemented there, instead.

Note that in Joule, message selectors are not strings.  They are the object 
responsible for what happens if the message is not understood.   This is 
used to implement type extension (an extremely useful concept).  Any new 
package of code can define new operations on any other type; the operation 
definition includes the behavior for the operation for objects that don't 
understand it.  Note that the default behavior has no special access to the 
object (just the capability to it)

>Can an "==" invocation result in a "NoSuchMethodError" if the arguments 
>are of incompatible types?

There is the generic "==" method which does not incorporate types into its 
double-dispatch (i.e., there is only "equalFrom", not 
"equalFromInteger").  A subtype, Foo, could implement "==" by having it 
send the "equalsFoo", with the default behavior of "equalsFoo" being to 
return false.  Since only other implementors of the Foo contract would have 
access to the equalsFoo unsealer, only they could respond with non-default 
behavior to the equalsFoo message.

Note that the generic "==" is really asking for the receiver to use some 
default equivalence notion.  Most types implement that by mapping to a more 
type-specific equivalence concept.  Thus, for integers, it maps generic 
equality to mathematical equality, but one can invoke mathematical equality 
directly (with different methods) and more precisely (e.g., with an epsilon 
for fuzzy equality).

>>>Is "==" just another method on the object?
>>
>>Essentially, though there is no primitive notion of identity equality 
>>because the only thing it means to point at an object is that you can 
>>send messages to it.  There may not be a single locus process, etc. that 
>>is the thing that has identity.  There is some small primitive support 
>>for classes that wish to represent their identity as simply the 
>>possession of a specific nonce, but that is less frequent than might be 
>>expected.
>
>If there is no primitive notion of identity equality, does that mean that 
>using a pointer to a remote object as a key in a hashtable will always 
>result in remote method invocations during a hashtable search? If the 
>answer to this question is yes, then Joule also has to deal with the 
>"settling of a forked reference" issue, but instead of resolving the 
>reference once, upon receipt, it essentially resolves it every time it is 
>used. This seems to pretty much preclude using remote references as keys 
>in a hashtable.

One of the most entertaining things about Joule is how careful one must be 
about such conclusions....

First, let's look at the simple universe in which the remote proxies don't 
assist with "==".  You are correct, the messages go over the wire.  BUT, 
fundamental to Joule is the realization that concurrency compensates for 
latency  (though I like Chip's variant:  "concurrency is your 
friend").  Those messages go over the wire in a packet with a whole lot of 
other messages.  The computation based on the result of that "==" hangs 
out, but that's just one clause of a larger program that has plenty of 
other things to do, including sending other messages to the same remote 
machine....  Though performance for this simple story depends somewhat on 
the program, it is completely transparent, requires no special support, and 
is far better performance than one might expect.

Of course, Joule is in many ways motivated by smart proxies, and all those 
proxies are written in Joule.  Thus, the remote proxies for an 
"identity-based" object could perfectly well have the nonce in them so that 
"==" could be computed at any given remote locale.  Delays in getting that 
nonce for rapid local eq just devolve to the above remote invocation 
process, but with no need for special case support.

>>>If so, doesn't this mean that your hashtable implementation "relies" on 
>>>the keys? If so, how can you make robust "server" objects with brittle 
>>>hashtables?

A hashtable can be made to not rely on its keys.  By this, I mean that the 
correct answer to a request given a key relies only on the correct behavior 
of the specified key, and is independent of the behavior of any other 
request of any other key.  (This is implemented by racing among all keys 
that match the hash of the supplied keys so the correct one will always be 
able to respond.)  For misbehaving keys, the answer might be wrong, but the 
hashtable is not broken.  The hashtable does not rely on the keys because 
it doesn't care if you shoot yourself in the foot by supplying bad keys.

A robust server has the same opportunity.  If its ability to function 
requires certain properties of the keys, then it must establish that those 
properties are true.  I think that this turns out to be extremely rare in 
practice, but it's straightforward.  More commonly, if the key is broken, 
then request about the key are broken, but the server is just fine.  Thus, 
the service does not rely on the keys.

As a quick aside, this conversation reminded me of one of the reasons I 
like multi-maps:  the keys become completely independent of each 
other.  With non-multimaps, adding a key requires testing against other keys.

>>If the server has an internal hash table with internally defined keys, 
>>then the server is only relying on its own stuff.
>>
>>If the server is using objects provided by the client for anything, it 
>>must not rely on promptness of those objects unless it makes prior arrangement.
>
>If "==" is just another method on an object, then the server also must not 
>rely on the object providing a stable response to the "==" method (ie: "a 
>== b" is true and then later "a == b" is false).

Unless of course it uses smart proxies locally that ensure monotonicity.

>  Does this mean that robust "server" objects require a vouching service 
> for all client provided objects that are to be used as a key in a hashtable?

Only if it actually relies on the key, of course.  BTW I have always 
preferred the Xanadu-style maps in which the keys must be positions in a 
coordinate space, so they obey a somewhat more interesting protocol then 
just object.  There is an unordered coordinate space for identity such that 
creating a position in that space can go through the "vouching" process.

There are several "vouch" functions that are primarily "give me a version 
of yourself with the following property".  They are used sparingly because 
they are rarely actually necessary, but they provide the kind of thing you 
are talking about.

>>   In E, that prior arrangement is made by requiring near objects or just 
>> using the identity of settled remote objects.  Joule has various other 
>> mechanisms by which robust servers could arrange to not care about 
>> promptness of arguments to send, but I haven't swapped in quite enough 
>> to describe any yet.  :-)
>>
>>(These are fun questions, BTW.  Any more? :-)
>
>I think this is boiling down to two main issues:
>
>#1 Without a built-in "==", it is not feasible to use remote pointers as 
>descriptors, since any check requires a remote invocation. For example, 
>this means hashtables should not use remote pointers as keys.

As above, I disagree.  For typical use, there will be proxies that support 
the simplified model of identity with smarts equivalent to E's proxies, but 
they are not built in magic.  There is specific support for rich proxies so 
that an object can be spread across the wire with some local functionality 
(e.g., eq) and some remote functionality.  The proxies in E are just a 
special case.  BTW with some of the PassByConstruction support, they may 
become more a special case in E as well.

Even without the above proxies, remote invocations over high-bandwidth 
lines cost latency, but there's plenty to do in the meantime, so it's 
typically easy to amortize.  More important, they require no code change 
(unlike in E).  Therefore, sending messages over the wire is not 
unreasonable, either.  (Note that it would be in any system without 
optimistic remote invocation!).

>#2 A built-in "==" guarantees the properites of the "==" operation. This 
>reduces the need for vouching services. For example, naive use of a 
>hashtable is safe with a built-in "==".
>
>These two issues give me concerns about the type of world I end up in 
>without some kind of built-in "==". I was hoping that these questions 
>would reveal some form of weak "==" in Joule that would somehow offer 
>reasonable solutions to these issues. Of the two issues, the second seems 
>likely to be the most bothersome. How do you cope with this in Joule?

There actually are a few weaker notions of EQ in Joule:

- a low level primitive capability that is closely held by the 
implementation, and virtualized by the comm layer, persistence layer, 
etc.  Because it can break transparency, it is not available to normal 
programs.
- specific type equalities such as numbers
- synergy support

Joule's point of view is that EQ is the hammer approach to synergy, and if 
it is a defined part of the language, then too many things look like either 
a nail (hashtables) or a thumb (distributed latency compensating remote 
objects).  In Joule, you can define objects that play the eq game when you 
really want to just pound out the problem, but as with multiple 
inheritance, the cases where it is actually a good idea turn out to be few 
and far between.  Instead, Joule makes it easy to ask the question, "what 
synergy do I need?" and provide an answer that does not rely on magic, is 
much easier to distribute, make concurrent, etc.

I'm sure I missed some points in here, so have at it :-)