Did you know ... | Search Documentation: |

Example: Factorial relation |

- Documentation
- Reference manual
- The SWI-Prolog library
- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
- Introduction
- Arithmetic constraints
- Declarative integer arithmetic
- Example: Factorial relation
- Combinatorial constraints
- Domains
- Example: Sudoku
- Residual goals
- Core relations and search
- Example: Eight queens puzzle
- Optimisation
- Reification
- Enabling monotonic CLP(FD)
- Custom constraints
- Applications
- Acknowledgments
- CLP(FD) predicate index
- Closing and opening words about CLP(FD)

- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains

- The SWI-Prolog library
- Packages

- Reference manual

We illustrate the benefit of using #=/2 for more generality with a simple example.

Consider first a rather conventional definition of n_factorial/2,
relating each natural number *N* to its factorial *F*:

n_factorial(0, 1). n_factorial(N, F) :- N #> 0, N1 #= N - 1, n_factorial(N1, F1), F #= N * F1.

This program uses CLP(FD) constraints *instead* of low-level
arithmetic throughout, and everything that *would have worked* with
low-level arithmetic *also* works with CLP(FD) constraints,
retaining roughly the same performance. For example:

?- n_factorial(47, F). F = 258623241511168180642964355153611979969197632389120000000000 ; false.

Now the point: Due to the increased flexibility and generality of
CLP(FD) constraints, we are free to *reorder* the goals as follows:

n_factorial(0, 1). n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).

In this concrete case, *termination* properties of the predicate
are improved. For example, the following queries now both terminate:

?- n_factorial(N, 1). N = 0 ; N = 1 ; false. ?- n_factorial(N, 3). false.

To make the predicate terminate if *any* argument is
instantiated, add the (implied) constraint `F #\= 0`

before
the recursive call. Otherwise, the query `n_factorial(N, 0)`

is the only non-terminating case of this kind.

The value of CLP(FD) constraints does *not* lie in completely
freeing us from *all* procedural phenomena. For example, the two
programs do not even have the same *termination properties* in all
cases. Instead, the primary benefit of CLP(FD) constraints is that they
allow you to try different execution orders and apply **declarative
debugging** techniques *at all*! Reordering goals (and
clauses) can significantly impact the performance of Prolog programs,
and you are free to try different variants if you use declarative
approaches. Moreover, since all CLP(FD) constraints *always terminate*,
placing them earlier can at most *improve*, never worsen, the
termination properties of your programs. An additional benefit of
CLP(FD) constraints is that they eliminate the complexity of introducing `(is)/2`

and `(=:=)/2`

to beginners, since *both* predicates are
subsumed by #=/2 when
reasoning over integers.

In the case above, the clauses are mutually exclusive *if* the
first argument is sufficiently instantiated. To make the predicate
deterministic in such cases while retaining its generality, you can use zcompare/3
to *reify* a comparison, making the different cases distinguishable
by pattern matching. For example, in this concrete case and others like
it, you can use `zcompare(Comp, 0, N)`

to obtain as `Comp`
the symbolic outcome (`<`

, `=`

, `>`

)
of 0 compared to N.

Tags are associated to your profile if you are logged in

Tags: