Side-effect free containers for E

[Mark S. Miller]

At 02:21 PM 8/15/00 , Dean Tribble wrote:
>At 07:06 PM 8/14/00 -0700, Mark S. Miller wrote:
>>Echoing Ken's last message, I think this issue is the first showing a
>>tension between good capability protocol design practices, and good object
>>protocol design practices -- assuming the object designer isn't
>>concerned with security per se.  Subtyping, including subtyping that adds
>>authority, is part of how object programmers achieve lots of pleasant
>>polymorphism without having to say alot.
>
>I pretty much disagree with most of this :-)  I think this is another fine example of where capability design principles lead to uniformly better object designs (if it doesn't, its because you didn't properly apply the capability design principles...refute that! :-).  To rephrase in what hopefully comes across as an entertainingly provocative style: "subtyping, including subtyping that adds authority, is part of how a few expert designers occasionally make nice abstractions, but most programmers typically achieve large balls of mud with incoherent interfaces and contracts."

Frankly, you may be right.  But it would be interesting seeing you make this 
argument to object programmers without invoking security issues.  That's as 
in "security per se", as distinct from normal software engineering 
modularity issues.  From now on, I'll refer to the 
object-without-security-per-se perspective as simply the object perspective.

For concreteness, let's contrast two protocols for a Mutable Cell (ie, Slot 
or Location).  Using Java interface declarations as an interface description 
language (for which they are not bad):

Protocol M (for MarkM):

     public interface CellReader {
         Object getValue();
     }

     public interface CellEditor extends CellReader {
         CellReader readOnly();
         void setValue(Object newValue);
     }

Protocol DT (for Dean & Tyler):

     public interface CellReader {
         Object getValue();
     }

     public interface CellEditor {
         CellReader readOnly();
         void setValue(Object newValue);
     }

These two protocols are very similar.  In both, an instance of a CellEditor 
provides authority to modify the value of the Call (via setValue), and, 
directly or indirectly, provides authority to read the value of the Cell.  
An instance of CellEditor also provides a method to create a forseen facet 
providing read authority but not write authority to the value of the Cell.

I claim that Protocol DT is preferred from a capability perspective, but that 
protocol M is preferred from an object perspective.  I believe Dean claims 
that protocol DT is preferred from both perspectives.  If Dean should prove 
right on this example, then he's probably right on the more general claim.

(For clarity, the code examples that follow sufficiently declare all 
variables so as to pass a Java-rules static type checker.)

In protocol M, when someone holding a CellEditor, ce, 

     define ce :CellEditor := ...

wishes to read the value of the Cell, they merely do:

     define value := ce getValue

whereas in protocol DT, they must do

     define value := ce readOnly getValue

(which would also work in protocol M).  For this case, the second is more 
complicated than the first with no compensating virtue.

Now, let's say we have a foo function that only needs read access to the 
Cell.  It might be defined as

     define foo(cr :CellReader) ... { ... }

The holder of ce can call this either as

     foo(ce)
or
     foo(ce readOnly)

The first, of course, violates the principle of least authority, and so is 
much worse from a capability perspective.  However, the second is arguably 
more complex, and so is arguably worse from an object perspective.  In 
protocol DT, the first is an error that's caught early; either statically, 
if we've got a static type checker; or dynamically, by the ":CellReader" 
SlotGuard.



>Capability Design Rule #1:  All distinctions in authority are represented by different capabilities.  (Note that I'm rephrasing on the fly here to not confuse the people that still believe that objects are something you point to as opposed to the emergent phenomena of having pointed :-).
>
>A subclass that extends a superclass with more authority violates this rule (or rather, its instances do).  Note that a difference in function (potentially including additional operations) is not necessarily a difference in authority.  BTW: I do think that this particular problem is sufficiently subtle that it deserves its own principle.

Dean & I just had a long phone conversation.  I believe we agreed that the 
above paragraph conflates two issues.  The above example *does* obey 
capability design rule #1, but violates the "no subtypes that add authority" 
rule.  In both, a CellEditor instance provides both read and write authority 
over the value of the Cell.  In both, the object returned by the readOnly 
message provides only read authority.  In protocol M, an object of type 
CellReader may or may not provide write authority, since it may or may not 
also be a CellWriter.  In DT, there is no such ambiguity.  Perhaps Dean is 
reaching for a rule like Capability Design Rule #X:  All distinctions in 
static authority contracts are represented by different interface types.  
Rule #X is a static analog of Rule #1, but they are quite different.


>I know of no principle that says extending interfaces is a priori good, only that it is possible.  Do you?

I prefer empirical to a priori arguments anyway, so I refer again to the 
above Cell protocol designs.  The principle is expressive simplicity.


>>Curiously, KeyKOS and EROS are rife with subtypes that add authority (or,
>>equivalently, supertypes that subtract authority, ie, "thinning").  Since the
>>issue seems to be independent of language vs OS, it will be interesting to
>>see how KeyKOS and EROS folks react to this criticism.
>
>The key approach in Joule is, of course, facets (each facet is a different capability).  To design such that the write authority includes the read authority, the write authority just has an operation to return the read authority facet (which is a different capability).  This is cheap, and syntactically non-painful, prevents the kind of security exposure we discussed, and results in smaller interfaces.  (The result of smaller interfaces is more polymorphism, more reusability, etc. but that's a separate topic :-)

The DT protocol follows this description exactly.  We see it has a cost.


>This means that thinning as a strategy is to be avoided (in retrospect :-)--it defines a supertype with less authority.  Instead, KeyKOS, etc. should follow a strategy of facets in which the capability bits controls which orthogonal set of operations can be invoked, and you can never have a capability that allows invoking more than one of them.  Note that this does not affect the overall architecture, but just how domains functions are organized.

And the protocols of the primitive capabilities exported from the Kernel.  
I'm very curious how KeyKOS and EROS people will react to the proposal that 
their protocols be redesigned in this manner.  Guys, please speak up!


>>I created the extra polymorphism, though, precisely out of
>>    those best-practices object principles that we see here is in tension with
>>    good capability design principles.
>
>Just for consistency, I'll object to this here too :-)  There's no "best practice" violation involved.

Just for consistency, ....



         Cheers,
         --MarkM