ALU capability (was Re: [E-Lang] Authority -- what is its dual?)

Jonathan A Rees
Mon, 22 Oct 2001 08:31:32 -0700

Thanks for accumulating the cc: list.

   Date: Thu, 18 Oct 2001 17:35:41 -0700
   From: "Mark S. Miller" <>

   Well, I've read your paper, and I don't see what I'm supposed to conclude 
   from it.

   At the beginning, you make a clear statement of the problem.  You then show 
   why the problem is hard to solve in Scheme itself, and hard to solve by 
   making small changes to Scheme.  I kept thinking to myself "But what about 
   his own T language? -- that would seem to be an approach that might keep 
   upwards compatibility while escaping the other problems."  E's treatment of 
   the "run" message, in order to enable function-like object behavior, is 
   based on a similar construct in Joule, which is based on T.

I have been struggling with articulating this idea for a long time,
and I apologize for the lack of clarity.  I think I'm talking about
something deeper than you are.

First I should say I believe that E and Scheme are indistinguishable
for the purposes of the EiaO problem, by the equivalence

       def _ :any { match [verb, args] { --STUFF-- } }
       (lambda (verb . args) --STUFF--)

(hoping I've got the E correct here).  So I'm not talking about how an
object is defined or invoked, or about functions vs. objects, but
about the basic idea of sending a message of some kind to an object.
(After all, the recipient has no idea how the construct was written in
the code for the sender!)  In E, the message is [verb, args], and in
Scheme, the message is simply all of the arguments.

(All T does in defining procedure call in terms of message passing is
to move the problem to a different place in the semantics.  T is very
complicated, because it has no "match" and the the verb might actually
be protected from the recipient (I'd have to check the manual!), so it
might have properties that E and Scheme don't.  E.g. it bundles rights
amplification and object identity into message dispatch, since verbs
are capability-like.  T objects are bizarre things that no one seems
to care about much, so I'll ignore them.)

I should say that I'm worried about the version of EiaO, where *all*
you have is message passing -- no identity or equality.  We might call
this "all you can do is send a message" or AYCDISAM, but I'll call it
"strong EiaO" instead.  Actually weak EiaO doesn't really qualify as
EiaO, since identity can be used to implement passive objects
(e.g. numbers) that are never sent messages.

The thesis (theorem?) is this:
  [Strong EiaO sucks] If under strong EiaO I obtain a novel object
  from an untrusted source, there's nothing I can do to reliably
  determine any property whatsoever of that object.

First of all, if you call a random object to ask it a question of any
kind, you can get a denial of service in the form of nontermination.
This can be mitigated by using an asychronous send or resource
limitation, in which case you may get no information about the object.

But it's worse than this.  Even if you ignore DOS and timeout, you
might think you could do challenge/response for authentication = "type
check" or brand predication.  Let's see how this would work: You send
a challenge, and get an object back that's the response to the
challenge.  Now how do you determine whether the response is the right
response?  Without identity, all you can possibly do is send a message
to the response -- and you're faced with the problem you had before.
Even if you have identity, the solution is pretty gross -- the two
ends of the authentication protocol would have to share the set (very
large) of potential response objects.

Well, maybe this can be fixed using encryption somehow.  Remember that
communication is a priori insecure because of things like

  (lambda args
    (spy-on! args)
    (let ((result (apply target args)))
      (spy-on! result)

So how do you do decryption under strong EiaO?  After you receive the
encrypted result (another object, by EiaO), you have to send a message
to it - there's nothing else you can do.  So how do you know that
communication with the message itself is private?  After all, you
received the encrypted message over an insecure channel, so a nasty
fake-encrypted-message might be substituted that spies on your attempt
at decryption.

I wish this were a theorem, but it's missing the part that says "and
there is no other way".  I think this is not far away, though.

Another approach is to say that we don't have to solve this particular
problem.  Perhaps there is some way to arrange for safety information
about all objects to be managed out of band, in which case you'd never
need to deal with an unknown object at all; but this would be awkward
odd, and not very OO.

I didn't think you were such an OO partisan.  If you are, then you
will probably find my reasons for despising it (other than the above)
to be very touchy-feely, and they are.  I think comprehensive OO
(occasional OO is fine) is a very poor metaphor for the world, a poor
tool for problem solving, and an unnatural way to think.  Here are
some particulars off the top of my head:

- It accounts poorly for symmetric interaction, such as chemical
  reactions and gravity.

- It deals poorly with information-oriented phenomena such as
  mathematical objects, copying, broadcast, encryption, caching, and
  signing.  E takes a step in the right direction by introducing the
  "selfless" notion, but this isn't enough.

- It usually has a very imperative, operational flavor to it.
  It begs you to write a recipe, not to describe the result that you
  want as functional languages do.  This isn't really inherent, and E
  is much better on this count than C++/Java.

- It forces you to always decide who's on top in any interaction,
  i.e. which object should define the method, a decision that's not
  always easy and one that you often want to change.

- It's a poor match both syntactically and semantically with
  natural language, making it awkward for expressing things that are
  in people's minds.

I have a feeling that Brian Smith (_On the Origin of Objects_ is a
philosophical critique of the conventional notions of "object") and I
agree on a lot of this, although I don't know because I don't
understand the book.

I stayed up too late!