PPL Prolog Language Interface  1.2
System-Independent Features

# System-Independent Features

The Prolog interface provides access to the numerical abstractions (convex polyhedra, BD shapes, octagonal shapes, etc.) implemented by the PPL library. A general introduction to the numerical abstractions, their representation in the PPL and the operations provided by the PPL is given in the main PPL user manual. Here we just describe those aspects that are specific to the Prolog interface.

## Overview

First, here is a list of notes with general information and advice on the use of the interface.

• The numerical abstract domains available to the Prolog user consist of the simple domains, powersets of a simple domain and products of simple domains.
• The simple domains are:
• convex polyhedra, which consist of C_Polyhedron and NNC_Polyhedron;
• weakly relational, which consist of BD_Shape_N and Octagonal_Shape_N where N is one of the numeric types int8, int16, int32, int64, mpz_class, mpq_class, float, double, long_double;
• boxes which consist of Int8_Box, Int16_Box, Int32_Box, Int64_Box, Uint8_Box, Uint16_Box, Uint32_Box, Uint64_Box, Double_Box, Long_Double_Box, Z_Box, Rational_Box, Float_Box; and
• the Grid domain.
• The powerset domains are Pointset_Powerset_S where S is a simple domain.
• The product domains consist of Direct_Product_S_T, Smash_Product_S_T, Constraints_Product_S_T and Shape_Preserving_Product_S_T where S and T are simple domains.
• In the following, any of the above numerical abstract domains is called a PPL domain and any element of a PPL domain is called a PPL object.
• The Prolog interface to the PPL is initialized and finalized by the predicates 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 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.
• A PPL object such as a polyhedron can only be accessed by means of a Prolog term called a handle. Note, however, that the data structure of a handle, is implementation-dependent, system-dependent and version-dependent, and, for this reason, deliberately left unspecified. What we do guarantee is that the handle requires very little memory.
• A Prolog term can be bound to a valid handle for a PPL object by using predicates such as
ppl_new_C_Polyhedron_from_space_dimension/3,
ppl_new_C_Polyhedron_from_C_Polyhedron/2,
ppl_new_C_Polyhedron_from_constraints/2,
ppl_new_C_Polyhedron_from_generators/2,
These predicates will create or copy a PPL polyhedron and construct a valid handle for referencing it. The last argument is a Prolog term that is unified with a new valid handle for accessing this polyhedron.
• As soon as a PPL object is no longer required, the memory occupied by it should be released using the PPL predicate such as 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, for example, a variable bound to a handle for a Polyhedron dies or is uninstantiated, the handle can be garbage-collected, but the polyhedron 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.
• For a PPL object with space dimension k, the identifiers used for the PPL variables must lie between 0 and and correspond to the indices of the associated Cartesian axes. For example, 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 of the main PPL user manual.
• As explained above, a polyhedron has a fixed topology C or NNC, that is determined at the time of its initialization. All subsequent operations on the polyhedron must respect all the topological compatibility rules stated in Section Representations of Convex Polyhedra of the main PPL user manual.
• Any application using the PPL should make sure that only the intended version(s) of the library are ever used. Predicates allow run-time checking of information about the version being used.

## Predicate Specifications

The PPL predicates provided by the Prolog interface are specified below. The specification uses the following grammar rules:

