NEM 2005-09-28: Traits

[1] (and [2]) are another technique for organising Object-Oriented code. They are presented as an alternative to both multiple inheritance and mixins (as in XOTcl). In reviewing TIP #257: Object Orientation for Tcl I came across the concept and thought it might be worth writing up as more food for thought while debate is occurring over this TIP. Below I'll summarise the argument and mechanisms described in the paper.

The paper linked above identifies a number of problems with both multiple inheritance (MI) and mixin inheritance as means of reusing implementations. Problems of MI are well-known, such as handling conflicts when the same functionality is defined in two parents, handling case where the same parent is inherited from twice ("diamond" inheritance), and being able to define "wrapper" functionality. This is made more complicated by the use of mutable state. While conflicts between methods can often be resolved, it is less clear what should happen with conflicting state variables. Mixins solve some of these problems, but not all. They are conceptually easier than MI, but they still have some problems. You define a total order on mixins, which is the order in which they get to intercept messages on an object. However, if mixin objects A and B define an overlapping set of methods, out of which you want some methods from A to have priority, and some from B, then it is difficult to specify this with mixins. In addition, mixins add a similar kind of fragility as found in MI: adding a new method to a mixin may silently shadow a same-named method on a different mixin somewhere else in the inheritance order. More examples are given in the paper.

The solution proposed is that of traits. Traits are basic collections of functionality that are used as building blocks for assembling classes. A trait essentially:

• Provides a set of methods implementing some behaviour (i.e., some interface);
• Requires a set of methods to parameterise this behaviour (see below);
• Have no state variables, i.e. provide only methods;
• Can be composed with other traits and classes. Order of composition doesn't matter; conflicts have to be resolved explicitly.

In addition, a composition of traits is equivalent to the flattened trait containing all of the combined methods individually. So basically, a trait provides some implementation of some interface. However, rather than defining it in terms of a specific object representation, it instead defines it in terms of some other interface (which it requires--bullet 2 above). This interface is either provided by another trait, or by a class. A class then provides the actual state variables that form the implementation of the class, and a primitive interface for accessing these variables (i.e., a built-in trait). Classes can also use single-inheritance for reusing state definitions in a strict is-a hierarchy. So, a class is basically:

 class = superclass + state + traits + glue

Where the "glue" is code to explicitly resolve any conflicts between traits and provide access to the state. Traits can then be seen as stateless implementations of functionality which just require a "self" parameter with the right interface.

As I mentioned earlier, the semantics of trait composition is defined as being the same as if the traits were all flattened into one big trait. In other words:

 trait T1 defines methods { m1, m2, m3 }
 trait T2 defines methods { m4, m5, m6 }
 then (T1 compose T2) defines methods { m1, m2, m3, m4, m5, m6 }

i.e., traits are sets of methods and composition is set union. As this is set union, duplicates are not allowed. Methods are only distinguished by name though, so two methods may be duplicates from the point of view of the composition, but actually define different behaviour. Note, however, that if we compose the same trait multiple times then we can ignore those conflicts as the methods are identical, and traits define no state (are referentially transparent) so we can happily just pick one instance of the trait/method in question. This is not the case though for conflicting methods from different traits or between classes. These conflicts are resolved explicitly (manually), rather than relying on some general strategy. However, when adding traits to classes, two general rules are used:

• Class methods take precedence over trait methods;
• Trait methods take precedence over superclass methods.

The latter follows from the flattened-composition policy -- trait methods should look as if they are actual methods of the class, and so should have precedence over superclass methods. The first rule makes sense as class methods provide the only access to state, and so if they were overridden then there would be no access.

If conflicts are left unresolved then the composition operation replaces the conflicting methods with a new method that simply errors indicating the conflict if called. This new method is only present in the composite; the original traits are left as is (they are perfectly useable individually still). Trait composition is thus associative and commutative, i.e.:

    T1 compose (T2 compose T3) == (T1 compose T2) compose T3 -- associative
                 T1 compose T2 == T2 compose T1              -- commutative

These are clearly important modularity properties to preserve while building software components, ensuring that the order and manner in which you compose components doesn't affect the overall behaviour of the resulting composite component.

In order to resolve conflicts, traits support two operations:

• Aliasing allows a method from one trait to appear under a different name in the composite;
• Exclusion suppresses methods from one trait, allowing methods from a different trait to be composed without conflict.

