next up previous contents
Next: Calling Patterns Up: The `Reversibility' of Previous: The `Reversibility' of

Evaluation in Prolog

Unlike many programming languages, Prolog does not automatically evaluate `expressions'. For example, in Pascal,

Y := 2 + 1;

the term 2 + 1 is automatically evaluated and Y is assigned the value 3. Here is an attempt to do `the same thing' in Prolog using =/2:
Y = 2 + 1.

with the consequence that the term 2+1 is unevaluated and the term Y is unified with the term 2+1 with the result that Y is bound to 2+1.
Similar problems arise in relation to LISP. LISP will generally seek to evaluate expressions. For example, in
(foo (+ 1 2) 3)

LISP evaluates the term (s-expression) (foo (+ 1 2) 3) by evaluating (+ 1 2) to 3 and then evaluating (foo 3 3). A naive attempt to construct a similar expression in Prolog might look like:

but Prolog does not try to evaluate the term 1+2.

Of course, there are times when evaluation is exactly what is wanted. Sometimes, particularly with arithmetic expressions, we want to evaluate them. A special predicate is/2 is provided. This predicate can be used as in:

Y is 2 + 1.

In this case, the term 2+1 is evaluated to 3 and Y is unified with this term resulting in Y being bound to 3.

We can use is/2 to implement a successor relation:


Y is X + 1.

where it is intended that successor/2 takes the first argument as input and outputs the second argument which is to be the next largest integer.

In the above, note that X + 1 is intended to be evaluated.

This means that you must use the stated calling pattern as to try to solve the goal successor(X,7) will lead to trying to evaluate X + 1 with X unbound. This cannot be done. The result is an error message and the goal fails.

Consider the query
?-  3 is X+1.

This results in a failure and an error message.
*** Error: uninstantiated variable in arithmetic expression:

Yet the logical statement that we might associate with the query is
  X 3 is_one_more_than X

This requires that we can search for the integer that, when added to 1 gives 3. Quite reasonable, but the arithmetic evaluator used is non-reversible. So the evaluation of arithmetic expressions is a one-way process.

Therefore is/2 must always be called with its second argument as an arithmetic expression which has any variables already bound. So successor/2 is not `reversible'. For these queries,

  1. successor(3,X).  
  2. successor(X,4).  
  3. successor(X,Y).  
  4. successor(3,5).  
The 1st and 4th goals result in correct results (success and failure respectively) while the 2nd and 3rd goals produce error messages and fail.

next up previous contents
Next: Calling Patterns Up: The `Reversibility' of Previous: The `Reversibility' of

Paul Brna
Mon May 24 20:14:48 BST 1999