From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Mixins (long)
Summary: Description of mixin technology
Keywords: Mixins
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
Date: Thu, 28 Jan 1993 19:23:52 GMT

	MIXIN SOFTWARE TECHNOLOGY
	=========================

Here is a long promised description of mixins. Sorry,
there are no real examples here. Its up to your imagination
until I get something real prepared. But this description
couldn't wait.

I hope it helps.

	John MAX Skaller, Maxtal P/L, Sydney, Australia.
	maxtal@extro.ucc.su.oz.au

QUESTION: What are mixins?

ANSWER:  "Mixin" in C++ is a high power technique for using
multiple inheritance (MI) with abstract virtual bases (AVB) 
to enable incremental development of both interfaces and implementations
of classes.

To understand mixins we first need to know the basic enabling
technology. I've often commented mixins were Bjarnes greatest
achievement in C++: the following two questions outline 
that achievement. Note Bjarne claims it wasn't intended
to enable mixin technology: so much the greater is a
scientific law that has unexpected and useful consequences.



QUESTION: How do mixins work?

ANSWER: Mixins rely on the "sibling call" mechanism described in
the ARM on p234:

	"A call to a virtual function through one path
	in an inheritance structure may result in the invocation 
	of a function redefined on another path. 
	This is an elegant way for a base class to 
	act as a means of communication between sibling classes."

                   B f()=0
                  /\
                 /  \
        f();    X    Y g(){ f(); }
                 \  /
                  \/
                  D

The virtual base B in this diagram contains a 'hook' or 'vector'
function 'f'. The definition of 'f' is supplied in X, while
'f' is used by 'g' in Y. The class D is derived from X and Y
to 'connect' the definition of 'f' in X with the usage of
'f' in Y via their shared virtual base B.

QUESTION: Why does Sibling Call work?

ANSWER: Sibling call works because of the Name Dominance Rule,
described in the ARM in 10.1.1 on pp204-205:

	"A name X::f dominates a name B::f if its class X has
	B as a base. If a name dominates another no ambiguity
	exists between the two; the dominant name is used
	when there is a choice ...

	"The dominance rule is necessary for virtual functions
	since it *is* the rule for which function should be 
	invoked for a virtual call ... for virtual functions
	the dominance rule is what guarrantees that the
	same function is called independently of the static
	type of the pointer, reference, or name of the object
	for which it is called"


	Axiom Classes
	-------------

The base classes in mixin technology are usually small, independent,
and abstract: ideal for placement in a library.  The member
functions of these classes are usually small in number,
independent, and pure virtual, and may be called axioms.

	class Ax1	class Ax2	class Ax3

A set of global functions operating on the base abstractions
can be written and also placed in the library:
they will work for all implementations of the abstractions
because of polymorphism. Note that these functions
are like 'theorems' in that they are defined in terms
of the undefined pure virtual axioms. 


	g(Ax1&);	g(Ax2&);	g(Ax3&);
	h(Ax1*);	h(Ax2*);	h(Ax3*);

	k(Ax1*,Ax2*);

Although global, these functions do NOT pollute the global namespace,
since they are qualified by the classes they operate on:
they are as attached to the class as its members, but have
no access to implementation details.

The axiom classes can be combined using public virtual inheritance
to form larger, convenient, sets of axioms.

	Theorem (Interface) Classes
	---------------------------

It is common practice to put a set of related 'theorem'
functions in a 'Theorem' class derived from the axiom classes
to which it refers. If more than one class is refered
to, MI must be used. The inheritance is usually public,
although sometimes it is protected or private if the
axioms are considered too primitive for end-user invokation.
The inheritance will almost always be virtual, so that
subsequent combination of theorem classes by MI will
always only ever have one instance of each axiom class.

These classes are sometimes called 'Interface' classes,
since they contain higher level functionality than the
primitive axiom classes, which is more suitable for
use by end-users.

In general, various schemes of building on the base abstractions
can be used, or no scheme at all. It is not incorrect to
introduce new axioms into theorem classes, for example.

