Side-effect free containers for E

[Dean Tribble]

This is one of my favorite O-O design topics, so I'll respond to both 
messages in one go....

At 07:06 PM 8/14/00 -0700, Mark S. Miller wrote:
>This is also along the lines of a design rule Dean has advocated (and
>presumably practiced) for Joule code: No subtypes that add authority.

I think so!  :-)

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

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.

>Of course, for E, the existence of such a tension is especially unfortunate,
>as E is trying to gently seduce object programmers into being capability
>programmers.  E's strategy depends on enabling new E programmers (but old
>object programmers) to build simple things quickly without having to learn
>very much.  So I think E must evaluate separately each case where these
>principles conflict.

I know of no principle that says extending interfaces is a priori good, 
only that it is possible.  Do you?  Most good designs in my experience have 
multiple implementations of interfaces, but very little extension of 
interfaces (i.e., substantial subtyping).  Thus, I don't think this is a 
conflict at all, especially not in the design of the standard 
libraries.  Though you will need to design them carefully, I would expect 
the result to be at least as wonderful :-)

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

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.

>For the two cases in front of us, I think Tyler probably wins on both 
>counts.

Yes.

>* For Sets and Maps, if I made Sets a separate data type, rather than just
>    how the domains of Maps behave, I would not be violating any pre-existing
>    expectation.

I hadn't registered that there was not a Set abstraction because I was 
thinking Xanadu collections.  Of course the domain of a Map is a Set (or 
maybe bag :-).  If you want to iterate through the domain, ask for the 
domain facet, which implements the Set interface.  Note that the Set 
interface does not provide a corresponding authority to get the Map facet.

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

Now on to Tyler's message---------------------------------

> > This is also along the lines of a design rule Dean has
>
>I think there is a significant design methodology issue here that,
>strangely enough, coincides with the recent discussion of facets (ie:
>the whole counter object thread).

As noted above, I consider facets to be one of the primary answers to this 
issue.

>In the case of containers, it is possible to dodge the issue entirely
>by simplifying the type hierarchy down to one. However, in general,
>saying "No subtypes that add authority" is a prohibition that offers
>no solution. It is only an excellent guidepost and a clear warning
>flag.

However, the rule #1 above provides slightly more direction:  you need a 
different capability :-)

>It seems so many of these issues are derived from the debate of
>delegation vs. inheritance.
>
>The other way to create authority aggregates is through delegation. In...

I generally agree with your discussion, with the following change:  I would 
phrase the alternatives as inheritance vs. *composition*, where delegation 
is merely one way of composing things that in many cases can introduce the 
same authority problems that inheritance does.  Thus *composition* is the 
way I address most such design problems, with the above Map example being a 
composition of a Map and a Set (which is approximately free because it is 
another facet on the same representation).

>The delegation solution also offers an important new advantage to the
>capability programmer. It allows you to leverage the type system to
>catch authority overflows. I believe this will be a driving force in
>the design of capability programs that is not present in object
>programming.

Delegation does *not* provide this if you merely use it to model an 
inheritance relationship.  Both composition and facets, however, do.

>Pictorially, an object design typically looks like a pyramid, with
>objects getting ever fatter as you descend the type hierarchy. I
>believe a good capability design should look like a collection of
>approximately uniformly small marbles with different shapes and sizes
>of boxes to put them in. The difference is that some object designers
>get their marbles confused with their boxes.

I didn't quite get the analogy, but I think I agree with sentiment :-)

>I think E's lexical scoping style will mean that inheritance style
>aggregates will rarely be a problem. I think we will mainly have to be
>careful when importing Java code into E, or reimplementing Java
>designs in E. So far, we certainly have some good empirical evidence
>to suggest that this is the case. Marcs wrote EDesk in E without
>having this problem and Markm couldn't add containers to E without
>having this problem.

I've occasionally been pleasantly surprised that some of the designs in the 
Java libraries have small interface bent.

>Amazing how language changes your thinking.

Heh heh.