Identity et al (was Re: [E-Lang] Authority -- what is its dual?)

[Jonathan A Rees]

Executive summary:

Apparently we still don't have common ground for communication.  I'm
trying to solve one problem (extract a bit from an unknown object) in
a particular world view (in which running time and connectedness are
basic semantic issues), and you're telling me I'm confused because
what I say is unrelated to the problem of verification (certain yes
answer with uncertain no or timeout) in a world in which system issues
are non-semantical extra frills.

I think Mark M has a good understanding of what I'm trying to get at
and shares much of my way of talking about things (even when he
disagrees), so I don't think I'm completely out to lunch.

The best way to settle such deep divides is to go formal, which is
what I'll do in the next week or so if no one jumps in to help me out.
In the meantime, please try to answer my question of which AYCDISAM
language / framework to use as a basis of discussion - one that is
simple, formal, and can be used a launching pad for explorations of
the important issues - i.e. needn't be replaced when new issues need
to be addressed.

--------------------------

   Date: Sun, 21 Oct 2001 23:17:44 -0700
   From: Dean Tribble <tribble@e-dean.com>

   What do you mean equivalent, and why do you think so?

Equivalence of features means that if you don't have one you can
implement it in terms of the other.  RA in terms of EQ is in my paper
(brand maintains population of all instances).  EQ in terms of
RA... well, maybe I spoke too quickly (as by now you know I often
do!).  I'll have to dive deeper into the EQ literature to answer.
Certainly if you have RA you can define objects on which you can do
EQ, but that would be an EQ limited to those objects, which doesn't
really count.

   The bounded time issue remains an issue entirely introduced by
   concurrency, not an issue of message passing.  Message passing
   reveals clearly that the issue is there, but it does not create the
   issue.

I see - your definition of sequential is that functions (objects) are
total, like mathematical functions.  Ordinarily, sequential means that
computations take some amount of time to run, and perhaps diverge.

One scenario I had in mind was a situation in which I, a sequential
process, want to check an object for timely termination before
invoking it synchronously.  But I'm much more interested in the
concurrent case.  Let's pick a particular semantics (satisfying
AYCDISAM) for the concurrent case so that we're not talking past one
another.  I was going to propose an operational semantics of CBV
lambda-calculus plus asynchronous message passing and state (maybe the
actors "become" primitive), but hadn't worked out the details.  Act I?
FCP?  Toontalk?  Pi-calculus?

   There are several types of complexity.  My main reason for moving away from 
   Lambda (while lifting most of the useful insights :-) is ...

I'm not saying lambda-calculus is the right thing, I was just
proposing it in the absence of anything better, and for its match with
AYCDISAM.  (But in my mind anything that satisfies AYCDISAM is a
flavor of lambda-calculus (algebraic structure with single binary
operator = call = send).)

   I'd like to reduce or ignore the issue of "bounded time".  The bounded time 
   is not in the verification.  In the above case, Alice has something she 
   will do when she gets a message with Kellogg-Cereal; there is no a priori 
   time-bound to that something.  If there were nothing she wanted to do with 
   the answer, then of course the verification would be irrelevant.

I wouldn't.  What Alice wants to do with the information of
Kelloggness is irrelevant.  Perhaps she wants information now that
will only be important later (this is what type declarations are
about).  She just wants a bit, on the basis of which she'll make some
decision, and she wants it now.  This is the difference between the
problem you're solving and the one I'm trying to solve.

But I will continue to figure out how you could be right.  You never
answered my question about modeling quantum mechanics - is this
related somehow?  You can't get information about something without
interfering with it (by sending it a message)?

   >Alice is careful not to lend too many computing resources to Cereal in
   >case Cereal is an unresponsive service denier.
   Now I need to introduce a very important OO concept:

This was an aside.  Of course Cereal may come with its own resources,
in which case Alice needn't lend any resources, and the condition is
trivially satisfied.

   Thus, in the above example, Alice should not and probably does not care 
   about the resources or time required to determine Kellogg-ness.