Number --> unsigned integer ranging from 0 to an upper bound
depending on the actual Prolog system.
C_int --> Number | - Number C integer
C_unsigned --> Number C unsigned integer
Coeff --> Number used in linear expressions;
the upper bound will depend on how
the PPL has been configured
Dimension_Type
--> Number used for the number of affine and
space dimensions and the names of
the dimensions;
the upper bound will depend on
the maximum number of dimensions
allowed by the PPL
(see ppl_max_space_dimensions/1)
Boolean --> true | false
Handle --> Prolog term used to identify a Polyhedron
Topology --> c | nnc Polyhedral kind;
c is closed and nnc is NNC
VarId --> Dimension_Type variable identifier
PPL_Var --> '\$VAR'(VarId) PPL variable
Lin_Expr --> PPL_Var PPL variable
| Coeff
| Lin_Expr unary plus
| - Lin_Expr unary minus
| Lin_Expr - Lin_Expr subtraction
| Coeff * Lin_Expr multiplication
| Lin_Expr * Coeff multiplication
Relation_Symbol --> = equals
| =< less than or equal
| >= greater than or equal
| < strictly less than
| > strictly greater than
Constraint --> Lin_Expr Relation_Symbol Lin_Expr
constraint
Constraint_System list of constraints
--> []
| [Constraint | Constraint_System]
Modulus --> Coeff | - Coeff
Congruence --> Lin_Expr =:= Lin_Expr congruence with modulo 1
| (Lin_Expr =:= Lin_Expr) / Modulus
congruence with modulo Modulus
Congruence_System list of congruences
--> []
| [Congruence | Congruence_System]
Generator_Denominator --> Coeff must be non-zero
| - Coeff
Generator --> point(Lin_Expr) point
| point(Lin_Expr, Generator_Denominator)
point
| closure_point(Lin_Expr) closure point
| closure_point(Lin_Expr, Generator_Denominator)
closure point
| ray(Lin_Expr) ray
| line(Lin_Expr) line
Generator_System list of generators
--> []
| [Generator | Generator_System]
Grid_Generator
--> grid_point(Lin_Expr) grid point
| grid_point(Lin_Expr, Generator_Denominator)
grid point
| parameter(Lin_Expr) parameter
| parameter(Lin_Expr, Generator_Denominator)
parameter
| grid_line(Lin_Expr) grid line
Grid_Generator_System list of grid generators
--> []
| [Grid_Generator | Grid_Generator_System]
Artificial_Parameter --> Lin_Expr / Coeff
Artificial_Parameter_List --> []
| [Artificial_Parameter | Artificial_Parameter_List]
Atom --> Prolog atom
Universe_or_Empty PPL object
--> universe | empty
Poly_Relation --> is_disjoint with a constraint or congruence
| strictly_intersects with a constraint or congruence
| is_included with a constraint or congruence
| saturates with a constraint or congruence
| subsumes with a (grid) generator
Relation_List --> []
| [Poly_Relation | Relation_List]
Complexity --> polynomial | simplex | any
Vars_Pair --> PPL_Var - PPL_Var map relation
P_Func --> [] list of map relations
| [Vars_Pair | P_Func].
Width --> bits_8 | bits_16 | bits_32 | bits_64 | bits_128
Representation --> unsigned | signed_2_complement
Overflow --> overflow_wraps | overflow_undefined | overflow_impossible
Optimization_Mode --> max | min
Problem_Status --> unfeasible
| unbounded
| optimized
Control_Parameter_Name --> pricing for MIP problems
| control_strategy for PIP problems
| pivot_row_strategy for PIP problems
--> pricing_steepest_edge_float
| pricing_steepest_edge_exact
| pricing_textbook
| control_strategy_first
| control_strategy_deepest
| control_strategy_all
| pivot_row_strategy_first
| pivot_row_strategy_max_column
Vars_List --> [] list of PPL variables
| [PPL_Var | Vars_List].

## Predicate Descriptions

Below is a short description of many of the interface predicates. For full definitions of terminology used here, see the main PPL user manual.

### Domain Independent Predicates

First we describe the domain independent predicates that are included with all instantiations of the Prolog interfaces.

 ppl_version_major(?C_int)
Unifies C_int with the major number of the PPL version.

 ppl_version_minor(?C_int)
Unifies C_int with the minor number of the PPL version.

 ppl_version_revision(?C_int)
Unifies C_int with the revision number of the PPL version.

 ppl_version_beta(?C_int)
Unifies C_int 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_Coefficient_bits(?Bits)

Unifies Bits with the number of bits used to encode a Coefficient in the C++ interface; 0 if unbounded.

 ppl_Coefficient_is_bounded

Succeeds if and only if the Coefficients in the C++ interface are bounded.

 ppl_Coefficient_max(Max)

If the Coefficients in the C++ interface are bounded, then the maximum coefficient the C++ interface can handle is unified with Max. If the Prolog system cannot handle this coefficient, then an exception is thrown. It fails if the Coefficients in the C++ interface are unbounded.

 ppl_Coefficient_min(Min)

If the Coefficients in the C++ interface are bounded, then the minimum coefficient the C++ interface can handle is unified with Min. If the Prolog system cannot handle this coefficient, then an exception is thrown. It fails if the Coefficients in the C++ interface are unbounded.

 ppl_max_space_dimension(?Dimension_Type)

Unifies Dimension_Type 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(+Csecs)

Computations taking exponential time will be interrupted some time after Csecs centiseconds after that call. If the computation is interrupted that way, the current timeout exception atom will be thrown. Csecs must be strictly greater than zero.

 ppl_reset_timeout

Resets the timeout time so that the computation is not interrupted.

 ppl_set_deterministic_timeout(+Unscaled_Weight, +Scale)

Computations taking exponential time will be interrupted some time after reaching the complexity threshold . If the computation is interrupted that way, the current timeout exception atom will be thrown. Unscaled_Weight must be strictly greater than zero; Scale must be non-negative; an exception is thrown if the computed weight threshold exceeds the maximum allowed value.

