FAQ

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

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' (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,
}

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:

  • it may be too old and/or
  • it may be installed into a nonstandard place and/or
  • it may have been built with the C++ interface disabled and/or
  • 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:

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.

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: The list of desiderata is quite long. We currently focus on the needs of the semantic analysis engines of ECLAIR as well as on the needs of our customers and users.

Q: When will next release of PPL be?
A: It is difficult to say. In general, we will release as the need arises.

Contributing

Q: How can I contribute?
A: There are several ways you can contribute to the success of the PPL: please, at least be kind; to be even kinder to us, you could contribute your personal time and/or your CPU time. All contributions will be greatly appreciated and properly recognized in an appropriate way.

Be Kind

Doing what is considered The Right Thing (TM) in the various communities we belong to (scientific community: give credit, cite; free software community: release code; human community: provide feedback, be grateful) is what we ask of you.

By Citing Wherever Appropriate

If you use the PPL in a research project that gives rise to some kind of publication, please do acknowledge the PPL and cite one or more appropriate papers. If you are unsure about what to cite, you can consult our little PPL papers road map.

By Distributing Your Software

Most of the things we know about software development are largely due to the chances we have had in obtaining, playing with and modifying good quality software written by others. Moreover, most of the tools routinely used in producing the PPL have been made available by the free software community, to which we belong. By distributing the PPL as free software and by taking the occasion, during the development work, of contributing to the improvement of the entire tool chain, we are able to give something back to this community.

Now about you. We hope you find the PPL useful in some way and, if you write an application using it, we wish to encourage you to release it. Do not be shy: it will never be polished enough. Do not be modest: even if you think that your application will not interest many people, we are interested in it. We routinely use (and need more) applications based on the PPL for the purposes of regression testing and performance monitoring. To summarize: if you don't care about free software or its community, it doesn't matter; if you don't have a potential user community, it doesn't matter; if you don't have a nice packaging or documentation, it doesn't matter; by releasing your code anyway, you will do a personal favor to the people who provided the PPL.

By Providing Feedback or Just Saying Hello

Feedback is always useful, whether it positive or negative. Whatever you are doing with the PPL, we are glad to know about it. If you are disappointed or satisfied or you have suggestions about the library or its documentation or this web site, just let us know. Even if you think you have nothing particularly useful to say, just knowing that you have been doing something with the PPL will give us extra motivation to continue our work.

Contribute Time

Time is our biggest problem: if you can spare some time, then you have something important to contribute to the project.

By Giving a Little

With Beta Testing
We need beta testers. You can help by downloading, compiling, running the test suite of the library, and letting us know the result; if went OK or, if not, what went wrong.
By Mirroring
If you have the possibility of mirroring the repository, please use the anonymous rsync access facility and let us know how we can retrieve the mirror images in case of need.

By Giving More

With Ports to Other Platforms
If you would like to see the PPL ported to other platforms, you are welcome to work with us toward this objective. The work should be facilitated by the fact that we have always tried hard to be compliant to all the applicable standards.
With Test Programs
Writing small programs that test the PPL facilities is one of the best ways to learn how to use the library. If you plan to do this exercise, then send us your test programs: they are useful for regression testing. If you want advice on how to write your test programs so that their utility can be maximized please contact us; we will be very happy to help.

By Giving Even More

With Projects and Theses

English The PPL and applications one can write using it provide excellent material for projects and theses. Please, do not be mistaken: not all projects or theses that can be built around the PPL require a deep knowledge of the mathematics that justifies its inner mechanisms, and several of them do not require any knowledge of the inner machinery.

Italiano La PPL e le applicazioni che con essa si possono realizzare forniscono spunti eccellenti per tesi e progetti. Non ci si inganni: non tutti i progetti o le tesi che si possono costruire attorno alla PPL richiedono una conoscenza profonda della matematica che giustifica i suoi algoritmi. Al contrario, molti progetti o tesi possono prescindere completamente dai dettagli implementativi.

Italiano Se sei uno studente all'Università di Parma e pensi che una tesi, un progetto o un tirocinio interno potrebbero interessarti, mettiti in contatto con Roberto Bagnara o Enea Zaffanella.

English If you are a student or teacher anywhere in the world and are interested about a project (for you or for some of your students) on/with/around the PPL, then get in touch with us and we will try to help as much as we can.

By Contributing CPU Cycles

The Tinderbox system is based on build machines: these are machines that repeatedly fetch the code in some Git branch and try to compile it and to run the non-regression test suite. The frequency with which this task is executed varies: on our own machines it may be continuous near release dates, but this does not have to be the case; it can be controlled by means of a cron job. Sensible frequencies are in the range from once per day to once per week and, of course, these jobs can be run overnight so as to minimize impact on other activities. If you have a machine with spare time and you would like to help, please get in touch with us: we will send you the scripts and all the instructions you need to make it act as a build machine.