A Theory of Objects suitable to the Conventional Machine

This is a companion to ideas about defining objects at the machine level.

This is a theory of objects as in OCAPs. It is not meant to exclude contradictory theories. It may be compatible with contradictory theories via mappings. Capabilities are sort of implicit here.

We define objects, capabilities and messages by mutual recursion. A capability denotes an object and may have some further properties that we will elucidate as we go. An object is composed of immutable behavior and mutable state. The state of an object may include capabilities and data. The behavior is likely a program whose only access is to its state. It addresses its data and capabilities explicitly. This needs to be made precise but not here and now.

Systems composed of objects will find that their logic depends on information about the behaviors of many or most of these objects but that information will be an emergent property in this theory, unlike Actors whose types provide an explicit place to keep what you know about other objects.

The behaviors of an object are operations on the data of its state as a conventional computer operates on the data in its memory, plus invocations of capabilities in its state further elucidated here. For object X to invoke a capability which designates object Y is to send a message which is delivered to the state of Y, whereupon the behavior of Y operates on its modified state. The most common outcome is for Y to invoke another capability designating X with a message which allows X to continue. The first message may include some of the data and capabilities from the state of X. The data generally includes some data that serves as an order code. Upon sending a message the object Y gets the message whereupon the state of the addressee incorporates the data and capabilities of the message among its own state and continues to operate (behave).

The state of an object is under exclusive control of its behavior, as influenced by messages it may receive.

In some system plans messages never exist except at the instant (atomic event) where they are assembled by the sender from the sender’s state and dispersed among the recipient’s state.

Meta

I find it necessary to introduce here a concrete feature of Keykos, the reply capability, that has made its way thru a few systems into seL4. A reply capability closely matches the CS notion of continuation. The reply capability denotes an object but with a property that distinguishes it from other capabilities to that object. There is a variation on sending a message that causes the system to include in the message a newly created reply capability designating the sender and leaving the sender object is a state that only messages addressed with the reply capability can reactivate it. This raises several issues that are resolved in Keykos. I am just now at a loss as how to proceed without narrowing the scope of this note to Keykos like systems. Some capability systems provide a stack as an additional primitive construct. The normal objection to continuations as the sole primitive is that the stack is so much more efficient. That is so for systems that impose these disciplines at compile time but Keykos found no way to maintain stack discipline on untrusted compilers such as are allowed in Keykos. Also the greater generality of continuations was needed.

Another fault in this story is that we omit the dynamic creation of new objects and their examination (debugging). This function is supported but not imposed by the Keykos kernel. There are several user replaceable objects outside the kernel that are relied upon to ensure that only the behavior of an object directly accesses its state. It is perfectly obvious to a Keykos theorist when this can be relied upon and I don’t think it has been explained anywhere in English. Those things conform to a deeper capability discipline which is not evident here and so this is not the most fundamental security theory. We must also raise the issue of resources, space and time, which Keykos chose to make explicit instead of ambient.

Variations

I see two sorts of variations: (1) essential and (2) inessential. Mainly, the essential variation impacts the system where the inessential impacts only the description of the system.

Expose “method index”? In this plan method selection is explained and perhaps facilitated in the foundations. Otherwise a method index is provided within the data of the method and the object’s behavior is responsible for validating the index, checking for conformance of parameter shapes with selected method, etc. Languages do this to great advantage at compile time to catch early errors and provide performance. My description of objects hides this detail. I consider this an important yet inessential variation.

Whether to allow concurrent processes into the same object is, I think, an essential difference. My intuition on schedulers undoubtedly biases this bias towards disallowing simultaneous processes in one object.