NOTE: This "timeout" checking functionality is said to be deterministic because it is not based on actual elapsed time. Its behavior will only depend on (some of the) computations performed in the PPL library and it will be otherwise independent from the computation environment (CPU, operating system, compiler, etc.). The weight mechanism is under beta testing: client applications should be ready to reconsider the tuning of these weight thresholds when upgrading to newer version of the PPL.

 ppl_reset_deterministic_timeout

Resets the deterministic timeout so that the computation is not interrupted.

 ppl_set_rounding_for_PPL

Sets the FPU rounding mode so that the PPL abstractions based on floating point numbers work correctly. This is performed automatically at initialization-time. Calling this function is needed only if restore_pre_PPL_rounding() has previously been called.

 ppl_restore_pre_PPL_rounding

Sets the FPU rounding mode as it was before initialization of the PPL. After calling this function it is absolutely necessary to call set_rounding_for_PPL() before using any PPL abstractions based on floating point numbers. This is performed automatically at finalization-time.

 ppl_irrational_precision(?Precision)

Unifies Precision with the precision parameter for irrational calculations.

 ppl_set_irrational_precision(+Precision)

Sets the precision parameter for irrational calculations to Precision. In the following irrational calculations returning an unbounded rational (e.g., when computing a square root), the lesser between numerator and denominator will be limited to 2**Precision.

### Predicates for MIP_Problem

Here we describe the predicates available for PPL objects defining mixed integer (linear) programming problems.

 ppl_new_MIP_Problem_from_space_dimension(+Dimension_Type, -Handle)

Creates an MIP Problem with the feasible region the vector space of dimension Dimension_Type, objective function and optimization mode max. Handle is unified with the handle for .

 ppl_new_MIP_Problem(+Dimension_Type, +Constraint_System, +Lin_Expr, +Optimization_Mode, -Handle)

Creates an MIP Problem with the feasible region the vector space of dimension Dimension_Type, represented by Constraint_System, objective function Lin_Expr and optimization mode Optimization_Mode. Handle is unified with the handle for .

 ppl_new_MIP_Problem_from_MIP_Problem(+Handle_1, -Handle_2)

Creates an MIP Problem from the MIP Problem referenced by Handle_1. Handle_2 is unified with the handle for .

 ppl_MIP_Problem_swap(+Handle_1, +Handle_2)

Swaps the MIP Problem referenced by Handle_1 with the one referenced by Handle_2.

 ppl_delete_MIP_Problem(+Handle)

Deletes the MIP Problem referenced by Handle. After execution, Handle is no longer a valid handle for a PPL MIP Problem.

 ppl_MIP_Problem_space_dimension(+Handle, ?Dimension_Type)

Unifies the dimension of the vector space in which the MIP Problem referenced by Handle is embedded with Dimension_Type.

 ppl_MIP_Problem_integer_space_dimensions(+Handle, ?Vars_List)

Unifies Vars_List with a list of variables representing the integer space dimensions of the MIP Problem referenced by Handle.

 ppl_MIP_Problem_constraints(+Handle, -Constraint_System)

Unifies Constraint_System with a list of the constraints in the constraints system representing the feasible region for the MIP Problem referenced by Handle.

 ppl_MIP_Problem_objective_function(+Handle, ?Lin_Expr)

Unifies Lin_Expr with the objective function for the MIP Problem referenced by Handle.

 ppl_MIP_Problem_optimization_mode(+Handle, ?Optimization_Mode)

Unifies Optimization_Mode with the optimization mode for the MIP Problem referenced by Handle.

 ppl_MIP_Problem_clear(+Handle)

Resets the MIP problem referenced by Handle to be the trivial problem with the feasible region the -dimensional universe, objective function and optimization mode max.

 ppl_MIP_Problem_add_space_dimensions_and_embed( +Handle, +Dimension_Type)

Embeds the MIP problem referenced by Handle in a space that is enlarged by Dimension_Type dimensions.

 ppl_MIP_Problem_add_to_integer_space_dimensions(+Handle, +Vars_List)

Updates the MIP Problem referenced by Handle so that the variables in Vars_List are added to the set of integer space dimensions.

 ppl_MIP_Problem_add_constraint(+Handle, +Constraint)

Updates the MIP Problem referenced by Handle so that the feasible region is represented by the original constraint system together with the constraint Constraint.

 ppl_MIP_Problem_add_constraints(+Handle, +Constraint_System)

Updates the MIP Problem referenced by Handle so that the feasible region is represented by the original constraint system together with all the constraints in Constraint_System.

 ppl_MIP_Problem_set_objective_function(+Handle, +Lin_Expr)

