Taxonomy of Facets & Composites
Mark S. Miller
Wed, 26 Jul 2000 23:56:12 -0700
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
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
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
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
* 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
* Trust boundaries of various types.
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.
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
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
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
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
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
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
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.