Note that in advanced mixin use, interface classes may themselves
be introduced initially as abstract classes. Their pure
virtuals are then defined in terms of some set of axioms
by creating an implementation class which derives from both
the interface class and the axiom classes, and implements
the interface functions in terms of the axiom functions.
The resultant interface is still abstract: but the abstraction
has been shifted from the high level interface functions
to the low level axiom primitives. Subsequent definition
of the primitives 'concretises' the interface class.


	Model (Implementation) Classes
	------------------------------

For each base abstraction, a typical library will contain several
implementations with different properties. An implementation
of an abstract class is derived *virtually* from the abstraction,
and implements it by overriding the virtual functions.

Typically, one implementation will be optimised for speed, and another
to use the least memory. However, the implementations
may also differ in their semantics, for example the pure
virtual function 'Draw()' may be overriden in different
classes to draw different shapes.

The implementation of an axiom class is called a Model or
Implementation class. As above, in a non-strict scheme,
Model classes may implement only some of the pure virtual
functions, and subsequent derivations may be needed to
completely concretise the abstraction. Such derivations
may also inherit other abstractions in order to concretise
the first set, transfering the burden of definition
sideways.

	Constructor (Mixin) Classes
	---------------------------

Now when you want to create an object which has a certain
interface, you select, or build using MI, an appropriate
interface class for your application. This class must
be globally known, and is the class with which
you perform all work.

Luckily, you dont have to write many procedures that operate
on this class: they are already in the library, although
they are typically defined to work on the bases: you can
still call them because your interface class 'isA' base,
for each of its bases.

However, the interface class is abstract, you cant
make an object of the interface class directly.
Instead you must 'mixin' <finally!> an implementation
of each axiom base by multiple virtual inheritance.

Suppose you have an interface class IF which has axiom
classes Ax1, Ax2 and Ax3. You choose to use the
implementations Ax1Im3, Ax2Im7 and Ax3Im2, because these
are optimised for speed and support the semantics you desire.
Here's how you do the mixin:

  IF * makeIF()
  {
	class Dummy : public IF,
		public virtual Ax1Im3,
		public virtual Ax2Im7,
		public virtual Ax3Im2
	{};
	return new Dummy;
  }


QUESTION: Where's the CODE??

ANSWER: You already wrote it. Mixins embody the idea 
of reusability to the fullest possible extent. 
Mixins are for lazy programmers --- the best kind :-)
 
You may have to write a constructor, though, because
constructors are not inherited. :-(

Thats why using mixins is sometimes called 'Programming
by Constructor': the constructor is the only code
you often have to write.

QUESTION: Why is the mixin class declared in function local scope?

ANSWER: It would be even better to use an anonymous class: 
the name of this class is not important and should not be known
by the rest of the system. It is, after all, a class
created purely for the purposes of implementing the interface:
and it is good practice to hide implementation details.

It is often crucial that these details are hidden, and cannot
be retrieved *even* with nasty hacks like dynamic downcasting.
This is because the implementations that have been hooked
in are too primitive for client access, and their direct
use by the end user may destroy the integrity of the object.

Making the constructor class local or anonymous defeats
downcasting, an excellent idea: the object should only
be accessed through its declared interface.

Perhaps unfortunately it is sometimes necessary to use
public derivation of the implementations so that
their constructors and destructors are accessible.
It is also usually necessary to name the concrete class
since you cannot define a constructor for the class
otherwise.

If the constructor class cannot be hidden by making it
local, its a good idea to hide it by declaring it
in file scope only.

Such definitions of the constructor class are
called 'On-The-Fly', because you make up the class
on the spot, just before you create an instance of it,
purely for the purposes of creating that instance,
and then forget the class immediately after the object
has been constructed.

Usually, the only new functions you can sensibly add to a mixin
class are those of *the* constructor and destructor,
and any helpers need by those functions. Only one constructor
is needed, since you only construct one object immediately
after mixin defintion: you might as well use the default
constructor.

It is also possible that you have selected or built an interface
class that is still partially abstract. In this case
you must also override the remaining pure virtual functions
in the mixin class. It is also possible to override
other virtual functions 'At The Last Minute' to provide
more efficient access or modified functionality.

QUESTION: Is this scheme of Axiom (primitive), Theorem(Interface), 
Model(Implementation) and Constructor(Mixin) classes 
the only way to do mixins?

ANSWER: No. You can do anything you want :-) 
The scheme outlined above is intended to indicate the 'Spirit of Mixin',
and not any set of hard and fast rules.

