Package jpaul.Constraints

Generic solver for inequality constraints over lattices.


Interface Summary
SolAccessor<V extends Var<Info>,Info> SolAccessor provides access to the values of the variables from a system of constraints.
SolReader<V extends Var<Info>,Info> SolReader provides read-only access to the (possibly partial) solution of a system of constraints.

Class Summary
Constraint<V extends Var<Info>,Info> Constraint models a constraint between several variables.
ConstraintSystem<V extends Var<Info>,Info> ConstraintSystem is an efficient solver for a system of constraints.
CtConstraint<V extends Var<Info>,Info> CtConstraint models a constraint of the form "constant ct is less than the value of the variable vd".
LtConstraint<V extends Var<Info>,Info> LtConstraint models a "less than" constraint: the value of variable vs is smaller than the value of variable vd, according to the order relation from the corresponding lattice.
Var<Info> Var models a variable from a system of constraints.

Package jpaul.Constraints Description

Generic solver for inequality constraints over lattices.

This package provides a generic way of modeling and solving systems of inequality constraints over lattices. This package deals with constraints of the form

f(vi_1,vi_2,...,vi_m) <= <vo_1,vo_2,...,vo_n>
where the ordering relation <= is specific to the relevant lattices. The function f is not defined in a specialized declarative language: instead, it is defined as a Java method that reads the values of the input variables vi_1, ..., vi_m, computes some values, and finally joins the computed values to the output variables vo_1, ..., vo_m; the constraints access the values of the variables through a well-defined interface (SolAccessor). The programmer can define new constraints by subclassing the Constraint class.

A system of constraints may involve variables that take values in different lattices: e.g., the values of some variables are sets of atoms, while the values of some other variables are binary relations between atoms. As such, this package generalizes usual set constraint solvers. Of course, specialized set solvers may be much faster and you are encouraged to take a look over them too.

The essential classes from this package are

Classes from this package are parameterized over the type of variables (always a subtype of Var) and the common supertype of the classes representing the value lattices (in the extreme case, if there is no better supertype, this type parameter can be Object). If we have several value lattices, certain type errors cannot be detected statically: e.g., a constraint that states that a binary relation is included in a set of atoms will trigger a dynamic exception. The program should be careful about this aspect when writting constraints.

To use this package, the programmer must follow the following steps

  1. Write one subclass of Var for each kind of variables: e.g., one subclass for the variables that have set values and one subclass for the variables that have relation values. The essential point here is to define the lattice-related operations copy and join. In addition, it is usually a good idea to add some debug information; e.g., override the default Var.toString method.
  2. If necessary, write one subclass of Constraint for each kind of constraints. This package already contains two very basic kinds of constraints (CtConstraint and LtConstraint), but you usually need to define your own constraints too. Here is a sample constraint implementation: simplified SetConstraints.IntersectConstraint.
  3. Construct a collection of constraints and use ConstraintSystem to solve them. [ ConstraintSystem works in two steps: first, it computes some data structures that allow the efficient computation of a fixed-point solution; next, we can solve it several times, at different moments in time: if some of the constraints use external values that change, the solutions may be different. So, ConstraintSystem is an optimized constraint system schema that can be efficiently solved several times. ]

Alexandru Salcianu -
See Also:

Copyright 2005 Alexandru Salcianu -