Let's look at an example using a Tcl-ish syntax of what defining a class would then look like:

 class define circle {
     # Define some state
     variable centre
     variable radius
     variable colour

     # Pull in a bunch of traits and compose them with current class
     trait use tcircle -rename {
         hash circleHash
         =    circleEqual
     }
     trait use tdrawing
     trait use tcolour -rename {
         hash colourHash
         =    colourEqual
     }

     # Define some glue methods
     method hash {} {
         expr {[self circleHash] ^ [self colourHash]}
     }

     method = object {
         expr {[self circleEqual $object] &&
               [self colourEqual $object]}
     }
     # Other methods here to provide access to state, and other "intrinsic"
     # operations
     ...
 }

This example is taken from the paper where it is written in Squeak Smalltalk syntax (pp. 13). If we later decide that colour equality is not important in our definition of circle equality then we can remove the references to colourEqual/colourHash from the code and change the trait inclusion to:

 trait use tcolour -remove { hash = }

to get rid of the conflict. (As an aside, it strikes me (NEM) that as these traits behave like sets, then perhaps we could use set or relational operators to manipulate them. i.e., use set difference for removal, and a relational rename [3]. That also suggests more powerful ways of manipulating traits...).

One of the consequences of how trait composition is defined is that in any given class + collection of traits, there is only ever a single method with a given name. This means that calling "super" (or "next" as it is in XOTcl) will always result in a call to the super class, rather than to some other trait. This also means that we can collapse a number of chained resolution calls into a single one, which should help with efficiency too.

Discussion

In general, I think traits are a powerful concept. They seem to be much more rigorously defined than many OO techniques, and the separation of an implementation of an interface from the state that that implementation uses seems like a good one, and this seems to make reasoning about composition of behaviour more tractable. The idea also reminds me quite a lot of type-classes in Haskell, where there is no state at all (even in classes, which would be types in Haskell). Type-classes can be parameterised over several other types/type-classes though, whereas traits only allow one (the "self" object which will be extended by the trait). Type-classes also ensure that "method names" are unique, but they don't allow renaming or exclusion: operations defined in type-classes have to be globally unique within the current module scope. There are also other differences in detail of how the two mechanisms work, but they both do well at separating out implementations of different interfaces. One thing I particularly like about type-classes is that you can make a type (or combination of types) an instance of a type-class at any time, not just at definition time. i.e., you can do:

 instance SomeClass MyType where
     ... implementation of SomeClass interface for MyType ...

The equivalent for traits would be adding another trait to a class after definition time. Perhaps through some syntax like:

 myclass trait use $sometrait

Of course, you'd have to resolve any conflicts again, to make sure the new trait didn't affect the existing behaviour of the class (unless you explicitly want it to).

One small change I might make, is that if a trait method has been removed to avoid a conflict then it might be possible to still access it through an explicit calling convention. For instance, it each trait was also an ensemble, then I could do:

 set c [circle create]
 tcolour hash $c

Where [tcolour hash] is the explicit name for the hash method of the tcolour trait that we removed earlier.

I might adopt this mechanism in the next version of TOOT. I think it could work quite well there, especially as traits are already stateless (like TOOT objects).

Anyway, I thought I'd write this up for the thoughts of the community. Think of this as part of a requirements-gathering exercise for TIP 257. It's another feature I'd like to see be possible to implement on top of whatever OO system was in the core. It may well be possible to implement traits on top of the XOTcl-like current proposal, or it may be possible that XOTcl can be implemented in terms of traits. Comments please.

---

