The system-independent features of the library are described in Section System-Independent Features. Section Compilation and Installation explains how the various incarnations of the Prolog interface are compiled and installed. Section System-Dependent Features illustrates the system-dependent features of the interface for all the supported systems.
The Prolog interface provides access to the PPL polyhedra. A general introduction to convex polyhedra, their representation in the PPL and the operations provided by the PPL is given in Sections A Library for Convex Polyhedra, An Introduction to Convex Polyhedra, Representations of Convex Polyhedra and Operations on Convex Polyhedra of this manual. Here we just describe those aspects that are specific to the Prolog interface.
First, here is a list of notes with general information and advice on the use of the interface.
ppl_initialize/0 and ppl_finalize/0. Thus the only interface predicates callable after ppl_finalize/0 are ppl_finalize/0 itself (this further call has no effect) and ppl_initialize/0, after which the interface's services are usable again. Some Prolog systems allow the specification of initialization and deinitialization functions in their foreign language interfaces. The corresponding incarnations of the PPL-Prolog interface have been written so that ppl_initialize/0 and/or ppl_finalize/0 are called automatically. Section System-Dependent Features will detail in which cases initialization and finalization is automatically performed or is left to the Prolog programmer's responsibility. However, for portable applications, it is best to invoke ppl_initialize/0 and ppl_finalize/0 explicitly: since they can be called multiple times without problems, this will result in enhanced portability at a cost that is, by all means, negligible.
ppl_new_Polyhedron_from_dimension/3, ppl_new_Polyhedron_empty_from_dimension/3, ppl_new_Polyhedron_from_Polyhedron/4, ppl_new_Polyhedron_from_constraints/3, ppl_new_Polyhedron_from_generators/3. ppl_new_Polyhedron_from_bounding_box/3.
ppl_new_Polyhedron_from_Polyhedron/4, the first and third arguments) denotes the topology and can be either c or nnc indicating a C or NNC polyhedron, respectively. The third argument (in the case of ppl_new_Polyhedron_from_Polyhedron/4, the fourth argument) is a Prolog term that is unified with a new valid handle for accessing this polyhedron.
ppl_delete_Polyhedron/1. To understand why this is important, consider a Prolog program and a variable that is bound to a Herbrand term. When the variable dies (goes out of scope) or is uninstantiated (on backtracking) the term it is bound to is amenable to garbage collection. But this only applies for the standard domain of the language: Herbrand terms. In Prolog+PPL, when a variable bound to a handle for a PPL Polyhedron dies or is uninstantiated, the handle can be garbage-collected, but the polyhedra to which the handle refers will not be released. Once a handle has been used as an argument in ppl_delete_Polyhedron/1, it becomes invalid.
k, the identifiers used for the PPL variables must lie between 0 and
and correspond to the indices of the associated Cartesian axes. When using the predicates that combine PPL polyhedra or add constraints or generators to a representation of a PPL polyhedron, the polyhedra referenced and any constraints or generators in the call should follow all the space dimension-compatibility rules stated in Section Representations of Convex Polyhedra.
Here is a list of all the PPL predicates provided by the Prolog interface.
ppl_version_major(?Integer)
ppl_version_minor(?Integer)
ppl_version_revision(?Integer)
ppl_version_beta(?Integer)
ppl_version(?Atom)
ppl_banner(?Atom)
ppl_max_space_dimension(?Integer)
ppl_initialize
ppl_finalize
ppl_set_timeout_exception_atom(+Atom)
ppl_set_timeout(+Integer)
ppl_reset_timeout
ppl_new_Polyhedron_from_dimension(+Topology, +Integer, -Handle)
ppl_new_Polyhedron_empty_from_dimension(+Topology, +Integer, -Handle)
ppl_new_Polyhedron_from_Polyhedron(+Topology_1, +Handle_1, +Topology_2, -Handle_2)
ppl_new_Polyhedron_from_constraints(+Topology, +Constraint_System, -Handle)
ppl_new_Polyhedron_from_generators(+Topology, +Generator_System, -Handle)
ppl_new_Polyhedron_from_bounding_box(+Topology, +Box, -Handle)
ppl_Polyhedron_swap(+Handle1, +Handle2)
ppl_delete_Polyhedron(+Handle)
ppl_Polyhedron_space_dimension(+Handle, -Integer)
ppl_Polyhedron_get_constraints(+Handle, -Constraint_System)
ppl_Polyhedron_get_minimized_constraints(+Handle, -Constraint_System)
ppl_Polyhedron_get_generators(+Handle, -Generator_System)
ppl_Polyhedron_get_minimized_generators(+Handle, -Generator_System)
ppl_Polyhedron_relation_with_constraint(+Handle, +Constraint, -Relation)
ppl_Polyhedron_relation_with_generator(+Handle, +Generator, -Relation)
ppl_Polyhedron_get_bounding_box(+Handle, +Complexity, -Box)
ppl_Polyhedron_is_empty(+Handle)
ppl_Polyhedron_is_universe(+Handle)
ppl_Polyhedron_is_bounded(+Handle)
ppl_Polyhedron_bounds_from_above(+Handle, +LinExpr)
ppl_Polyhedron_bounds_from_below(+Handle, +LinExpr)
ppl_Polyhedron_maximize(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool)
ppl_Polyhedron_maximize_with_point(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool, ?Point)
ppl_Polyhedron_minimize(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool)
ppl_Polyhedron_minimize_with_point(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool, ?Point)
ppl_Polyhedron_is_topologically_closed(+Handle)
ppl_Polyhedron_contains_Polyhedron(+Handle_1, +Handle_2)
ppl_Polyhedron_strictly_contains_Polyhedron(+Handle_1, +Handle_2)
ppl_Polyhedron_is_disjoint_from_Polyhedron(+Handle_1, +Handle_2)
ppl_Polyhedron_equals_Polyhedron(+Handle_1, +Handle_2)
ppl_Polyhedron_OK(+Handle)
ppl_Polyhedron_add_constraint(+Handle, +Constraint)
ppl_Polyhedron_add_constraint_and_minimize(+Handle, +Constraint)
ppl_Polyhedron_add_generator(+Handle, +Generator)
ppl_Polyhedron_add_generator_and_minimize(+Handle, +Generator)
ppl_Polyhedron_add_constraints(+Handle, +Constraint_System)
ppl_Polyhedron_add_constraints_and_minimize(+Handle, +Constraint_System)
ppl_Polyhedron_add_generators(+Handle, +Generator_System)
ppl_Polyhedron_add_generators_and_minimize(+Handle, +Generator_System)
ppl_Polyhedron_intersection_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_intersection_assign_and_minimize(+Handle_1, +Handle_2)
ppl_Polyhedron_poly_hull_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_poly_hull_assign_and_minimize(+Handle_1, +Handle_2)
ppl_Polyhedron_poly_difference_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_affine_image(+Handle, +PPL_Var, +LinExpr, +Integer)
ppl_Polyhedron_affine_preimage(+Handle, +PPL_Var, +LinExpr, +Integer)
ppl_Polyhedron_generalized_affine_image(+Handle, +PPL_Var, +Relation_Symbol, +LinExpr, +Integer)
ppl_Polyhedron_generalized_affine_image_lhs_rhs(+Handle, +LinExpr1, +Relation_Symbol, +LinExpr2)
ppl_Polyhedron_time_elapse_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_BHRZ03_widening_assign_with_token(+Handle_1, +Handle_2, ?Integer)
ppl_Polyhedron_BHRZ03_widening_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_limited_BHRZ03_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
ppl_Polyhedron_limited_BHRZ03_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
ppl_Polyhedron_bounded_BHRZ03_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
ppl_Polyhedron_bounded_BHRZ03_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
ppl_Polyhedron_H79_widening_assign_with_token(+Handle_1, +Handle_2, ?Integer)
ppl_Polyhedron_H79_widening_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_limited_H79_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
ppl_Polyhedron_limited_H79_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
ppl_Polyhedron_bounded_H79_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System)
ppl_Polyhedron_bounded_H79_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
ppl_Polyhedron_topological_closure_assign(+Handle)
ppl_Polyhedron_add_dimensions_and_embed(+Handle, +Integer)
ppl_Polyhedron_add_dimensions_and_project(+Handle, +Integer)
ppl_Polyhedron_concatenate_assign(+Handle1, +Handle2)
ppl_Polyhedron_remove_dimensions(+Handle, +List_of_PPL_Vars)
ppl_Polyhedron_remove_higher_dimensions(+Handle, +Integer))
ppl_Polyhedron_expand_dimension(+Handle, +PPL_Var, +Integer))
ppl_Polyhedron_fold_dimensions(+Handle, +List_of_PPL_Vars, +PPL_Var))
ppl_Polyhedron_map_dimensions(+Handle, +P_Func))
The PPL predicates provided by the Prolog interface are specified below. The specification uses the following grammar rules:
Handle --> Prolog term
Topology --> c | nnc
VarId --> number | + number variable identifier
PPL_Var --> '$VAR'(VarId) PPL variable
LinExpr --> PPL_Var PPL variable
| number
| + LinExpr unary plus
| - LinExpr unary minus
| LinExpr + LinExpr addition
| LinExpr - LinExpr subtraction
| number * LinExpr multiplication
| LinExpr * number multiplication
Relation_Symbol
--> = equals
| =< less than or equal
| >= greater than or equal
| < strictly less than
| > strictly greater than
Denominator --> number
| + number | - number number must be non-zero
Constraint --> LinExpr Relation_Symbol LinExpr
constraint
Constraint_System list of constraints
--> []
| [Constraint | Constraint_System]
Generator --> point(LinExpr) point
| point(LinExpr, Denominator)
point
| closure_point(LinExpr) closure point
| closure_point(LinExpr, Denominator)
closure point
(the point or closure point is defined by LinExpr/Denominator.)
| ray(LinExpr) ray
| line(LinExpr) line
Generator_System list of generators
--> []
| [Generator | Generator_System]
Atom --> Prolog atom
Relation --> is_disjoint between a constraint and a polyhedron
| strictly_intersects between a constraint and a polyhedron
| is_included between a constraint and a polyhedron
| saturates between a constraint and a polyhedron
| subsumes between a generator and a polyhedron
Relation_List list of relations
--> []
| [Relation | Relation_List]
Complexity --> polynomial | simplex | any
Rational_Numerator
--> number | + number | - number
Rational_Denominator
--> number number must be non-zero
Rational --> Rational_Numerator rational number
| Rational_Numerator/Rational_Denominator
Bound --> c(Rational) closed rational limit
| o(Rational) open rational limit
| o(pinf) unbounded in the positive direction
| o(minf) unbounded in the negative direction
Interval --> i(Bound, Bound) rational interval
Box --> [] list of intervals
| [Interval | Box]
Vars_Pair --> PPLVar - PPLVar map relation
P_Func --> [] list of map relations
| [Vars_Pair | P_Func].
Below is a short description of each of the interface predicates. For full definitions of terminology used here, see Sections A Library for Convex Polyhedra, An Introduction to Convex Polyhedra, Representations of Convex Polyhedra and Operations on Convex Polyhedra of this manual.
ppl_version_major(?Integer)
Unifies Integer with the major number of the PPL version.
ppl_version_minor(?Integer)
Unifies Integer with the minor number of the PPL version.
ppl_version_revision(?Integer)
Unifies Integer with the revision number of the PPL version.
ppl_version_beta(?Integer)
Unifies Integer with the beta number of the PPL version.
ppl_version(?Atom)
Unifies Atom with the PPL version.
ppl_banner(?Atom)
Unifies Atom with 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.
ppl_max_space_dimension(?Integer)
Unifies Integer with the maximum space dimension this library can handle.
ppl_initialize
Initializes the PPL interface. Multiple calls to ppl_initialize does no harm.
ppl_finalize
Finalizes the PPL interface. Once this is executed, the next call to an interface predicate must either be to ppl_initialize or to ppl_finalize. Multiple calls to ppl_finalize does no harm.
ppl_set_timeout_exception_atom(+Atom)
Sets the atom to be thrown by timeout exceptions to Atom. The default value is time_out.
ppl_timeout_exception_atom(?Atom)
The atom to be thrown by timeout exceptions is unified with Atom.
ppl_set_timeout(+Integer)
Computations taking exponential time will be interrupted some time after Integer ms after that call. If the computation is interrupted that way, the current timeout exception atom will be thrown. Integer must be strictly greater than zero.
ppl_reset_timeout Resets the timeout time so that the computation is not interrupted.
ppl_new_Polyhedron_from_dimension(+Topology, +Integer, -Handle)
Creates a new universe C or NNC polyhedron
, depending on the value of Topology, with Integer dimensions. Handle is unified with the handle for
. Thus the query
?- ppl_new_Polyhedron_from_dimension(c, 3, X).
with X bound to a valid handle for accessing it.
ppl_new_Polyhedron_empty_from_dimension(+Topology, +Integer, -Handle)
Creates a new empty C or NNC polyhedron
, depending on the value of Topology, with Integer dimensions. Handle is unified with the handle for
. Thus the query
?- ppl_new_Polyhedron_empty_from_dimension(nnc, 3, X).
with X bound to a valid handle for accessing it.
ppl_new_Polyhedron_from_Polyhedron(+Topology_1, +Handle_1, +Topology_2, -Handle_2)
If Handle_1 refers to a C or NNC polyhedron
(depending on the value of Topology_1), then this creates a copy
of
with topology C or NNC, depending on the value of Topology_2. Handle_2 is unified with the handle for
. Thus the query
?- ppl_new_Polyhedron_empty_from_dimension(nnc, 3, X),
ppl_new_Polyhedron_from_Polyhedron(c, X, nnc, Y).
referenced by X and then makes a copy, converting the topology to an NNC polyhedron. with Y bound to a valid handle for accessing it.
When using ppl_new_Polyhedron_from_Polyhedron/2, when the source polyhedron is NNC and the copy is C, care must be taken that the source polyhedron referenced by Handle1 is topologically closed.
ppl_new_Polyhedron_from_constraints(+Topology, +Constraint_System, -Handle)
Creates a polyhedron
represented by Constraint_System with topology C or NNC, depending on the value of Topology. Handle is unified with the handle for
.
ppl_new_Polyhedron_from_generators(+Topology, +Generator_System, -Handle)
Creates a polyhedron
represented by Generator_System with topology C or NNC, depending on the value of Topology. Handle is unified with the handle for
.
ppl_new_Polyhedron_from_bounding_box(+Topology, +Box, -Handle)
Creates a polyhedron
represented by Box with topology C or NNC, depending on the value of Topology, and Handle is unified with the handle for
. A bound of the form o(Rational) can be included in an interval in Box only if Topology is nnc.
ppl_Polyhedron_swap(+Handle1, +Handle2)
Swaps the polyhedron referenced by Handle1 with the one referenced by Handle2. The polyhedra
and
must have the same topology.
ppl_delete_Polyhedron(+Handle)
Deletes the polyhedron referenced by Handle. After execution, Handle is no longer a valid handle for a PPL polyhedron.
ppl_Polyhedron_space_dimension(+Handle, ?Integer)
Unifies the space dimension of the polyhedron referenced by Handle with Integer.
ppl_Polyhedron_get_constraints(+Handle, ?Constraint_System)
Unifies Constraint_System with a list of the constraints in the constraints system representing the polyhedron referenced by Handle.
ppl_Polyhedron_get_minimized_constraints(+Handle, ?Constraint_System)
Unifies Constraint_System with a minimized list of the constraints in the constraints system representing the polyhedron referenced by Handle.
ppl_Polyhedron_get_generators(+Handle, ?Generator_System)
Unifies Generator_System with a list of the generators in the generators system representing the polyhedron referenced by Handle.
ppl_Polyhedron_get_minimized_generators(+Handle, ?Generator_System)
Unifies Generator_System with a minimized list of the generators in the generators system representing the polyhedron referenced by Handle.
ppl_Polyhedron_relation_with_constraint(+Handle, +Constraint, ?Relation_List)
Unifies Relation_List with the list of relations the polyhedron referenced by Handle has with Constraint. The possible relations are listed in the grammar rules above; their meaning is given in the paragraph specifying the relation_with operations in Section Operations on Convex Polyhedra.
ppl_Polyhedron_relation_with_generator(+Handle, +Generator, ?Relation_List)
Unifies Relation_List with the list of relations the polyhedron referenced by Handle has with Generator. The possible relations are listed in the grammar rules above; their meaning is given in the paragraph specifying the relation_with operations in Section Operations on Convex Polyhedra.
ppl_Polyhedron_get_bounding_box(+Handle, +Complexity, ?Box)
Succeeds if and only if the bounding box of the polyhedron referenced by Handle unifies with the box defined by Box. E.g.,
?- A = '$VAR'(0), B = '$VAR'(1),
ppl_new_Polyhedron_from_constraints(nnc, [B > 0, 4*A =< 2], X),
ppl_Polyhedron_get_bounding_box(X, any, Box).
Box = [i(o(minf), c(1/2)), i(o(0), o(pinf))].
Box are in canonical form. E.g., the following will fail: ?- A = '$VAR'(0), B = '$VAR'(1),
ppl_new_Polyhedron_from_constraints(nnc, [B > 0, 4*A =< 2], X),
ppl_Polyhedron_get_bounding_box(X, any, Box),
Box = [i(o(minf), c(2/4)), i(o(0), o(pinf))].
The complexity class Complexity determining the algorithm to be used has the following meaning:
polynomial allows code of the worst-case polynomial complexity class;simplex allows code of the worst-case exponential but typically polynomial complexity class;any allows code of the universal complexity class.
ppl_Polyhedron_is_empty(+Handle)
Succeeds if and only if the polyhedron referenced by Handle is empty.
ppl_Polyhedron_is_universe(+Handle)
Succeeds if and only if the polyhedron referenced by Handle is the universe.
ppl_Polyhedron_is_bounded(+Handle)
Succeeds if and only if the polyhedron referenced by Handle is bounded.
ppl_Polyhedron_bounds_from_above(+Handle, +LinExpr)
Succeeds if and only if LinExpr is bounded from above in the polyhedron referenced by Handle.
ppl_Polyhedron_bounds_from_below(+Handle, +LinExpr)
Succeeds if and only if LinExpr is bounded from below in the polyhedron referenced by Handle.
ppl_Polyhedron_maximize(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool)
Succeeds if and only if the polyhedron
referenced by Handle is not empty and LinExpr is bounded from above in
.
Integer1 is unified with the numerator of the supremum value and Integer2 with the denominator of the supremum value. If the supremum is also the maximum, Bool is unified with the atom true and, otherwise, unified with the atom false.
ppl_Polyhedron_maximize_with_point(+Handle, +LinExpr, ?Integer1, ?Integer2, ?Bool, ?Point)
Succeeds if and only if the polyhedron
referenced by Handle is not empty and LinExpr is bounded from above in
.
Integer1 is unified with the numerator of the supremum value, Integer2 with the denominator of the supremum value, and Point with a point or closure point where LinExpr reaches this value. If the supremum is also the maximum, Bool is unified with the atom true and, otherwise, unified with the atom false.
ppl_Polyhedron_minimize(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool)
Succeeds if and only if the polyhedron
referenced by Handle is not empty and LinExpr is bounded from below in
.
Integer1 is unified with the numerator of the infimum value and Integer2 with the denominator of the infimum value. If the infimum is also the minimum, Bool is unified with the atom true and, otherwise, unified with the atom false.
ppl_Polyhedron_minimize_with_point(+Handle, +LinExpr, ?Integer, ?Integer, ?Bool, ?Point)
Succeeds if and only if the polyhedron
referenced by Handle is not empty and LinExpr is bounded from below in
.
Integer1 is unified with the numerator of the infimum value, Integer2 with the denominator of the infimum value, and Point with a point or closure point where LinExpr reaches this value. If the infimum is also the minimum, Bool is unified with the atom true and, otherwise, unified with the atom false.
ppl_Polyhedron_is_topologically_closed(+Handle)
Succeeds if and only if the polyhedron referenced by Handle is topologically closed.
ppl_Polyhedron_contains_Polyhedron(+Handle_1, +Handle_2)
Succeeds if and only if the polyhedron referenced by Handle_1 is included in or equal to the polyhedron referenced by Handle_2.
ppl_Polyhedron_strictly_contains_Polyhedron(+Handle_1, +Handle_2)
Succeeds if and only if the polyhedron referenced by Handle_1 is included in but not equal to the polyhedron referenced by Handle_2.
ppl_Polyhedron_is_disjoint_from_Polyhedron(+Handle_1, +Handle_2)
Succeeds if and only if the polyhedron referenced by Handle_1 is disjoint from the polyhedron referenced by Handle_2.
ppl_Polyhedron_equals_Polyhedron(+Handle_1, +Handle_2)
Succeeds if and only if the polyhedron referenced by Handle_1 is equal to the polyhedron referenced by Handle_2.
ppl_Polyhedron_OK(+Handle)
Succeeds only if the polyhedron referenced by Handle is well formed, i.e., if it satisfies all its implementation invariants. Useful for debugging purposes.
ppl_Polyhedron_add_constraint(+Handle, +Constraint)
ppl_Polyhedron_add_constraint_and_minimize(+Handle, +Constraint)
Updates the polyhedron referenced by Handle to one obtained by adding Constraint to its constraint system. Thus, the query
?- ppl_new_Polyhedron_from_dimension(c, 3, X),
A = '$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
ppl_Polyhedron_add_constraint(X, 4*A + B - 2*C >= 5).
X to consist of the set of points in the vector space
satisfying the constraint
.
Note that ppl_Polyhedron_add_constraint_and_minimize/2 will fail if, after adding the constraint, the polyhedron is empty.
ppl_Polyhedron_add_generator(+Handle, +Generator)
ppl_Polyhedron_add_generator_and_minimize(+Handle, +Generator)
Updates the polyhedron referenced by Handle to one obtained by adding Generator to its generator system. Thus, after the query
?- ppl_new_Polyhedron_from_dimension(c, 3, X),
A = '$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
ppl_Polyhedron_add_generator(X, point(-100*A - 5*B, 8)).
X to be the single point
in the vector space
.
ppl_Polyhedron_add_constraints(+Handle, +Constraint_System)
Updates the polyhedron referenced by Handle to one obtained by adding to its constraint system the constraints in Constraint_System. E.g.,
| ?- ppl_new_Polyhedron_from_dimension(c, 2, X),
A = '$VAR'(0), B = '$VAR'(1),
ppl_Polyhedron_add_constraints(X, [4*A + B >= 3, A = 1]),
ppl_Polyhedron_get_constraints(X, CS).
CS = [4*A+1*B>=3,1*A=1] ?
Handle can be empty and a query will succeed even when Constraint_System is unsatisfiable.
ppl_Polyhedron_add_constraints_and_minimize(+Handle, +Constraint_System)
Updates the polyhedron referenced by Handle to one obtained by adding to its constraint system the constraints in Constraint_System. E.g.,
?- ppl_new_Polyhedron_from_dimension(c, 2, X),
A = '$VAR'(0), B = '$VAR'(1),
ppl_Polyhedron_add_constraints_and_minimize(X, [4*A + B >= 3, A = 1]),
ppl_Polyhedron_get_constraints(X, CS).
CS = [1*B>= -1,1*A=1]
?- A = '$VAR'(0), B = '$VAR'(1),
ppl_new_Polyhedron_from_dimension(c, 2, X),
ppl_Polyhedron_add_constraints_and_minimize(X,
[4*A + B >= 3, A = 0, B =< 0]),
ppl_Polyhedron_get_constraints(X, CS).
ppl_Polyhedron_add_generators(+Handle, +Generator_System)
Updates the polyhedron referenced by Handle to one obtained by adding to its generator system the generators in Generator_System.
If the system of generators representing a polyhedron is non-empty, then it must include a point (see the paragraph on generator representation in Section Representations of Convex Polyhedra). Thus care must be taken to ensure that, before calling this predicate, either the polyhedron referenced by Handle is non-empty or that whenever Generator_System is non-empty the first element defines a point. E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 3, X),
A='$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
ppl_Polyhedron_add_generators(X,
[point(1*A + 1*B + 1*C, 1), ray(1*A), ray(2*A)]),
ppl_Polyhedron_get_generators(X, GS).
GS = [ray(2*A), point(1*A+1*B+1*C), ray(1*A)]
ppl_Polyhedron_add_generators_and_minimize(+Handle, +Generator_System)
Updates the polyhedron referenced by Handle to one obtained by adding to its generator system the generators in Generator_System.
Unlike the predicate ppl_add_generators, the order of the generators in Generator_System is not important. E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 3, X),
A='$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
ppl_Polyhedron_add_generators_and_minimize(X,
[ray(1*A), ray(2*A), point(1*A + 1*B + 1*C, 1)]),
ppl_Polyhedron_get_generators(X, GS).
GS = [point(1*A+1*B+1*C), ray(1*A)]
ppl_Polyhedron_intersection_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_intersection_assign_and_minimize(+Handle_1, +Handle_2)
Assigns to the polyhedron referenced by Handle_1 its intersection with the polyhedron referenced by Handle_2.
ppl_Polyhedron_poly_hull_assign(+Handle_1, +Handle_2)
ppl_Polyhedron_poly_hull_assign_and_minimize(+Handle_1, +Handle_2)
Assigns to the polyhedron referenced by Handle_1 its poly-hull with the polyhedron referenced by Handle_2.
ppl_Polyhedron_poly_difference_assign(+Handle_1, +Handle_2)
Assigns to the polyhedron referenced by Handle_1 its poly-difference with the polyhedron referenced by Handle_2.
ppl_Polyhedron_affine_image(+Handle, +PPL_Var, +LinExpr, +Integer)
Transforms the polyhedron referenced by Handle assigning the affine expression LinExpr/Integer to PPL_Var.
ppl_Polyhedron_affine_preimage(+Handle, +PPL_Var, +LinExpr, +Integer)
This is the inverse transformation to that for ppl_affine_image.
ppl_Polyhedron_generalized_affine_image(+Handle, +PPL_Var, +Relation_Symbol +LinExpr, +Integer)
Transforms the polyhedron referenced by Handle assigning the generalized affine image with respect to the transfer function PPL_Var Relation_Symbol LinExpr/Integer.
ppl_Polyhedron_generalized_affine_image_lhs_rhs(+Handle, +LinExpr1, +Relation_Symbol +LinExpr2)
Transforms the polyhedron referenced by Handle assigning the generalized affine image with respect to the transfer function LinExpr1 Relation_Symbol LinExpr2.
ppl_Polyhedron_time_elapse_assign(+Handle_1, +Handle_2)
Assigns to the polyhedron
referenced by Handle_1 the time-elapse
with the polyhedron
referenced by Handle_2.
ppl_Polyhedron_BHRZ03_widening_assign_with_token(+Handle_1, +Handle_2, ?Integer)
The polyhedra referenced by Handle_1 and Handle_2 are unaltered. The token Integer is 0 if a BHRZ03 widening would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_BHRZ03_widening_assign(+Handle_1, +Handle_2)
Assigns to the polyhedron referenced by Handle_1 its BHRZ03-widening with the polyhedron referenced by Handle_2.
ppl_Polyhedron_limited_BHRZ03_extrapolation_assign_with_token( +Handle_1, +Handle_2, +Constraint_System, ?Integer)
The polyhedra referenced by Handle_1 and Handle_2 are unaltered. The token Integer is 0 if a BHRZ03-widening with the polyhedron referenced by Handle_2, improved by enforcing those constraints in Constraint_System would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_limited_BHRZ03_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
Assigns to the polyhedron
referenced by Handle_1 the result of its BHRZ03-widening with the polyhedron referenced by Handle_2, improved by enforcing those constraints in Constraint_System.
ppl_Polyhedron_bounded_BHRZ03_extrapolation_assign_with_token( +Handle_1, +Handle_2, +Constraint_System, ?Integer)
The polyhedra
and
referenced by Handle_1 and Handle_2, respectively are unaltered. The token Integer is 0 if a BHRZ03-widening with
, improved by enforcing all the constraints of the form
and
that are satisfied by all the points of
together with the constraints in Constraint_System would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_bounded_BHRZ03_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
Assigns to the polyhedron
referenced by Handle_1 the result of its BHRZ03-widening with the polyhedron referenced by Handle_2 improved by enforcing all the constraints of the form
and
that are satisfied by all the points of
together with the constraints in Constraint_System.
ppl_Polyhedron_H79_widening_assign_with_token(+Handle_1, +Handle_2, ?Integer)
The polyhedra referenced by Handle_1 and Handle_2 are unaltered. The token Integer is 0 if an H79 widening would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_H79_widening_assign(+Handle_1, +Handle_2)
Assigns to the polyhedron referenced by Handle_1 its H79-widening with the polyhedron referenced by Handle_2.
ppl_Polyhedron_limited_H79_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
The polyhedra referenced by Handle_1 and Handle_2 are unaltered. The token Integer is 0 if a H79-widening with the polyhedron referenced by Handle_2, improved by enforcing those constraints in Constraint_System would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_limited_H79_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
Assigns to the polyhedron
referenced by Handle_1 its H79-widening with the polyhedron referenced by Handle_2, improved by enforcing those constraints in Constraint_System.
ppl_Polyhedron_bounded_H79_extrapolation_assign_with_token(+Handle_1, +Handle_2, +Constraint_System, ?Integer)
The polyhedra
and
referenced by Handle_1 and Handle_2, respectively are unaltered. The token Integer is 0 if a H79-widening with
, improved by enforcing all the constraints of the form
and
that are satisfied by all the points of
together with the constraints in Constraint_System would have changed the polyhedron referenced by Handle_1 and is 1 otherwise.
ppl_Polyhedron_bounded_H79_extrapolation_assign(+Handle_1, +Handle_2, +Constraint_System)
Assigns to the polyhedron
referenced by Handle_1 the result of its H79-widening with the polyhedron referenced by Handle_2 improved by enforcing all the constraints of the form
and
that are satisfied by all the points of
together with the constraints in Constraint_System.
ppl_Polyhedron_topological_closure_assign(+Handle)
Assigns to the polyhedron referenced by Handle its topological closure.
ppl_Polyhedron_add_dimensions_and_embed(+Handle, +Integer)
Embeds the polyhedron referenced by Handle in a space that is enlarged by Integer dimensions, E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 0, X),
ppl_Polyhedron_add_dimensions_and_embed(X, 2),
ppl_Polyhedron_get_constraints(X, CS),
ppl_Polyhedron_get_generators(X, GS).
CS = [],
GS = [point(0),line(1*A),line(1*B)]
ppl_Polyhedron_concatenate_assign(+Handle1, +Handle2)
Updates the polyhedron
referenced by Handle1 by first embedding
in a new space enlarged by the space dimensions of the polyhedron
referenced by Handle2, and then adds to its system of constraints a renamed-apart version of the constraints of
.
E.g.,
?- ppl_new_Polyhedron_from_dimension(nnc, 2, X),
A = '$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
D = '$VAR'(3), E = '$VAR'(4),
ppl_new_Polyhedron_from_constraints(nnc, [A > 1, B >= 0, C >= 0], Y),
ppl_Polyhedron_concatenate_assign(X, Y),
ppl_Polyhedron_get_constraints(X, CS).
CS = [1*C > 1, 1*D >= 0, 1*E >= 0]
ppl_Polyhedron_add_dimensions_and_project(+Handle, +Integer)
Projects the polyhedron referenced by Handle onto a space that is enlarged by Integer dimensions, E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 0, X),
ppl_Polyhedron_add_dimensions_and_project(X, 2),
ppl_Polyhedron_get_constraints(X, CS),
ppl_Polyhedron_get_generators(X, GS).
CS = [1*A = 0, 1*B = 0],
GS = [point(0)]
ppl_Polyhedron_remove_dimensions(+Handle, +List_of_PPL_Vars)
Removes the space dimensions given by the identifiers of the PPL variables in list List_of_PPL_Vars from the polyhedron referenced by Handle. The identifiers for the remaining PPL variables are renumbered so that they are consecutive and the maximum index is less than the number of dimensions. E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 3, X),
A='$VAR'(0), B = '$VAR'(1), C = '$VAR'(2),
ppl_Polyhedron_remove_dimensions(X, [B]),
ppl_Polyhedron_space_dimension(X, K),
ppl_Polyhedron_get_generators(X, GS).
K = 2,
GS = [point(0),line(1*A),line(1*B),line(0)]
ppl_Polyhedron_remove_higher_dimensions(+Handle, +Integer))
Projects the polyhedron referenced to by Handle onto the first Integer dimension. E.g.,
?- ppl_new_Polyhedron_empty_from_dimension(c, 5, X),
ppl_Polyhedron_remove_higher_dimensions(X, 3),
ppl_Polyhedron_space_dimension(X, K).
ppl_Polyhedron_expand_dimension(+Handle, +PPL_Var, +Integer))
Integer copies of the space dimension referenced by PPL_Var are added to the polyhedron referenced to by Handle.
ppl_Polyhedron_fold_dimensions(+Handle, +List_of_PPL_Vars, +PPL_Var))
The space dimensions referenced by the PPL variables in list List_of_PPL_Vars are folded into the dimension referenced by PPL_Var and removed. The result is undefined if List_of_PPL_Vars does not have the properties described in the paragraph specifying the fold_dimensions operator in Section Operations on Convex Polyhedra.
ppl_Polyhedron_map_dimensions(+Handle, +P_Func))
Maps the dimensions of the polyhedron referenced by Handle using the partial function defined by P_Func. The result is undefined if P_Func does not encode a partial function with the properties described in the paragraph specifying the map_dimensions operator in Section Operations on Convex Polyhedra.
When the Parma Polyhedra Library is configured, it tests for the existence of each supported Prolog system. If a supported Prolog system is correctly installed in a standard location, things are arranged so that the corresponding interface is built and installed.
In the sequel, prefix is the prefix under which you have installed the library (typically /usr or /usr/local).
As an option, the Prolog interface can track the creation and disposal of polyhedra. In fact, differently from native Prolog data, PPL polyhedra must be explicitly disposed and forgetting to do so is a very common mistake. To enable this option, configure the library adding -DPROLOG_TRACK_ALLOCATION to the options passed to the C++ compiler. Your configure command would then look like
path/to/configure --with-cxxflags="-DPROLOG_TRACK_ALLOCATION" ...
Support for CIAO Prolog is under development and will be available in a future release. Only Ciao Prolog 1.9 #44 or later is supported.
The GNU Prolog interface to the PPL library is available both as ``PPL enhanced'' GNU Prolog interpreter and as a library that can be linked to GNU Prolog programs. Only GNU Prolog version 1.2.12 or later is supported.
Notice that GNU Prolog version 1.2.12 suffers from a serious limitation as far as foreign code is concerned. In order to be safe you must configure GNU Prolog with the --disable-ebp option (note that this has a negative effect on performance). See http://www.cs.unipr.it/pipermail/ppl-devel/2002-June/001777.html, http://www.cs.unipr.it/pipermail/ppl-devel/2002-June/001780.html, http://www.cs.unipr.it/pipermail/ppl-devel/2002-June/001788.html and http://www.cs.unipr.it/pipermail/ppl-devel/2002-June/001789.html for more information.
We have experienced other serious problems with the GNU Prolog interface, up to and including GNU Prolog version 1.2.16: see http://www.cs.unipr.it/pipermail/ppl-devel/2002-October/002657.html for more information.
ppl_gprolog Executable
If an appropriate version of GNU Prolog is installed on the machine on which you compiled the library, the command make install will install the executable ppl_gprolog in the directory prefix/bin. The ppl_gprolog executable is simply the GNU Prolog interpreter with the Parma Polyhedra library linked in. The only thing you should do to use the library is to call ppl_initialize/0 before any other PPL predicate and to call ppl_finalize/0 when you are done with the library.
In order to allow linking GNU Prolog programs to the PPL, the following files are installed in the directory prefix/lib/ppl: ppl_gprolog.pl contains the required foreign declarations; libppl_gprolog.* contain the executable code for the GNU Prolog interface in various formats (static library, shared library, libtool library). If your GNU Prolog program is constituted by, say, source1.pl and source2.pl and you want to create the executable myprog, your compilation command may look like
gplc -o myprog prefix/lib/ppl/ppl_gprolog.pl source1.pl source2.pl \ -L '-Lprefix/lib/ppl -lppl_gprolog -Lprefix/lib -lppl -lgmpxx -lgmp -lstdc++'
The SICStus Prolog interface to the PPL library is available both as a statically linked module or as a dynamically linked one. Only SICStus Prolog version 3.9.0 or later is supported.
ppl_sicstus Executable
If an appropriate version of SICStus Prolog is installed on the machine on which you compiled the library, the command make install will install the executable ppl_sicstus in the directory prefix/bin. The ppl_sicstus executable is simply the SICStus Prolog system with the Parma Polyhedra library statically linked. The only thing you should do to use the library is to load prefix/lib/ppl/ppl_sicstus.pl.
In order to dynamically load the library from SICStus Prolog you should simply load prefix/lib/ppl/ppl_sicstus.pl. Notice that, for dynamic linking to work, you should have configured the library with the --enable-shared option.
The SWI-Prolog interface of the library is available both as a statically linked module or as a dynamically linked one. Only SWI-Prolog version 5.0 or later is supported.
ppl_pl Executable
If an appropriate version of SWI-Prolog is installed on the machine on which you compiled the library, the command make install will install the executable ppl_pl in the directory prefix/bin. The ppl_pl executable is simply the SWI-Prolog shell with the Parma Polyhedra library statically linked: from within ppl_pl all the services of the library are available without further action.
In order to dynamically load the library from SWI-Prolog you should simply load prefix/lib/ppl/ppl_swiprolog.pl. This will invoke ppl_initialize/0 automatically but, at least for SWI-Prolog versions up to 5.0.7, it is the programmer's responsibility to call ppl_finalize/0. Alternatively, you can load the library directly with
:- load_foreign_library('prefix/lib/ppl/libppl_swiprolog').
ppl_initialize/0 automatically. Analogously, :- unload_foreign_library('prefix/lib/ppl/libppl_swiprolog').
ppl_finalize/0.
Notice that, for dynamic linking to work, you should have configured the library with the --enable-shared option.
The XSB Prolog interface to the PPL library is available as a dynamically linked module. Only XSB version 2.5 and following is supported.
In order to dynamically load the library from XSB you should load the ppl_xsb module and import the predicates you need. For things to work, you may have to copy the files prefix/lib/ppl/ppl_xsb.xwam and prefix/lib/ppl/ppl_xsb.so in your current directory or in one of the XSB library directories.
The YAP Prolog interface to the PPL library is available as a dynamically linked module. Only YAP version 4.4 or later is supported.
In order to dynamically load the library from YAP you should simply load prefix/lib/ppl/ppl_yap.pl. This will invoke ppl_initialize/0 automatically; it is the programmer's responsibility to call ppl_finalize/0 when the PPL library is no longer needed. Notice that, for dynamic linking to work, you should have configured the library with the --enable-shared option.
1.3.8-20040812