[PPL-announce] Parma Polyhedra Library 0.5

[Roberto Bagnara]

We are happy to announce the availability of PPL 0.5, the latest
release of the Parma Polyhedra Library.

This innovative release is packed with new features.  We now have the
most precise widening operator on Earth.  Still concerning widenings,
there is now support for "widening with tokens": a new and original
improvement over the traditional widening delay technique.  Several
new operations on polyhedra have been added.  The C and Prolog
interfaces have been extended and the Prolog interface now supports
six different Prolog systems.  Many efficiency, usability and
portability improvements have been made and, of course, a number of
bugs have been fixed.

Even though there is no compatibility of any kind with previous
versions of the library, we believe that the interfaces are
stabilizing and will not change much in the future.  Starting from
this release, the library provides macros and functions that allow the
client applications to adapt to different versions of the library.

For more information, visit the PPL web site at

       http://www.cs.unipr.it/ppl/

The PPL development team:

      Roberto Bagnara  <bagnara at cs.unipr.it>
      Patricia M. Hill <hill at comp.leeds.ac.uk>
      Elisa Ricci      <ericci at cs.unipr.it>
      Enea Zaffanella  <zaffanella at cs.unipr.it>


New and Changed Features
========================

o  New methods Polyhedron::BHRZ03_widening_assign() and
    Polyhedron::BHRZ03_limited_extrapolation_assign().  The BHRZ03 widening
    is a novel widening that is always more precise than the one, by now
    standard, we call H79.

o  The novel "widening with tokens" technique improves on the good old
    widening delay technique by refraining from widening only when
    necessary.  Precision is thus increased still guaranteeing
    convergence.  All widening operators can now be supplied with an
    optional argument, recording the number of available tokens, which
    is decremented when tokens are used.

o  Two new methods have been defined that compute the image of
    a polyhedron under an affine relation. The first method,
    Polyhedron::generalized_affine_image(var, relsym, expr, denom),
    generalizes the classical Polyhedron::affine_image() method by allowing
    `relsym' to denote any of the relations <, <=, =, >=, >.
    The second method, Polyhedron::generalized_affine_image(lhs, relsym, rhs),
    is a variant where an arbitrary linear expression `lhs' is allowed to
    occur on the left-hand side of the affine relation.

o  New constructors to build polyhedra from read-only constraint and
    generator systems: C_Polyhedron(const ConSys&),
    C_Polyhedron(const GenSys&), NNC_Polyhedron(const ConSys&), and
    NNC_Polyhedron(const GenSys&).  In the C interface the functions
    taking non-const arguments named ppl_new_<T>_from_<S> have been
    renamed ppl_new_<T>_recycle_<S>, where <T> is either "C" or "NNC",
    and <S> is either "ConSys" or "GenSys".  The old names have been
    given to the new const functions.

o  New function LinExpression& operator*=(LinExpression&, const Integer&)
    to multiply (in place) an expression by a scalar.

o  The methods Polyhedron::check_empty() and Polyhedron::check_universe()
    have been renamed is_empty() and is_universe(), respectively.

o  New method bool Polyhedron::is_disjoint_from(const Polyhedron& y)
    returning true if and only `*this' and `y' are disjoint.

o  New methods bool Polyhedron::add_constraint_and_minimize(const
    Constraint&) and bool Polyhedron::add_generator_and_minimize(const
    Generator&) to add a constraint or a generator and minimizing the
    result at the same time.

o  New method: template <typename PartialFunction>
    void Polyhedron::map_dimensions(const PartialFunction&).
    This allows to rename the dimensions of a polyhedron according
    to a partial function mapping dimensions to dimensions.

o  New function LinExpression operator+(const LinExpression&): previously
    an expressions like `+x2-x3-x4 <= 0' could not constitute valid syntax
    for a constraint.

o  New type `dimension_type': an unsigned integral type for representing
    space dimensions.

o  New function dimension_type max_space_dimension():
    returns the maximum space dimension this library can handle.

o  New function dimension_type not_a_dimension():
    returns a value that does not designate a valid dimension.

o  The method Polyhedron::add_dimensions_and_constraints(ConSys&)
    has gone.  A similar functionality is provided by the new method
    Polyhedron::concatenate_assign(const Polyhedron&).  The same change
    has, of course, been performed on all the PPL interfaces.

o  New macros PPL_VERSION_MAJOR, PPL_VERSION_MINOR, PPL_VERSION_REVISION,
    and PPL_VERSION_BETA allow the client application to adapt to different
    versions of the library.

o  New function const char* version() returns a character string
    containing the PPL version.

o  New function const char* banner() returns a character string
    containing information about the PPL version, the licensing,
    the lack of any warranty whatsoever, the C++ compiler used
    to build the library, where to report bugs and where to look
    for further information.

o  The Prolog interface now supports also Ciao Prolog and XSB.

o  The C and Prolog interfaces have been extended so as to make more of
    the library's functionality available to Prolog and C users.

o  Timeout computation facilities have been added to the Prolog interfaces:
    new predicates ppl_set_timeout_exception_atom/1,
    ppl_timeout_exception_atom/1, ppl_set_timeout/1, ppl_reset_timeout/0.

o  Many efficiency improvements have been achieved.  Part of these have
    been obtained by increasing the degree of "lazyness" of the library.

o  Many portability and standard-conformance improvements: the library
    can now be compiled with GNU g++, Intel C++ Compiler 7.0 for Linux,
    and Comeau C/C++ 4.3.0.1 Compiler Front-End; the library has also
    been tested on a variety of platforms.

o  The functions
    Polyhedron::operator<=(const Polyhedron&, const Polyhedron&),
    Polyhedron::operator>=(const Polyhedron&, const Polyhedron&),
    Polyhedron::operator<(const Polyhedron&, const Polyhedron&), and
    Polyhedron::operator>(const Polyhedron&, const Polyhedron&)
    have been removed.
    The methods Polyhedron::contains(const Polyhedron&) and
    Polyhedron::strictly_contains(const Polyhedron&) provide
    the same functionality.

o  The method Polyhedron::limited_H79_widening_assign() has been renamed
    Polyhedron::limited_H79_extrapolation_assign().  From now on, the name
    `widening' is reserved for operators that come with a convergence
    guarantee (i.e., with the ability of turning infinite chains to finite
    ones).  Upper bound operators without such a guarantee contain the word
    `extrapolation' in their name.

o  The renamed method Polyhedron::limited_H79_extrapolation_assign()
    takes the constraint system argument by const reference (in the
    old Polyhedron::limited_H79_widening_assign() that argument was
    passed by non-const reference).

o  We now require GMP 4.1.2 or higher.

o  In conformance with the C++ standard [17.4.3.1.2], in all the
    identifiers exported by the C interface, any occurrence
    of "__" (double underscore) has been replaced by "_" (underscore).

o  Added a parameter to Polyhedron::shrink_bounding_box(): this specifies
    the complexity class of the algorithm to be used.

o  All the input/output operators have been confined into namespace
    Parma_Polyhedra_Library::IO_Operators.  This way they do not conflict
    with the operators the user might want to define.

o  The operator Constraint operator>>(const Constraint&, unsigned int)
    has been removed.

o  The method
    Polyhedron::poly_difference_assign_and_minimize(const Polyhedron&)
    has been removed.



Bugfixes
========

o  Fixed a bug in operator-=(LinExpression&, const LinExpression&)
    whereby we computed a wrong result in some circumstances.

o  Fixed a bug in method Polyhedron::minimized_constraints() that,
    under some circumstances, could cause a wrong result or a program
    crash.

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it