Concepts of Programming Languages

16.7 Deficiencies of Prolog 751

Suppose we need to be able to determine whether a given symbol is in a

given list. A straightforward Prolog description of this is

member(Element, [Element | _]).

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

The underscore indicates an “anonymous” variable; it is used to mean

that we do not care what instantiation it might get from unification. The first

statement in the previous example succeeds if Element is the head of the list,

either initially or after several recursions through the second statement. The

second statement succeeds if Element is in the tail of the list. Consider the

following traced examples:

trace.

member(a, [b, c, d]).

(1) 1 Call: member(a, [b, c, d])?

(2) 2 Call: member(a, [c, d])?

(3) 3 Call: member(a, [d])?

(4) 4 Call: member(a, [])?

(4) 4 Fail: member(a, [])

(3) 3 Fail: member(a, [d])

(2) 2 Fail: member(a, [c, d])

(1) 1 Fail: member(a, [b, c, d])

no

member(a, [b, a, c]).

(1) 1 Call: member(a, [b, a, c])?

(2) 2 Call: member(a, [a, c])?

(2) 2 Exit: member(a, [a, c])

(1) 1 Exit: member(a, [b, a, c])

yes

16.7 Deficiencies of Prolog

Although Prolog is a useful tool, it is neither a pure nor a perfect logic pro-

gramming language. This section describes some of the problems with Prolog.

16.7.1 Resolution Order Control

Prolog, for reasons of efficiency, allows the user to control the ordering of pat-

tern matching during resolution. In a pure logic programming environment,

the order of attempted matches that take place during resolution is nondeter-

ministic, and all matches could be attempted concurrently. However, because

Prolog always matches in the same order, starting at the beginning of the data-

base and at the left end of a given goal, the user can profoundly affect efficiency