NEM: Thinking about this some more, traits are basically like classes which take their "self" argument as a parameter at construction time. This leads to a system very much like the pattern described in Designing SNIT widgets as mixins. However, they also make sure that only the very inner-most class/trait actually has any state, which makes the laws of composition clearer, and cleaner (IMO). So it should be possible to do similar tricks like:

 [undoable [contextmenu [autocomplete [entry $path]]]

However, the main difference here is that typically these "traits" would be overriding the same methods a lot, leading to lots of conflicts to be manually resolved. Additionally, some of these "traits" (e.g., undoable) really look like they would add some additional state. So perhaps here the total ordered approach of mixins would be more appropriate. Still, the basic idea of having collections of methods which are explicitly parameterized by their "self" object seems like a good one. Perhaps it is then just a case of deciding at composition time whether to use mixin or trait-like composition. The idea of having self be an explicit construction-time parameter is also present in OCaml, where you can have, for instance:

 class printable_point x_init =
   object (self)
     val mutable x = x_init
     method getX = x
     method move d = x <- x + d
     method print = print_int self#getX
   end;;

Here "self" is an explicit parameter to the object constructor. The (great) paper "Haskell's overlooked object system" (Kiselyov/Lammel/Schupke) [4] also takes a similar approach, where objects are created out of monadic records:

 printable_point x_init self =
   do
     x <- newIORef x_init
     returnIO
       $  mutableX .=. x
      .*. getX     .=. readIORef x
      .*. move     .=. (\d -> modifyIORef x ((+) d))
      .*. print    .=. ((self # getX) >>= Prelude.print)
      .*. emptyRecord

The self argument is actually supplied by a monadic fix-point operation (see Combinator Engine for a description of the "Y" combinator, which is another fix-point operation):

  do
    p <- mfix (printable_point 7)
    p # move $ 2
    p # print

So here, even our inner-most class remains parameterized by self, and we use a fix-point operation to effectively pass it itself as the parameter. BTW, I recommend that OOHaskell paper for anyone who really wants to understand and relate various concepts in OO languages. (You need to know a bit of Haskell and monads first, though).

---

AM I very much like the idea of a flat organisation: the hierarchy imposed by inheritance of any sort seems too much an implementation aspect rather than an essential feature. Delegation tries to overcome that, IIRC. How does delegation relate to traits? (I am no expert on OO paradigms and I hope I will be able to understand the paper on OO in Haskell, knowing the little about Haskell that I do know.)

I am not sure yet how this works in practice ...

As an aside:

In Fortran 90 modules were introduced as a way to organise code. The properties of modules (using them in another context, renaming items contained in the modules and including only selected items) reminds me very much of traits.

It just shows how the people from the C++/Java community have monopolised the object-oriented programming world. There is so much more possible than what is propagated in these worlds!

NEM Delegation is another technique that achieves much the same ends (it is briefly mentioned in the paper linked at the top of this page). Delegation takes up the extreme late-bound/dynamic position on the spectrum of how to handle these things. That makes it extremely flexible (as Snit demonstrates), but also makes it harder to determine what interfaces an object supports from introspection. You have to trace through the delegation chain to work out what messages get forwarded where, and which ones are handled by what component. I'm not sure whether this is much of a real problem for Snit in practice, but it is worth exploring alternatives. I guess another advantage of traits is the possibility for optimisation: as method name conflicts have to be resolved for trait composition, then resolution should be simple/direct without requiring a complex lookup procedure. Of course, that means you basically encode the resolution procedure yourself in special purpose glue code, but for most cases I imagine this is not much of a chore.

---

Traits in XOTcl

Solving Traits problems with standard OO

jima: I liked what NEM is saying here about traits and as I also like XOTcl tried this. Comments wellcome !

---

Conflicts in Traits

jima: I was reading NEM's comments to Artur Trzewik's [5] and thought of something perhaps of interest. The thing is that NEM states that, for Traits, no special pre-arranged method for resolving conflicts should be used. Users should be in charge when dealing with those conflicts.

I am considering now an scheme in which the order of composition determines the way two procs with the same name (a conflict) are used.

I will try to make myself clear by means of an example.

If there is a trait ThA_Trait that includes a method ToDoSome and there is also a trait ThB_Trait that includes a different method also called ToDoSome then, if I compose like:

 ThA_Trait + ThB_Trait

I would be implictly saying I would prefer to invoke ToDoSome from ThA_Trait in this case. Saying:

 ThB_Trait + ThA_Trait

I would be meaning just the opposite.

How does this sound to you as a predefined conflict solver (if that concept does not clash with the definition of traits)?

NEM Well, firstly, the traits research as described above requires conflicts to be resolved by authors of a class -- i.e., conflicts are resolved manually at composition time. In Artur Trzewik's implementation via aggregation the "conflict" is instead left to clients of the object. Alternatively, you could say that there is no conflict, as methods from individual traits remain in separate namespaces (aggregate components). My comments on that page were that I think this is not so bad a decision, and may even make more sense than the flat composition of traits. That is a sharp departure from traits, though, and may not be adviseable in practice (I'd have to review the rationale behind the decision in traits more carefully).

Secondly, regarding your specific suggestion, what you propose is essentially very similar to what mixins provide already in XOTcl, or indeed what inheritance itself provides (to a certain degree). Traits however explicitly avoid this form of ordered composition (as described above) in favour of commutativity of composition. There are a couple of reasons for this. Firstly, ordered composition doesn't solve the situation where several methods between two traits overlap, but you want to use some from one trait and some from the other. Secondly, if ordering is important, then you have to trace the execution flow of your program to see in what order traits are composed to be able to determine which traits (mixins) have priority. If all trait composition was specified at the same time then this would be acceptable, but there is always the possibility that someone will add a new trait to your object later (indeed, I'd expect that to be a useful way of extending the functionality of an existing object) in some other part of the code. With traits, adding a new trait to an object leaves the original objects unchanged and returns a new object as the result of the composition. This means that I can always be sure which traits form part of the object I have, and that these traits won't change over time. e.g., rather than doing:

 Class foo ...
 foo mixin ... ;# Add a mixin
 ....
 foo mixin ... ;# Add another, much later, changing the composition

You'd instead do something like:

 set myobj [trait1 -rename {foo bar} [trait2 [myclass args...]]]
 ...
 set myobj2 [trait3 [$myobj rename foo bar]] ;# $myobj2 has new composition, $myobj is left unchanged

I've used a different syntax for traits here, one which I think works better. The semantics are essentially the same. Notice how in the traits example we don't mutate the object to add a new trait, but rather derive a new object from composition of the new trait and the old object. This means that code which already uses $myobj can continue exactly as before, guaranteed that the interface of $myobj is not going to suddenly change. Of course, there may be times when you explicitly do want to change the original object (e.g., to fix a bug, or update some implementation). You could still achieve that by mutating the variable containing the object, rather than the object itself. Of course, all of this can be implemented on top of XOTcl easily enough, by just being more careful about the use of mutable state. I think an implementation via dicts would work just as well (well, if we had decent lambdas for the methods), except for the base classes at the very centre of the compositions, where you might want something more flexible (e.g., XOTcl objects supporting inheritance and mixins etc -- getting the best of all worlds).

jima: I see NEM point concerning my proposal. It is true that it does fall close to actual XOTcl mixings. Perhaps it departs from it in the sense that I would consider a trait an object of a certain class that can be composed with other traits to produce more trait objects. The key thing for me would be establishing the rules of trait objects compositions (perhaps similar to the one I proposed). Then, at run time, users should select the collection of functions their traits are made of in order to pass functionality to their objects. They do so by mounting the mechano of trait pieces with the known set of rules.

Perhaps, this goes along escargo's following comment, refactoring is greatly improved by using adjustable collections of methods that can be changed easily from one version to another of the code, without changes in the actual functions being selected.

---

Refactoring with Traits

One issue about traits that I haven't see discussed yet is program evolution when using an object system with Traits.

Refactoring is one of the key development practices (expecially for Extreme Programming). Instead of abstracting common behavior into a new or modified parent class, Traits allows common behavior to be refactored into new Traits. Smalltalk has a refactoring browser [6] to facilitate reorganization of code. (Apparently so does Ruby [7].)

Taking full advantage of using Traits will require adding refactoring support to OO IDEs so that Traits can be supported as part of an extract trait from class refactoring operation. - escargo 3 Oct 2005

NEM The paper cited at the top of the page discusses refactoring the Smalltalk standard library using traits. IIRC, they developed a new refactoring browser for this task. More details seem to be available in this [8] paper, although I haven't read that one myself yet.

escargo Adding trait-extraction to XOTclIDE would be the challenge, I guess. (Are there other OO IDEs for Tcl?)

Another thought occurred to me: For a less sophisticated way to try to solve the same problem, if ones' langauge supported it, you could use source (or include) or a macroprocessor system to insert pieces of source code (corresponding to the trait implementations) into the code. As usual, such a system would be less effective than one that actually has the right tool support (a refactoring browser), but it might serve as a testbed to see how well trait-based coding might work.

---

ulis, 2006-11-21. Very interesting. Very near my point of view ('Simple', my new algoritmic language).

---

escargo 28 Dec 2006 - The Scala programming language is an object-oriented language that supports Traits: http://scala.epfl.ch/

See Also  edit

polymorphism

---