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
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,
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
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
-- 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk