% $Id: design.tex,v 1.1.1.6 2005/01/26 13:42:23 nthiery Exp $

\section{The design of the \texttt{MuPAD-Combinat} package}

\Mnode{design}
\label{design}

\subsection{The development platform}

The choice of the development platform was a difficult question; at
some point, after long discussions, we had to take a decision. We try
to present here why we were led to choose \mupad{}. The
table~\ref{table.platform.rating} summarizes how we evaluated several
platforms with respect to our specifications for this project (see the
\Mhref[index,specifications]{specifications}).  This evaluation is
based on our personal daily experience, in our field, with our
programming and computing habits; we have tried to be as objective as
possible, but we do not claim any kind of scientific rigor nor
universality. We will also be glad to update it, if some readers
explain to us why their favorite system has been underrated.

\makeatletter
\newskip\@bigflushglue \@bigflushglue = -100pt plus 1fil

\def\bigcenter{\trivlist \bigcentering\item\relax}
\def\bigcentering{\let\\\@centercr\rightskip\@bigflushglue%
\leftskip\@bigflushglue
\parindent\z@\parfillskip\z@skip}
\def\endbigcenter{\endtrivlist}
\makeatother

\begin{sidewaystable}%
\small
\begin{bigcenter}
  \def\s{@{\,\vline\,}}
\begin{tabular}{@{\vline\,}c*{12}{@{\,\vline\,}c}@{\,\vline}}
  \hline
  Aspect & Relevance &
    \caml& \cpp& \gap & \java& \magma & \maple & \mupad
                                                    & \mathematica
                                                         & \maxima
							      & \axiom
							      & \aldor
                                                                    \\\hline
  License & B &
    A    & A   & A    & A    & C      & E      & B  & E  & A  & A & A  \\\hline
  Community & C &
    B    & A   & C    & A    & C      & B      & C  & B  & D  & D & D  \\\hline
  Potential user base & B &
    C    & C   & B    & C    & B      & A      & B  & A  & C  & C & C  \\\hline
  Long term availability & B &
    A    & A   & B    & A    & B      & A      & B  & A  & ?  & ? & ?  \\\hline
  Long term compatibility & A &
    A    & C   & ?    & A    & B      & E      & A  & B  & ?  & C & C  \\\hline
  Support & A &
    A    & A   & A    & A    & B      & D      & A  & B  & ?  & D & D  \\\hline
  Development cycle & A &
    B    & E   & ?    & ?    & ?      & C      & B  & ?  & ?  & D & D  \\\hline
  Ease of use for beginners & B &
    C    & D   & B    & C    & B      & A      & A  & A  & ?  & C & C  \\\hline
  Functional programming & A &
    A    & C   & B    & C    & ?      & D      & B  & ?  & ?  & C & C  \\\hline
  Typing/Object Oriented & A &
    A    & A   & B    & A    & C      & E      & B  & ?  & F  & A & A  \\\hline
  Overloading & B &
    ?    & A   & A    & D    & ?      & F      & B  & ?  & ?  & A & A  \\\hline
  Term rewriting & D &
    ?    & ?   & ?    & ?    & ?      & ?      & C  & A  & ?  & ? & ?  \\\hline
  Interactive usage & B &
    C    & C   & A    & C    & A      & A      & A  & A  & A  & A & A  \\\hline
  Compilation & C &
    A    & A   & A    & A    & B      & F      & F  & ?  & ?  & B & A  \\\hline
  Programming tools & A &
    A    & A   & B    & A    & ?      & D      & B  & ?  & ?  & B & A  \\\hline
  Computer algebra tools & A &
    C    & C   & C    & D    & B      & B      & B  & ?  & ?  & B & C  \\\hline
  Linear algebra tools & B &
    ?    & B   & B    & ?    & B      & B      & C  & ?  & ?  & C & ?   \\\hline
  Group theory tools & C &
    ?    & ?   & A    & ?    & A      & E      & E  & ?  & ?  & C & C  \\\hline
  Inter Process Com. & B &
    A    & A   & B    & A    & ?      & C      & C  & ?  & ?  & D & C  \\\hline
  Dynamic modules & B &
    A    & A   & A    & A    & F      & B      & B  & ?  & ?  & D & A  \\\hline
  Overall &&
    C    & C   & B    & D    & C      & D      & B  & ?  & ?  & B & B  \\\hline
\end{tabular}
\end{bigcenter}

\caption{Rating of some platforms we investigated with respect to
  different aspects we judged of importance. Each rating ranges from F
  (worst) to A (best), ? meaning a lack of information. For example,
  \caml{} is a full featured
  functional programing language and is rated A, whereas \mupad{} does
  not support at all compilation of user code, and is rated F.
  For general purpose programming language, we tried to take into
  account open source or freely available libraries to build upon.
  This includes for example \focref{} for \caml{}, or \synapsref{} and
  \linboxref{} for \cpp{}.}
\label{table.platform.rating}
\end{sidewaystable}

A short summary is in order. The development cycle is too long in
programming languages like \cppref{}, and there are not yet strong
enough computer algebra libraries for our needs. We would have
preferred to use a computer algebra system that was already widely
used, in particular in the algebraic combinatorics community, like the
commercial system \mapleref{} or \mathematicaref{}. However, the
programming language, the license conditions, and the long term
maintenance of \maple{} are terrible. Technically, \mathematica{}
looks better, but does not seem to fit our technical requirements
concerning object oriented features and overloading. Not going for the
academic system \gapref{} was a tough choice, as they have an
excellent open source development model and a clean programming
language. What kept us from choosing it is that general computer
algebra tools are missing.  Still we want to collaborate closely with
the \gap{} team, for example for using \gap{} as a group theory
computation server. \axiomref{} was not yet open-source at that time,
and even today, its future seems still to be uncertain; aside from
this, its language and design, together with the existence of the
\aldorref{} compiler, makes it an excellent candidate; in fact, many
ideas in the design of \mupad{}, like domains and categories, are
borrowed from \axiom{}. \aldor{} is a computer algebra system in its
own, but the computer algebra libraries are in construction. Again,
its type system makes \aldor{} as one of the most interesting systems
for our goals.  Finally, \magmaref{} was quite appealing, in
particular for its impressive efficiency.  However, we are afraid that
their closed development model, with a lot of the work being done in
\texttt{C} in the kernel, will not scale in the long run. Also it does
not offer us the programming flexibility that we need.

Only the future will tell us if our choice of \mupad{} was a right
one. So far, after three years of development, the programming
language has proved to fit well our needs, and the collaboration with
the \mupad{} group has worked out beautifully. Just to give a figure, in
2003, 400 out of the 1400 messages on the \texttt{mupad-combinat-devel}
mailing list originated from the \mupad{} team; this included code
reviews, explanations on the internals of \mupad{}, tips and tricks
for optimizations, discussions on common developments that deserved to
be synchronized, and so on.

Having our code deeply integrated in the \mupad{} library is of great
benefit for us. First, we gain in visibility, since our code is widely
distributed.  Second, it enforces high standards for code stability
and documentation; though this is quite time consuming for us and
imposes deadlines which are not necessarily compatible with our
research schedule, this is essential for attracting new users. Also,
our code and documentation are tested every night on the \mupad{}
servers as part of their standard test-suite. In this way, any
incompatibilities are instantly detected. In particular, the \mupad{}
developers have to take our project into account before deciding any
backward incompatible change that could break our code; if the change
is still done, they are forced to either fix our code directly, or at
least to provide us with timely information on how to do it
ourselves. This is essential for the long term maintenance of our
project. Reciprocally, some of our suggestions have had an essential
impact in their decision for several small but critical kernel
changes; this helped us to write cleaner and more efficient code.

Altogether, there is essentially one single aspect we are not happy
with for the long term survival of \mupadcombinat{}, namely that
\mupad{} is not open-source. Still, they have kept so far their
promises to remain relatively open. The situation has even improved
recently with \mupad{} Light being completely free (gratis) for
research and education. They also have promised to release the code
source of the library under a well known open-source license, some
day.

\subsection{The development model}

Looking back at previous projects shows that the choice of a proper
development model is essential for the long term survival of a
project. In fact, the first months of the development of this project
have been spent in large parts discussing this issue and trying out
different solutions.

First, it is important that the \emph{core} development be done by
several persons with permanent positions to avoid the
left-for-industry dreaded effect. Of course, this does not preclude
students from writing libraries around this core, on the contrary!
Also, code sharing code is time-consuming: seen over a short period,
providing a polished implementation of a routine, with documentation
and tests, represents much more work than just going for a
write-once-use-once implementation. There, it is essential to reach
quickly the critical mass of developers so that altogether they
actually save time by participating to the project and benefiting from
other's code.

In this spirit of sharing code and attracting new users and
developers, going for an open source license was an obvious choice.
Having an open platform would have helped as well. What is less
obvious is how much the standard open source development models apply
to the algebraic combinatorics community. The main problem is that
this community is relatively small with not so many potential
participants. The fact that participating in such a software requires
the use of several standard open source management tools (cvs, make,
Wiki) which are essential to automatize things may be seen as an
additional difficulty. We try our best to leverage those difficulties,
and the \href{http://sourceforge.net} support center is of great help
for that. But still, some of those tools have a steep learning curve.
Also, the structure of the package, which as been designed with
genericity and extensibility in mind, is clear and systematic, but not
so simple, and relies on non trivial programming concepts (generators,
inheritance, ...).

As a consequence of this, and despite much documentation, advertising,
and teaching efforts, we have not been as successful as we would have
desired at attracting new users and developers. In particular, we have
not yet quite reached the required critical mass. Another aspect of
this is that the project is not yet as international and
lab-independent as it ought to be to ensure its political
independence.  It seems that, so far, getting new developers started
still requires a regular physical contact.

\subsection{Naming conventions}

\subsubsection*{Long names versus abbreviations}

The convention for library, domain and function names is to use long
names that are as meaningful and close to the English spelling as
possible: e.g. \Mex{partitions} instead of \Mex{PART},
\Mex{FreeQuasiSymmetricFunctions} instead of \Mex{FQSym}, etc. In
particular, abbreviations should be avoided, except in extreme cases
where the short name is really well established (say Lex instead of
Lexicographic). Here are the motivations for this convention:
\begin{itemize}
\item This is the convention used in \mupad;
\item Since \mupad{} $\geq$ 2.0.0 has automatic name completion, long
  names are not too much of a pain to type in.
\item This is helpful for users coming from other areas;
\item The user can easily define shorthands (via aliases or
  assignments) for the functions he uses a lot. Actually this is quite
  reasonable: a working session starts by the definition of the
  notations and shorthands, exactly as any mathematical document. Tip: in our
  daily usage, we have one file per topic we do research on, with a
  set of appropriate shorthands. Typically, when working on the
  Loday-Ronco Algebra, we use shortcut \Mex{BT} for
  \Mex{combinat::binaryTrees}, \Mex{Perm} for
  \Mex{combinat::permutations}, \Mex{LRA} for the Loday-Ronco Algebra,
  and so on.
\item Given the variety of areas that intersect on combinatorial
  algebras, there are too many risks of conflicts with short names;
  the user needs to be able to choose his own notations given the
  context and the set of objects that are to be manipulated at the
  same time.
\end{itemize}

\subsubsection*{Case of names}

We follow the capitalization rules of the \mupad{} coding standard,
which are quite similar to \texttt{Java} or \texttt{C++} rules:
\begin{itemize}
\item When a name is composed of several parts, the later parts are
  separated by capitalizing the first letter of the following parts.
  For example, ``from reduced word'' yields \Mex{fromReducedWord}.
  Using underscores to separate parts (as in \Mex{from_reduced_word})
  is not recommended; some names in our code do not follow this
  recommendation yet.
\item Names of options and local variables of domains are capitalized
  (\Mex{MinLength}, \Mex{R}).
\item Names of normal variables, of functions, and of methods are not
  capitalized (for example \Mex{combinat::partitions::type},
  \Mex{Dom::Matrix::transpose},
  \Mex{combinat::permutations::fromReducedWord}).
\item A few internal variables are fully capitalized to alert the user
  that they have a very specific behavior, and should be used with
  care (\Mex{DOM}, \Mex{TEXTWIDTH}).
\item Badly enough neither the \mupadcombinat{} package, nor the
  \mupad{} standard library do respect any clearly defined rule for
  domain names. As a rule of thumb, the name of a domain is not
  capitalized when the domain is a library (\Mex{combinat},
  \Mex{combinat::generators}, and is capitalized when it is a true
  domain which contains elements (\Mex{Series}, \Mex{Dom::Rational},
  \Mex{examples::SymmetricFunctions}). The later case includes for
  example all the domains in \Mex{Dom}, \Mex{examples},
  \Mex{experimental}. On the other hand, the names of combinatorial
  classes in \Mex{combinat} are not (yet) capitalized
  (\Mex{combinat::partitions}). Other exceptions to this rule
  typically appear when the name of a library comes from initials
  (\Mex{IPC}) or from a person name.
  
  This lack of coherency is a burden for both users and developers,
  and we hope to fix it at some point in the future, when the \mupad{}
  library will undergo a similar naming convention cleanup.
\end{itemize}

\subsubsection*{Composite names}

When the name of a library, domain or function is composed of several
parts, and those parts are also used in other names, it may be
worthwhile to order those parts from the most general to the most
specific. For example, we used the name
\Mex{combinat::integerVectorsWeighted} instead of the more natural
name \Mex{combinat::weightedIntegerVectors}. The advantage is that all
the domains dealing with integer vectors start with the same prefix,
which is particularly practical with respect to automatic completion.
This is also coherent with the hierarchy
\Mex{library::sublibrary::subsublibrary}. Another typical case is when
several functions return a similar result but under different forms;
the function that is the most useful or natural gets the short name,
and the names of the other functions, are suffixed with the "type"\ of
the result (\Mex{words::inversions}/\Mex{words::inversionsList}, ...).
We also used this rule of thumb for the names of the free module
methods
\begin{itemize}
\item \Mex{mult}/\Mex{multBasis}/\Mex{mult2}/\Mex{mult2Basis},
\item \Mex{straighten}/\Mex{straightenBasis},
\item \Mex{print}/\Mex{printTerm}/\Mex{printMonomial}/\Mex{printBasis}.
\end{itemize}

\subsection{Representing combinatorial objects and classes}

\Mnode{designCombinatorialClasses}

The notion of \emph{combinatorial object} is best described by some
examples: a partition, a binary tree, a permutation, a graph, a
Feynman diagram, a Dyck word, and other similar discrete objects are
all combinatorial objects.

A \emph{combinatorial class} is a (countable) set of related
combinatorial objects (e.g. the set of all partitions, the set of all
binary trees, the set of all standard permutations), on which a
\emph{size} function is defined (e.g. the size of partition is the sum
$n$ of its parts; the size of an integer vector consist of a pair
$(n,k)$ of integers: its sum $n$ and its length $k$; the size of a
tree is the number of its nodes). Typically, the fibers of the size
function define natural finite subsets of the class that one wants to
count, enumerate, and so on (e.g.  counting all the partitions of
$n=4$, listing all the integer vectors of sum $5$ and length $3$); we
say ``typically'', because there are some cases where it is practical
to use this framework even if the subsets are only countable. In many
cases optional restrictions can be added to define smaller subsets of
the class to be counted/enumerated/..., (e.g. the partitions of $4$ of
length at most $4$). In some combinatorial classes (e.g. the class of
the permutations of $5$), the size function may be degenerated and
have only one non trivial fiber.

\subsubsection*{Representing combinatorial objects}

A combinatorial object may belong to several combinatorial classes
simultaneously.  For example, the list \Mex{[4,3,2,1]} may be
interpreted as a partition, a permutation, an integer vector, a
composition.  This is reflected in \mupad{} by our convention that a
combinatorial object is not necessarily strongly typed by the
combinatorial class(es) to which it belongs. An object has a unique
domain: it corresponds to the data structure of the object and can be
obtained by the command \Mup{domtype}. On the other hand, it may be of
different types: they correspond to the different semantics that can
be attached to the object, and they can be tested with \Mup{testtype}.

For example, \Mex{[3,4,2,1]} belongs to the \mupad{} domain of lists,
\Mup{DOM_LIST}; it is simultaneously a list of positive integers
(\Mupc{Type::ListOf}{Type::PosInt}), a word, a permutation, etc, while
it is not a partition:
\begin{Mexin}
domtype ([3, 4, 2, 1]);
\end{Mexin}
\begin{Mexout}
                           DOM_LIST
\end{Mexout}
\begin{Mexin}
testtype([3, 4, 2, 1], Type::ListOf(Type::PosInt)),
testtype([3, 4, 2, 1], combinat::words),
testtype([3, 4, 2, 1], combinat::compositions),
testtype([3, 4, 2, 1], combinat::integerVectors),
testtype([3, 4, 2, 1], combinat::permutations),
testtype([3, 4, 2, 1], combinat::partitions)
\end{Mexin}
\begin{Mexout}
              TRUE, TRUE, TRUE, TRUE, TRUE, FALSE
\end{Mexout}
In the \mupad{} terminology, the domains like
\Mup{combinat::compositions} are called \emph{facade domains}; they do
not really contain elements of their own.

On the other hand, some combinatorial objects, such as trees, require
a specific data structure; these objects are strongly typed, that is
their domain is the class itself.
% Alessandra: ????
This has, among others, the advantage that they are pretty printed by
the system:
\begin{Mexin}
t := combinat::labelledBinaryTrees([1, [2], [3]]);
domtype(t);
testtype(t, combinat::labelledBinaryTrees);
\end{Mexin}
\begin{Mexout}
                               1
                              / \
                              2 3

                 combinat::labelledBinaryTrees

                             TRUE
\end{Mexout}

This choice of not systematically using strong typing for
combinatorial classes is not an obvious one, and there is no clear cut
criteria for deciding whether a given combinatorial class should use
strong typing or not. On the one hand, strong typing allows for
object-oriented techniques and overloading. On the other hand, having
to cope with all the conversions (a partition is also a composition,
...) can be quite a burden for both the user and the programmer;
indeed, choosing which implicit conversions to provide is not an easy
task, given the overwhelming number of natural bijections. Finally,
with the current \mupad{} language, there is a small memory and time
overhead with strong typing; this can be considered as a misfeature of
\mupad{} though.

Aside from the data structure criteria, another reasonable criteria is
whether the combinatorial class has natural ``algebraic operations''.
This is why we currently have both a facade domain
\Mup{combinat::permutations} for general permutations seen as words,
and a real domain \Mup{Dom::SymmetricGroup} for standard permutations
seen as elements of the symmetric group. Actually, it could be
reasonable to have a real domain \Mup{Dom::Permutation}, and have
\Mup{Dom::SymmetricGroup} and \Mup{Dom::PermutationGroup} be facade
domains for \Mup{Dom::Permutation}. This is still under discussion,
and comments are welcome.

% Alessandra: I prefer the actual choice, if it must include the product.

\subsubsection*{Representing combinatorial classes}

Combinatorial classes for which we want to do counting, generation, or
other manipulations are represented by \mupad{} domains, like
\Mup{combinat::partitions} or \Mup{combinat::binaryTrees}. Note that,
in many cases, those domains are just \emph{facade domains} and do not
really contain elements: as we said above, the domain of a partition,
or of a permutation, is really \Mup{DOM_LIST}. Those domains also
define a \mupad{} type;
% FIXME: isA instead of type
by convention, it is named like
\Mex{combinat::partitions::type}, and can be tested with:
\begin{Mexin}
testtype([3, 2, 2, 1], combinat::partitions)
\end{Mexin}
\begin{Mexout}
                             TRUE
\end{Mexout}
\begin{sloppypar}
  Simpler combinatorial classes, which we only want to use for type
  checking, are just represented by \mupad{} types. This is typically
  used for subsets of other combinatorial classes. For example, the
  standard permutations form a subset of all permutations, and are
  represented by the type \Mup{combinat::permutations::typeStandard}.
  We are not quite happy with this naming convention; however, for
  better localization, we really would like to keep the types defining
  a subset of a domain inside this domain. Another option was to use
  subdomains even in this case. But domains are quite special (and
  expensive?)  objects in \mupad{}: they have a reference effect, they
  cannot be deleted, etc. So, we feel that this would be overkill,
  especially for parametrized types like
  \Mupc{PermutationOf}{[a,b,c,d]}.
\end{sloppypar}

\begin{sloppypar}
  Another related situation: quite often, we have a function that
  returns a collection $C$ of related objects, usually as a list.
  Think of \Mupc{combinat::words::shuffle}{[1,2,3],[a,b,c]} which
  returns a list of words. Or think of the inverse of a function that
  is not at all injective like
  \Mup{combinat::permutations::fromCycleType} (it returns all the
  permutations having a given cycle type). In such cases, we often
  want to do some more involved things, like having a generator for
  the elements of $C$, or being able to count them without actually
  generating them. Then, it is natural to consider $C$ as a
  combinatorial class, and to represent it by a \mupad{} domain. This
  gives a unified interface to all the standard functions for
  counting, generating, ...:
\end{sloppypar}
\begin{itemize}
\item \Mupc{combinat::words::shuffle::count}{word1,word2}
\item \Mupc{combinat::words::shuffle::list}{word1,word2}
\item \Mupc{combinat::words::shuffle::generator}{word1,word2}
\end{itemize}

As a nice side effect, the standard alias from \Mex{new} to \Mex{list}
allows one to use the natural syntax
\Mupc{combinat::words::shuffle}{word1,word2} to obtain the collection
$C$. So, switching from a simple function which returns $C$ to a
domain for the elements of $C$ is transparent for the user.  Usually,
such a domain will be a subdomain of an existing domain (here
\Mup{combinat::words::shuffle} is a subdomain of
\Mup{combinat::words}).

\subsubsection*{Combinatorial classes and categories}

\begin{sloppypar}
  A domain which represents a combinatorial class belongs to the
  category \Mup{Cat::CombinatorialClass}. Such a domain should
  implement at least \Mup{generator} or \Mup{list}. This category also
  provides naming conventions for usual functions like \Mex{count},
  \Mex{first}, \Mex{next}, \Mex{random}, \Mex{unrank}, ...  The
  implementation of those functions is not explicitly required by the
  category \Mup{Cat::CombinatorialClass}: depending on the specific
  combinatorial class sometimes they are not yet implemented,
  sometimes there exists no efficient algorithm, or sometimes they
  simply do not really make sense.
\end{sloppypar}
In the future, we may think about refining
\Mup{Cat::CombinatorialClass} into subcategories that describe which
of those functions are available (for example, the category of
combinatorial class which provide an \Mex{unrank} function). So far,
the benefits coming from such refinements do not seem to justify the
overhead in the complexity of the category hierarchy.

Also, all of this is not really specific to combinatorial classes.  We
could imagine generalizing this to any kinds of collections of
objects, and mimic the category hierarchy of, e.g. \texttt{Aldor}.
%Comment a class is not necessarily a finite collection; the sections of this class are.

\begin{sloppypar}
  By convention, all the subcategories of
  \Mup{Cat::CombinatorialClass} have a name of the form
  \Mex{Cat::XxxClass}. Right now, we have two sub categories of
  \Mup{Cat::CombinatorialClass}:
\end{sloppypar}
\begin{itemize}
\item \Mup{Cat::decomposableClass}
\item \Mup{Cat::integerListsLexClass}
\end{itemize}
\begin{sloppypar}
  Those two categories are purely technical; they respectively provide
  wrappers around the generic domains
  % Alessandra: ?wrappers
  \Mup{combinat::decomposableObjects} and
  \Mup{combinat::integerListsLexTools}, and allow one to factor out some
  routine code. For example, \Mup{combinat::partitions},
  \Mup{combinat::integerVectors}, and \Mup{combinat::compositions} are
  in the category \Mup{Cat::integerListsLexClass}, which takes care of
  the parsing of common options.
\end{sloppypar}

\subsubsection*{Further naming comments}

%% Naming conventions for bijections and more generally functions between
%% combinatorial classes: put the function in the source class
%% (\Mex{myClass::toMyOtherClass}), with possibly an alias in the target
%% class (\Mex{myOtherClass::fromMyClass}), and in any case a reference
%% to it in the documentation of both structure. Examples:
%% \Mup{combinat::dyckWords::toNonCrossingPartition}.

%% When there are several bijections, or when the bijection is not
%% obviously canonical, the name of the bijection can be postfixed:
%% myClass::toMyOtherClassBijectionName. When the result of the function
%% has a standard mathematical name, it is preferable to use it instead
%% of the name of the target class. Examples:
%% \Mup{combinat::partitions::conjugate},
%% \Mup{combinat::permutations::cycles}.

%% In some cases, it can be acceptable to only put the function in the
%% target class, typically when the function is not a bijection between
%% the two full classes.
%% \begin{itemize}
%% \item \Mex{combinat::dyckWords::fromTableau}: Dyck words are in
%%   bijection with a subset of tableaux (namely tableaux with two rows);
%%   so, \Mex{combinat::tableaux::toDyckWord} would only be partially
%%   defined;
%% \item \Mup{combinat::permutations::fromCycles}: there is no
%%   \mupad{} domain (yet) for the combinatorial class of permutations in
%%   cycle notation.
%% \end{itemize}

%% TODO: naming conventions for subclasses (check the wiki)

\begin{sloppypar}
  The names of the domains \Mup{combinat::integerListsLexTools} and
  \Mup{combinat::decomposableObjects} are quite different. This
  reflects the fact that those two domains do not play the same role.
  \Mup{combinat::decomposableObjects} is a parametrized domain whose
  instantiations represent combinatorial classes, whereas
  \Mup{combinat::integerListsLexTools} essentially is a collection of
  tools with a scarce interface, geared toward speed and internal use.
\end{sloppypar}

\begin{sloppypar}
  The name \Mex{Cat::integerListsLex} is too general, since this
  category contains only the combinatorial classes described using
  length, bound, and slope constraints. For example, the elements of
  \Mup{combinat::permutations} are integer lists and are naturally
  ordered lexicographically; however this combinatorial class is
  \emph{not} in \Mex{Cat::integerListsLex}. Badly enough, we have not
  found a better name that would not be too long. Unless someone comes
  up with a clever suggestion we will stick to this name.
\end{sloppypar}

We use \Mup{Next} for the name of the method that computes the next
element in a combinatorial class. This is not coherent with
\Mex{first}, \Mex{last} and with the general convention that a method
name start by a lowercase letter. Badly enough, \Mex{next} is a
reserved keyword, and we cannot use it as method name in \mupad.

\subsection{Representing combinatorial algebras}

\Mnode{designCombinatorialAlgebras}

\subsubsection*{What is a combinatorial algebra after all?}

Let us start by a precise definition for the term \emph{combinatorial
  algebra} that we have used so far in a rather informal way.

%So far, we have used the term \emph{combinatorial algebra} in a rather
%informal way. In the following, we will need a more precise definition
%that we give now.

Given a combinatorial class $C$, and a ring $R$, one can define the
\emph{free module $F$ with basis indexed by $C$ over the ring $R$}; an
element of $F$ is a formal finite linear combination of elements of
$C$ with coefficients in $R$. Alternatively, an element of $F$ can be
interpreted as a function from $C$ to $R$ with finite \emph{support};
that is a function which is zero except on finitely many elements of
the basis $C$.

For example, here is an element of the free module with basis indexed
by partitions, over $\mathbb{Q}$:
\begin{displaymath}
  x:=4 [3,2,1] + 3 [2,1,1] + 1/4 [1,1,1,1]\,.
\end{displaymath}

Polynomials are another typical example of free modules, and we extend
the usual definitions used for polynomials. The \emph{coefficient} of
$[1,1,1,1]$ in $x$ is $1/4$; we call the partition $[3,2,1]$, seen as
an element of $F$, a \emph{term}; $4 [3,2,1]$ is a \emph{monomial};
finally, the \emph{support} of $x$ is the set of the partitions with
non-zero coefficients, that is $\{[3,2,1], [2,1,1],[1,1,1,1]\}$.

By \emph{combinatorial algebra} we mean such a free module, together
with some extra algebraic operations (a product, coproduct, antipode)
which makes it an algebra, a bialgebra, or a Hopf algebra. Those
operations are typically defined by linearity on the basis.

With this definition, we have distinguished a special basis of the
combinatorial algebra. Most of the time, a combinatorial algebra (like
the algebra of symmetric functions) will actually have several
interesting basis (Schur functions, power-sum functions, ...), all of
them indexed by $C$. The underlying free module remains the same, but
the operations will vary accordingly. Changing from one basis to the
other is one of the fundamental operations.

\subsubsection*{Why use strong typing?}

% Alessandra: what is strong typing ?

Traditionally in computer algebra systems (say with \ssf, \ace{} or
\muec), symmetric functions have been represented by symbolic
expressions:
\begin{Mexin}
p[2]*p[1];
muEC::SYMF::Top(p[2]*p[1]);
muEC::SYMF::Tos(p[2]*p[1])
\end{Mexin}
\begin{Mexout}
                           p[1] p[2]

                            p[2, 1]

                       s[3] - s[1, 1, 1]
\end{Mexout}
This is also the approach used for polynomials, and more generally for
Ore-algebras in \maple. This has several advantages:
\begin{itemize}
\item This is simple, and requires (at first) very little programming
  and computer algebra knowledge from the user;
\item The syntax for constructing elements is terse;
\item All the standard tools for manipulating expressions such as
  \Mex{factor}, \Mex{expand}, \Mex{simplify},~\dots are instantly
  available;
\item One can easily manipulate factored expressions which mix
  different basis.
\end{itemize}

However, this approach has also serious drawbacks:
\begin{itemize}
\item The syntax for manipulating expanded expressions is lengthy;
  one cannot simply write (a*b);
\item The tools for manipulating expressions do not know what they
  manipulate, and may do invalid operations; for example, symbolic
  expressions are usually considered as commutative, which may yield
  incorrect results when computing with non commutative symmetric
  functions. Staying on the safe side may require a fair amount of
  knowledge about the system from the user, which is not acceptable
  for beginners.
\item Programming a function which deals with elements of the free
  module requires a fair amount of work just to parse the expressions
  on input (75\% of the code in the symmetric functions package in ACE
  is related to this); one option to reduce the amount of code, is to
  first convert the input into an internal representation before
  manipulating it; however this means that the elements are converted
  back and forth all the time, which has a non-negligible computation
  cost.
\item The data structure is not hidden, and there is no room left for
  optimization;
\item There is a risk of conflict if two combinatorial algebras use
  the same name for their basis (e.g. all generalizations of the
  symmetric functions have some kind of elementary functions, which one
  would like to display as \Mex{e}). In particular, one cannot mix two
  algebras that use the same basis name in the same expression.
\item One cannot easily choose the coefficient ring (think of
  symmetric functions with coefficients in a finite field, free
  symmetric functions with coefficients being themselves symmetric
  functions).
\item One cannot easily hide and factor out the complexity, and let a
  user define his own algebra in a very short amount of code.
\end{itemize}

Altogether, this approach is fine when there are very few
combinatorial algebras; however it does not scale to a dozen
predefined algebras (that's our short-term goal) plus myriads of
user-defined algebras. In practice, this is one of the main reasons
why the \ace{} project stalled when defining many new algebras became
a must.

It was time for a complete redesign and rewrite of the package.  We
will see that using strong typing allows for circumventing all those
drawbacks, without loosing too much of the advantages. The choice of
switching to \mupad{} was largely influenced by the strong integration
of their domains/axioms/category mechanism in their system, that
allows for strong typing, and object-oriented techniques.

\subsubsection*{Representing free modules}

The first thing to do is to choose the internal data structure to
store an element of a free module. There are different possible
implementations without a clear cut advantage of one over the others
(as a parallel, in \texttt{C++} there exists two implementations of
association tables: \texttt{map} using sorted lists and
\texttt{hash\_map} using hash tables). We provide several of them:

\paragraph*{\Mex{Dom::FreeModuleTable(R, Basis)}}

An element \Mex{x} is stored as an association table
(\Mup{DOM_TABLE}). For example, here is the internal representation of
an element \Mex{x}:
\begin{Mexin}
F := Dom::FreeModuleTable(Dom::Rational, combinat::partitions):
x := 4*F([3, 2, 1]) + 3*F([2, 1, 1]) + 1/4*F([1, 1, 1, 1]);
extop(x)
\end{Mexin}
\begin{Mexout}
     4 B([3, 2, 1]) + 3 B([2, 1, 1]) + 1/4 B([1, 1, 1, 1])

                     table(
                       [1, 1, 1, 1] = 1/4,
                       [2, 1, 1] = 3,
                       [3, 2, 1] = 4
                     )
\end{Mexout}
Since any \mupad{} object can be used as index of a table, there is no
restriction on the basis elements. Accessing the coefficient of a term
is constant time.

\paragraph*{\Mex{Dom::FreeModulePoly(R, Basis)}}

The kernel polynomial objects of \mupad{} (domain \Mup{DOM_POLY}) are
stored in a sparse non-recursive way using sorted lists of monomials
with a fixed number of variables. If one forgets about the product,
this provides a sparse data structure which is both compact in memory
and very fast for linear operations.  Typically, the \mupad{} sparse
matrices (domain \Mup{Dom::Matrix}, former \Mex{Dom::SparseMatrix})
use univariate polynomials internally as internal representation for
sparse column vectors.

Similarly, an element \Mex{x} of \Mex{Dom::FreeModulePoly(R,
  Basis)} is stored using a polynomial:
\begin{Mexin}
(F := Dom::FreeModulePoly(Dom::Rational, combinat::partitions); 
x := 4*F([3, 2, 1]) + 3*F([2, 1, 1]) + 1/4*F([1, 1, 1, 1]));
extop(x)
\end{Mexin}
\begin{Mexout}
     1/4 B([1, 1, 1, 1]) + 3 B([2, 1, 1]) + 4 B([3, 2, 1])

                     3           2
      poly(1/4 `#_X_`  + 3 `#_X_`  + 4 `#_X_`, [`#_X_`])
\end{Mexout}
To achieve this, one needs to be able to represent an element of the basis
using an exponent vector (an integer, or a fixed-length list of
integers). This is trivial when the basis readily consists of fixed
length lists of integers (integer vectors, standard permutations of a
given $n$, \dots). Otherwise, the user may provide a pair of functions
\Mex{rank} and \Mex{unrank} that does the conversions. By default, the
system creates a dummy pair of such functions: the \Mex{rank} function
associate in turn the numbers \Mex{1,2,3,\Mseq{}} to each new object
it encounters. For example, the rank of \Mex{[3,2,1]}, \Mex{[2,1,1]},
and \Mex{[1,1,1,1]} above are respectively \Mex{1},\Mex{2}, and
\Mex{3}, that corresponds to the order in which the corresponding
elements of \Mex{F} have been created.

This representation is very fast for linear operations. Furthermore,
if univariate polynomials are used with the variable \Mex{_X} (this is
the default), the data structure coincides exactly with the one used
by \Mup{Dom::Matrix}. This allows for zero-cost conversions to and
from sparse vectors, for doing linear algebra.

Accessing the coefficient of a term in an element \Mex{x} is
logarithmic in the number of terms of \Mex{x} (in the multivariate
case, with \mupad{} < 3.0.0 this is linear instead of logarithmic).

Ranking and unranking is only done for conversions, and computing
products. In practice, the overhead with the dummy implementation
seems to be negligible, and largely compensated by the fact that most
operations deal with integers.

\paragraph*{\Mex{Dom::FreeModuleList(R, Basis)}}

Thanks to Stefan Wehmeier, (Univ. Paderborn) and Werner M. Seiler
(Univ.  Karlsruhe), this was mostly already implemented in the
\mupad{} library under the name \Mex{Dom::FreeModule} since 1997. An
element is represented by a sorted list of terms. For example, here is
the representation of the element \Mex{x} above: \Mex{[[4, [3, 2, 1]],
  [3, [2, 1, 1]], [1/4, [1, 1, 1, 1]]]}.

Obviously, there needs to be an order on the basis elements
(\Mex{Basis} should be a \Mup{Cat::OrderedSet}). Accessing a leading
or trailing term is constant-time; accessing the coefficient of a
given term in an element \Mex{x} is logarithmic in the number of terms
of \Mex{x}.

All those implementations are in the category
\Mup{Cat::ModuleWithBasis} which defines a unified interface. So, one
can change the underlying implementation at any time. Unless you have
a specific reason to choose one of the implementations, just use the
default implementation \Mex{Dom::FreeModule(R, Basis)}.


\subsubsection*{Representing combinatorial algebras on a given basis}

Once the underlying linear structure is implemented, it is very easy to
construct functions on a free module by linearity / bilinearity /
multilinearity on the basis (see the examples) using the utilities
from \Mup{operators}. So, implementing operations like products,
coproducts, antipodes usually boils down to implement the underlying
combinatorics. Note that we do not have yet a general construction for
the tensor product of two free modules \Mex{F1} and \Mex{F2}, but you
can emulate one by hand by building a free module whose basis elements
are pairs of basis elements of \Mex{F1} and \Mex{F2}.

Altogether, this allows to implement a domain \Mex{F} for the elements
of a combinatorial algebra expanded on a given basis (e.g. the domain
of symmetric functions expanded on the Schur functions, or the domain
of symmetric functions expanded on the power-sum functions). The
product of two elements of \Mex{F} is automatically expanded on the
basis, and belongs again to \Mex{F}. Such a domain belongs to the
category \Mex{Cat::AlgebraWithBasis} (later on, there will be
categories such as \Mex{Cat::BialgebraWithBasis},
\Mex{Cat::HopfAlgebraWithBasis}).

% Draw the category hierarchy

\subsubsection*{Representing combinatorial algebras with several bases}

\Mnode{designOverloading}

A combinatorial algebra with several natural bases will be represented by
several domains. Converting from one basis to another is an
essential operation, and it is strongly desirable to be able to mix in
the same expression elements that are expressed in different basis.
This can now be achieved through overloading and the definition of
appropriate implicit conversions (see the demonstration).

Developing the underlying tools that allow to do this seamlessly
required a fair amount of work. Indeed, one parameter overloading in
\mupad{} works fine by delegating the work to the corresponding method
of the parameter; on the other hand, the plain system essentially does
not help much for multi-parameter overloading, which has to be
carefully done by hand in each and every library (think about
computing a product where the operands are in turn a symmetric
function on the p basis, an integer, a symmetric function on the e
basis, and a rational number). So we had to specify and implement a
new mechanism that takes care of implicit conversions, and
multi-parameters overloading.  We essentially mimicked ideas taken
from the GAP system~\cite{GAP4}, as well as from the static
overloading mechanisms of standard languages like \texttt{C++}. The
main difficulty was to choose the right level of generality, so as to
make the system powerful enough, yet simple, safe, and sound. Our
choices were largely influenced by our practical experience with the
kind of computations we have in mind.  This new overloading mechanism
is being discussed for integration and systematic use in the \mupad{}
library.  We are not at all specialists of this sensible subject, so
comments and suggestions about this are very welcome. For details,
see:

\url{http://mupad-combinat.sf.net/doc/html/operators/overloaded.html}

This mechanism is currently pretty rudimentary and limited. However,
we have been playing with it intensively, and have done some really
hairy stuff based on it. The semantic has proven so far to be safe,
sound and robust, while really much more practical and powerful than
the plain overloading mechanism. The time overhead is reasonable; if
it became an issue, the specifications leave quite some room for
optimisations, in particular by inclusion in the \mupad{} kernel.

When defining combinatorial algebras with several bases, we organize
the code in a fairly standardized way, which takes care of various
technical issues such as initialization or parameterization of the
algebra by the coefficient ring. We urge the interested reader to
check out the code in the examples library, and in particular:

\url{http://mupad-combinat.sf.net/lib/EXAMPLES/SymmetricFunctions.mu}

\subsubsection*{Conversions to and from expressions}

Having strong safeguards is essential so that a beginner can run
computations with confidence. However, one of our motto is that the
system should not try to be too clever, and in particular should
always leave a way for the user to take over the control (and the
responsibilities!).  Indeed, there always are situations where the
user knows that a given operation, invalid in general, happens to be
perfectly legal in the current context. Most of the time, this can be
taken care of by systematically providing conversions to and from
symbolic expressions that the user may manipulate at his convenience.
However, there is no clearly-defined representation of elements of
non-commutative algebras using symbolic expressions, because \mupad{}
(as most other systems) assumes that the latter are commutative. Just
to give a flavor of the issue: which commutation rules should be
applied automatically by the system in the expression
\Mex{2*e[1]*q*3*f[3]}?  Suggestions are very welcome here.

\subsubsection*{Compact notations}

Throughout the tutorial, we have used fairly lengthy notations for
constructing elements of combinatorial algebras. For example, to
define the first symmetric power-sum, we wrote \Mex{S::p([1])}. This
is fine in a tutorial when safety is at a premium, but in everyday's
use, having terse notations is highly desirable. We are currently
experimenting several tricks that allow for simultaneously using
\Mex{p} to represent the domain of symmetric functions in the \Mex{p}
basis, and \Mex{p[1]} for creating the first symmetric power-sum,
while still being able to convert symmetric functions into symbolic
expressions containing literals such as \Mex{p[1]}. As soon as we will
have more experience with this, we will describe the recommended
practice in the Tips and Tricks section of the reference manual.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
