Did you know ... | Search Documentation: |
Example: Factorial relation |
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.