Taxonomy of Facets & Composites

[Mark S. Miller]

An exciting development unprecedented in the history of capability systems: 
For the first time we have, on e-lang, a critical mass of different kinds of 
capability systems represented, adequate to develop taxonomies of the 
choices in engineering such systems.  We have at least:

* KeyKOS, represented by Norm & Bill
* EROS, represented by Jonathan
* Vulcan & Toontalk, represented by Ken, Dean, & MarkM
* Joule, represented by Dean & MarkM
* E, represented at least by MarkM, Chip, Bill, Danfuzz, & Eric
* Droplets, represented by Tyler
* E-speak2.2/split-capabilities, represented by Alan
* E-speak3.0/SPKI, represented by Alan & Bill
(Jonathan Rees, it would be wonderful to tempt you to join and represent the 
W7 view.)

Apologies for systems & people left out.  Bill, you get the diversity prize ;)

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

I now need words in order to propose one of the taxonomies this richness 
enables -- of patterns of faceting.  Although obviously not everyone agrees 
with this, I have found nothing in this discussion to discourage me from 
continuing to use terminology as defined in our 
http://www.erights.org/elib/capability/ode/ode-objects.html , so I will 
proceed using this terminology.  This terminology is inadequate to describe 
the flexibility of Ken's "Objects a Fresh Look", or Actors with "become", 
but it is adequate to describe at least KeyKOS, EROS, Joule, E, Droplets, 
and W7 (Rees's capability-secure Scheme).  I believe it to be adequate for 
E-speak3.0/SPKI.  As far as E-speak2.2/split-capabilities, I don't know.

To recap the terminological points in this document:

At the "laws of physics" level, there are only objects, not facets or 
composites.  An object is a combination of state and behavior.  Using Norm's 
note, I'd further say that the behavior computes new state and outgoing 
messages as a function of the current state and the incoming message.  An 
object reference refers to a given object.  An object only has one object 
reference.  (Or, all object references to the same object are equivalent.)  
A capability == an object reference in an system with object-level 
capability security.

By this definition, objects include:
* an E object -- what an E object-expression evaluates to.
* a W7 closure -- what a lambda-expression evaluates to.
* a Joule Server-Facet.
* a KeyKOS/EROS start capability including data-byte (facet identifier).

Where facets come in is during subjective aggregation.  When someone, for 
their own descriptive purposes, aggregates together a subgraph of objects 
into a conceptual unit, we call such a unit a "composite".  We call the 
entry objects of a composite -- those objects within the composite that may 
be referred to by objects outside the composite -- "facets".  In any object 
model pure enough to qualify as a capability system, overt (in-model) 
causality can only enter into a composite from outside via a message to a 
facet.

This note attempts to further develop a taxonomy of useful kinds of 
composites/facets.  Note that these are coupled.  We only end up with a 
certain kind of facet by defining a certain kind of composite, or vice 
versa.  Different descriptive purposes will carve the same system up into 
different composites.  (This taxonomy will also be important for the next 
discussion thread I'm about to start -- compiling E.)  Composites to be 
covered include:

* The KeyKOS/EROS domain.
* The Joule Server.
* The E/W7 "lexical-composite" pattern.
* The E vat.
* The access-rights/thinning pattern.

and should eventually include

* Confinement.
* Trust boundaries of various types.
and more...

                              Forseen vs Unforseen

The first distinction is Norm's wonderful split between forseen and 
unforseen facets.  A forseen facet is one whose behavior was designed in 
concert with the design of the "real" state this facet manipulates.  By 
"real" state, I once again don't mean anything fundamental -- facets are in 
the eye of the beholder -- I mean the state one refers to in explaining 
the semantics of invoking the facet.  By contrast, unforseen facets can 
occur after the fact by writing new entry objects that front-end other 
earlier-designed objects in the composite.

A good implementation-independent example of forseen facets: If objects A 
and B are two facets of the same composite, and if B was obtained (or could 
have been obtained) by asking A for a B-ish facet, then B-facet-ness was 
forseen by the designer of A.

                                Thinnings

Both forseen and unforseen facets can provide thinnings of other facets.  A 
thinning is defined as accepting a subset of the messages accepted by the 
facet being thinned, but for those message that are accepted, doing 
precisely what the thicker facet would have done.  The EC "Stone Cast" 
(explained in the message titled "Static Types vs Dynamic Capabilities (was: 
a few thoughts)") is an example of thinning with a front-end.  E-speak/SPKI 
is an example of thinning by having the receiver do an allow/disallow 
calculation based on unforgeable information in the capability, but then 
proceeding into common logic for the allowed cases.  

 From Jonathan's comments, I'd guess that the various primitive facets of a 
EROS node (ie, all facets other than start capabilities) are forseen 
thinnings.  Perhaps this is true for KeyKOS as well.  (Possibly the 
disagreements between Jonathan & I over the semantics of EROS is that he's 
trying to state a semantics of primitive capabilities, while I'm trying 
to state a semantics of start capabilities.)

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

The rest of the taxonomy elaborates implementation-dependent kinds of 
forseen facets.

                          Lexical-Composites / Lexical-Facets

In E and W7, a common pattern is to define several objects/closures within 
the same lexical scope.  The variables they each use freely are their 
instance variables.  Because they are defined in the same scope, they have 
the same set of variables available to use freely.  We define a 
lexical-composite to include exactly these objects, and the union of the 
variables they use freely.  This set of variables are the instance variables 
of the lexical-composite.  The objects defined in this scope that might be 
referred to from outside this scope are lexical-facets of this 
lexical-composite.  In the Ode, all diagrammed cases of a composite are in 
fact lexical-composites.

For purposes of compilation, we coarsen this a bit.  We define an allocation 
contour to be the outermost scope to which a variable declaration could be 
moved and have the variable instantiated exactly as often.  In Kernel-E, 
this is exactly a method, matcher, or loop.  A lexical-composite for 
purposes of compilation includes those objects defined within this 
allocation-contour, but not within a nested allocation-contour.  All such 
objects can share one array holding all instance variables of this 
lexical-composite.  Some Scheme compilers (like Orbit) have similar 
optimizations.  Since different component objects use different subsets of 
these variables freely, there is a danger of preventing the garbage 
collector from doing its job, but I'll deal with that in a separate note.

The Joule Server has many of the properties of a lexical-composite, but it's 
composite-ness is a distinct notion, rather than something for a compiler to 
infer-or-not.

The KeyKOS/EROS domain also has some of the properties of a 
lexical-composite, even though operating systems are syntax-free.  The use 
of memory addresses and clist-indexes by the code that constitutes the 
behavior of a domain's various facets are interpreted in the "scope" of that 
domain's address space.  This reiterates Jonathan Rees's profound statement 
that (paraphrasing): "clist indexes in capability OSes serve much the same 
function as names in the lambda calculus."

Finally, in a hypothetical capability secure variant of Java (such as 
Original-E), all the objects that are instances of classes defined in the 
same package have package-scope-based sibling-communications 
rights-amplifications rights to each other.  Therefore, it is useful to 
consider this set of objects jointly as being a composite.  I'm not sure if 
I want to lump this in with lexical-composites or to give it its own category.


                             Monitor-Composites / Synchronizing-Facets

Joule has just as much Scheme-nature as E, and has even more of a compulsion 
towards minimalism than E.  So why does Joule need explicit Server/Facet 
concepts while E can get away without them?  Because of their different 
views of concurrency.  E can be understood as a mostly sequential language, 
and its views on lexically shared side effects -- taken from Scheme -- are 
suitable only for languages in which only one of these sharers may run at a 
time.

Joule is massively concurrent.  While this isn't preemptive multithreading 
concurrency, it does make shared access by several objects to mutable state 
a more interesting matter than updating your own instance variables.  The 
normal variables which are simply in scope from lexical scoping are 
therefore pure lambda variables -- they are bindings directly to values, not 
to mutable locations holding values.  By contrast, "Server" introduces a set 
of mutable instance variables, to be mutated by the facets of the server.  In 
order to prevent the facets from interfering with each other, all facets of 
the same server coordinate on one mutual exclusion lock to gain entry to the 
server.  This is proper Tony Hoare monitor-like discipline -- the lock goes 
with the mutable state, not with the behavior.  (Actually, it's much better 
than monitors because Joule has no synchronous messages, but that's another 
matter.)

So we define a "monitor-composite" to be all objects that must hold the same 
mutual exclusion lock in order to proceed with their invocation 
behavior, and all state protected by that lock.  The synchronizing-facets of 
such a composite are the subset of these objects that might be pointed to 
from outside the composite.  Other examples of monitor-composites are 
KeyKOS/EROS domains and an E vat as a whole.

A Joule Server has a static set of facets, much as an E/W7 lexical-composite.  
However, a Joule Server is also Joule's monitor-composite, whereas E's 
monitor-composite -- the vat -- has a very dynamic number of facets -- all 
the objects in the vat that other vats may have remote references to.  
KeyKOS and EROS domains are capable of having a dynamic number of facets, 
but rarely do.  The normal domain style is more like the Joule server or the 
E/W7 lexical-composite.  

None of these distinctions are to argue for or against any of these systems. 
It is rather a demonstration that this taxonomy can give us insight into 
how these systems differ.  


         Cheers,
         --MarkM