Taxonomy of Facets & Composites

[Karp, Alan]

A couple of minor points.

An e-speak object is a resource having an entry in the e-speak repository.

An e-speak facet is the set of operations allowed by the presented
capabilities.  In e-speak DR 3.0, the SPKI certificate contains the
reference to the resource and a list of allowed methods. In e-speak Beta
2.2, the repository entry for the resource contains pairs associating
permissions with a reference to the capability resource.  If this capability
was presented, the associated permissions become part of the facet.

One question.  Can we reason about a composite as a "has a" relation?  In
other words, can I think of a composite as an object having methods to
access the visible interface to the composite?

_________________________
Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278


> -----Original Message-----
> From: Mark S. Miller [mailto:markm@caplet.com]
> Sent: Wednesday, July 26, 2000 11:56 PM
> To: E Language Discussions
> Cc: Jonathan A Rees
> Subject: Taxonomy of Facets & Composites
> 
> 
> 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
>