[boost] Comments on Value Semantics vs. OOP et. al.

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  
decrement
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
sparent_at_[hidden]