Frequently Asked Questions about the PPL

Please, let us know if you think that our answers are unclear or not to the point.

• Name and Credits
  • What is the name of the library?
  • If I use the library for doing something that results in a publication of any kind, which papers on the PPL should I cite?
• Licensing
  • Are you going to release the PPL under the GNU Lesser General Public License (LGPL)?
  • What if I cannot/do not want to use the PPL under the GNU General Public License (GPL)?
• Installation
  • The configuration procedure says that I don't have GMP installed, but I do have it!
  • The configuration procedure says that I don't have XYZZY-Prolog installed, but I do have it!
• Documentation
  • I get a TeX error message when trying to build the documentation from scratch. How can I fix it?
• Performance
  • What is the worst-case computational complexity of the operations provided by the PPL?
  • How fast is the PPL?
• Development
  • Why are you developing the PPL in C++?
  • What's next? What are you working on?
  • When will next release of PPL be?

Q: What is the name of the library?
A: It is `Parma Polyhedra Library', spelled exactly as indicated and possibly abbreviated with the acronym `PPL'. In particular, the name of the library is neither `Parma' (which is, instead, the name of the nice town in Italy where the PPL was initially created), nor `Parma Polyhedral Library' (where the extra ell after `Polyhedra' simply should not be there), nor `Parma PolyLib' (PolyLib is another library), nor `Parma Polyhedron Library' (geez... some people never learn). The authors of the library thank you in advance for calling the library with its correct name.

Q: If I use the library for doing something that results in a publication of any kind, which papers on the PPL should I cite?
A: Please cite this paper. You can use the following BibTeX entry:

@Article{BagnaraHZ08SCP,
  Author = "R. Bagnara and P. M. Hill and E. Zaffanella",
  Title = "The {Parma Polyhedra Library}: Toward a Complete Set of Numerical
           Abstractions for the Analysis and Verification
           of Hardware and Software Systems",
  Journal = "Science of Computer Programming",
  Volume = 72,
  Number = "1--2",
  Pages = "3--21",
  Year = 2008,
}

Q: Are you going to release the PPL under the GNU Lesser General Public License (LGPL)?
A: No.

Q: What if I cannot/do not want to use the PPL under the GNU General Public License (GPL)?
A: If you are prepared to support our research and development work, we can find a solution. The rationale behind our licensing policy is that we are only interested to work with and for those that are willing to contribute back. There are two ways to contribute back:

1. by joining our community (the free software community), using the library under the GPL, in which case you will contribute back with your source code if/when you decide to release it; or
2. by using the library under an alternative licensing scheme, in which case you will contribute back by funding our research (post-doc positions, PhD studentships, equipment, travel money, ...).

Q: The configuration procedure says that I don't have GMP installed, but I do have it!
A: You may have a version of GMP installed on your system, but:

1. it may be too old and/or
2. it may be installed into a nonstandard place and/or
3. it may have been built with the C++ interface disabled and/or
4. additional compiler/linker options you may have specified via configure options or environment variables are invalid on the platform you use.

Q: The configuration procedure says that I don't have X-Prolog installed, but I do have it!
A: You may have a version of X-Prolog installed on your system, but the configuration procedure is not finding it. The situation changes depending on what Prolog system X-Prolog is:

Ciao Prolog

Make sure the command ciao is in your PATH and that the C/C++ compilers can find the header file ciao_prolog.h. In order to ensure the latter, you can configure the library by invoking the configure script setting the CPPFLAGS environment variable. For example:

  /path/to/ppl-x.y/configure ... CPPFLAGS=-I/usr/local/lib/ciao/ciao-1.13/include
  

GNU Prolog

Make sure the command gprolog is in your PATH and that the C/C++ compilers can find the header file gprolog.h. In order to ensure the latter, you can configure the library by invoking the configure script setting the CPPFLAGS environment variable. For example:

  /path/to/ppl-x.y/configure ... CPPFLAGS=-I/usr/lib64/gprolog-1.3.0/include
  

SWI-Prolog

Make sure either the command pl or swipl or swi-prolog are in your PATH. This should be enough. If not, then you have found a bug: please report it to ppl-devel@cs.unipr.it.

SICStus Prolog

Make sure the command sicstus is in your PATH. This should be enough. If not, then you have found a bug: please report it to ppl-devel@cs.unipr.it.

XSB

Make sure the command xsb is in your PATH. This should be enough. If not, then you have found a bug: please report it to ppl-devel@cs.unipr.it.

YAP

Make sure the command yap is in your PATH and that the C/C++ compilers can find the header file Yap/c_interface.h. In order to ensure the latter, you can configure the library by invoking the configure script setting the CPPFLAGS environment variable. For example:

  /path/to/ppl-x.y/configure ... CPPFLAGS=-I/usr/local/include
  

Q: I get a TeX error message when trying to build the documentation. How can I fix it?
A: See the discussion near to the end of the distributed file doc/README.doc, also reported here.

Performance

Q: What is the worst-case computational complexity of the operations provided by the PPL?
A: It depends on the numerical abstraction and the operation under consideration. In the following discussion and unless otherwise stated, the complexities are expressed in terms of the space dimension.

Closed and not-necessarily closed polyhedra

Most important operations on these abstractions use exponential time and space in the worst case. The implementation, in fact, is based on the double description method: a polyhedron is represented by means of a system of constraints and/or a system of generators. For some operations (such as intersection, adding constraints, computing the relation between a polyhedron and a generator) only the constraints are required; for some others (such as convex polyhedral hull, adding generators, removal or mapping of space dimensions, computing the relation between a polyhedron and a constraint, finiteness/boundedness and emptiness checks, time-elapse) only the generators are required; for a few of them (inclusion and equality tests, widenings) both constraints and generators are required. The time of obtaining the generators of the polyhedra starting from the constraints is, in the worst case, exponential (and we cannot do better than this [KBB⁺06]). By duality, the same holds for the conversion from generators to constraints. Since both the constraints and the generators are represented explicitly, the complexity in space of these operations is also exponential in the worst case. Of course, the implementation is very careful to compute generators from constraints and constraints from generators only when absolutely necessary. For example, assume that the application performs a sequence of constraint additions to a polyhedron. The first such operation may cause the constraints of the polyhedron to be computed, in case they were not already available, incurring an exponential cost in the worst case. However, all subsequent constraint additions will only have an amortized linear cost. Some operations handle special cases in an optimized way. For example, the operation that maps space dimensions handles the case where the mapping function is a permutation in a special way that never causes a constraints-generators or generators-constraints conversion. More specifically, if the mapping function is a permutation:

• if the constraint system is up to date, the polyhedron is mapped in linear time in the number of constraints;
• if the generator system is up to date, the polyhedron is mapped in linear time in the number of generators;
• if both the constraint and the generator systems are up to date, both are mapped as above.

Notice that a polyhedron may well have an exponential number of constraints and/or generators, so this optimization does not change the worst-case complexity. Finally, operations that are intended to provide support for throttling the computational complexity of polyhedra, allow to trade precision for efficiency. This is the case for the constructors of boxes, bounded-difference and octagonal shapes from polyhedra, where the callers can specify a complexity parameter. When this parameter is set to polynomial complexity a cheaper computation will deliver a possibly approximated result. When the parameter is set to simplex complexity or any complexity the result will be exact, but the cost is, in the worst case, exponential both in time and space, with simplex complexity possibly performing better in practice.

Grids

The grid operations take polynomial time and space. As for polyhedra, the implementation is based on a double description method: a grid is represented by means of a system of congruences and/or a system of grid generators; one or both of these needed for the different operations. The time needed to obtain the grid generators (resp., congruences) starting from the congruences (resp., grid generators) is, in the worst case, quadratic on the space dimension and linear on the number of congruences (resp., grid generators). Of course, as for polyhedra, the implementation is very careful to compute grid generators from congruences and congruences from grid generators only when absolutely necessary. More information about the operations and their complexity can be found in [BDH⁺07]).

Bounded-difference and octagonal shapes

Closure by entailment, which takes cubic time in the worst case, is the most complex operation on these abstractions, which have a quadratic space requirement. As always, it should be considered that closure is not always needed and that the implementation is very careful not to employ it unnecessarily.

Boxes

The most complex operations over this abstractions, which store one interval for each space dimension, have linear time complexity.

Q: How fast is the PPL in practice?
A: It compares very well to other libraries. In 2005 we collected some experimental results on the efficiency of the component that converts systems of constraint to systems of generators and the other way around. As explained above this is the most expensive polyhedra manipulation primitive.

Development

Q: Why are you developing the PPL in C++?
A: Because everyone must use the programming language he/she deserves. And we deserve C++. This does not limit the freedom of the PPL users: they can choose among the C, C++, Java, OCaml and Prolog interfaces.

Q: What's next? What are you working on?
A: For PPL 0.11 we are adding new operations and numerical abstractions that allow to approximate the result of bounded integer computations. If all goes well, PPL 0.12 will be focused on facilities to support the analysis of floating point computations. For the same release we hope to add serialization for all PPL objects.

Q: When will next release of PPL be?
A: It is difficult to say. We hope to release PPL 0.11 in May/June 2009.

[Page last updated on June 02, 2009, 08:47:26.]