The basic principle of mixin is simply that you should defer
binding of the implementation of an interface until
the last possible place, and that the basic functional
primitives be encapsulated in small, independent abstract
classes.

QUESTION: Is there an even more powerful technique than mixin?

ANSWER: Yes and No :-)

YES: Delegation is more powerful than mixin.
With delegation the 'base' classes are accessed via
a pointer (or reference) to another object, and the
construction and destruction of these 'base' objects
are under programmer control. 

NO: With mixin, there are also (in many implementations) 
hidden pointers to virtual base sub-objects in the classes: 
these pointers are needed to locate the virtual bases.
However these hidden pointers are initialised and accessed
correctly at all times because they are manipulated directly
only by the compiler, not the programmer.

Mixin is the most powerful statically secure method available
in C++. 

QUESTION: Can you combine mixins and delegation?

ANSWER: It is not at all uncommon to combine the two techniques.
Mixins are prefered where possible because they are statically
and dynamically secure, and because construction and destruction
are managed automatically.

QUESTION: Is the use of virtual bases necessary in mixins?

ANSWER: Absolutely. Both the interface and implementation
classes inherit from the axioms: one to build on the
primitives, and the other to define them. If you
didnt use virtual inheritance in both cases, the definitions
would not be called by the interface functions:


                          Ax f()=0  Axiom: MUST be shared
                         /\
virtual mandatory --->  /  \   <---- virtual mandatory
                       /    \
Implementation   f(); Im    If g(){ f(); } Interface
                        \  /
                         \/
                          Mx Mixin


QUESTION: Why does mixin enable incremental development?

ANSWER: Because you can provide, and use as you desire,
implementations and abstractions in small pieces,
independently. The binding of the implementation pieces
is defered to the last minute: on the fly construction
from the pieces.

This cannot be done with single inheritance (SI):
with SI you get 'layered development', in which
binding is done in layers.

Of course, delegation also provides incremental development,
and is more powerful than mixin, so arguing that
only SI and delegation is needed is pointless: mixin
is the technology that provides greatest power while
remaining statically secure.

QUESTION: Can I use mixins with templates?

ANSWER: Oh YES. Please do.

QUESTION: Whats the best way to build a class library?

ANSWER: With mixins of course. Delegation may also
be required for more advanced techniques. However,
delegation is not as well supported or secure as
mixin in C++: use mixins wherever possible.

QUESTION: Whats the worst way to build a library?

ANSWER: Thats a leading question :-) The worst way
is to use an 'Object Heirarchy' which has a single
class 'Object' from which everything is derived by SI
in increasing levels of complexity.

This inevitably leads to either a VERY fat interface for
the 'Object' class in order to preserve polymorphic access via
virtual functions, or use of downcasting to emulate dynamism. 

Both these methods are ugly in C++, and break all the known
principles of good modular design:

	o Small interfaces
	o Weak coupling
	o Explicit coupling
	o Hiding of implementation
	o Closure of modules to changes
	o Openness of modules to extension
	o Reusability

	
Those not believing this should try to combine the use
of several Object based class libraries. The original
Borland and NIH libraries are examples.

QUESTION: Why dont mixins have this problem?

ANSWER: Because a mixin library is based on a set of small,
independent abstractions. Using two mixin libraries together
is just a case of taking the union of the abstractions.


QUESTION: Does use of mixins lead to an exponential explosion
of classes?

ANSWER: Not necessarily, it should do precisely the opposite.
The sets of basic abstractions and their implementations
can be combined by a simple union: the numbers of
such classes is just a simple addition --- its linear not
exponential.

Certainly, the number of *possible* combinations you can
have with mixins is exponential --- its supposed to be!
This is the whole point: you can have a very wide choice
of interfaces, yet implement them by a simple mixin
of some set of implementation classes.

But these choices are made 'on the fly': the existant
combinations in any one program will always be small,
and the differing implementation choices are irrelevant
because they're hidden.

Again, the number of useful interface classes you can
form will be exponential on the axiom classes, and this
is desirable. You dont have to actually create every such
combination.

Mixin libraries should be considered a toolkit of reusable
components, together with a few common combinations of these,
supplied for convenience.

A mixin library is not a monolithic, integrated, tightly
coupled system like an 'Object Heirarchy'.

QUESTION: Are mixin libraries hard to design?

ANSWER: Yes, all reusable components are hard to design.
It is not easy to decide exactly how to divide up functionality
between classes.

QUESTION: Are mixin libraries hard to use?

ANSWER: No, they're quite easy to use: often you need only
derive an appropriate class, mixing in the desired implementation
components, and possibly writing a constructor.

However, you should note that a mixin library does not
present you with a total solution to your problem. It still
leaves the task of designing solutions and implementing
them up to you, the programmer. It presents a wide variety
of solutions: you have much more choice than with an Object
Library.

What the mixin library does is save you writing code: you will
spend more time deciding which classes to use, and how to
plug them together than coding: the code is already written.

When you do have to write code, its usually to supply a new
implementation of an axiom class. In that case, the constraints
are extremely tight: the interface to which you must
conform is well defined, and the coding job is usually trivial.

You can, and will, of course, create new axiom classes,
some more application specific than others. Mixins are 
wonderful in supporting this, because you only have
to provide the application specific interface and
implementation details, you can reuse other components
togther with your application axioms just as you
can when using the library classes: by using
MI to combine your classes with those in the library
to provide more complete application interfaces,
and by using mixins to construct them.


QUESTION: How will mixin libraries change my coding style?

ANSWER: You wont spend much time writing code. Your effort
will be directed towards design rather than hacking.

QUESTION: Are there any good mixin libraries available?

ANSWER: Not that I'm aware of. There are several reasons:

	1) Early C++ didnt have mixins: there was no
	  MI, only SI. People still use class libraries
	  designed at this time.

	2) Many existing compilers have or had until recently,
	  bugs in the implementation of MI, 
	  abstract classes and virtual functions.

	  For example, Cfront version 3 incorrectly diagnosed
	  mixin classes as abstract, defeating the use of mixins.
	  Version 3.0.1 is fixed, I believe.

	3) Mixin technology is not well understood.
	   Thats why I've written this article.

	   Mixins use some of the newest concepts in C++:
	   Abstract classes, Multiple Inheritance, and
	   Virtual bases: in combination. And templates and
	   exceptions will add to this technology.
	
	4) Many programmers come from a Smalltalk background.
	   So they are still thinking of OOP in terms of
	   dynamics and Object Hierarchies, techniques not
	   suited to C++, which is an essentially a strongly typed,
	   static, and compiled language.

	   C++ OOP is so different from Smalltalk, that I have
	   trouble conceiving them as both OOPLs. In fact I
	   tend to think of C++ as a class based language,
	   not an object based one.

	5) There are few examples. Because of 1-4, there are few
	   examples for other to learn from and improve on.
	   I hope this will soon change :-)
	   Use of a technique is exponential, there is the well
	   known 'Snowball' or 'Band Wagon' effect.

	   The situation is improving: already Borland, for example,
	   has replaced its Object based classes with the much
	   better BIDS classes. Although these are not yet
	   quite mixin classes (BC 3.1 has the mixin disabling bug),
	   they do use templates and MI: the precursor to
	   mixins.

QUESTION: Can I get around the mixin disabling bug?

ANSWER: Yes, you can just define a dummy body for your
pure virtual functions: it will never get called, but
it does make the code look messy, and it does prevent
the linker detecting when you have failed to supply
an implementation for a pure virtual (since they're
not pure virtual if you give a dummy body).

QUESTION: Can you show me an example of mixins?

ANSWER: Yes I promise! But not yet, I'm still working on one that
is non-trivial and actually usable. This is not so easy,
as my compiler has the mixin disabling bug. The compromise
between a 'Micky-Mouse' example (not convincing) and
an industrial strength one (lots of work and may have
too much detail for educational purposes) is an example
of the sort of design problem that I'm grappling with.

I'm currently working on a text screen based database.
(No, not a persistent object store, just a device independent
record manager with windows, dialog boxes etc--usable but
not sophisticated).

However, I invite those few programmers that have used
mixins to post examples.



-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;------ SCIENTIFIC AND ENGINEERING SOFTWARE ---ph:  2 799 8223 --------
Newsgroups: comp.lang.c++