Safe object composition in the presence of subtyping

Testo completo


Safe object composition in the presence of subtyping

Lorenzo Bettini1 Viviana Bono2 Silvia Likavec2

1Dip. di Sistemi ed Informatica, Univ. di Firenze,

2Dip. di Informatica, Univ. di Torino,{bono,likavec}

Abstract. Object composition arises as a natural operation to combine objects in an object-based setting. In our incomplete objects setting, it has a strong meaning, as it may combine objects with different internal states. In this paper, we study how to make object composition safe in the presence of width subtyping: we propose two solutions, and discuss alternative ones.

1 Introduction

Object composition is often advocated as an alternative to class inheritance, in that it is defined at run-time and it enables dynamic object code reuse by assembling the existing components.

“Ideally, you shouldn’t have to create new components to achieve reuse. You should be able to get all the functionality you need just by assembling existing components through object composition.” [11].

This paper is about combining safely object composition and width subtyping on objects, as their co-existence introduces run-time conflicts between methods that might have been hidden by subsumption, in situations where statically there would be no conflict. Suppose we have two objects O1and O2that we want to compose. Object O1 has a method m1that calls a method m, which might be hidden by subsumption (i.e., its name does not appear in the type of the object O1). Object O2has a method m2 that calls a method m, also possibly hidden by subsumption. (Notice that it is enough if the method m is hidden in at least one of the objects.) When these two objects are composed, there is no explicit name clash at the type level, but methods m1 and m2 both call a method with the same name, m, and it is necessary to: (i) ensure that after object composition, methods m1and m2continue calling the method m they were calling originally, before the composition; (ii) guarantee that if one of the m’s is not hidden, we expose the reference to the right one in the object’s “public interface”. Note that if both m’s were hidden by subsumption, none of them is available to external users anymore, and if none were hidden there is a true conflict, ruled out statically.

This situation is an instance of the “width subtyping versus method addition” prob- lem (well known in the object-based setting, see for instance [9]). This kind of name clash (named dynamic name clash) should not be considered an error, but we must make sure that we solve all ambiguities, in such a way that accidental overrides do not occur.

We tackle this problem in our calculus of incomplete objects [1, 2], a calculus that combines some of the discipline of mixin-based features with some of the flexibility of object-based ones, with the aim of fitting into one setting “the best of both worlds”.


Mixins [4, 10] are subclass definitions parameterized over a superclass. A mixin can be seen as a function that, given one class as an argument, produces another class, by adding and/or redefining certain sets of methods. The operation of applying a class to a mixin is called a mixin application. The class must supply all the methods required to complete the mixin in order to obtain a fully-fledged subclass. Note that, as for standard subclasses, a mixin can have its own newly introduced methods and it inherits also all the methods from the superclass, even the ones it does not require. Mixins can be seen as incomplete classes, and their instances would be incomplete objects that could be completed in an object-based fashion. Therefore, we think that the best suited inheri- tance mechanism to be integrated with the object-based paradigm is a mixin-based one more than a pure class-based one.

In our calculus it is then possible: (i) to instantiate classes (created via mixin-based inheritance), obtaining fully-fledged objects ready to be used; (ii) to instantiate mixins, yielding incomplete objects that may be completed via method addition and/or object composition (that composes an incomplete object with a complete one).

Our form of method addition do not introduce any problems with respect to subtyp- ing, as we can add one by one only those methods that are required explicitly by the incomplete object, that is, we have total type information about the methods to be added (coming directly from the corresponding well-typed class hierarchy) before the actual addition takes place (see Sections 3 and 4). The conflict arises, instead, with object com- position that mirrors mixin application, therefore the complete object may have more methods than the ones required by the incomplete object, and these methods may clash with some of the newly introduced methods of the incomplete object. Notice that this problem is exactly the same as the one introduced by the general object composition example described above.

One of the possible approaches to solving the problem seemed to be exploiting the dictionaries of Riecke and Stone [13]. Unfortunately, their mapping “internal label- external label” does not solve completely the ambiguities introduced by object compo- sition in the presence of subtyping described above. In particular, there is still ambiguity when only one of the m’s is hidden by subsumption. It has to be said, however, that the original dictionaries setting is stateless, therefore method composition can be simulated by successive method additions, and dictionaries would be sufficient to model object composition. In our setting, instead, all objects (complete and incomplete) have a state (i.e., initialized fields), and object composition cannot be linearized via any form of repeated method additions. On a side note which will be useful later, we would like to recall that the calculus of [13] is “late-binding”, i.e., the host object is substituted to self (in order to solve the self autoreferences) at method-invocation time, whereas our calculus is “early-binding”, i.e., the host object is bound to self at object-creation time.

To the best of our knowledge it is not possible to remove all the ambiguities without either carrying along the additional information on the methods hidden by subsumption, or restricting the width subtyping. We discarded immediately the solution of re-labelling method names at object composition time, as this is untidy from a semantical point of view and impractical from an implementation one.

In this version of the calculus, we decided to allow width subtyping only on com- plete objects, and we present two solutions. The first one is an “early-binding” version


e : := const | x |λx.e | e1e2| fix

| ref | ! | : = | {xi= ei}i∈I

| e.x | H h.e | classvalhvg, Mi

| mixin

method mj= vmj; ( j∈N) redefine mk= vmk; (k∈R) expect mi; (i∈E) constructor vc; end

| mixinvalhvg, N, R, Ei| new e

| e1⋄ e2| e1←+ mi= e2| e1←+ e2

| objh{mi= vmi}i∈I, vgi

| objh{mi= vmi}i∈I, vg, r, N, R, Ei

v : := const | x |λx.e | fix | ref| !

| : = | : = v | {xi= vi}i∈I

| classvalhvg, Mi

| mixinvalhvg, N, R, Ei

| objh{mi= vmi}i∈I, vgi

| objh{mi= vmi}i∈I, vg, r, N, R, Ei

Table 1. Syntax of the core calculus: expressions and values.

of the dictionaries approach, where the notion of “privacy-via-subsumption” of [13] is completely implemented (see Section 3 and Section 4). The second one solves the con- flict “method composition versus width subtyping” without implementing the above mentioned notion in its completeness (see Section 5). We argue that the first solution is more elegant formally, while the second solution is less restrictive from the point of view of typing, and it might give better “performances” if implemented. A side benefit of presenting both is to be able to show the flexibility of our approach, in fact to go from the first solution to the second one it is enough to change only the rules that deal directly with object composition (one in the operational semantics, one in the type system).

In Section 6 we will hint to other possible solutions to the conflict “method compo- sition versus width subtyping”.

2 Syntax

Starting from the imperative calculus of records, functions, classes, and mixins of [3], we add the constructs to work with incomplete objects.

The lambda-calculus related forms in Table 1 are standard. For the explanation of the heap-related expressions, we refer the reader to [3, 14]. We describe below the forms related to mixins and incomplete objects.

classvalhvg, Mi is a class value, the result of mixin application. The function vgis the generator used to generate its instances, and the setM contains the indices of all the methods defined in the class.


method mj= vmj; ( j∈N) redefine mk= vmk; (k∈R) expect mi; (i∈E)

constructor vc; end

is a mixin. It contains three sorts of method declarations: new methods (mj), which are the newly introduced methods by the mixin seen as a subclass, redefining meth- ods (mk), which wait for a superclass containing methods with the same name to


be redefined, and provide the overriding body, and expected method names (mi), which are methods not implemented by the mixin but must be provided by the su- perclass (since they might be used by new and redefining methods). We assume that the programmer must declare the expected method names in the mixins, but that their types are inferred from new and redefining method bodies. New and rede- fined methods are distinguished in the mixin implementation, since a new method may have arbitrary behavior, while the behavior of a redefined method must be

“compatible” with that of the old method it replaces (“behavior” being formalized via types). Each method body vmj,k is a function of the privatefield, and ofself, which will be bound to the newly created object at instantiation time. In method redefinitions, vmk is also a function ofnext, which will be bound to the (old) re- defined method from the superclass. The constructor value vcis a function of one argument that returns a record of two components: thefieldinit value used to initial- ize the private field, and thesuperinit value passed as an argument to the superclass constructor. When evaluating a mixin, vcis used to build the generator.

mixinvalhvg, N, R, Ei is a mixin value, the result of mixin evaluation. The generator vgfor the mixin is a “partial generator” of incomplete objects, used also in the⋄ operation evaluation, where it is appropriately composed with the class generator.

The setsN, R and E contain the indices of new, redefining, and expected methods defined in the mixin.

new e creates a function that returns a new object (incomplete, in the mixin case).

– e1⋄ e2is the application of mixin value e1to class value e2, producing a new class value that is a subclass of e2.

– e1←+ mi= e2is the method addition operation: it adds the definition of method miwith body e2to the (incomplete) object to which e1evaluates.

– e1←+ e2is the object composition operation: it composes the (incomplete) object to which e1evaluates with the complete object to which e2evaluates.

objh{mi= vmi}i∈I, vgi is a fully-fledged object that might have been created by directly instantiating a class, or by completing an incomplete object. Its first com- ponent is a record of methods, the second component is a generator function, kept also for complete objects, since they can be used to complete the incomplete ones.

objh{mi= vmi}i∈I, vg, r, N, R, Ei is an incomplete object. {mi= vmi}i∈I is a record of methods, vgis a generator function, r is a record containing redefining methods which will be used when anextfor them becomes available during method addition or object composition. When the setsR and E become empty (and so does the record of redefining methods) the incomplete object becomes a complete object.

Mixins are first-class citizens in our calculus, i.e., all the usual operations are al- lowed on them. However, class values, mixin values, and object forms are not intended to be written directly. Instead, these expression forms are used only to define the se- mantics of programs. Class values are created by mixin application, mixin values result from evaluation of mixins, and object forms can be created by class and mixin instanti- ation. We define the root of the class hierarchy, classObject, as a predefined class value Object= classvalh λ .λ .{}, [ ] i necessary to treat uniformly all the other classes.

It might be tempting to argue that object composition is just syntactic sugar, i.e., it can be derived via an appropriate sequence of method additions, but this is not true.


const v→δ(const, v) (δ) refv→ Hhx, vi.x (ref) if δ(const, v) is defined Hhx, vih.R[!x] → Hhx, vih.R[v] (deref) (λx.e) v → [v/x] e (βv) Hhx, vih.R[: =xv] → Hhx, vih.R[v] (assign) fixx.e) → [fix(λx.e)/x]e (fix) R[H h.e] → H h.R[e], R 6= [ ] (lift) {. . . , x = v, . . .}.x → v (select) H h.H h.e → H h h.e (merge)

Table 2. Reduction rules for standard expressions and heap expressions

In fact, when adding a method, the method does not have a state, while a complete object used in an object composition has its own internal state (i.e., it has a private field, properly initialized when the complete object was created via a “new” from a class, or when part of it was created via a “new” from a mixin). Being able to choose to complete an object via the composition or via a sequence of method additions (of the same methods appearing in the (complete) object used in the composition) gives our calculus an extra bit of flexibility.

It is very important to notice that fields do not appear explicitly in the syntax, as we model the field as a lambda-abstracted variable in method bodies. For the sake of simplicity, we consider only one field for each mixin, but this is not a restriction, as the field could be a tuple. Also, the calculus does not enforce the field to be available to all the methods of the mixin, but this is easily obtained by declaring it to be of typeref. If so, the field behaves like a proper instance variable (it is non-accessible, not only non- visible). To understand fully how, we refer the reader to [14], from which we borrowed the side-effect part of our calculus.

Some usage examples for the calculus can be found in [1].

3 Operational semantics

Our approach is the one of giving the calculus a semantics as close as possible to an implementation. In order to do so, the formal operational semantics is a set of rewriting rules including some standard rules for a lambda calculus with stores (in our case the Reference ML of Wright and Felleisen [14]), and some rules that evaluate the object- oriented related forms to records and functions, according to the object-as-record ap- proach and Cook’s class-as-generator-of-object principle. This operational semantics can be seen as something close to a denotational description for objects, classes, and mixins, and this “identification” of implementation and semantical denotation is, in our opinion, a good by-product of our approach.

The operational semantics extends the one of the core calculus of classes and mixins [3], therefore exploits the Reference ML of Wright and Felleisen [14] treatment of side- effects. To abstract from a precise set of constants, we only assume the existence of a partial functionδ: Const × ClosedVal ⇀ ClosedVal that interprets the application of functional constants to closed values and yields closed values.

In Table 2, R’s are reduction contexts [6, 7, 12] and their definition can be found in Table 3. We assume the reader is familiar with the treatment of imperative side-effects via reduction contexts and we refer to [3, 14] for a description of the related rules.

The meaning of the object-oriented related rules in Table 4 is as follows.


R : := [ ] | R e | v R | R.x | new R | R ⋄ e | v ⋄ R

| {m1= vm1, . . . , mi−1= vmi−1, mi= R, mi+1= emi+1, . . . , mn= emn}1≤i≤n

| R ←+ m = e | R ←+ e | v ←+ m = R | v ←+ R Table 3. Reduction contexts mixin

method mj= vmj; ( j∈N) redefine mk= vmk; (k∈R) expect mi; (i∈E) constructor vc; end

→ mixinvalhGenm, N, R, Ei (mixin)

where Genm


let t= vc(x) in








mjy.vmjt.fieldinit self y ( j∈N) mky. self .mky (k∈R)

mi=λy. self .miy (i∈E)

 ,

superinit= t.superinit,

redef= {mky.vmkt.fieldinit y (k∈R)}







new classvalhvg, Mi →λw.objhfix(vgw), (vgw)i (new class) new mixinvalhGenm, N, R, Ei →λw.let vg= (Genmw) in

objhfix(vg.gen), vg.gen, vg.redef, N, R, Ei

(new mixin)

mixinvalhGenm, N, R, Ei ⋄ classvalhvg, Mi → classvalhGen, N ∪ Mi (mix app) where


let mixinrec= Genm(x) in let mixingen= mixinrec.gen in let mixinred= mixinrec.redef in let supergen= vg(mixinrec.superinit) in

mjy.(mixingen self ).mjy ( j∈N)

mk=λy.(mixinred.mkself) (supergen self ).mky (k∈R) miy.(supergen self ).miy (i∈M−R)

objh{. . . , mi= vmi, . . .}, vgi.mi→ vmi (obj sel) Table 4. Reduction rules for object-oriented forms

(mixin) rule turns a mixin expression into a mixin value (notice that all the other mixin operations, i.e., mixin application and mixin instantiation, are performed on mixin val- ues). Given the parameter x for the constructor c of the mixin expression (we remind that c is a function that calculates the initializing values for the private field of the mixin, and for the generator of the future superclass), the mixin generator returns a record con- taining the following:


– a (partial) object generatorgen which binds the private field of the methods mj

