Skip to Content

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}

Name and Credits

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’ (]{#Library_Name}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]{#Papers_To_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,
}

Licensing

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: Alternative licensing schemes are available from BUGSENG . The same company offers commercial support of the PPL (whatever is the license under which the library is being used).

Installation

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.

See the file README.configure  for details.

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:]{#Prolog_Not_Found}

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

Documentation

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.]{#Complexity}

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}

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.]{#Why_Using_Cplusplus}

Q: What’s next? What are you working on?

A: We are focused on improvements of memory utilization and facilities to support the analysis of floating point and machine integer computations. We also want to add serialization for all PPL objects.]{#New_Features}

Q: When will next release of PPL be?

A: When it is ready.

Last updated on