Previous Table of Contents Next


6.2.8.3. Some Subtleties of the Execution Model

The Prolog execution model as given is a simplification in several ways:

  In matching a predicate call to a clause (as in solve_clause), Prolog actually renames the variables in the clause so that they do not clash with the variables in the actual query. The variables in the clauses are not intended to be the same as the ones in the query! This is particularly important with recursive calls because otherwise, the same variables would come up again and again.
  We need to keep track of the substitution of values for variables that is being built up, in order to report it to the user. I could have listed this as another parameter, but for simplicity, I have omitted that parameter in the pseudocode I presented.
  In solve_eq, we should make sure that a term that is being substituted for a variable does not contain an occurrence of variable somewhere within it. For instance, there is no substitution for X that makes the query X = [a,X] true. Most Prolog implementations actually do not do this “occurs check” for efficiency reasons. Although it is seldom a problem, we should still do it to be strictly in accord with logic.
  The execution model does not take into account some of the features we will look at later, such as function symbols and negation. Computations involving these features are described as they come up.

The algorithm as presented looks very inefficient because when substituting a variable by another term, we go through the rest of the query looking for all occurrences. Of course, real implementations don’t do this. Rather, occurrences of variables are represented as pointers to structures, and only those structures are changed.

What about the output predicates write and nl that we met in section 6.2.1? These are handled by Prolog in a straightforward way: When a write or nl is the first atom in a query, the system simply does the output action and goes on evaluating the rest of the query. Consider the query member([a,b], X), write(‘Trying ‘), write(X), nl, X=b. The substitutions returned by Prolog are exactly the same as those in the example of section 6.2.8.1 because the output predicates have no effect on variables. The output of the query is

   Trying a
   Trying b
   X = b ?

After the system backtracked to try the second clause of member again, it executed the write and nl atoms again, producing two outputs. The other I/O predicates of Prolog (which we will meet in section 6.3.5) behave in a similar way.

We can use these imperative features to debug programs in Prolog if we want. However, if your Prolog has an interactive debugger (the most common kind is described in section 6.3.8), it is probably better to use that because the output from a backtracking program is difficult to follow. It is better to use Prolog’s I/O system for interacting with the user.

6.3. More Advanced Features

This section deals with some of the most important advanced features of Prolog. The logic and control constructs we look at here include negation, the Prolog “cut,” the predicates for finding all solutions, and the predicates for manipulating the knowledge base. The forms of terms we explore include numeric terms, function-symbol terms, and strings. We also look at advanced usability features such as the Prolog interactive debugger, definite clause grammars, and operator declarations.

6.3.1. Negation

It is sometimes necessary to state not that a property holds, but that a property does not hold. Prolog provides the negation symbol \+ for doing this. \+ is a prefix operator that we can apply to any atom. For instance, if we want to find a term that is in the list [a,b] but not in the list [b,c], we can do so with the query

   member([a,b], X), \+ member([b,c], X).

The only solution that Prolog returns is a because this is the only element of [a,b] that is not also an element of [b,c]. The \+ operator is of lower precedence than the comma that separates atoms in a goal, so it applies only to the next atom in a comma-separated sequence. Thus the query

   member([a,b], X), \+ member([b,c], X), member([a], X).

would return the same thing. An atom or the negation of an atom is often referred to as a literal.


Previous Table of Contents Next