(newly defined by the mixin) tofieldinit (returned by the constructor). Recall that method bodies take parametersfield,self, and, if it is a redefinition, also next. The output ofgen has “dummy” method bodies in place of redefined and expected methods to enable the correct instantiation of incomplete objects. Intuitively,self must refer to all the methods: not only the new ones, but also the ones that are still to be added;

– the argumentsuperinit for the superclass constructor, as returned by the mixin con- structor c (theconstructor subexpression c is a function of one argument which returns a record of two components: one is the initialization expression for the field fieldinit the other is the superclass generator’s argument superinit);

– theredef component which contains a record of redefined methods that have their private field already bound tofieldinit (returned by the constructor), and are ready to have theirnext parameter bound to a method added to the object at run time, with theirselfstill unbound. This record will be used during method addition and object composition to recover the actual body of the redefined methods, complete it, and insert it in the working part of the object.

The above generator is called “partial” since it returns an object that contains redefined and expected methods that cannot be invoked (present as “dummy” methods). The ac- tual implementation of those methods can be provided by (meth add 1), (meth add 2), and/or (obj comp) in Table 5.

(new class) rule enables the creation of new objects from class definitions. It builds a function which, once passed an argument v, produces the complete object objhfix(g v), (g v)i. (g v) is the object generator, obtained by applying the class gen- erator g to an argument v. This creates a function fromself to a record of methods.

fix(g v) is the record of methods that can be invoked on that object, obtained by apply- ing the fixed-point operator fix (following [5]) to(g v) to bindself in method bodies and create a recursive record.

(new mixin) rule creates incomplete objects from mixin values. First, it applies the mixin generator Genmto an argument v, thus binding the private field of new and rede- fined methods and providing access to Genm’sgen and redef components. The mixin object generator g.gen is a function from self to a record of mixin methods, while g.redef is the record of the redefined mixin methods that have their fieldinit bound (self andnexthave still to be bound). The g.redef record is used for “remembering” the par- tial redefined method bodies for the future use. The application of the fixpoint operator to g.gen creates a recursive record of methods.

(obj sel) enables method invocation on a complete object.

(mix app) rule evaluates the application of a mixin value to a class value and represents inheritance in our calculus. Amixin value is applied to a superclass value classvalhg, Mi, whereM is the set of all method names defined in the superclass. The resulting class value is classvalhGen, N ∪ Mi where Gen is the generator function, and N ∪ M lists all the method names of the subclass. Using a class generator delays full inheritance resolution until object instantiation time whenselfbecomes available.


The class generator takes a single argument x, which is used by the mixin generator, and returns a function fromselfto a record of methods. When the fixed-point operator is applied to the function returned by the generator, it produces a recursive record of methods representing a new object (see the (new class) rule). Gen first calls Genm(x) to computemixinrec, which is used first to compute the mixin object generatormixingen, a function fromselfto a record of mixin methods. Next, it is used to computemixinred, which provides the record of redefining methods from the mixin. Then, Gen calls the superclass generator g, passing argumentmixinrec.superinit, to obtain a functionsuper- genfromselfto a record of superclass methods. Finally, Gen builds a function fromself that returns a record containing all methods — from both the mixin and the superclass.

