Prolog Language Using Modern Prolog CLP(FD) for integer arithmetic
Example
Traditionally Prolog performed arithmetic using the is and =:= operators. However, several current Prologs offer CLP(FD) (Constraint Logic Programming over Finite Domains) as a cleaner alternative for integer arithmetic. CLP(FD) is based on storing the constraints that apply to an integer value and combining those together in memory.
CLP(FD) is an extension in most Prologs that support it, so must be loaded explicitly. Once it is loaded, the #= syntax can take the place of both is and =:=. For example, in SWI-Prolog:
?- X is 2+2.
X = 4.
?- use_module(library(clpfd)).
?- X #= 2+2.
X = 4.
Unlike is, #= is able to solve simple equations and unify in both directions:
?- 4 is 2+X.
ERROR: is/2: Arguments are not sufficiently instantiated
?- 4 #= 2+X.
X = 2.
CLP(FD) provides its own generator syntax.
?- between(1,100,X).
X = 1;
X = 2;
X = 3...
?- X in 1..100.
X in 1..100.
Note that the generator does not actually run: only the range constraint is stored, ready for later constraints to be combined with it. The generator can be forced to run (and brute force constraints) using the label predicate:
?- X in 1..100, label([X]).
X = 1;
X = 2;
X = 3..
Using CLP can allow some intelligent reduction of brute force cases. For example, using old-style integer arithmetic:
?- trace.
?- between(1,10,X), Y is X+5, Y>10.
...
Exit: (8) 6 is 1+5 ? creep
Call: (8) 6 > 10 ? creep
...
X = 6, Y = 11; ...
Prolog still loops through the values 1-5 even though it is mathematically provable from the given conditions that these values cannot be useful. Using CLP(FD):
?- X in 1..10, Y #= X+5, Y #> 10.
X is 6..10,
X+5 #= Y,
Y is 11..15.
CLP(FD) immediately does the maths and works out the available ranges. Adding label([Y]) will cause X to loop only through the useful values 6..10. In this toy example, this does not increase performance because with such a small range as 1-10, the algebra processing takes as long as the loop would have done; but when a larger range of numbers are being processed this may valuably reduce computation time.
Support for CLP(FD) is variable between Prologs. The acknowledged best development of CLP(FD) is in SICStus Prolog, which is commercial and expensive. SWI-Prolog and other open Prologs often have some implementation. Visual Prolog does not include CLP(FD) in its standard library, although extension libraries for it are available.