Updates the MIP Problem referenced by Handle so that the objective function is changed to Lin_Expr.

 ppl_MIP_Problem_set_control_parameter(+Handle, +Control_Parameter_Value)

Updates the MIP Problem referenced by Handle so that the value for the relevant control parameter name is changed to Control_Parameter_Value.

 ppl_MIP_Problem_get_control_parameter(+Handle, +Control_Parameter_Name, ?Control_Parameter_Value)

Unifies Control_Parameter_Value with the value of the control parameter Control_Parameter_Name.

 ppl_MIP_Problem_set_optimization_mode(+Handle, +Optimization_Mode)

Updates the MIP Problem referenced by Handle so that the optimization mode is changed to Optimization_Mode.

 ppl_MIP_Problem_is_satisfiable(+Handle)

Succeeds if and only if the MIP Problem referenced by Handle is satisfiable.

 ppl_MIP_Problem_solve(+Handle, ?MIP_Problem_Status)

Solves the MIP problem referenced by Handle and unifies MIP_Problem_Status with: unfeasible, if the MIP problem is not satisfiable; unbounded, if the MIP problem is satisfiable but there is no finite bound to the value of the objective function; optimized, if the MIP problem admits an optimal solution.

 ppl_MIP_Problem_feasible_point(+Handle, ?Generator)

Unifies Generator with a feasible point for the MIP problem referenced by Handle.

 ppl_MIP_Problem_optimizing_point(+Handle, ?Generator)

Unifies Generator with an optimizing point for the MIP problem referenced by Handle.

 ppl_MIP_Problem_optimal_value(+Handle, ?Coeff_1, ?Coeff_2)

Unifies Coeff_1 and Coeff_2 with the numerator and denominator, respectively, for the optimal value for the MIP problem referenced by Handle.

 ppl_MIP_Problem_evaluate_objective_function(+Handle, +Generator, ?Coeff_1, ?Coeff_2)
Evaluates the objective function of the MIP problem referenced by Handle at point Generator. Coefficient_1 is unified with the numerator and Coefficient_2 is unified with the denominator of the objective function value at Generator.

 ppl_MIP_Problem_OK(+Handle)

Succeeds only if the MIP Problem referenced by Handle is well formed, i.e., if it satisfies all its implementation invariants. Useful for debugging purposes.

 ppl_MIP_Problem_ascii_dump(+Handle)

Dumps an ascii representation of the PPL internal state for the MIP problem referenced by Handle on the standard output.

### Predicates for PIP_Problem

Here we describe some functions available for PPL objects defining parametric integer programming problems.

 ppl_new_PIP_Problem_from_space_dimension(+Dimension_Type, -Handle)

Creates a PIP Problem with the feasible region the vector space of dimension dimension, empty constraint_system and empty set of parametric variables. Handle is unified with the handle for .

 ppl_new_PIP_Problem_from_PIP_Problem(+Handle_1, -Handle_2)
Creates a PIP Problem from the PIP Problem referenced by Handle_1. Handle_2 is unified with the handle for .

 ppl_new_PIP_Problem(+Dimension_Type, +Constraint_System, +Vars_List, -Handle)

Creates a PIP Problem having space dimension dimension, a feasible region represented by constraint_system and parametric variables represented by Vars_List. Handle is unified with the handle for .

 ppl_PIP_Problem_swap(+Handle_1, +Handle_2)
Swaps the PIP Problem referenced by Handle_1 with the one referenced by Handle_2.

 ppl_delete_PIP_Problem(+Handle)
Deletes the PIP Problem referenced by Handle. After execution, Handle is no longer a valid handle for a PPL PIP Problem.

 ppl_PIP_Problem_space_dimension(+Handle, ?Dimension_Type)
Unifies the dimension of the vector space in which the PIP Problem referenced by Handle is embedded with Dimension_Type.

 ppl_PIP_Problem_parameter_space_dimensions(+Handle, ?Vars_List)
Unifies Vars_List with a list of variables representing the parameter space dimensions of the PIP Problem referenced by Handle.

 ppl_PIP_Problem_constraints(+Handle, ?Constraint_System)
Unifies Constraint_System with a list of the constraints in the constraints system representing the feasible region for the PIP Problem referenced by Handle.

 ppl_PIP_Problem_get_control_parameter(+Handle, +Control_Parameter_Name, ?Control_Parameter_Value)

Unifies Control_Parameter_Value with the value of the control parameter Control_Parameter_Name.

 ppl_PIP_Problem_clear(+Handle)
