=Paper=
{{Paper
|id=Vol-1804/paper-01
|storemode=property
|title=CoCoA and CoCoALib: Fast Prototyping and Flexible C++ Library for Computations in Commutative Algebra
|pdfUrl=https://ceur-ws.org/Vol-1804/paper-01.pdf
|volume=Vol-1804
|authors=John Abbott,Anna Maria Bigatti
|dblpUrl=https://dblp.org/rec/conf/synasc/AbbottB16
}}
==CoCoA and CoCoALib: Fast Prototyping and Flexible C++ Library for Computations in Commutative Algebra==
https://ceur-ws.org/Vol-1804/paper-01.pdf
CoCoA and CoCoALib:
Fast Prototyping and Flexible C++ Library
for Computations in Commutative Algebra
John Abbott Anna Maria Bigatti
Institut für Mathematik Dipartimento di Matematica
Universität Kassel Università degli Studi di Genova, Italy
Kassel, Germany http://www.dima.unige.it/∼bigatti
http://www.dima.unige.it/∼abbott
Abstract—The CoCoA project began in 1987, and conducts (with two closely related applications being the interactive
research into Computational Commutative Algebra (from which system and the compute server). This initial decision, together
its name comes) with particular emphasis on Gröbner bases with the desire to help the software prosper, has many im-
of ideals in multivariate polynomial rings, and related areas. A
major output of the project is the CoCoA software, including the plications: e.g. designing a particularly clean interface for all
CoCoA-5 interactive system and the CoCoALib C++ library. The functions with comprehensive documentation. This cleanliness
software is open-source (GPL v.3), and under continual, active makes it easy to integrate CoCoALib into other software in a
development. We give a summary of the features of the software trouble-free manner.
likely to be relevant to the SC-Square community.
Many computer algebra systems have a two-tier structure:
I. I NTRODUCTION a compiled kernel with interpreter, and an external library
CoCoA-5 is a well-established Computer Algebra System of interpretable code for more advanced functions. Our aim
specialized in operations on polynomial ideals, and a number with CoCoALib is different: we plan to have all functions
of allied operations (e.g. factorization, and linear algebra). implemented directly in the C++ library so that all features
It offers a dedicated, mathematician-friendly programming are available to programs which link to CoCoALib.
language, and numerous functions covering many aspects of CoCoALib reports errors using C++ exceptions, while the
Commutative Algebra. There is a strong emphasis on both library itself is exception-safe and (largely) thread-safe. The
rigour and ease of use. For details see [1]. current source code follows the C++03 standard; a passage to
The mathematical core of the software is CoCoALib. It is the C++11 standard is planned for the near future (and this
an open source C++ software library which has been designed should enable the code to become fully thread-safe).
to be user-friendly, facilitating integration with other software.
The library is fully documented, and also comes with about A. Library Design
100 illustrative example programs (since it is often quicker We want CoCoALib to be a desirable software library, so it
to copy and modify existing working code than write it from must be easy to use, reliable, robust and fast. Unfortunately,
scratch). For details see [2]. achieving all these features together is not always possible,
There is also a prototype “CoCoA server” giving access so there are occasional compromises. One guiding principle is
to many functions via a remote-procedure-call connection. that we want no nasty surprises.
Currently, communications to and from the server use an Here are the main features of the design of CoCoALib:
OpenMath-like syntax. A more sophisticated “remote session”
• it is well-documented, free and open source C++ code
communication model is envisaged, which will reduce overall
(under the GPL v.3 licence);
transmission costs.
• the design is inspired by, and respects, the underlying
The CoCoA software is interesting to SC-square because
mathematical structures;
it includes a well-documented, open source C++ library of-
• the source code is clean and portable;
fering a good implementation of Gröbner bases, polynomial
• the user function interface is natural for mathematicians,
factorization, etc. The interactive system is well-suited to rapid
and easy to memorize;
prototyping, while the server offers possibilities for looser
• execution speed is good with robust error detection.
integration.
Our design of CoCoALib aims to make it easy to write
II. T HE S OFTWARE L IBRARY C O C OAL IB correct programs, and difficult to write incorrect ones or ones
A crucial aspect of the CoCoA software is that it was which produce “nasty surprises”. While trying to follow this
designed from the outset to be an open-source software library guideline we encountered some delicate aspects of the design:
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: E. Ábrahám, J. Davenport, P. Fontaine, (eds.): Proceedings of the 1st Workshop on Satisfiability Checking and Symbolic Computation (SC2 ),
Timisoara, Romania, 02-07-2016, published at http://ceur-ws.org
• precise definition of a function’s domain (e.g. what result Mayer-Vietoris trees associated to monomial ideals. A sig-
should IsPrime(-2) give? And IsPrime(0)?) nificant aspect of this contribution is that the author worked
• a choice between absolute mathematical correctness or completely independently relying entirely on the documenta-
decent computational speed (and a remote chance of a tion of CoCoALib — thus confirming the quality of the docu-
wrong answer) mentation. His work has encouraged us to develop specialized,
In general, CoCoALib handles limit cases properly. The efficient handling for monomial ideals (see [7]).
domain of each CoCoALib function is described in the docu- A more recent contribution comes from M. Albert, who
mentation; for instance IsPrime throws an exception if the implemented an algorithm for computing Janet Bases of ideals
argument is not strictly positive — our reasoning is that it in polynomial rings. Once a Janet Basis has been obtained,
is unusual to want to test the primality of zero or a negative many ideal invariants can readily be determined ([4], [5]).
number, so it is likely that the routine which called IsPrime Work is still under way to further expand this contribution.
has already made a mistake, so it is better to report it “as soon
C. Combining with External Libraries
as possible”. CoCoALib offers the programmer the choice
between absolute correctness or probable correctness and good We have combined some of the features of various external
speed, e.g. IsPrime and IsProbPrime. libraries into CoCoALib. An important step in each case is
An example of design: Finding a library interface which is the “translation” of a mathematical value from its CoCoALib
easy to learn and use, mathematically correct, but also efficient representation to that of the foreign library, and vice versa.
at run-time often requires a delicate balance of compromise. To make it easier to do this CoCoALib offers operations for
We cite here one example from CoCoALib where the solution destructuring the various data-structures it operates upon.
is untraditional but successful. One aspect of combining libraries which requires careful
CoCoALib uses continued fractions internally in various attention is any global initialization the libraries perform, for
algorithms. A continued fraction is an expression of the form: instance specifying the memory manager for the common un-
1 derlying library GMP. CoCoALib addresses this by requiring
a0 + explicit initialization of its globals; there are various options,
a1 + a + 1 1
2 a3 +··· including one for specifying a memory manager for GMP.
where a0 is an integer, and a1 , a2 , . . . are positive integers. The first library we combined with CoCoALib is Frobby
Every rational number has a finite continued fraction which, (see [8]) which is specialized for operations on monomial ide-
for compactness, is often represented as a list of integers als. The experience also helped us improve the interfacibility
[a0 , a1 , a2 , . . . , as ]. of CoCoALib.
The most natural implementation in CoCoALib would sim- The most advanced integration we have achieved so far is
ply compute this list. But in many applications only the first with the Normaliz library (see [6]) for computing with affine
few ak are needed, and computing the entire list is needlessly monoids or rational cones. This is part of a closer collaboration
costly. So the CoCoALib implementation produces an iterator which is described in more detail in [3]. In this particular case,
(a basic concept well-known in object-oriented programming) a new data-structure (called cone) was added to CoCoALib
which produces the values of the ak one at a time. to contain the type of value which Normaliz computes with.
B. Extending CoCoALib The most recent integration was with GFanLib (see [9])
Naturally most of the source code in CoCoALib was written which is a C++ software library for computing Gröbner fans
by us, but the design of the library (and its openness) was and tropical varieties. The experience gained from the earlier
chosen to facilitate and encourage “outsiders” to contribute. integrations made this a swift and painless operation.
We distinguish two categories of contribution: code writ- There is also an experimental connection to some of the
ten specifically to become part of CoCoALib, and stand- functions of GSL (GNU Scientific Library [10]). This is an
alone code written without considering its integration into interesting challenge because the interface has to handle two
CoCoALib. contrasting viewpoints: the exact world of CoCoALib, and the
Specific Direct Contributions to CoCoALib: The first out- approximate (i.e. floating-point) world of GSL.
side contribution came from M. Caboara, who wrote the
code for computing Gröbner bases and related operations III. T HE I NTERACTIVE S YSTEM C O C OA-5
while CoCoALib was still quite young. At that stage the The CoCoA-5 system replaces the old CoCoA-4 system
detailed implementation of CoCoALib was still quite fluid, whose heritage can be traced back at least to 1989. For
and a number of pretty radical changes in the underlying several reasons CoCoA-5 is a completely new implementation,
data-structures were still to occur; yet despite these upheavals whose design was developed under the precept that it be
Caboara’s implementation of Buchberger’s algorithm required “as backward-compatible as (reasonably) possible” while also
virtually no changes, thus confirming the good modularity and eliminating the limitations inherent in the older system.
stability of the CoCoALib interface design. All incarnations of the CoCoA system have been noted
Another significant outside contribution came from for their approachability especially for “computer-phobic”
E. Saenz-de-Cabezon, who wrote the code for computing mathematicians, and CoCoA-5 is no exception. Indeed, the
aim was to make CoCoA-5 even friendlier than its forebears: package. The package indicates which of those functions
a notable example is the importance given to generating it will export; the rest are internal auxiliary functions.
genuinely helpful error messages. • The last way is to write the new functions in C++, add
Here is a typical error message from CoCoA-5; note that the them to CoCoALib, and then make them “visible” to
error was actually signalled by CoCoALib as a C++ exception, CoCoA-5. This last operation is normally quite straight-
which the interpreter caught, and then “translated” into human- forward thanks to an ingenious combination of C++
readable form: inheritance and C macros (see [3]). Indeed we use exactly
this mechanism for making standard CoCoALib functions
# X := 99 + FloorSqrt(-99);
accessible from an interactive CoCoA-5 session.
--> ERROR: Value must be non-negative
--> X := 99 + FloorSqrt(-99); While many CoCoA-5 functions just call CoCoALib di-
--> ˆˆˆˆˆˆˆˆˆˆˆˆˆˆ rectly, there are still a few packages containing functions
which have yet to be migrated into CoCoALib.
Note how the subexpression which actually triggered the error
is indicated by “up-arrows”, a most helpful feature in more IV. T HE C O C OAS ERVER
complicated expressions. Included in the CoCoA software distribution is the Co-
Compared to earlier versions CoCoA-5 has a number of sig- CoAServer, currently still a prototype which provides a
nificant new abilities, notably including algebraic extensions client/server mechanism for accessing the capabilities of Co-
and ring homomorphisms. The latter can be used to “move CoALib. It uses an OpenMath-like language to accept com-
rigorously” values from one ring to another. putation requests, and then send the result back. An early
use of the protype was to grant access to CoCoALib features
A. The Language in CoCoALib and in CoCoA-5 from CoCoA-4.7 while the new CoCoA-5 system was under
When designing CoCoALib and CoCoA-5 we envisaged development.
researchers and advanced users wishing to tackle hard compu- The advantages of computing via a “server” are that it
tations initially developing a prototype implementation in the can be called by any other “client” software (which has an
convenient interpreted environment of CoCoA-5, and when the OpenMath interface), and it avoids the delicate intricacies of
code is working properly, they translate it into C++ (using Co- close integration occuring in monolithic compilation.
CoALib functions) for better performance. Consequently, one Currently the server remains in prototype form as resources
of the joint design goals of CoCoALib and the new CoCoA-5 are directed, for the time being, at CoCoALib and CoCoA-5.
language was to make it easy to convert CoCoA-5 code into
C++ code built upon CoCoALib. That said, CoCoALib offers V. C ONCLUSION
a richer programming environment, but also demands greater The CoCoA software offers access to advanced capabilities
discipline from the programmer. For instance, CoCoA-5 does in computational commutative algebra via three interfaces: an
not have a special type for a “power-product” (it is just a interactive system, a C++ library, and a prototype server. This
polynomial with 1 term and coefficient 1), whereas CoCoALib variety allows users to choose whichever approach suits them
has a special class, PPMonoidElem, which represents power- best.
products. Thus a good translation into C++ of a CoCoA-
R EFERENCES
5 program manipulating power-products will require some
effort, but the reward should be a decisive gain in speed. [1] J. Abbott, A.M. Bigatti, G. Lagorio, CoCoA-5: a system for do-
ing Computations in Commutative Algebra. Available from website
To facilitate the conversion into C++ we have, whenever http://cocoa.dima.unige.it/cocoalib
possible, used the same function names in both CoCoA-5 [2] J. Abbott and A.M. Bigatti, CoCoALib: a C++ library for do-
and CoCoALib. We have also preferred traditional “func- ing Computations in Commutative Algebra. Available from website
http://cocoa.dima.unige.it/cocoalib
tional” syntax in CoCoALib over object oriented “method [3] J. Abbott, A.M. Bigatti, C. Söger, Integration of libnormaliz in CoCoALib
dispatch” syntax, e.g. in CoCoALib we define deg(f) rather and CoCoA 5 Proc. ICMS 2014, Springer LNCS 8592, pp. 647–653,
than f.deg(). 2014.
[4] M. Albert, Janet Bases in CoCoA; bachelor thesis, Institut für Mathe-
matik, Universität Kassel, 2011.
B. Extending CoCoA-5 [5] M. Albert, Computing Minimal Free Resolutions of Polynomial Ideals
The capabilities of CoCoALib and CoCoA-5 are continually with Pommaret Bases master thesis, Institut für Mathematik, Universität
Kassel, 2013.
expanding as the software evolves. So our design deliberately [6] W. Bruns, B. Ichim, T. Römer, C. Söger Normaliz. Available from
makes it easy to add new functions to CoCoA-5. In fact, there http://www.mathematik.uni-osnabrueck.de/normaliz
are several ways of extending CoCoA-5. [7] O. Fernàndez-Ramos, E. Garcı́a-Llorente, E. Sáenz-de-Cabezón A mono-
mial week (Spanish) Gac. R. Soc. Mat. Esp. 13, No. 3, 515–524, 2010.
• The easiest way to add a new function is to write it in [8] B.H. Roune, Frobby. Available from website
CoCoA-5 Language. Anyone can create new CoCoA-5 http://www.broune.com/frobby
[9] A.N. Jensen, GFan. Available from website
functions this way, and for instance give them to students http://home.math.au.dk/jensen/software/gfan/gfan
or colleagues. [10] M. Galassi et al., GNU Scientific Library Reference Manual (3rd
• Often there are several functions to be added together; Ed.), ISBN 0954612078. GSL complete package available from website
http://www.gnu.org/software/gsl
in this case it is best to place them all in a CoCoA-5