Re: Standard Matrix interfaces

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2001-08-22 04:17:19

Hi,

John Max Skaller (skaller_at_[hidden]) wrote: 
>         Interesting! What is the relationshup between 
> a 'solver' and the 'interface' of an algorithm? 
> [No, I should say 'a collection of algorithms' which solve 
> the same problem] 

The interfaces of collection of algorithms solving the same problem
would have similar signatures: The various arguments would follow some
common minimal requirements, ie. they would be based on the same
concepts (if they don't, it should be possible to provide thin
wrappers: if this isn't possible, they are apparently solving at least
slightly different problems). Basically, the solver describes how a
specific problem can be solved: It gives a name to be used for solving
a problem (eg. 'std::sort()'), specifies arguments are to be used,
which concepts these have to follow, and in which order they occur,
provides a worst case complexity for solving the problem with this
particular solver, etc. In some sense this can be seen as the interface
of algorithms solving this specific problem, although the names of the
corresponding algorithms would vary.

Actually, my major objection to the term "algorithm" for things like
'std::sort()' is that 'std::sort()' does not at all specify 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.

>         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. 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;
if this information is errornous, eg. because a new algorithm was
discovered since the specialization was provided, it has to be
corrected) for specific types.

>         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? I thought that class based
polymorphism depends on the static types, too, just that the selection
of the algorithms is deferred until run-time, typically because the
static type information is "lost" during operation and only recovered
whem the actual algorithm is called. 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 know that the formulation is a little bit vague but bringing it
into a precise formulation is unnecessarily costly, at least I don't
see an obvious approach, and I think it is clear what I want to say...

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. In both cases the choice
depends on a set of static types (all other choices, eg. on the basis
of attributes, are equally possible in both approaches). Technically,
in C++ (some other language handle this differently) the static types
considered in algorithm choices are different, however: For dynamic
polymorphism, only variation in the first argument is used for
algorithm selection, the types of all other arguments is not considered
for algorithm selection. For static polymorphism all arguments can be
used to determine the algorithm.

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.
--
<mailto:dietmar_kuehl_at_[hidden]> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
__________________________________________________________________
Do You Yahoo!?
Gesendet von Yahoo! Mail - http://mail.yahoo.de