CSE 341 - Controlling Search in CLP(R)

Ideally, one could think entirely declaratively, and just write rules and goals within rules in any order. In practice, however, you sometimes need to know about the search order that CLP(R) uses, particularly if you are running a goal "backwards" (i.e., not using it in the same way as the analogous function in say Scheme).

CLP(R) incrementally explores the derivation tree, depth first, and considers rules in the order in which they are written in the program. Sometimes things just work; other times you may need to reorder your rules, or add additional constraints.

As a first example, consider the traditional append relation, but with the rules written in the other order:

append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
append([],Ys,Ys).

This works fine for most things, but if you give the goal append(A,B,C) you get a stack overflow right away -- when you write the rules in the standard way, this works fine (and gives you all of the possible lists A and B that appended together give you C). So for full generality, write the append rules in that order. As a general heuristic, if you've got a recursive rule, write the base case first, unless there is some reason to do otherwise.

Another useful technique is to add additional constraints to the body of the rule. Consider these two versions of the length rule:

/* length of a list, without and with a (usually redundant) constraint that
   the length is non-negative */

not_so_good_length([],0).
not_so_good_length([_|Xs],N) :- not_so_good_length(Xs,N-1).

length([],0).
length([_|Xs],N) :- N>0, length(Xs,N-1).

Both versions work the same for many queries. But if you try length(S,10) to find a list of length 10, length works fine. not_so_good_length gives you one correct answer, but if you backtrack CLP(R) gets a stack overflow, as it looks at longer and longer lists hoping that one of them will have length 10. And if you try length(S,-1) length correctly just says no, but not_so_good_length bombs.

There is nothing mysterious about any of these examples -- if you work through the derivation trees you can see the cases in which CLP(R) gets stuck in an infinite search.

The 'cut' operator

Finally, CLP(R), like Prolog, has a rather crude operator 'cut' (written !) that prunes the search tree, by committing to the choices in the current rule made up to the point you encounter the '!'. You should definitely not use cut in your homework -- it isn't necessary, and may prevent CLP(R) from finding some of the answers. The CLP(R) manual entry for it says "The dreaded cut. As usual, its use is not recommended ...."

However, it can sometimes be useful, and you should know about it if you are to have a reasonable knowledge of logic and constraint programming.

Compare these two versions of the member rule:

/* the standard definition of member */
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).

member_cut(X,[X|Xs]) :- !.
member_cut(X,[Y|Ys]) :- member_cut(X,Ys).

/*
member(1,[1,2,3,1]) will succeed twice
member(X,[1,2,3,1]) will succeed four times.

member_cut(1,[1,2,3,1])   will succeed just once

member_cut(X,[1,2,3]) will only give one answer: X=1.
*/

my_not(X) :- call(X), !, fail.
my_not(X).

(There is a builtin version of 'not'.)

This works correctly if X is ground (i.e. it doesn't contain any variables when you call it), but otherwise won't always give the correct answer. Try these:

not(1=1).
not(1=2).
not(X=1).

Advanced Topic - Details of 'cut'

creatures([squid,octopus]).
creatures([dolphin,whale,porpoise]).

creatures(L), member(C,L).

But if we try this goal:

creatures(L), member_cut(C,L).

C = squid
L = [squid, octopus]

C = dolphin
L = [dolphin, whale, porpoise]