Of course she does.  She wants to know the answer, NOW.  Alice is
mortal.  Time is important.

   - you are casually introducing into an extremely narrow example the *HUGE* 
   issues of locality, migration, and disconnection which are all at a 
   different conceptual layer of the system.

I thought they were on the table already, and I don't think they can
be avoided.  We started out talking about AYCDISAM and the
appropriateness of the OO metaphor.  Connectedness, bandwidth,
mobility, etc. are all basic properties of the real world, not
details.  I'm looking for simple models and metaphors that can grow to
capture idealizations of all these phenomena.  I believe such models
should exist and shouldn't be so huge.  In any case, if they are at a
different conceptual layer, and you still claim that AYCDISAM and OO
are all-encompassing metaphors, then we should be able to apply
AYCDISAM at those other layers, and this should be a graceful process.
If we get stuck, then the claim is refuted.

We can start the analysis by considering different simplifying
assumptions, such as latency across a capability = either 1 or
infinity (or perhaps 0 or infinity), and then work towards
strengthening results by weakening the assumptions.  It sounds like
your RA implementation assumes bounded latency, but your assumptions
need to be made explicit so that we don't fight.  (Yes, I'm guilty of
not articulating assumptions too.)

   By analogy, its like bringing up 
   issues about multiprocessor synchronization for weak pointers and 
   finalization.  They are real issues that do indeed impact what we are 
   talking about, but it's a different conversation.

These sound like computer-geek things, not fundamental issues around
the object metaphor.  Concurrency and resource use are fundamental
ideas in all of science and computer science.  Synchronization
generally is pretty important, although I don't know what
multiprocessors have to do with anything.  Weak pointers and
finalization can be ignored for quite a while, unless we discover that
they have some legitimate analogs outside of the narrow, parochial
field of software engineering.

   Addressing the kind of 
   thing you are talking about is a system design thing, not so much a 
   semantic thing.  For example, the Brand implementation can have presences 
   (bit of code that together make up the virtual distributed object) on all 
   the machines that care about Kellogg-ness.

Then we have different ideas about semantics.  To me, concurrency and
resources are semantically fundamental.  In science, everything starts
with these issues: QM, relativity, evolution, ecology....  If the OO
dogma is true, it should equally well at all levels of analysis.

   - in the real world, doing this with signatures is beyond 
   nightmarish.  Distribution of keys is *exactly* the same problem of 
   distribution of capabilities.  How do you know that you have the actual 
   Kellogg key?  How do you get a new one if that one is compromised or 
   expired?

Then let's come up with an idealization with clean semantics that
captures the right way to do it.  I don't see why this is a tall
order, since we already have the capability model as an idealization
of cryptography and/or physical security.  Digital signatures also
seem perfectly natural to me and should have a simple idealization.  I
had thought that RA could be used to implement signatures.
Distribution and recovery are things that can be solved within the
framework - and if they can't be, my original critique of the
framework (OO) is strengthened.

   By definition, EQ can tell the difference between "transparent"
   forwarders, so if there is EQ, then you fundamentally cannot have
   transparent forwarders.

Tell me your definition of EQ then.  I was referring to the following:

   Date: Sat, 20 Oct 2001 21:11:56 -0700
   From: "Mark S. Miller" <markm@caplet.com>
   ... in Act-1 or Joule, a user-defined transparent 
   forwarder in front of an object cannot be distinguished from the object 
   itself.

The usual informal definition of EQ (in my experience) is that if you
hold two ways to refer to something, then EQ will tell whether the two
ways both refer to a single thing; equivalently, whether you can
replace one reference by the other with no observable effect.
Formalizing this definition is impossible, since with this EQ in the
language you can make two objects that are the same only if they
aren't; besides which, operational sameness isn't computable.  So you
use a more conservative definition in order to make it tractable,
making identity distinctions between objects that have no other reason
to be distinct.

My apologies for not being on top of E's or Joule's definitions.
Perhaps you can send me a URL to your favorite definition of EQ.

-JAR