Resets the PIP problem referenced by Handle to be the trivial problem with the feasible region the -dimensional universe.

 ppl_PIP_Problem_add_space_dimensions_and_embed( +Handle, +Dimension_Type1, +Dimension_Type2)
Embeds the PIP problem referenced by handle in a space that is enlarged by dimension1 non-parameter dimensions and dimension2 parameter dimensions.

 ppl_PIP_Problem_add_to_parameter_space_dimensions(+Handle, +Vars_List)
Updates the PIP Problem referenced by Handle so that the variables in Vars_List are added to the set of parameter space dimensions.

 ppl_PIP_Problem_add_constraint(+Handle, +Constraint)
Updates the PIP Problem referenced by Handle so that the feasible region is represented by the original constraint system together with the constraint Constraint.

 ppl_PIP_Problem_add_constraints(+Handle, +Constraint_System)
Updates the PIP Problem referenced by Handle so that the feasible region is represented by the original constraint system together with all the constraints in Constraint_System.

 ppl_PIP_Problem_set_control_parameter(+Handle, +Control_Parameter_Value)

Updates the PIP Problem referenced by Handle so that the value for the relevant control parameter name is changed to Control_Parameter_Value.

 ppl_PIP_Problem_is_satisfiable(+Handle)
Succeeds if and only if the PIP Problem referenced by Handle is satisfiable.

 ppl_PIP_Problem_solve(+Handle, ?PIP_Problem_Status)
Solves the PIP problem referenced by Handle and unifies PIP_Problem_Status with: unfeasible, if the PIP problem is not satisfiable; optimized, if the PIP problem admits an optimal solution.

 ppl_PIP_Problem_solution(+Handle1, ?Handle2)
Solves the PIP problem referenced by Handle1 and creates a PIP tree node representing this a solution if it exists and bottom otherwise Handle_2 is unified with the handle for .

 ppl_PIP_Problem_optimizing_solution(+Handle, ?PIP_Tree_Node)
Solves the PIP problem referenced by Handle1 and creates a PIP tree node representing this an optimizing solution if a solution exists and bottom otherwise Handle_2 is unified with the handle for .

 ppl_PIP_Problem_has_big_parameter_dimension(+Handle, +Dimension_Type)
Succeeds if and only if the PIP Problem referenced by Handle has a dimension dim for the big parameter and Dimension_Type unifies with dim.

 ppl_PIP_Problem_set_big_parameter_dimension(+Handle, +Dimension_Type)

Updates the PIP Problem referenced by Handle so that the dimension for the big parameter is Dimension_Type.

 ppl_PIP_Problem_OK(+Handle)
Succeeds only if the PIP Problem referenced by Handle is well formed, i.e., if it satisfies all its implementation invariants. Useful for debugging purposes.

ppl_PIP_Problem_ascii_dump(+Handle)
Dumps an ascii representation of the PPL internal state for the PIP problem referenced by Handle on the standard output.

 ppl_PIP_Tree_Node_constraints(+Handle, ?Constraint_System)
Unifies Constraint_System with a list of the parameter constraints in the PIP tree node referenced by Handle.

 ppl_PIP_Tree_Node_is_solution(+Handle)
Succeeds if and only if handle represents a solution node.

 ppl_PIP_Tree_Node_is_decision(+Handle)
Succeeds if and only if handle represents a decision node.

 ppl_PIP_Tree_Node_is_bottom(+Handle)
Succeeds if and only if handle represents bottom.

 ppl_PIP_Tree_Node_artificials(+Handle, ?Artificial_Parameter_List)
Unifies Artificial_Parameter_List with a list of the artificial parameters in the PIP tree node referenced by Handle.

 ppl_PIP_Tree_Node_OK(+Handle)
Succeeds only if the PIP tree node referenced by Handle is well formed, i.e., if it satisfies all its implementation invariants. Useful for debugging purposes.

 ppl_PIP_Tree_Node_parametric_values(+Handle, +Var, ?Lin_Expr)
Unifies Lin_Expr with a linear expression representing the values of problem variable Var in the solution node represented by Handle. The linear expression may involve problem parameters as well as artificial parameters.

 ppl_PIP_Tree_Node_true_child(+Handle1, ?Handle2)
If the PIP_Tree_Node represented by Handle1 is a decision node unifies the PIP tree node referenced by Handle2 with the child on the true branch of the PIP tree node represented by Handle1. An exception is thrown if this is not a decision node.

 ppl_PIP_Tree_Node_false_child(+Handle1, ?Handle2)
If the PIP_Tree_Node represented by Handle1 is a decision node unifies the PIP tree node referenced by Handle2 with the child on the false branch of the PIP tree node represented by Handle1. An exception is thrown if this is not a decision node.