Parma Polyhedra Library 0.5
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
The PPL development team:
Roberto Bagnara bagnara@cs.unipr.it Patricia M. Hill hill@comp.leeds.ac.uk Elisa Ricci ericci@cs.unipr.it Enea Zaffanella zaffanella@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.
participants (1)
-
Roberto Bagnara