[PPL-devel] Parma Polyhedra Library 0.5
bagnara at cs.unipr.it
Mon Apr 28 09:00:39 CEST 2003
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 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
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++ 188.8.131.52 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 [184.108.40.206.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
has been removed.
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
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
mailto:bagnara at cs.unipr.it
More information about the PPL-devel