All methods of the superclass that are not redefined by the mixin, mi where iM − R, are inherited by the subclass: they are taken intact from the superclass’s object (supergen self). These methods mi include all the methods that are expected by the mixin (as checked by the type system). Methods mjdefined by the mixin are taken intact from the mixin’s object (mixingen self). As for redefined methods mk,nextis bound to (supergen self).mkby Gen, which is then passed to( Notice that at this stage, all methods have already received a binding for the private field. Moreover, for all methods in all generator functions, the method bodies are wrapped insideλy. · · · y to delay evaluation in our call-by-value calculus.

The next four rules in Table 5 are the basic rules for manipulating the incomplete objects, i.e., they enable completing them with the method definitions that they need either as expected or redefined.

(meth add 1) rule adds to an incomplete object a method ml that some other methods expect. The function incgen mapsselfto a record of methods, where new method def- initions are taken from the object generator g, the redefining and expected (excluding ml) methods remain “dummy” and the method ml is added. Therefore, applying the fix operator to incgen produces a recursive record of methods with boundselfand implic- itly enables invocation of the methods that could have not been invoked before. The incgen function is part of the reduct because it must be carried along in the evaluation process, in order to enable future method additions and/or object compositions.

(meth add 2) rule is similar to the previous one, the difference being that now a method is added in order to complete a redefining method ml, acting as its next. Therefore the definition of the redefined method is not “dummy” anymore, but gets a new body ml=λy. ( self) (vml self) y. The body of ml is taken from r (it is already bound tofieldinit) and (vml self) is passed to it asnext. Naturally, this method becomes fully functional, therefore its definition is removed from r, and the index l is removed from R and added to N.

The only requirement for ml both in rules (meth add 1) and (meth add 2) is that the body vml must be a function ofself.

(obj comp) rule combines two objects in such a way that the new added object o2

(which must be already complete) completes the incomplete object o1 and makes it fully functional. After completion, it is possible to invoke all the methods that were in the interface of the incomplete object, i.e., those inN ∪ R ∪ E. The record of methods in incgen is built by taking the new methods from the incomplete object o1(these are


objh{. . .}, vg, r, N, R, Ei ←+ (ml= vml) → let incgen=λself.



mj=λy. (vgself).mjy ( j∈N) mky. self .mky (k∈R) miy. self .miy (i∈E−{l}) mly. vmlself y



in objhfix(incgen), incgen, r, N ∪ {l}, R, E − {l}i where l∈ E

(meth add 1)

objh{. . .}, vg, r, N, R, Ei ←+ (ml= vml) → let incgen=λself.



mjy. (vgself).mjy ( j∈N) mk=λy. self .mky (k∈R−{l}) miy. self .miy (i∈E) ml=λy. (r.mlself) (vml self) y



in objhfix(incgen), incgen, r −, N ∪ {l}, R − {l}, Ei where l∈ R

(meth add 2)

objh{. . .}, vg, r, N, R, Ei ←+ objh{mi= vmi}i∈P, vgi → let incgen=

let gen1s1s2. (

mly. (vgs2).mly (l∈P−(R∪E))

mry. s1.mry (r∈P∩(R∪E))


in λself.



mjy. (vgself).mjy ( j∈N)

mk=λy. (r.mkself) (vgfix(gen1self)).mky (k∈R) miy. (vgfix(gen1self)).miy (i∈E)


 in objhfix(incgen), incgeni

(obj comp)

objh{mi= vmi}i∈P, vg, {}, P,/0,/0i → objh{mi= vmi}i∈P, vgi (completed) Table 5. Reduction rules for object composition

the only methods that are fully functional in this object), binding thenextparameter in redefining methods from o1, and taking the expected methods from the complete object o2. During this operation we have to make sure that:

– methods of the complete object o2that are requested by the incomplete objects o1

getselfrebound to the new resulting object (this is the reason why we need to keep the generator also for complete object values). This rebinding automatically enables dynamic binding of methods that are redefined even when called from within the methods of o2;

– methods of o2that are not requested by o1(we call these methods additional) are not subject to “accidental” override.

The second point is crucial in our context, where additional methods in the complete object, due to subsumption, may clash with methods already present in the incomplete object (i.e., those inN). The above two goals are achieved altogether using the addi- tional generator gen1. This generator builds a record where the additional methods are


bound, once and for all, to their implementation in the complete object (through s2that will be propagated with the auto-binding of self, via the fixpoint operator application).

The other methods (those requested by the incomplete object) are instead “open” to re- definitions since they rely on the reboundself. This generator gen1is used in the incgen generator to pass to vg(the generator of o2), the “self” record, obtained by passing the newself to gen1and then applying fix. This realizes the basic idea that the method bodies of the complete objects will use the “self” where the additional methods are the original ones, while for the others, dynamic binding is applied.

(completed) rule transforms an incomplete object, for which all the missing methods are provided, into a corresponding complete one.

3.1 An example of reduction

Let us show how the object completion works through an example. Suppose we have the following objects (for simplicity let us forget the parameter of methods,λy. . . . y, and dummy methods):

o1= objh{m1=λself. self .m2}, v1g, {m3=λnext.λself. . . .}, N = {1}, R = {3}, E = {2}i o2= objh{m1=λself. self .m3, m2=λself. self .m1, m3=λself. . . .}, v2gi

o= o1←+ o2

where m1in o2is hidden by subsumption. Now, following the rule (obj comp), o will have the shapeobjhfix(incgen), incgeni, where incgen is as follows:

let incgen=

let gen1s1s2.

m1= (v2gs2).m1

m2= s1.m2

m3= s1.m3

 in


m1= (v1gself).m1

m3= (r.m3self) (v2gfix(gen1self)).m3

m2= (v2gfix(gen1self)).m2

In the following we use the notation oi::mjto refer to the (fully qualified) implementa- tion of mjin object (or incomplete object) oi. If we invoke m1on o we would like that o1::m1is executed, then o2::m2, then o2::m1(i.e., no accidental override took place), and finally o1::m3 (i.e., the complete object uses the redefined version). Let us make explicit the reduction steps performed upon the invocation of the method m1on object o. (we denote gen1fix(incgen) by gg):

o.m1→ fix(incgen).m1→ (v1gfix(incgen)).m1→ (λself. self .m2)fix(incgen) OK: o1::m1

→ fix(incgen).m2→ (v2gfix(gen1fix(incgen))).m2→ (v2gfix(gg)).m2→ (λself. self .m1)fix(gg) OK: o2::m2

→ fix(gg).m1→ (v2gfix(gg)).m1→ (λself. self .m3)fix(gg) OK: o2::m1

→ fix(gg).m3→ fix(incgen).m3→ (r.m3fix(incgen)) (v2gfix(gg)).m3→ (λnext.λself. . . .)(fix(incgen))(v2gfix(gg)).m3 OK: o1::m3


4 Type system

Besides functional, record, and reference types, our type system has class types, mixin types, and object types (both for complete and incomplete objects):

τ: :=ι|τ1→τ2|τref| {mimi}i∈I| classhτ,ΣPi

| mixinhτ12NREi| objhΣi | objhΣNREi

whereιis a constant type,→ is the functional type operator,τref is the type of locations containing a value of typeτ.Σ(possibly with a subscript) denotes a record type of the form{mimi}i∈I, I⊆ N. If mii∈Σwe say that the label mioccurs inΣ(with type τmi). Labels(Σ) denotes the set of all the labels occurring inΣ.

Typing environments are defined asΓ: :=ε | Γ, x :τ | Γ,ι1<:ι2where x∈ Var,τ is a well-formed type,ι12are constant types, and x,ι16∈ dom(Γ).

Typing judgments are the following:

Γ⊢τ1<:τ2 τ1is a subtype ofτ2 Γ⊢ e :τ e has typeτ.

Typing rules for lambda expressions are standard. Typing rules for expressions deal- ing with imperative side-effects via stores and the rules for typing records can be found in [3]. We do not need any form of recursive types because we do not use a polymorphic MyType to typeself(see, for instance, [8]). This prevents the type system from typing binary methods, but it still allows it to type methods that modifyself, which can be modelled as “void” methods that return nothing.

Typing rules for class and complete object related forms are given in Table 6. In rule (T class val), classhγ,ΣPi is the class type whereγis the type of the generator’s argument andΣP= {mimi} is a record type representing the interface of the objects instantiated from the class. Rule (T obj) says that the type of a complete object is the record of its method types. Notice that objects instantiated from class values do not have a simple record typeΣ, but an object typeobjhΣi. This is useful for distinguishing standard complete objects, which can be used for completing incomplete objects, from their internal auto-referenceself, that has typeΣ(in particular, this is to avoid self- inflicted object completions, which are unsound in our calculus). Note also that in the object expression, the second component g is a function fromselftoself(so typed with Σ→Σ), because it works on the first component of the object, which is the record of object’s methods. The only operation allowed on complete objects is method selection and it is typed as ordinary record component selection (rule (T sel)).

Typing rules for mixin related forms are given in Table 7. In the mixin type mixinhγbdNREi:

γbis the expected argument type of the superclass generator, γdis the exact argument type of the mixin generator,

ΣN= {mjmj} are the exact types of the new methods introduced by the mixin, ΣR= {mkmk} are the exact types of the methods redefined by the mixin, ΣE= {mimi} are the types of the methods expected to be supported by the super-

class to which the mixin is applied,


(T class val) (T class inst) Γ⊢ vg→ {mimi}i∈M→ {mimi}i∈M

Γ⊢ classvalhvg, Mi : classhγ, {mimi}i∈Mi

Γ⊢ e : classhγ, {mimi}i∈Ii Γ⊢ new e :γ→ objh{mimi}i∈Ii

(T obj) (T sel)

Γ⊢ {mi= vmi}i∈I:{mimi}i∈I Γ⊢ vg:{mimi}i∈I→ {mimi}i∈I Γ⊢ objh{mi= vmi}i∈I, vgi : objh{mimi}i∈Ii

Γ⊢ e : objhΣi mimi∈Σ Γ⊢ e.mimi

Table 6. Typing rules for class related forms

Γ⊢ e : mixinhγbdNREi Γ⊢ new e :γd→ objhΣNREi

(T mixin inst)

For j∈ N:Γ⊢ vmjmj For k∈ R:Γ⊢ vmkmk For i∈ E:Γ⊢ vmimi

Γ⊢ vg:Σ→Σ Γ⊢ r : {mk:Σ→τmk→τmk}k∈R

Γ⊢ objh{mp= vmp}p∈N∪R∪E, vg, r, N, R, Ei : objhΣNREi

(T inc obj)

For j∈ N : Γ⊢ vmj:η→Σ→τmj For k∈ R : Γ⊢ vmk:η→Σ→τmk→τmk

Γ⊢ vcd→ {fieldinit :η, superinit :γb}

Γ⊢ mixin

method mj= vmj; ( j∈N) redefine mk= vmk; (k∈R) expect mi; (i∈E) constructor vc; end

: mixinhγbdNREi

(T mixin)

Γ⊢ Genmd→ {gen :Σ→Σ, superinit :γb, redef : {mk:Σ→τmk→τmk}k∈R} Γ⊢ mixinvalhGenm, N, R, Ei : mixinhγbdNREi

(T mixin val)

Γ⊢ e1: mixinhγbdNREi Γ⊢ e2: classhγcPi Γ⊢γb<:γc Γ⊢ΣP<:ΣE∪ΣR Labels(ΣP) ∩ Labels(ΣN) =/0

Γ⊢ e1⋄ e2: classhγdN∪ΣPi

(T mix app)

where in all the rules

Σ=ΣN∪ΣR∪ΣE ΣN= {mjmj},ΣR= {mkmk},ΣE= {mimi} τmiare inferred from method bodies

Table 7. Typing rules for mixin related forms

The rules (T mixin) and (T mixin val) assign the same type to their respective ex- pressions, although deduced in a different way. Also, the type assigned to an incomplete object is similar to the one of the mixin the object is the instance of, but it does not con- tain information about the constructor (see rule (T inc obj)). This is consistent with the fact that the constructor has already been called when an incomplete object has been


Γ⊢ e : objhΣNREi mlml∈ΣE Γ⊢ vml1→τml

Γ⊢ (ΣN∪ΣR∪ΣE) <:Σ1

Γ⊢ e ←+ (ml= vml) : objhΣN∪ {mlml},ΣRE− {mlml}i

(T meth add 1)

Γ⊢ e : objhΣNREi mlml∈ΣR Γ⊢ vml1→τml

Γ⊢ (ΣN∪ΣR∪ΣE) <:Σ1

Γ⊢ e ←+ (ml= vml) : objhΣN∪ {mlml},ΣR− {mlml},ΣEi

(T meth add 2)

Γ⊢ e1: objhΣNREi Γ⊢ e2: objhΣPi Γ⊢ΣP<:ΣE∪ΣR Labels(ΣP) ∩ Labels(ΣN) =/0

Γ⊢ e1←+ e2: objhΣN∪ΣR∪ΣEi

(T obj comp)

Table 8. Typing rules for incomplete object-related forms

created. A related difference results in the types of redefined methods: in object values, the type of the private field disappears since it has already been bound during mixin instantiation. We recall now the “dummy” methods introduced in Section 3, to fully justify them according to the typing rules: when typing an incomplete object value,

“dummy” methods allow us to assign the typeΣ→Σto the generator g (the generator being a function fromselftoself). In fact, the body of “dummy” methods simply calls the homonym method onself, so the type inferred for expected and redefined methods will be consistent with the types of “dummy” method bodies (and so with the types of expected andnext methods sought by their sibling methods). If the “dummy” method

“trick” was not used, the fix operator could not be applied to generate an incomplete object.

In the rule (T mix app),ΣPcontains the type signatures of all the methods supported by the superclass to which the mixin is applied (superclass may have more methods than those required by the mixin constraints).ΣP<: (ΣE∪ΣR) ensures that the super- class provides all the methods requested by the mixin. Labels(ΣP) ∩ Labels(ΣN) =/0 guarantees that no name clash will take place during the mixin application. The result- ing class contains the signatures of all the methods defined by the mixin, and inherited from the superclass.

Finally, Table 8 shows the typing rules related to incomplete objects. A method ml can be added to an incomplete object (rule (T meth add 1)), only if this method is ex- pected by the incomplete object. Method addition in this case presents a sort of symme- try: the added method completes the functionalities of some already present methods, and may invoke some of them as well. Therefore, ml’sselftypeΣ1imposes some con- straints on the type of the incomplete object that mlis supposed to complete. Hence, the incomplete object must provide all the methods listed inΣ1, on which the added method is parameterized.Σ1is inferred from ml’s body. The rule for adding anextmethod to complete a method ml that is redefined in the incomplete object is similar therefore its explanation is omitted due to the lack of space.

The main novelty in the typing system with respect to the one of [2] is the subtyping relation on complete objects (Table 9). In the original calculus [1, 2] both depth and


J⊆ I

Γ⊢ {mii}i∈I<: {mjj}j∈J

( <: record) Γ⊢Σ<:Σ Γ⊢ objhΣi <: objhΣi

( <: cobj)

Table 9. Subtyping for objects

width subtyping was defined on record types. Here, for uniformity with respect to object types, we define width subtyping only on record types as well. The cost we pay is a less expressive mixin application typing rule. However, modifying the subtyping rules in order to allow also depth subtyping on record types only would be just a technicality and an orthogonal issue with respect to the subject of the paper, therefore we leave this modification out for the sake of clarity.

5 A more flexible solution

In the solution presented so far, the interface of an object resulting from an object com- position is dictated by the incomplete object only, in the sense that, in the resulting composed object, only the methods of the incomplete object are invocable by an exter- nal user. This is not symmetric with mixin application, where the additional methods of the class are still present in the interface of the resulting subclass, so also visible and therefore invocable on the subclass’ instances.

Actually, such a restriction on object composition was not present in the previous versions of the calculus of incomplete objects [1, 2]; we introduced it here to give a first solution to the subtyping-composition conflict. However, this restriction is not neces- sary to solve the problems of dynamic name clashes, although it actually simplifies its treatment, and it allows to implement fully an “early-binding” version of the “privacy- via-subsumption” notion of [13].

In this section, we present an alternative solution that removes this restriction and thus it is more flexible (in the sense that the interface of the composed object will be richer, i.e., it will contain more methods).

Interestingly enough, from the point of view of typing, all we have to do is to change the typing rule for object composition in order to include all these class methods, as in rule (T obj comp) in Table 10 (which mirrors the original rule of [2]).

Now, the semantic rule for object composition must be changed, since we cannot hide all the additional methods: those that do not clash with methods defined by the incomplete object must be visible in the resulting object (while those that clash are still hidden). All we have to do is to modify slightly the rule (obj comp), obtaining the one given in Table 10.

6 Remarks

In this paper we presented two possible solutions to solve the “method composition versus width subtyping” conflict. Both solutions were proved sound (the metatheory can be found at

We would like to remark that the high-level ideas underpinning our solutions are general. In particular, the idea of having self basically “split” into two parts when com- posing two objects, one taking care of the statically bound methods, the other one deal-


Γ⊢ e1: objhΣNREi Γ⊢ e2: objhΣPi Γ⊢ΣP<:ΣE∪ΣR Labels(ΣP) ∩ Labels(ΣN) =/0

Γ⊢ e1←+ e2: objhΣN∪ΣPi

(T obj comp)

objh{. . .}, vg, r, N, R, Ei ←+ objh{mi= vmi}i∈P, vgi → let incgen=

let gen1=λs1.λs2. (

ml=λy. (vgs2).mly (l∈P∩N) mr=λy. s1.mry (r∈P−N)


in λself.



mj=λy. (vgself).mjy ( j∈N)

mky. (r.mkself) (vgfix(gen1self)).mky (k∈R) mi=λy. (vgfix(gen1self)).miy (i∈P−(N∪R))


 in objhfix(incgen), incgeni

(obj comp)

Table 10. The typing and semantic rule to change

ing with the dynamically bound ones, can be applied within any setting presenting the same problem.

We would also like to stress the flexibility of our approach, i.e., giving the incom- plete object-calculus an ML-like based operational semantics: working directly with class-as-generator-functions and objects-as-records (and their respective types) allows us to alternate between one version of the calculus and another with minimal changes, both in the typing rules and in the semantics. In particular, since the operational seman- tics is a set of rewriting rules into functions, we can manipulate functions to achieve our goals, instead of using ad-hoc changes to the semantics. Moreover, with respect to the dictionaries of [13] in the late-binding setting, our early-binding setting allows a corre- sponding solution that is more oriented to an implementation and, in particular, would not suffer from overheads due to dictionary management and lookups, as the original calculus does, which is pointed out in [13] itself. This is true also for the alternative solution.

The approach we chose here was to allow width subtyping on complete objects only.

It is possible to have width subtyping on incomplete objects as well, if hidden method names are carried along: (i) in the type of the object; (ii) in the object itself.

Solution (i) would imply a more restrictive typing rule for object composition, to also check the possible conflicts among non-hidden and hidden methods, and rule out such conflicts completely. We think, though, that such a solution is too restrictive, as we think this kind of name clash is not an error. Hidden method name information in the object (solution (ii)) would solve all possible ambiguities at run-time, but it would be less standard, as the subsumption rule would act on the object expression, not only on its type. Nevertheless, we think this solution has the advantage of being quite general, even though it might be considered not elegant, and it will be presented as future work.


As a future work plan, we also consider the integration of a form of object-based override, a form of depth subtyping on object types, and solutions to deal with the conflicts arising when adding these two features together.


1. L. Bettini, V. Bono, and S. Likavec. A core calculus of mixin-based incomplete objects. In FOOL 11, pages 29–41, 2004.

2. L. Bettini, V. Bono, and S. Likavec. Safe and Flexible Objects. In SAC, Special Track on Object-Oriented Programming Languages and Systems. ACM Press, 2005. To appear.

3. V. Bono, A. Patel, and V. Shmatikov. A core calculus of classes and mixins. In Proc. ECOOP

’99, pages 43–66. LNCS 1628, Springer-Verlag, 1999.

4. G. Bracha and W. Cook. Mixin-based inheritance. In Proc. OOPSLA ’90, pages 303–311, 1990.

5. W. R. Cook. A Denotational Semantics of Inheritance. PhD thesis, Brown University, 1989.

6. E. Crank and M. Felleisen. Parameter-passing and the lambda calculus. In Proc. POPL ’91, pages 233–244, 1991.

7. M. Felleisen and R. Hieb. The revised report on the syntactic theories of sequential control and state. Theoretical Computer Science, 103(2):235–271, 1992.

8. K. Fisher, F. Honsell, and J. C. Mitchell. A lambda-calculus of objects and method special- ization. Nordic J. of Computing, 1(1):3–37, 1994. Preliminary version appeared in Proc.

LICS ’93, pp. 26–38.

9. K. Fisher and J. C. Mitchell. A delegation-based object calculus with subtyping. In Proc.

10th International Conference on Fundamentals of Computation Theory (FCT ’95), pages 42–61. LNCS 965, Springer-Verlag, 1995.

10. M. Flatt, S. Krishnamurthi, and M. Felleisen. Classes and mixins. In Proc. POPL ’98, pages 171–183, 1998.

11. E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

12. I. Mason and C. Talcott. Programming, transforming, and proving with function abstractions and memories. In Proc. ICALP ’89, pages 574–588. LNCS 372, Springer-Verlag, 1989.

13. J. G. Riecke and C. A. Stone. Privacy via subsumption. Information and Computation, 172(1):2–28, 2002. A preliminary version appeared in FOOL5.

14. A. Wright and M. Felleisen. A syntactic approach to type soundness. Information and Computation, 115(1):38–94, 1994.





Argomenti correlati :