Mathemagix

[Bernard Mourrain <address@concealed>]

Hi Joris,

Here are some comments on part 2 of an old message, regarding the merge 
of algebrix and algebramix:
> A second main and recurrent concern is the way to customize
> implementations, such as the use of different implementations
> of Polynomial C (dense, sparse, Bernstein). In synaps this is done
> by templating containers over namespaces. In mathemagix, we have
> so far used the concept of a special template argument called the variant,
> using which a class can be customized a posteriori.
>
> In the Mathemagix language, the ideal solution would be to
> declare the correctness assumptions for every routine.
> For instance, if we have a routine foo which does something
> interesting on polynomials, we might write
>
>         forall (C: Ring, P: Polynomial_ring C) foo (p: P): P == ...
>
> We see here that we *explicitly* have to abstract the routine
> so as to work for all kinds of polynomial rings instead of
> a particular one. This is more or less equivalent to specifying
> a variant template parameter, except that the customization has
> not to be foreseen in any of the implementations of polynomials
> themselves. Rather, the signatures of the different implementations
> have to match Polynomial_ring (and wrappers might be added to force this).
> Of course, in C++, we might have written
>
>         template<class C,class P> P foo (const P& p) { ... }
>
> or
>
>         template<class P> P foo (const P& p) { ... }
>
> where C equals P::C_type for some typedef inside P.
> This leads me to the opinion that we probably should do something
> similar in C++: never try to "prepare the ground" for future
> customization of some class, but rather allow for the customization
> of the implementation itself.
>
> In fact, it seems that the variant mechanism still remains useful,
> but only for the customization of underlying implementation issues,
> much in the same way as synaps specifies namespaces for the underlying
> arithmetic. Notice that having classes as template arguments is nicer
> than having namespaces, because classes can be templated themselves.
> For instance, consider
>
>         template<class C, class V= dense_polynomial_variant<C> >
>         class dense_polynomial { ... };
>
> In this example, the default underlying arithmetic for dense_polynomial<C>
> naturally depends on C.
>
> An advantage of namespaces is that they may be extended a posteriori.
> However, in view what has been said above, we do not really want to do this:
> strict application of the philosophy would rather mean that the variant
> (class or namespace) should only be used in order to customize
> the implementation in consideration (dense_polynomial in the above example).
> Indeed, V corresponds to mathematical or implementation hypothesis
> under which the implementation of a new function or class is valid.
> Such hypothesis should never be extended: instead a new hypothesis class
> should be created.
>   
The "slight" difference between the implementation of algebrix (based on 
namespace) and
algebramix is that in the first case, the container type  is a parameter 
type, whereas in the second package
the representation is attached to the interface class. For instance 
univariate polynomials = array of coefficients +  size.
In the first case, this would be implemented as a container parameter 
R  (which could be specialized to [ array of coeff +size]
with the basic accessors/ iterators). The choice of the correct function 
can be done by namespaces
(open) or explicit call through the Variants (we can use variants 
parametrized by the container).
In the first case, an interest is that the code can be reused more easily.
For instance, if one want to manipulate polynomials in the bernstein 
basis on a interval [a,b]
the container will be = [array of coeff. + size + a,b]
and the operations on this representation will be linked to the 
bernstein basic operations at the interface class level.
(In the other approach a specific class has to be rewritten).
This gives a way to use general functions on all dense polynomials, 
whereas in the other case,
helpers have to be developed, case by case.

What about multivariate polynomials or sparse structures: should the 
type of the monomials be attached to the class ?
even if the algebra/code on the sparse structure is the same ?
Also, how to deal with the zoology of matrices (symmetric, upper, lower 
triangular, orthogonal, ...) ?
for codes which are generic for dense matrices?
> Of course, carrying out this strategy is somewhat verbose (thank you C++).
> Mathemagix style factorizations:
>
>         forall (C: Ring, Pol: Polynomial_ring C) {
>            foo1 ...
>            foo2 ...
>         }
>
> can be mimicked using the usual #define #undef cruft:
>
>         #define TMPL template<class Pol>
>         #define C (typename Pol::scalar_type)
>
>         TMPL foo1 ...
>         TMPL foo2 ...
>
>         #undef C
>         #undef TMPL
>
> or by regrouping things in a class with static member functions.
>
> Summarizing, what about the following general practice:
>
>   1) For types whose implementations depend on lower layers,
>      use a variant class to select particular implementations
>      of the lower layers.
>
>   2) Never use variant classes to factor different implementations
>      of the same kind of object; rather give the different implementations
>      different names and template over the implementation when using
>      them in an even higher level.
>
> Another benefit of this practice might be that it is actually quite
> straightforward to upgrade an existing code for, say, polynomials
> to work with other implementations: it suffices to systematically
> use templates and replace polynomial<C> by a template class Pol.
>
> Best wishes, Joris
>   
The path that you propose requires the current class names to be more 
explicit:

vector -> dense_vector
matrix -> dense_matrix
structured_matrix
sparse_matrix  (with many possible formats)
...
polynomial -> dense_univariate_ polynomial
bezier_univariate_polynomial
horner_univariate_polynomial (representation in the Horner basis of a 
given polynomial)
sparse_univariate polynomial
sparse_multivariate_polynomial
...
Are this changes Ok ? Which  naming conventions to choose ? ...

Best regards, Bernard