Common Pitfalls

3.9 Common Pitfalls

Prolog is different from conventional programming languages, and a common problem is to program Prolog like a conventional language. Here are some points to note:

Unification is more powerful than normal case discrimination (see section 3.9.1);
Prolog procedure calls are more powerful than conventional procedure calls. In particular, backtracking is possible (see section 3.9.2);

3.9.1 Unification works both ways

One common problem is to write a predicate expecting certain instantiation patterns for the arguments, and then get unexpected results when the arguments do not conform to the expected pattern. An example is the member relation, intended to check if an item Item is a member of a list or not. This might be written as:

member(Item, [Item|_]).
member(Item, [_|List]) :- member(Item, List).

The expected usage assumes both Item and the list are ground. In such cases, the above predicate does indeed check if Item occurs in the list given as a second argument. However, if either of the arguments are not ground, then potentially unexpected behaviour might occur. Consider the case where Item is a variable, then the above predicate will enumerate the elements of the list successively through backtracking. On the other hand, if any of the list elements of the list is a variable, they would be unified with Item. Other instantiation patterns for either arguments can produce even more complex results.

If the intended meaning is simply to check if Item is a member of a list, this can be done by:

  % is_member(+Element, +List)
  % check if Element is an element that occurs in a List of
  % ground elements
is_member(Item, [Element|_]) :- Item == Element.
is_member(Item, [_|List]) :- nonvar(List), is_member(Item, List).

Note the use of comments to make clear the intention of the use of the predicate. The convention used is that ‘+’ indicates that an argument should be instantiated (i.e. not a variable), ‘-’ for an argument that should be an uninstantiated variable, and ’?’ indicates that there is no restrictions on the mode of the argument.

3.9.2 Unexpected backtracking

Remember that when coding in Prolog, any predicate may be backtracked into. So correctness in Prolog requires:

Predicate returns the correct answer when first called.
Predicate behaves correctly when backtracked into.

Recall that backtracking causes alternative choices to be explored, if there are any. Typically another choice corresponds to another clause in the poredicate definition, but alternative choices may come from disjunction (see above) or built-in predicates with multiple (alternative) solutions. The programmer should make sure that a predicate will only produce those solutions that are wanted. Excess alternatives can be removed by coding the program not to produce them, or by the cut, or the conditional.

For example, to return only the first member, in the is_member/2 example, the predicate can be coded using the cut, as follows:

is_member(Item, [Element|_]) :- Item == Element, !.
is_member(Item, [_|List]) :- nonvar(List), is_member(Item, List).

Using conditional

Another way to remove excess choice points is the conditional:

is_member(Item, [Element|List]) :- 
    ( Item == Element ->
        true 
    ;
        nonvar(List), is_member(Item, List)
    ).