2.4.1 Predicate Objects and Inheritance

For normal objects, one object is a child of another object exactly when the relationship is declared explicitly through isa declarations by the programmer. Predicate objects, on the other hand, support a form of automatic property-based classification: an object O is automatically considered a child of a predicate object P exactly when the following two conditions are satisfied:

• the object O is a descendant of each of the parents of the predicate object P, and
• the predicate expression of the predicate object P evaluates to true, when evaluated in a scope where each of the predicate object's parent names is bound to the object O.

By evaluating the predicate expression in a context where the parent names refer to the object being tested, the predicate expression can query the value or state of the object.

Since the state of an object can change over time (fields can be mutable), the results of predicate expressions evaluated on the object can change. If this happens, the system will automatically reclassify the object, recomputing its implicit inheritance links. For example, when a buffer object becomes full, the predicates associated with the non_full_buffer and full_buffer predicate objects both change, and the inheritance graph of the buffer object is updated. As a result, different methods may be used to respond to messages, such as the put message in the filled buffer example. Predicate expressions are evaluated lazily as part of method lookup, rather than eagerly as the state of an object changes. Only when the value of some predicate expression is needed to determine the outcome of method lookup is the predicate evaluated. A separate paper describes efficient implementation schemes for predicate objects [Chambers 93].

If a predicate object inherits from another predicate object, it is a special case of that parent predicate object. This is because the child predicate object will only be in force whenever its parent predicate object's predicate evaluates to true. In essence, the parent's predicate expression is implicitly conjoined with the child's predicate expression. A non-predicate object also may inherit explicitly from a predicate object, with the implication that the predicate expression will always evaluate to true for the child object; the system verifies this assertion dynamically. For example, an unbounded buffer object might inherit explicitly from the non_full_buffer predicate object.

A predicate object need not have a when clause, as illustrated by the partially_full_buffer predicate object defined above. Such a predicate object may still depend on a condition if at least one of its ancestors is a predicate object. In the above example, the partially_full_buffer predicate object has no explicit predicate expression, yet since an object only inherits from partially_full_buffer whenever it already inherits from both non_empty_buffer and non_full_buffer, the partially_full_buffer predicate object effectively repeats the conjunction of the predicate expressions of its parents, in this case that the buffer be neither empty nor full.

Predicate objects are intended to interact well with normal inheritance among data abstractions. If an abstraction is implemented by inheriting from some other implementation, any predicate objects that specialize the parent implementation will automatically specialize the child implementation whenever it is in the appropriate state. For example, a new implementation of bounded buffers could be built that used a fixed-length array with insert and remove positions that cycle around the array:[4]

object circular_buffer isa buffer;
	field array(b@circular_buffer); -- a fixed-length array of elements
	var field insert_pos(b@circular_buffer); -- an index into the array
	var field remove_pos(b@circular_buffer); -- another integer index
	method max_size(b@circular_buffer) { b.array.length }
	method length(b@circular_buffer) {
		-- % is modulus operator
		(b.insert_pos - b.remove_pos) % b.array.length }

predicate non_empty_circular_buffer isa circular_buffer, non_empty_buffer;
	method get(b@non_empty_circular_buffer) {
		var x := fetch(b.array, b.remove_pos);
		b.remove_pos := (b.remove_pos + 1) % b.array.length;
		x }

predicate non_full_circular_buffer isa circular_buffer, non_full_buffer;
	method put(b@non_full_circular_buffer, x) {
		store(b.array, b.insert_pos, x);
		b.insert_pos := (b.insert_pos + 1) % b.array.length; }

The following diagram illustrates the extended inheritance graph for bounded and circular buffers (the partially_full_buffer predicate object is omitted):

Since the circular_buffer implementation inherits from the original buffer object, a circular_buffer object will automatically inherit from the empty_buffer or full_buffer predicate object whenever the circular_buffer happens to be in one of those states. No empty_circular_buffer or full_circular_buffer objects need to be implemented if specialized behavior is not needed. The non_empty_circular_buffer and non_full_circular_buffer predicate objects are needed to override the default get and put methods in the non-blocking states. Any object that inherits from circular_buffer and that also satisfies the predicate associated with non_empty_buffer will automatically be classified as a non_empty_circular_buffer.

The specification of when an object inherits from a predicate object implicitly places a predicate object just below its immediate parents and after all other normal children of the parents. For example, consider an empty circular buffer object. Both the buffer object and its parent, the circular_buffer object, will be considered to inherit from the empty_buffer predicate object. Because circular_buffer is considered to inherit from empty_buffer, any methods attached to circular_buffer will override methods attached to empty_buffer. Often this is the desired behavior, but at other times it might be preferable for methods attached to predicate objects to override methods attached to "cousin" normal objects.[5] If this were the case, then the buffer code could be simplified somewhat, as follows:

object buffer isa collection;
	... -- elements, length, etc.
	method get(b@buffer) { remove_from_front(b.elements) }
	method put(b@buffer, x) { add_to_back(b.elements, x); }

predicate empty_buffer isa buffer when buffer.is_empty;
	method get(b@empty_buffer) { ... } -- raise error or block caller

predicate full_buffer isa buffer when buffer.is_full;
	method put(b@full_buffer, x) { ... } -- raise error or block caller

object circular_buffer isa buffer;
	... -- array, insert_pos, length, etc.
	method get(b@circular_buffer) {
		var x := fetch(b.array, b.remove_pos);
		b.remove_pos := (b.remove_pos + 1) % b.array.length;
		x }
	method put(b@circular_buffer, x) {
		store(b.array, b.insert_pos, x);
		b.insert_pos := (b.insert_pos + 1) % b.array.length; }

The non-blocking versions of get and put would be associated with the buffer object directly, and the non_empty_buffer, non_full_buffer, and partially_full_buffer predicate objects could be removed (if desired). The non-blocking get and put routines for circular buffers would similarly be moved up to the circular_buffer object itself, with the non_empty_circular_buffer and non_full_circular_buffer predicate objects being removed also. If the methods attached to the empty_buffer object were considered to override those of the circular_buffer object, then sending get to a circular buffer that was empty would (correctly) invoke the empty_buffer implementation. In the current semantics of predicate objects in Cecil, however, the circular_buffer's implementation of get would be invoked, leading to an error. A third potential semantics would be to consider the predicate object to be unordered with respect to "cousin" objects, and methods defined on two cousins to be mutually ambiguous. More experience with predicate objects is needed to adequately resolve this question.