Sometimes basic constraint propagation does not find a solution to a set of constraints with integer variables:
?- X + Y #= 10, X - Y #= 2. 2+Y#=X, X+Y#=10.
In this situation we may ask Prolog's constraint solver to look for a solution. The predicate label(+Vars) asks it to find integer solutions for all variables in Vars. It works only if variables are known to be in a given finite range:
?- X + Y #= 10, X - Y #= 2, [X, Y] ins -1000 .. 1000, label([X, Y]). X = 6, Y = 4.
Sometimes label may be slow if it must search through a
large range of integers for solutions. The predicate labeling(+Opts,
+Vars) is similar, but lets you specify one or more options
that affect its search strategy. The bisect option asks
it to perform a binary search, and lets us solve the above equations
quickly even if the integer range is very large:
?- X + Y #= 10, X - Y #= 2, [X, Y] ins -1_000_000_000 .. 1_000_000_000, labeling([bisect], [X, Y]). X = 6, Y = 4
Prolog's constraint solver is powerful, and may be sometimes able to solve constraint systems with hundreds or thousands of variables.
In some constraint
satisfaction problems the predicate all_distinct(+Vars)
is useful. It says that all variables in the given list have distinct
integer values:
?- length(L, 5), ins(L, 1..5), all_distinct(L), label(L). L = [1, 2, 3, 4, 5] ; L = [1, 2, 3, 5, 4] ; L = [1, 2, 4, 3, 5] ; L = [1, 2, 4, 5, 3] ; L = [1, 2, 5, 3, 4] ...
Here's a functional stack, which is trivial to implement in Prolog.
% S is an empty stack. empty_stack(stack([])). % We can push X onto S to make the stack T. push(X, stack(S), stack([X | S])). % We can pop X from S to make the stack T. pop(X, stack([X | S]), stack(S)).
We can push N numbers onto an empty stack using recursion:
% S is the empty stack with the numbers 1 .. N pushed onto it. push_to_n(0, S) :- empty_stack(S). push_to_n(N, S) :- N #> 0, N1 #= N - 1, push_to_n(N1, S1), push(N, S1, S).
Or using foldl:
push_to_n2(N, S) :- empty_stack(E), numlist(1, N, NL),
foldl(push, NL, E, S).Here is a naive functional queue:
% empty_queue(Q) - Q is an empty queue empty_queue([]). % enqueue(X, Q, R) - we can enqueue X onto Q to make R enqueue(X, Q, R) :- append(Q, [X], R). % dequeue(X, Q, R) - we can dequeue X from Q to make R dequeue(X, [X | R], R).
It's inefficient: enqueue runs in O(N).
As we discussed in class, a clever implementation of a functional queue uses two stacks.
% back / front stacks empty_queue([] / []). % enqueue(X, Q, R) enqueues X onto Q to make R, pushing X to the back stack. enqueue(X, L / M, [X | L] / M). % dequeue(X, Q, R) dequeues X from Q to make R. It pops from the front stack % if it's non-empty, otherwise reverses the back stack and moves it to the front. dequeue(X, L / [X | M], L / M). dequeue(X, L / [], [] / M) :- reverse(L, [X | M]).
With this implementation,
enqueue
runs in O(1), and dequeue
runs in O(1) on average.
We can represent an empty binary tree as the atom 'nil', and a non-empty tree as t(L, X, R), where X is the value in the root node and L and R are left and right subtrees.
% true if N is contained in the binary search tree T. tree_member(N, nil) :- false. tree_member(N, t(_, N, _)). tree_member(N, t(L, X, R)) :- N #< X, tree_member(N, L). tree_member(N, t(L, X, R)) :- N #> X, tree_member(N, R). % tree_insert(N, T, U) is % true if we can insert N into the binary search tree T to produce the tree U. % A duplicate value is not inserted. tree_insert(N, nil, t(nil, N, nil)). tree_insert(N, t(L, N, R), t(L, N, R)). tree_insert(N, t(L, X, R), t(L1, X, R)) :- N #=< X, tree_insert(N, L, L1). tree_insert(N, t(L, X, R), t(L, X, R1)) :- N #>= X, tree_insert(N, R, R1).
The cut operator !
causes Prolog to commit to
all choices that it has already made in the current predicate. In
other words, it will not explore previous choice points looking for
more solutions:
?- (X = 3; X = 4, !; X = 5). X = 3 ; X = 4. ?- (Z = 1; Z = 2), (X = 3; X = 4, !; X = 5). Z = 1, X = 3 ; Z = 1, X = 4.
It will, however, continue to explore choices that appear to the right of the cut:
?- (X = 3; X = 4, !; X = 5), (Y = 10; Y = 20). X = 3, Y = 10 ; X = 3, Y = 20 ; X = 4, Y = 10 ; X = 4, Y = 20.
We can use the cut to write some predicates more simply if we know that certain arguments will always be instantiated. For example, consider this predicate:
kind(N, negative) :- N #< 0. kind(N, small) :- N #>= 0, N #< 100. kind(N, big) :- N #>= 100.
If we know that N will be instantiated, we can rewrite it as
kind2(N, negative) :- N #< 0, !. kind2(N, small) :- N #< 100, !. kind2(N, big).
However, queries involving N may now produce answers that are incorrect:
?- kind2(N, big). true.
The preceding answer would seem to indicate that all N are big, but that is not true. Furthermore, if a predicate uses the cut then answers may depend on goal order:
?- N = 10, kind2(N, K). N = 10, K = small. ?- kind2(N, K), N = 10. false.
In other words, the cut does not belong to the language's pure logical core, and so using it has several consequences:
Any predicate using the cut will probably not run in both directions.
Any predicate using the cut will probably return incomplete results for some queries.
In any predicate using the cut, reordering goals may change the results of a query.
By contrast, if you use only pure language features (including dif
and integer constraints), then
Any predicate will run in both directions at least theoretically (though it may sometimes fail to terminate).
Any query that terminates will always return results that are logically complete.
Reordering goals may affect termination, but will never change the results of a query.
The if-then-else operator
(P → Q ; R) is defined as P, !, Q; R.
The not operator
(\+ P) is defined as P, !, false; true, or
(equivalently using the if/then/else operator) as P → false
; true.
Because these operators are defined using the cut, they also do not belong to the pure core language, and using them will also probably result in programs that do not run in all directions and/or return incorrect results for some queries.
Is using the cut, or the
\+ operator,
worth it? It is up to you, but you should understand what you are
giving up by using these features. In this course, I have emphasized
the pure logical features of Prolog since it seems to me that that is
where Prolog shines the most. For example, I know of no other
mainstream language that can run matrix multiplication backwards to
yield matrix inversion.
At the same time, if a predicate will only be used in one direction, the cut really does no harm.