Constraint programming over rationals

Author(s): Christian Holzbaur, Daniel Cabeza, Samir Genaim (Meta-programming predicates).

Note: This package is currently being adapted to the new characteristics of the Ciao module system. This new version works right now with limitations, but it is under further development at the moment. Use with (lots of) caution.


Usage and interface

  • Library usage:
    :- use_package(clpq). or :- module(...,...,[clpq]).
  • New operators defined:
    .=./2 [700,xfx], .<>./2 [700,xfx], .<./2 [700,xfx], .=<./2 [700,xfx], .>./2 [700,xfx], .>=./2 [700,xfx].

Other information

Some CLP(Q) examples

(Other examples can be found in the source and library directories.)

  • 'Reversible' Fibonacci (clpq):

:- module(_, [fib/2], []).
:- use_package(clpq).

fib(X,Y):- X .=. 0, Y .=. 0.
fib(X,Y):- X .=. 1, Y .=. 1.
fib(N,F) :-
        N .>. 1,
        N1 .=. N - 1,
        N2 .=. N - 2,
        fib(N1, F1),
        fib(N2, F2),
        F .=. F1+F2.

  • Matrix multiplication (clpq):

:- use_package(clpq).
:- use_module(library(write)).

mmultiply([],_,[]).
mmultiply([V0|Rest], V1, [Result|Others]):-  
            mmultiply(Rest, V1, Others),
    	    multiply(V1,V0,Result).

multiply([],_,[]).
multiply([V0|Rest], V1, [Result|Others]):-  
            multiply(Rest, V1, Others),
    	    vmul(V0,V1,Result).

vmul([],[],0).
vmul([H1|T1], [H2|T2], Result):- 
	vmul(T1,T2, Newresult), 
	Result .=. H1*H2+Newresult.

matrix(1,[[1,2,3,4,5],[4,0,-1,5,6],[7,1,-2,8,9],[-1,0,1,3,2],[1,5,-3,2,4]]).
matrix(2,[[3,2,1,0,-1],[-2,1,3,0,2],[1,2,0,-1,5],[1,3,2,4,5],[-5,1,4,2,2]]).

%% Call with: ?- go(M).

go(M):-
        matrix(1,M1),
        matrix(2,M2), 
        mmultiply(M1, M, M2).

  • Queens (clpq):

:- use_package(clpq).

queens(N, Qs) :- constrain_values(N, N, Qs), place_queens(N, Qs).

constrain_values(0, _N, []).
constrain_values(N, Range, [X|Xs]) :-
        N .>. 0, X .>. 0, X .=<. Range, 
        N1 .=. N - 1,
        constrain_values(N1, Range, Xs), no_attack(Xs, X, 1).

no_attack([], _Queen, _Nb).
no_attack([Y|Ys], Queen, Nb) :-
        Queen .<>. Y+Nb,
        Queen .<>. Y-Nb,
        Nb1 .=. Nb + 1,
        no_attack(Ys, Queen, Nb1).

place_queens(0, _).
place_queens(N, Q) :- 
	N > 0, member(N, Q), N1 is N-1, place_queens(N1, Q).

Meta-programming with CLP(Q)

The implementation of CLP(Q) in Ciao compiles the constraints in the program to a sequence of calls to the underlying constraints solver (at compile-time). This results in efficient implementation, since the structure of the constraints is processed only at compile-time, but requires the constraints to be known at static time which can be a limitation for metaprogramming-based applications such as static program analyzers. For example, the call:

  ?- X=(A+B), Y=(C-D), X .>. Y.

  no

fails because X .>. Y is translated first to a sequence of calls that require (when they invoked) X and Y to be either numbers or free variables. To overcome this limitation, you can use clp_meta/1 which delays the translation of the constraints from compile-time to run-time (i.e., when clp_meta/1 is called), For example:

?- X=(A+B),Y=(C-D), clp_meta([X .>. Y]).

X = A+B,
Y = C-D,
C.<.D+A+B ?

The argument of clp_meta/1 accepts a goal or lists of goals, where each goal is limited to conjunctions, disjunctions, or CLP(Q) constraints. Other operations on constraints which are extensively used in meta-programming, in particular in static program analysis, are projection and entailment check. The projection operation restricts the constraints (that are available in the store) to a given set of variables and turns the answer into terms. You can use the multifile predicate dump_constraints/3 for that purpose:

?- A .>. C, C .>. B, dump_constraints([A,B],[X,Y],Cs).

Cs = [X.>.Y],
C.>.B,
C.<.A ?

?- C=(B+D), clp_meta([A .>. C, D .>. 0]), dump_constraints([A,B],[X,Y],Cs).

C = B+D,
Cs = [Y.<.X],
D.<. -B+A,
D.>.0 ?

The entailment check is used to check if a list of constrains is entailed by the store. You can use the predicate clp_entailed/1 for that purpose:

?- A .>. C, C .>. B, B .>. D, clp_entailed([ A .>. B, A .>. D]).

B.>.D,
C.>.B,
C.<.A ?

yes

?- A .>=. B, clp_entailed([ A .>. B ]).

no


Known bugs and planned improvements

  • clp(Q) and clp(R) cannot be used simultaneously in the same program, or even within the same toplevel session.