Re: [boost] Re: Standard Matrix interfaces

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-22 12:09:13

Dietmar Kuehl wrote:

[snip interesting discussion]

> Actually, my major objection to the term "algorithm" for things like
> 'std::sort()' is that 'std::sort()' does not at all specify an
> algorithm!

        I think your objection is ill founded, because you're
making a category error. In the Standard, 'sort' is called
an algorithm. But what it specifies is a 'solver' in your
terminology. But that is, in fact, correct, because the Standard
is requiring an algorithm be provided by the implementor
which is an 'instance' of the solver: the vendor has to
provide an actual algorithm (an actual piece of code
that sorts).

        There's no mechanism to have two sort algorithms
(in a single implementation).  That is, the requirement,
although it is a description of a solver, really is for
an algorithm.

> You can use different algorithms to actually implement this solver, eg.
> merge sort, heap sort, intro sort, and, due to the specific complexity
> restrictions of O(n * n), even quick sort. 'std::sort()' is in actually
> a name for a collection of possible algorithms, one of which is choosen
> at compile time to solve a specific problem.

        Yes. But a vendor must actually chose one particular
algorithm and supply it. So the requirement is for an algorithm
to be supplied which matches the solver which is specified
by the Standard: 'sort' is a solver in the Standard, but
an algorithm in a given compiler.
 
> >         In particular: using the notion of specialisation,
> > an STL algorithm interface still only admits ONE algorithm
> > as a solver: you can't have two ways to 'sort' iterators
> > of the same _type_, because specialisation is type based.
> 
> Yes, this is intentional! If you know exactly the types involved in the
> problem, you can once choose the best algorithm for this combination of
> types. 

        The best algorithm is almost never determined
by the data type. Rather, it is determined by the data functor:
that is, the container which is being sorted -- not the type
of elements in it. In STL, this is represented by the
'forward/bidirectional/random' iterator categories,
this is not really 'type' information (but an abstraction of it
which ignores the value type).

        To be more precise, ignoring iterators and
talking about sorting containers, if we write:

        list<int>
        list<string>
        vector<int>
        vector<string>

then it is the 'list' or 'vector' which characterises the
best algorithm for sorting, not the 'int' or 'string'.
It isn't the container 'type' that is important,
it is the container _structure_. The name given to that
in type theory is 'data functor': in C++ its just
called a class template :-) Either way, it is the template
that determines the best sort algorithm NOT the type
(of an instantiation).

> If you leave open just one type, you can still specialize on
> this on type to obtain a better solver. The important feature is that
> solving a problem always uses the same solver with the same name, order
> of arguments, concepts of the arguments, etc. independent from the
> exact types. The compiler will choose the best known algorithm (known
> by the compiler because people told him in the form of specialization;

        Yes. Very interesting characterization:

        solver == primary template interface
        algorithm == specialisation used (whether an instance of
                a general algorithm or a user defined specialisation
                isn't relevant)

> >         That constraint doesn't apply to class based
> > (virtual function based) polymorphism.
> 
> Are you saying that class based polymorphism supports different
> algorithms for the same static types? 

        Yes:

        struct Solver {
                void sort(Container &c)=0;
        };

        stuct Algo1 : Solver {
                void sort(Container &x);
        }
        struct Algo2 : Solver { ....}

        Algo1().sort(c); // use algo1: concrete
        Algo2().sort(c); // use algo2: concrete

        Solver *algo = Algo1();
        ..
        algo->sort(c); //polymorphic

> I thought that class based
> polymorphism depends on the static types, too, 

        Yes, but not just the type of the input data:
you can use a type (as shown) to choose a specialisation
_other_ than the container type. [And as Helmut pointed
out, you can do that for templates too, using a dummy tag type,
which is a crude form of policy/traits: its a hack, and 
the choice is at compile time not run time, but it does work
in some sense]

> There are, of course, good reasons
> to "loose" the static type information. All I want to point out is that
> dynamic polymorphism is no different from static polymorphism in
> choosing exactly one algorithm for a specific set of static types!

        Yes, I believe you're right. However, you can also use
_state_ to choose, and one can argue that the template type
tag hack is really a trick which uses type to represent state.

> Conceptually, the difference between using virtual functions or a
> generic approach (in the STL sense of generic; of course, dynamic
> polymorphism is also generic) to select an algorithm is just the point
> in time where the algorithm is choosen. 

        Yes. However, that difference is significant in todays
crude language technology: very little is known about construction
of partial evaluators (which provide a seamless division between
compile and run time).

> In general, however, whether to use dynamic or static polymorphism
> (virtual functions and templates) respectively depends on the problem
> at hand and I haven't seen situations where both are really choice:  If
> you need dynamic polymorphism, well, you need dynamic polymorphism.
> Otherwise you will probably use static polymorphism, mostly because it
> is more convenient.

        I wish you were right. I think that, often, making the choice
is not so easy. It is a balance between current needs and
future expectations of change, and the decision is often made
by non-technical people (indirectly, by timing, budget, and 
stupid technical constraints: eg, how do you choose static
polymorphism in Java? <g> How often have you seen a job advertisement
for 'programmer, capable of thinking and learning'?

-- 
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