Boost logo

Boost :

From: Sean Parent (sparent_at_[hidden])
Date: 2006-07-07 15:59:48

A couple of passing comments (okay - it turned into a lecture, I've
been doing to much public speaking lately...)

Generic programming is the processes of defining algorithms in terms
of semantic requirements on types and operations with the goal of
achieving maximum efficiency _and_ the highest level of abstraction.
I have a presentation with the following table relating generic
programming to abstract algebra.

Generic Programming Mathematics
Semantic Requirement Axiom
Concept Algebraic Structure
Model (types and operations) Model
Algorithms Theorems
Regular Function Function

Refined Concept - a Concept defined by adding requirements to an
existing concept.
        monoid: semigroup with an identity element
        BidirectionalIterator: ForwardIterator with constant complexity
Refined Algorithm - an algorithm performing the same function as
another but with lower complexity or space requirements given a
refined concept.

One of my favorite quotes from Alex is "Software is defined on
algebraic structures."

We don't make the semantic requirements up - we discover them in the
algorithms we write on the machine model we're given.

I like to bash on OOPs as much as the next Generic guy - but the fact
is that the same Concepts _must_ be reflected in OOP or the
algorithms _can't_ work. Generic programming is as much about
understanding how software works as how to write software. The most
common point of contention I hear is that the current practice of
Generic programming ignores "move" as a semantic requirement (we
speak in terms of assignment which is often too strong) where as OOP
(as currently practiced with heavy use of heap allocated objects)
gets "move" for free (as a side effect of an implementation detail to
get polymorphism) - hence OOP programmers don't see the strong need
for copy and assignment. Nearly all of the STL algorithms could be
recast in terms of move and would be more efficient. We can do a
pretty good job of an efficient move with swap() - but _really_ swap
should be defined in terms of move instead of being a primitive. An
interesting point is that move() is much more necessary with the
current style of OOP because of the need to use factory functions
instead of constructors for object creation - so us Generic guys
would rather just create the object in place.

The requirement of polymorphism comes from the desire to perform
algorithms on heterogeneous collections (different types modeling the
same Concept(s)). Since a model is a collection of types and
operations, imposing the requirement of polymorphism through
inheritance on closed classes is unnecessarily intrusive and
limiting. Inheritance becomes a significant barrier to code reuse.
The need for heap allocations stems from the fact that heterogeneous
types will be of different sizes - dealing with these pointers (and
the significant ensuing issues) is purely a side effect of that
implementation detail.

Non-mutable values have the advantage that pointers to a non-mutable
value have the same semantics (practically) as just a const value
(hence FP languages have value semantics even though they're
typically implemented with references). The difference with pointers
only appear with multiple write access; which in practice is
relatively rare, even by accident in systems with rampant use of ref
counted pointers. Trying to eliminate all mutating operations is
foolhardy. That's not just my opinion, John Backus told me he always
knew that mutating operations were necessary, he just didn't know how
to deal with them systematically - he is impressed by Alex's work in
this area.

The difference between having operator=() mean "move" and operator=()
mean "assign" is purely one of syntax - not semantics. It is
desirable to settle on a single syntax for the Regular operations
(copy, assign, move, equality comparison) and that implies the use of
copy_ctor, operator=(), swap (until we have a good move), and
operator==() for consistency with built in types (including the
pointers used to refer to the OOPs objects).

It is more important to define algorithms in terms of concepts then
to debate the syntactic issues. Algorithms are our theorems. Seek to
_understand_ what is going on with OOPs instead of simply slamming
it. The fact is, programming with runtime polymorphism using the
current Generic programming style is cumbersome and often requires
significant language abuse to achieve the same results that can be
had with simple inheritance. Of course, thanks to Boost much of that
abuse comes pre-packaged and ready to use.

Sean Parent
Sr. Engineering Manager
Adobe Software Technology Lab

Boost list run by bdawes at, gregod at, cpdaniel at, john at