As mentioned before, e.g. in Sect. 3.3, patterns inBetaand in gbetaare lists of mixins. This section describes what lists of mixins can be constructed. Sec-tion 3.6 and 3.7 describe how they can be constructed using inheritance and merging. Moreover, the organization of the set of patterns into a partial order relation is described and compared forBeta andgbeta.
For any given Beta program, the patterns may be organized into a tree, namely the well-known inheritance hierarchy which is associated with any sin-gle inheritance system. The root of the tree is object, and each node in the tree has its direct subpatterns as children. Theobjectpattern is the empty list of mixins. The `direct subpattern' relation is established by inheritance. Inher-itance is treated in the next section, but for now it suces to say that it works like the traditionalconsfunction, taking a listL (the prex, or superpattern) and an elementm(the new increment, a mixin) and returning a list whose head is the element and tail is the list, written asm::Lin, e.g., Standard ML.
Two small sets of pattern declarations are given in Fig. 3.2, and the corre-spondingBetapattern spaces are shown in Fig. 3.3 on page 55. The pattern space of a program is the set of patterns which may occur during an execution
of that program, organized into a partial order which denes the specialization (isa) relation. In this case we ignore the origins, for simplicity and because
3.5. THE PATTERN SPACE 55
[1] [2] [3]
[]
[]
[4]
[5,4]
[6,5,4]
Figure 3.3: The Beta pattern spaces of the examples in Fig. 3.2, using the MainPartnumbers
[]
[4]
[5,4]
[6,5,4]
[1] [2] [3]
[]
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
Figure 3.4: The gbeta pattern spaces of the examples in Fig. 3.2, using the MainPartnumbers
the origins would be the same for all mixins anyway.
When looking at Fig. 3.3, there is no direct reference to the names of pat-terns, such asaorq. This is because the patterns cannot be specied in terms of the declared namesthey denote entire patterns, and we need to explicitly show the construction of each pattern as a list of mixins. To be able to name the individual mixins, everyMainParthas been annotated with its own, unique number in Fig. 3.2; since the origins would all be identical, each number denotes exactly one mixin.
InBeta, in these examples and generally, every pattern in the pattern space is directly associated with a pattern constructing piece of syntax (mainly pattern declarations and inserted items). By disregarding the origins, the pattern is fully specied somewhere in the program by syntax and name lookup rules alone. Note that this even holds for virtual patterns: Even though the value of a virtual pattern may not be known at compile time, there is always some declaration in the program which denes the most specic, actual value of it.
Virtual patterns will be treated in Chap. 4.
Moreover, since theBetapattern space is always organized into a tree with every mixin occurring in only one node of the tree, it is actually possible to identify mixins and patterns in Beta: for any given mixin, there is one and only one pattern which has this mixin as its most specic, i.e., as the head of the list. Also, when starting from any node in the tree, each step towards the root removes one mixin from the pattern, namely the head of the list, thus producing the direct superpattern.
Consequently, the set of patterns in aBetaprogram is actually a very sparse selection of lists of mixins, considering how many combinations there are with a given set of dierent mixins.
In contrast, the pattern spaces of the two examples when considered asgbeta are quite dierent, as shown in Fig. 3.4. Thegbetapattern spaces contain the
Betapattern spaces because theBetasemantics is a special case of thegbeta semantics. But in the rst, horizontal, example, thegbetapattern space is much larger than the correspondingBetapattern space. This is because the mixins can be combined freely, using the merging operator (see Sect. 3.7).
When using pattern merging like multiple inheritance to bring together en-tirely unrelated patterns, there is no dierence between, e.g., [1;2;3] and [3;1;2].
But when behavior is involved it makes a big dierence, and any one of the com-binations may be the right choice in a concrete situation. Section 3.8 gives more details about behavior in connection with patterns containing more than one mixin.
So the horizontal example was quite dierent inBetaand ingbeta. On the other hand, as the gure shows, there is no dierence between the Beta and gbetapattern spaces with the second, vertical example. The situation is dier-ent because the mixins `4', `5', and `6' are introduced dierdier-ently. In Fig. 3.2, the mixin `5' is introduced in aDescriptor where p is used as a superpattern.
This makes a dierence, because all the p mixins are then guaranteed to be present in every pattern where mixin `5' occurs, and hence the declarations provided by thepmixins may freely be used when binding names and checking
3.5. THE PATTERN SPACE 57 types in the `5' mixin. This is a general phenomenon: A Descriptorbinds mix-ins associated with the containedMainPartto the list of mixins denoted by the specied superpattern, thus guaranteeing that the superpattern attributes will always be available for that mixin. With these guarantees, there are no other allowable patterns than those patterns which are already available with Beta semantics. The horizontal and the vertical examples are extreme cases, and it is a question of good software engineering practice to design inheritance graphs such that mixin dependencies are introduced just when they are needed, pre-serving exibility as much as possible. At the modeling level it corresponds to building clear and crisp concepts, since the independence corresponds to a sep-aration of concerns. However, it is always possible to make entities independent in the supercial sense that they do not technically depend on each otherfor example by tediously changing all the connections into other mechanisms such as parameter transfersand this may be an inappropriate move. The criterion is whether or not the separate parts are still both meaningful and usable.
The general observation is that each mixin in Beta is rigidly associated with one xed tail of mixins, whereas mixins can be combined freely in gbeta, subject to the restrictions which are necessary to ensure type safety in access to inherited attributes (to avoid MessageNotUnderstooderrors, one might say).
Furthermore, unrelated patterns, associated with at, horizontal inheritance graphs, more freely allow combinations of mixins, whereas tall, vertical inheri-tance graphs allow only few dierent combinations. In any case, the programmer does not need to worry about this, because the constraints are managed entirely by the language, simply because there is no way to specify a pattern containing a mixin for which the depended-upon mixins are not present.
The specialization (isa) relation may now be dened. The edges in the pattern spaces show individual elements of the specialization relation, and the relation may be obtained as the reexive and transitive closure of these elements.
However, a characterization in terms of lists of mixins is easier to make precise, and it is correct for bothBetaandgbeta:
Denition 1
Given two patterns P = [p1:::pn] and Q = [q1:::qm], we say that P is a specialization ofQiffP may be obtained fromQby adding zero or more mixins, i.e., if there is an injective, increasing function ' :f1:::mg!f1:::ngsuch that p'(i)=qi, for all i2f1:::mg.
In other words, a superpattern is a sublist, e.g., [1;2;3] Q when Q is any of [], [1], [2], [3], [1;2], [1;3], [2;3], or [1;2;3]. In the case where m = 0 (so Q=objectand f1:::mg=;), the requirement is trivially satised, so every pattern is a specialization of object, as expected.
ForBeta, only one special case of this specialization relation is exploited, because mixins are inseparable from their tails (the declared superpattern), namely the case where the deletions always remove the frontmost element. For example, [3;2;1] could be an actual specialization of [2;1] inBeta, but [3;1] or [2] could never exist if [3;2;1] exists. A consequence is that a specialization test in Beta can be made simply by inspecting the elements of a given pattern. P is a specialization ofQiff the frontmost mixin ofQoccurs in P.
Traditionally in theBetacommunity, this relation is called the `specializa-tion' relation, and the reverse relation is called the `generaliza`specializa-tion' relation. In other communities it may be called the `isa' relation or the `inheritance' relation.
Using `isa' would be ne, but using `inheritance' would redistribute the emphasis from the relation between concepts which may be more or less general/special, to the detailed, implementation-oriented phenomenon of `inheriting' attributes from a superclass. Since such reuse of attributes is denitely subordinate to the soundness of the relation between the modeled concepts, the term `inheritance' will be reserved for purposes which actually depend on attribute specics.