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

[Dean Tribble]

Your message may be the most interesting message that I have completely 
disagreed with in a long time :-)  I didn't incorporate many smileys, and 
it's late, so please interpret everything with the best of intentions :-)

   Date: Thu, 18 Oct 2001 17:35:41 -0700
>   From: "Mark S. Miller" <markm@caplet.com>
>
>   Well, I've read your paper, and I don't see what I'm supposed to conclude
>   from it.

I had the same reaction.

>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--)

This sounds like "Socrates is a man so all men are Socrates".  In the 
E/Joule computational model, lambda is a degenerate form of object; that 
does not mean that all objects are expressible as lambda.  Also, in Scheme, 
vectors, lists, etc. are not objects, and they can't be just swept them 
under the rug. Scheme has specific. built-in magic data-types that cannot be 
emulated/extended/anything by programmers.

Saying that in scheme one could implement some OO behavior is like saying 
that both languages are Turing complete.  It may be true, but is mostly 
beside the point.

>(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 care because they helped get energetic secrets correct in Joule.  I think 
that'as outside of the scope of this discussion, however :-)

>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.

This should be called "no eq".  Objects have identity, they just don't have 
eq.  This is truly fundamental because in a semantics of such a system, you 
need to represent the difference in identity between two stateful objects 
that happen to currently have the same value.  This requires a concept of 
identity even though no operation can ask what the identity is.  The result 
is that you can discover that two objects are different, but cannot prove 
(as a primitive) that they are the same.

For Joule, we worked out how to achieve all the properties achievable with 
eq in a language without eq as a primitive.  The last challange to fall 
(Tyler and MarkM were witnesses :-) was the Grant Matcher challange from E.

>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.

Of course it qualifies:  the big distinction we are making is between magic 
built-in datatypes that the user cannot emulate vs. everything has a uniform 
object semantics.

>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.

We have many counter examples.  This is what Joule verifiers, the KeyKOS 
factory patent, E Brands, FCP Logical Secrets, etc. are all about.  I think 
this hypothesis is simply false, though it was certainly interesting getting 
the first counter example.  The basic process is described below.

>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.

Then it probably was not the kind of object you were expecting.

>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.

I will describe the primary mechanism here.  I will not attempt to bottom it 
all out in this message, but it can be done.  You ask your verifier/brand(in 
Joule/E respectively) to "verify" the object.  It sends a challenge to the 
object.  In response to the challenge, the object (iff it is the kind of 
object required by the verifier) stores a pointer to itself in a location 
that is closely held by the object expected (e.g., system purses) and the 
verifier (e.g., the purse verifier).  The object then returns with no value. 
 The verifier then looks in the shared, closely held location, an extracts 
the direct pointer to the object, and returns it to you.  You now have a 
direct pointer to an object that obeys known code and a known contract, 
which you now use instead of the argument you started with.  This is all 
semantically implemented with message sending, though it is trivially 
optimizable in the typical case in which no-one is playing games with you.  
If there were semi-transparent forwarders around the object, they've been 
stripped off.

I expect that this should sounds very familiar to you, so I may be not 
understanding the point you are trying to make.

>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)
>      result))

This is what I would consider a transparent forwarder, exactly of the kind 
that the above verifier technique strips away.

>...
>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.

Do you agree that the counterexample generally disproves the hypothesis?

>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.

They were reasonable starting points to take as a challenge, which is one of 
the places Joule started:  how do you bottom out a pure message passing 
language with no eq.  It can be/has been done!

> 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.

I have exactly the opposite reaction:  multicast message passing is how the 
world works at all levels, and every other approach is sloppy thinking.

>Here are
>some particulars off the top of my head:
>
>- It accounts poorly for symmetric interaction, such as chemical
>  reactions and gravity.

The computation of these things is necessarily asymmetric in real computers. 
 If you want to come up with a model that pretends to be symmetric, you need 
to precisely talk about the asymmetric operations that accomplish that.  
Computers give you no other choice.

>- It deals poorly with information-oriented phenomena such as
>  mathematical objects, copying,

This are not clear enough examples for me to respond.  Can you clarify?

>broadcast,

Reality is multicast (this is a big difference between Joule and E).  Noi 
problem.  On uniprocessors, multicast is implemented by sequentially sending 
to the multiple recipients.  Again, that directly models what seems like 
should happen.

>encryption,

'dataObject encryptWith(key)'  Why is this not direct and precise?  If you 
prefer the abstraction 'encrypter encrypt(data, key)' that's a plausible 
alternative abstraction.

>caching,

As above, I don't know what the problem is.  I've built many, extremely 
reusable and sophisticated caching abstractions in OO, and use caching 
vastly more often and effectively than I have *ever* seen in any other 
programming approach.

>and
>  signing.

As above.

>  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.

Almost ever successful "functional" or "logic programming" program is 
written by people who thought operationally about the results.  I've seen 
lots of amateur prolog programs that took forever on trivial problems 
because they were written "declaratively".  In addition, with the ability to 
raise your expressive level of abstraction, you can make the operations 
appropriately abstract for the problem you are solving (e.g., match this 
graph pattern).  This supports conceptual decomposition and strong 
separation of concerns, without sweeping real computation issues under the rug.

>  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.

This is where OO design comes in.  When you take security concerns and a few 
other heuristics into account, most such separations are pretty easy.  And 
because of encapsulation, they are also easy to change.  I will however 
agree that there are lots of "OO" programmers that don't know where to draw 
these distinctions, and so they make messes.

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

DWIM died a long time ago.  Until there are much more intelligent machines 
and tools, all the characteristics you seem to be reaching for sound like 
devices for under-specifying requirements and solutions in ways that simply 
lead to inadequate, buggy, and surprising systems.  And at the point where 
people figure out what those vague desires would mean and how they could be 
implemented, an object can be built that implements that abstraction (a 
constraint solver, for instance).  thus, OO is a superset of most other 
design methodologies.

OK I may be overstating the case slightly :-)

OO thinking is valuable because it makes it possible to get a crisp handle 
on the abstractions being used to solve the problem.  It supports strong 
separation of concerns.  It straightforwardly models responsibilities and 
other security properties.  Etc.  No other approach has such breadth.

>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!

Tell me about it!  Look at the time :-)

dean