The Dynamic Specialization Mechanism

The dynamic object specialization mechanism in gbeta supports the modica-tion of an object at run-time such that it becomes an instance of a pattern that is less-equal than the pattern it was an instance of before the operation. This modication does not aect the identity of the object, and in particular all ex-isting references to the object will now see the more specialized object. This may for instance become evident because the behavior exhibited by the object when executing some methods has changed; or it may enable an alternative in a

whenimperative (a typecase) that was not enabled before, such that it becomes possible to access the object through a richer view, for example in order to call methods that the object did not have earlier. More information on the ^when imperative is given in Sect. 9.1.

Consider an object O which is an instance of a pattern P. After being dynamically specialized with the patternP⁰,Owill be an instance of the pattern P&P⁰, and this may aectO in various ways:

A. IfP P⁰ thenO is left unchanged: it was already an instance ofP⁰; this will of course always succeed.

B. If P and P⁰ share no mixins then all the part objects corresponding to the mixins of P⁰ are added to O (in more specic positions than all the existing P part objects, because that is the way `^&' works); there will be no interaction between the old and the new part objects except for a possible change in overall behavior due to added^do-parts; the operation will always succeed.

C. IfP⁰< P thenO will be enhanced with part objects corresponding to the mixins in P⁰ which are missing in P; this operation will succeed, unless it causes error 3, which is explained below. Note that error 3 only occurs when there is a variable attribute which is not^NONE, so it does not occur with new objects.

D. IfP and P⁰ share mixins but the shared mixins occur in the same order (this is the case if there is a patternQsuch thatP Q,P⁰Q, and Q contains all the shared mixins) then part objects will be added toO for

the missing mixins ofP⁰; this operation will succeed, unless it causes error 3 or error 2, explained below.

E. In the general case, part objects will be added toOfor the missing mixins ofP⁰, in the positions specied by the semantics of `^&'; this may fail with error 3, 2, or 1.

As we can see, dynamic object specialization is dangerous in the general case, but we believe that the less dangerous cases form recognizable and useful classes of usage of this mechanism; for the remaining cases, the potential errors will have to be handled, and alternative actions must be taken when it is detected that a given object specialization has failed. The failures come in three varieties, listed in order of their occurrence during the execution of the dynamic specialization operation:

1. The mergeP&P⁰may fail; if this happens then the requested object struc-ture is inconsistent, i.e., there is a pair of mixins, i and j, that both P andP⁰ contain, andP requiresito be more specic thanjwhereasP⁰ re-quires the opposite. Since the requested object structure cannot be built, the operation raises a run-time error immediately. Note that this error can only occur if both P andP⁰have at least two mixins each; a single-mixin pattern (just oneMainPart) is immune. Moreover, it can never happen for mixins i andj which are inherited from the same superpattern, directly or indirectly.

2. If the merge P&P⁰ succeeds then the new object structure can be built.

However, propagation may cause additional dynamic merge operations. If P and P⁰ further-bind the same virtual attribute in two dierent ways, then this will cause a dynamic merge that may fail. Further propagation is also possible, for instance to virtuals nested inside a shared virtual in P and P⁰. Note that if P and P⁰ do not have shared virtuals, or if at most one of them further-binds each shared virtual, then there will be no propagation and this error cannot occur.

3. If the merge P&P⁰ and subsequent propagated merges succeed then it is possible that the qualication of a variable object or pattern attribute has been made more special, because a virtual pattern was used for the qualication and that virtual pattern has been further-bound during the operation; if the variable attribute already refers to an object or a pattern then the strengthened qualication may be too strict for the object, and in that case a run-time error is raised. Note that a virtual which is used as a method (not as a qualication) can never cause this error.

There is actually yet another run-time error which may occur when an object is about to be specialized dynamically, but it is orthogonal to the others and does not depend on the two involved patterns. It is instead associated with exact qualications. There is an inherent conict between exact qualications and dynamic specialization. It is not possible to maintain the safety invariant

7.3. DYNAMIC SPECIALIZATION OF OBJECTS 151 of an exact reference and to dynamically specialize an object referred by that reference. As a result, a run-time error is raised if there is an attempt to specialize an object which is or has been referred by an exact reference. It would be possible to maintain a reference count and thus be able to remove the is-exact mark when the last exact reference to an object disappears, but the current implementation just marks objects and never removes the marks again.

This probably means that it is necessary to divide the universe of patterns into two sub-universes: the patterns whose instances may be specialized dynamically, and the patterns whose instances may be referred by exact references. As long as these subuniverses are kept apart, there will be no conict. It might even make sense to elevate this to a property of the pattern itself and thereby make it statically enforcable, but this has not been designed in detail nor implemented in gbeta.

Here is an illustration of how the other errors can arise. Since the rst two errors are associated with the merging operation, we present them in context of a dynamic pattern merging operation. The same merging operation could of course have been provoked implicitly during an object specialization, but this seems to expose the cause more directly. The third error can only happen in context of dynamic object specialization. An error of type 1 arises if we merge two patterns dynamically which both contain two given mixins (here it is mixin 1 and 2), but in dierent order:

(# a: ¹(# ^::: #); b: ²(# ^::: #); vp1,vp2: ##object do a&b## -> vp1##;

b&a## -> vp2##;

vp1 & vp2 (* Error 1! *)

#) ^Ex.

7-6

We use the variable patterns ^vp1and ^vp2to hide the actual patterns being merged, such that the compiler cannot detect the merging failure staticallyit makes no attempt to do ow analysis, so^vp1and^vp2are only known as some pattern which is less-equal than object when the merging of them is analyzed.

Since this is not known to be safe, a compile-time warning is issued, and the program actually fails with a run-time error during that merging operation.

The next case, errors of type 2, is concerned with propagation. To provoke this error, we create two patterns ^q1and ^q2which both inherit the virtual^vfrom the superpattern^p, so they have a shared virtual and therefore propagation of the combination operation will occur:

(# a: ¹(# ^::: #); b: ²(# ^::: #);

p: ³(# v:< object #);

q1: p⁴(# v::< a&b #);

q2: p⁵(# v::< b&a #);

vp1,vp2: ##object do q1## -> vp1##;

q2## -> vp2##;

vp1 & vp2 (* Error 2! *)

#) ^Ex.

7-7

When^vp1 and ^vp2are merged, a run-time error is raised. This is because of the same merging conict as in the previous example, only this time it occurs in the merging of the contributions to the shared virtual ^v. Again we use the generic variable patterns ^vp1and ^vp2to make this a run-time error and not a compile-time error. Finally, an error of type 3 can be provoked as follows:

(# p: ¹(# v:< object; aV: ^{^}v #);

aP: ^{^}p do

&aP[];

&integer[]->aP.aV[];

p²(# v::< string #)## -> aP## (* Error 3! *)

#) ^Ex.

7-8

We create an instance of ^p, make^aPrefer to it, and make its^aVvariable object attribute refer to a fresh ^integer object. The dynamic object specialization operation causes a warning, because it may hide the kind of problem that we are planning to create. Then we specialize ^aP such that the qualication of

aV changes from ^objectto ^string. While the ^integer object was perfectly acceptable for ^aV before the specialization (because ^{integer object}), it is a violation of a safety invariant after the specialization (because ^{integer 6}

string). Hence, a run-time error is raised.

After having visited this tarpit of trouble, we should remember that there are systematic ways to maneuver around the problems. Let us summarize some rules which are sucient to avoid run-time errors in dynamic object specializations:

It is always safe to add unrelated mixins to an object (this is case B).

It is always safe to specialize a new object with a subpattern of its current pattern (this is case C, and it is known that all variable attributes are

NONE, so error 3 cannot occur). One way to use this is to gradually build any instance from a single inheritance hierarchy by creating it as ^object and then adding up mixins along some path down through the inheritance tree (rst making it a ^Point, then proceeding to a ^ColorPoint, then a

SingingAndDancingColorPoint, etc.).

It is always safe to specialize an object with a pattern that does not further-bind any existing virtuals in the object (new virtuals and other attributes can be added).

It is always safe to specialize a new object with a pattern that only further-binds virtuals in the object that it owns. E.g., the virtual attributes of an abstract pattern may be divided into groups, and then an object may be built gradually by specializing it dynamically several times, each time with a pattern that takes care of exactly one group of shared virtuals.

So there are many ways in which dynamic object specialization can fail in the general case, but there are also many dierent conventions which can be em-ployed to ensure that they will actually never fail. It would be much better if

7.3. DYNAMIC SPECIALIZATION OF OBJECTS 153 the static analysis could detect exactly when the specialization operation would be guaranteed to succeed, but that question is of course undecidable, and the safe, algorithmic approximations that we have been able to come up with are too restricting to enforce generally.