A lower bound on a virtual attribute allows for more control over that ne balance between two incompatible dimensions of freedom which is characteristic of virtuals. A virtual attribute provides the programmer with a very valuable freedom, namely the freedom to elaborate on a pattern attribute, for instance in order to dene a method in an abstract pattern and then implement that method in various concrete subpatterns; or in order to parameterize a pattern with a class, for instance theelementattribute inlistwhich is the qualication of elements contained in thelist. However, a virtual attribute also reduces the freedom of programmers (who want to write type-safe code), because a virtual pattern generally varies along with the pattern of the enclosing object, i.e., it is covariant, and this means that it cannot be used in a contravariant position.
For example, if an object is only statically known to be an instance of listor a subpattern of listthen we cannot insert new elements into thelist, because the actual qualication could be any subpattern of object, i.e., any pattern whatsoever.
Virtual attributes are generally known either by upper bound or exactly. A virtual attribute is introduced with a declaration like v:< p, may be further-bound a number of times with declarations like v::< q, and it may be nal-bound with a declaration likev:: r. Virtual introductions and further-bindings provide upper bounds, only. A nal binding provides both an upper bound and a lower bound and thereby freezes the virtual attribute to be one particular pattern (at least if all the declarations for that virtual gave contributions which are compile-time constant patterns, but not, e.g., if the virtual is nal-bound to an open virtual). The static knowledge is in all cases either an upper bound
9.2. LOWER BOUNDS ON VIRTUALS 183 (so it may be any pattern less-equal than the bound), or it is a xed pattern.
An explicit lower bound on a virtual can help establishing a more exible limit on the covariance than the entirely frozen limit of a nal-binding, and it is at the same time more strict than the upper bound alone. This makes it possible to ensure type safety in cases which would be hard to handle without this tool. To give a concrete example we will need a few patterns; the central pattern for this example is shown in Fig. 9.1. It is the patternordered, which is used to represent values which are organized into some total order relation.
This example is a variation of a Cecil example given in [64]. This example has already been discussed in Sect. 4.4, but there are additional aspects now.
One of the main topics of this example is the notion of binary methods, namely methods which take an argument of the same type as the receiver of the message. This is hard to handle if it is combined with subtype polymorphism, because it is then typically only known that the two involved objects have types T1 and T2 which are less-equal than a given upper bound T, and that says nothing about whether or not T1 = T2. Assuming that all combinations of T1 and T2 are acceptable we may just choose the most specic type T0 such that T1 T0 and T2 T0 and then execute the method which expects two arguments of type T0. That is exactly what multi-methods like in Cecil will do, so the use of a multi-method is one possible solution to the problem of handling binary methods safely. This approach will of course not work if it is required thatT1=T2. Other approaches discard the subtyping polymorphism, but retain the potential for implementation inheritance by separating subtyping and inheritance (which is in this case called matching [16]).
Binary methods have been treated in several contexts, for example [16, 14, 15]. Usually they are concerned with the case where two arguments to a proce-dure must be of the same type, or the receiver and an argument of a message must be of the same type. This can for example be made type safe by ensuring that the exact type of both of the involved objects is known; with matching this is achieved by removing the support for subtype polymorphism. In this context we widen the concept such that the acceptable pairs of arguments must be in the same family of patterns, i.e., some combinations of dierent patterns are acceptable whereas others are not.
The patternordereduses the virtual attribute cmpTypeto dene the pat-terns which are expected to be known for comparisons. Initialization of instances of subpatterns goes into further-bindings of init. Comparisons are supported by the method lessEqual, and it is possible to select of the greater of two
orderedobjects using the methodmax. Finally, the methodasStringmakes it possible to obtain a stringwhich describes the givenorderedobject.
The virtual patterncmpTypedeserves closer consideration. Inside ordered, this attribute is not known exactly, but it is intended to be known exactly from the outside, when actual instances are to be compared. There will be a nal bound on it in these cases. However, since cmpType is an open vir-tual as seen from inside ordered, we would not be able to implement the
max method safely without the lower bound on cmpType. Assume that this lower bound were removed; in that case the reference assignment in line 12,
1 ordered:
2 (# cmpType:< ordered :> this(ordered);
3 init:< (# do INNER exit this(ordered)[] #);
4 lessEqual:<
5 (# other: ^cmpType; b: @boolean
6 enter other[] do INNER exit b
7 #);
8 max:
9 (# other,maxi: ^cmpType
10 enter other[]
11 do (if other[]->lessEqual
12 then this(ordered)[]->maxi[]
13 else other[]->maxi[]
14 if)
15 exit maxi[]
16 #);
17 asString:< (# s: @string do INNER exit s #)
18 exit this(ordered)[]
19 #);
Figure 9.1: The patternorderedrelies on a virtual lower bound
this(ordered)[]->maxi[], would not be type safe, because the qualication of maxi(which iscmpType) could be any pattern less-equal thanordered.
Now consider the situation where cmpType hasthis(ordered)as a lower bound, such as the example is actually written in Fig. 9.1. The lower bound has no run-time semantics, it is only a restriction which makes some programs illegal (which is unusual for a gbetaconstruct). The eect of the lower bound on the analysis is two-sided. Firstly, the analysis is allowed to assume that the lower bound is respected whenever the pattern cmpType is usedso it is safe to reference assign this(ordered) to maxi because the qualication of
maxiby the lower bound is guaranteed to be greater-equal than the pattern of
this(ordered). Secondly, in every pattern that inheritscmpTypeit is checked that any new upper bounds, which are applied tocmpTypeby further- or nal-binding declarations, are actually compatible with the given lower bound. In other words, no matter what happens tocmpTypeit must remain a superpattern of the pattern of its enclosing object. Of course, that is exactly what is needed in order to ensure soundness of the abovementioned assumption which is made wherevercmpTypeis used.
The intention with cmpType is that it should present a well-dened partial view of instances of subpatterns of ordered. This is exactly what the lower bound says, and we expect that this may be a quite useful feature in practical programming.
In the concrete example we use it to make comparisons between certain
9.2. LOWER BOUNDS ON VIRTUALS 185
ordered objects type safe and to detect and reject all other comparisons. To do this we divide the subpatterns of ordered into families. The members of these families should be comparable freely and safely amongst each other, but members of dierent families should not be compared, and there should be a compile-time complaint if anybody tries to do such a thing. The families we will consider are the one-member family text, and the family of numberand its two subpatterns int and float. The source code for these will be shown below, but let us rst consider a seemingly natural approach and explain why it can not be done in that way.
As explained in [64], a simple approach would be to let the qualications of the arguments to lessEqualand maxbe orderedin stead of cmpType, thus removing the need for cmpTypeentirely:
ordered:
(# init:< <<as in Fig. 9.1>>
lessEqual:<
(# other: ^ordered; b: @boolean enter other[] do INNER exit b
#);
max:
(# other,maxi: ^ordered
enter other[] do <<as in Fig. 9.1>> exit maxi[]
#);
asString:< <<as in Fig. 9.1>>
exit this(ordered)[]
#) Ex.
9-5
With this design we can actually implement maxsafely, but lessEqual could then be called with arbitrary ordered objects, so this would require that we either choose a way to compare anumberand atext, or thatlessEqual imple-ment certain comparisons, for instance of two numbers, and raise an exception in the remaining cases, such as comparing a numberand a text. In the rst case we would have to implement meaningless or contrived comparisons, and that was exactly one of the things we wanted to avoid. In the second case we would have to expect potential run-time errors at every comparison, and that is of course not desirable. In other words, this simple approach is not appropriate.
Hence, in the following we will assume the denition as it appears in Fig. 9.1.
The denition of thetextpattern which forms the rst family all by itself is as follows:
text: ordered (# cmpType::text;
init::(# enter value #);
lessEqual::(# do (other.value<=value) -> b #);
asString::(# do value->s #);
value: @string
#); Ex.
9-6
This denition of textnal-bindscmpTypetotext, thereby making it possible to safely compare instances of textor a subpattern of textwith each other.
Moreover, the virtual methods are implemented such thattextcan be used as a concrete class. The other family is rooted innumber:
number: ordered (# cmpType::number;
lessEqual::(# do (other.asReal<=asReal) -> b #);
asReal:< (# r: @real do INNER exit r #)
#); Ex.
9-7
Again,cmpTypeis nal-bound to numberin order to make allnumbers compa-rable. We introduce the methodasRealwhich is needed in the implementation of lessEqual; this implementation assumes that conversion to and comparison asreal values is appropriate for all kinds of numbers. Other choices might be better, but this is simple and not unreasonable. The other members of the family areintandfloat:
int: number
These patterns just add implementations of various methods. With all these patterns in place we can begin to use some ordered objects. The following MainPartis assumed to be in a context whereorderedand its subpatterns are available:
7 (if t1->t2.lessEqual then t1.asString->puttext if);
8 (t1->t2.max).asString->putline;
In this example, a couple of texts andnumbers and an auxiliary attribute are declared in line 13. In line 5 and 6 the two variabletexts are renewed and initialized with the two literalstrings. The twotexts are then compared in line 7 and the string value of t1 is printed if t1 is less-equal than t2 (and it is).
Next, the greater of the two texts is selected by max, and the string value of thattext(which is'world!') is printed; that was line 8.
9.2. LOWER BOUNDS ON VIRTUALS 187 In line 9, a new floatobject is created and initialized with a-like value, and n1 is made to refer to that float; similarly, line 10 creates a new int object and initializes it with the integervalue four. Finally the greater of the two numbers is selected using maxin line 11, and therealvalue of that number is assigned to the auxiliaryr.
In [64] it is explained how F-bounded polymorphism can handle this example.
With F-bounded polymorphism it is possible to letorderedbe a parameterized class whose type argument is used in F-bounds, like in this Pizza example:
interface Ordered<T> { bool lessEqual(T other);
T max(T other);
};
class Text implements Ordered<Text> { bool lessEqual(Text other) { ::: };
}
class Number implements Ordered<Number> { bool lessEqual(Number other) { ::: };
} Ex.
9-10
This does enable instances of Textto be compared to each other in a type safe manner. It also allows subclasses of Numberto be dened and instances thereof compared, and it does make it a static error to compare aTextand aNumber, as desired. The implementation of themaxmethod could not be given inOrdered in Pizza because Ordered is an interface, but it can be given at the abstract level in Cecil:
forall T where T isa Ordered[T]:
method max(x:T, y:T): T { if x>=y then x else y } Ex.
9-11
In Cecil, methods can be dened as inx operators like `>=', so the expression
x>=ycorresponds to an invocation ofgreaterEqualin the other languages. This implementation is type safe because the compiler will only accept invocations of
maxwith such arguments where there is a typeTto which the actual arguments are known to conform and such that Tis less-equal thanOrdered[T].
To summarize, bothgbetaand Cecil have the ability to safely support inter-family comparisons for dierent families of subpatterns ofordered, respectively instantiations ofOrdered[T], and at the same time statically detect attempts to compare across families. Moreover, this happens in a way that allows a type safe implementation of such a method as maxwhich is shared between all ordered objectswithout that constraint there would not be much of a challenge be-cause each family could then be implemented from scratch as unrelated class hierarchies, with a syntactically identical implementation of maxin the root of every family.
The most important dierences are that Cecil infers better return types formax, and gbetaallows for a more complete kind of dynamic polymorphism.
For the rst issue, Cecil will infer that the maximum of two floatobjects is again a float,2 whereas gbeta will only have a return type of number. This
2If Ordered[T]is declared to becontravariant inT, as explained in [64, p. 401].
dierence is caused by the fact that Cecil uses unication of actual arguments with formals at every call site in order to infer type arguments, whereasgbeta uses virtual attributes for type parameterization. This is discussed in more detail in Sect. 9.3. On the other hand, gbeta supports polymorphic access to
orderedobjects:
(# o: ^ordered do (if :::
then 3.14159->float.init->o[]
else 'world!'->text.init->o[]
if);
o.asString->putline
#) Ex.
9-12
This would not be possible in Cecil (or any other approach based on F-bounded polymorphism or simple type parameters), since it is not possible to have an attribute which is capable of referring to all instances of Orderedthe problem is thatOrdered is not a type but a function from types to types, so it cannot be the type of a reference.