Re: [boost] Re: Technical session at the October C++ meeting?

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-20 18:30:33

Peter Dimov wrote:

> But I said nothing about a stack or absence of compiler support. :-) 

        Ah: I misunderstood. OK.

> I said 'as efficient as', period. There are several ways to meet this requirement,
> for example having a lightning fast heap, or having a separate stack from
> "the stack," or making std::vector magical.

        Damn. I lost my spellbook yesterday.

> In short the goal is a std::vector that doesn't give us any excuses to use
> _alloca, realloc, new[], VLAs, or even scoped_array.

        Well, I think it would be possible to provide a pretty
fast vector with OS support. (Allocate a huge address space,
and use VM to fill the memory on demand). But this isn't
allowed in C (malloc must return real memory: i.e., you can't
get an out of memory error if malloc() returns non-NULL).

> > > My experience is somewhat different.
> > >
> > > class xml_element;
> > > class xml_text: public xml_element;
> > > class xml_tag: public xml_element;
> >
> > This is not a proper variant construction, unfortunately.
> > It is a common abuse of inheritance to try to emulate the missing
> > functionality.
> 
> No, this is not an abuse of inheritance. xml_text IS-A xml_element, and
> xml_element is fully abstract. I'm using a 'constrained' variant where the
> set of possible types is limited to those derived from a common base.

        Contradiction. If an xml_text is_a xml_element, there cannot
possibly be any reason to constrain the derived types, and there
cannot possibly be any reason to call it a variant, since there
are no operations specific to the type not represented 
in the abstraction.

        You need to understand what a variant is.
In ML, the syntax:

        type xml_element = 
                | Xml_text of string 
                | Xml_tag of string

denotes unification. The type 'xml_element' is a UNION of the types
'string' and 'string' discriminated by the tags 'Xml_text' and
'Xml_tag'. 

Such a union type, whose components are called variants,
is ABSOLUTELY NOTHING TO DO WITH ABSTRACTION AT ALL.
On the contrary, it is NOT the case that an Xml_text 'is-a' xml_element.
No. It isn't. Xml_text is an xml_element _constructor_. 
An xml_element can only be 'used' one way:

        match x with
        | xml_text s -> print "text "; print s
        | xml_tag s -> print "tag "; print s

[And the match statement is a union _destructor_]
It's very important to understand that the data type 'xml_element'
is a CONCRETE ALGEBRAIC DATA TYPE. No abstraction here.
No "is-a" relation.  

The implementation of the above is simple: the tags
are integers, and the match is a switch. In other words,
it uses run time type information, embodied in the tag.

My point again: you can use inheritance as a substitute
for variants. But it is ALWAYS a hack because the
relationship is anything but one of abstraction.
Quite specifically, it isn't a matter of abstraction,
but unification.

The big advantage of the boost variant technology
is that it seems to enshrine, once and for all,
this hackery into a recognizable pattern.

[My own implementation was more correct: I used a
union with a tag discriminant, the way it should be done.
But using it was a nightmare: inheritance is more
convenient, even if it isn't correct. The plain fact
is that C++ is deficient, and the only correct
fix is proper core language support: failing that,
anything that works and is recognizable is probably OK]

A LOT of people are wrong on what abstraction is.
A LOT of people, including respected book authors,
think that taxonomies are correct examples of subtyping.
They're completely wrong. A classification heirarchy
is NOT an case of abstraction at all, but one of
unification and equivalence classing. It is patently
obvious that:

        type animal = Dog of .. | Cat of ..

is the correct representation of (one level of)
a classification heirarchy, which proves
immediately that no abstraction is involved,
since the union/variant construction has
a well founded basis in type and category theory.

An abstraction is a FUNCTOR: a structure preserving
map. A collection of variants is a SUM type.
(And a tuple is a PRODUCT type).

Two correct examples of abstractions:

        1) An abstract class an one derived class:
        the conversion derived->base represents
        the functor ABSTRACTION-->INSTANCE
        (yes, it goes in the opposite direction)

        2) A template container C<T>
        Instantiation T-->X is a FUNCTOR
        from C<T> to C<X>
 

To be precise: there really IS a functor involved
with sum types, but it isn't the one you think:
in a category X with sums, there is a bifunctor

        X * X -> X

mapping every pair of objects (types) in X to
a sum. It is easier to understand the bifunctor
for a tuple: it maps every pair of types to
a tuple type tuple<A,B>. THATS the abstraction,
and it's at a meta-level to the relationship
between tuples and their components and 
sums and their variants.

You may be interested in the relationship
between variants and tuples: they're actually
dual constructions: the very same thing, control
inverted.	

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net