2.4 Predicate Objects
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:
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]
The following diagram illustrates the extended inheritance graph for bounded and circular buffers (theobject
circular_bufferisa
buffer;field
array(b@circular_buffer); -- a fixed-length array of elementsvar field
insert_pos(b@circular_buffer); -- an index into the arrayvar field
remove_pos(b@circular_buffer); -- another integer indexmethod
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_bufferisa
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_bufferisa
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; }
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:
The non-blocking versions ofobject
bufferisa
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_bufferisa
bufferwhen
buffer.is_empty;method
get(b@empty_buffer) { ... } -- raise error or block caller
predicate
full_bufferisa
bufferwhen
buffer.is_full;method
put(b@full_buffer, x) { ... } -- raise error or block caller
object
circular_bufferisa
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; }
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.
buffer
's max_size
field with a method and then ignores the buffer's elements
field. In practice a more efficient implementation would break up buffer
into an abstract parent object and two child objects for the queue-based implementation and the circular array implementation.
Generated with Harlequin WebMaker