Wednesday 22 February 2023

10 - Recursion With Arithmetic



Prolog isn't designed for numeric computation, but sometimes simple calculations are unavoidable. Here we'll demonstrate prolog's ability to do arithmetic as well as explain some caveats.


% Example 10 - Arithmetic

% length of a list
len([], 0). 
len([_H|T], L) :- len(T, M), L is M+1.

The example program defines a property len/2 between a list and the length of that list. Before we can discuss it, we need to learn about arithmetic in prolog.


Simple Arithmetic

In most programming languages a statement like X=2+3 would result in the variable X being assigned the value 5. This is not the case in prolog because the symbol = means unify, not assign.


?- X=2+3.

X = 2+3

The variable X becomes 2+3, not 5. 

To nudge prolog to actually carry out an arithmetic calculation we replace = with is. 


?- X is 2+3.

X = 5

Different prolog implementations will differ in what kinds of numeric calculation they support. Some will support floating point calculations, like 2.3+5.1=7.4, and some will even support rational number calculations, like 1+1/3=4/3. Our own focus here is logic programming and simple calculations with whole numbers, also called integers, is sufficient.


Calculate With Caution

Prolog's ability to do numerical calculation should be used with care. Let's see why.


?- X=3, Y is X+2.

X = 3,
Y = 5

Prolog works left to right so the first thing it tries is the unification X=3. This leaves X with the value 3. After that it executes Y is X+2. To do that it needs to evaluate X+2. This is possible because X currently holds the value 3, so Y is given the value 5. The end result is the same as if Y were unified with 5.

Let's now swap the order of the query.


?- Y is X+2, X=3.

Arguments are not sufficiently instantiated

Logically this query is equivalent to the previous one, but procedurally it is different. Prolog first tries to execute Y is X+2, but at this point the value of X is not known, that is, X is unbound. Prolog throws an error. 

Prolog has done two things that are atypical. First, it didn't fail the query in the usual way which allows backtracking. The entire prolog program itself is stopped, arguably an overdramatic response. Second, prolog did not assign an internal variable to Y which would have left open the possibility of a value being found for it later. 

So we must take additional care when using numerical calculation in prolog. We must make sure that any variables used in an arithmetic expression are grounded at the time it is evaluated. 


Length Of A List

We can now think about calculating the length of a list. As always, it is a good habit to first explore the problem visually, with pen and paper, before trying to write prolog code. A first attempt might be as follows.

  • The length of a list is calculated by visiting each item in a list, in order, incrementing a counter as we proceed.

Remembering that prolog only provides the [H|T] construct to get at the content of lists, we need an approach using heads and tails.

  • The length of a list is one more than the length of its tail.

We can now write this as a recursive definition.

  • Termination - length of an empty list is 0.
  • Continuation - length of a list is 1 plus the length of its tail.

We can see the continuation rule performs its key job of reducing the size of the problem by one step.


len/2

Let's now look at the definition of the property len(List, L), which is true if L is the length of the given List. 


len([], 0). 
len([_H|T], L) :- len(T, M), L is M+1.

The first rule len([],0) is the familiar termination rule, which says the length of an empty list is 0. 

The second rule is the continuation rule which relates the length of a list with the length of its tail. We can see the length of the given list is unified with L, the length of its tail is unified with M, and the two are related by the arithmetic relation L is M+1. Logically, this is true, but we also need to understand how it works procedurally. This is best done with an example.


?- len([a,b,c], L). 

L=3

  • len([a,b,c], L) is true if len([b,c], _M1) is true, and L is _M1+1.
  • len([b,c], _M1) is true if len([c], _M2) is true, and _M1 is _M2+1.
  • len([c], _M2) is true if len([], _M3) is true, and _M2 is _M3+1.
  • len([], 0) is true by the termination rule, which means _M3=0.

Prolog can now calculate _M2 is _M3+1, leaving _M2=1. Similarly, _M1 is _M2+1 leaving _M1=2. Finally, L is _M1+1, leaving L=3, the length of the given list. 

Remember that prolog creates its own randomly chosen names for the internal variables, which we've called _M1, _M2 and _M3 for clarity.


Depth-First Resolution

You may be asking why the continuation rule doesn't cause the prolog program to dramatically stop because the variables L and M don't have values at the time this rule is first executed.

Remember that prolog works left to right along the parts of a rule, and it doesn't move right until it has completed the part it is working on. 

  • To complete working on the first part len([b,c], _M1) it needs to apply the continuation rule again. 
  • That rule has a first part len([c], _M2), and itself requires applying the continuation rule again. 
  • The first part of that invocation is len([],_M3) which matches the termination rule. 

We can see why this method of searching for solutions, or resolving a rule, is called depth-first. Let's continue.

  • The termination rule tells us _M3=0, which allows the calling continuation rule to complete, len([],0) is true and _M2 is _M3+1, leaving _M2=1.
  • This allows the calling continuation rule to complete, len([c],1) is true and _M1 is _M2+1, leaving _M1=2.
  • Finally, this allows the calling continuation rule to complete, len([b,c],2) is true and L is _M1+1, leaving L=3, the length of the given list [a,b,c].

Although this breakdown is quite detailed, it is beneficial to work through it once to understand how the query is executed, and to see in detail why the variables in the arithmetic expression are actually grounded when it is executed. 


Broken len/2

It is useful to see an incorrectly structured continuation rule. The following definition for len/2 has the two parts of the continuation rule swapped.


% broken version of len/2 continuation rule
len([_H|T], L) :- L is M+1,len(T, M).

Logically the continuation rule is the same as before, but procedurally it is different. The first part of the rule's body is L is M+1, and this will always cause the prolog program to stop because both L and M are ungrounded when the first part of the continuation rule is executed.


?- len([a,b,c], L). 

Arguments are not sufficiently instantiated

Even if we supply a value for L in the query, for example by asking “the length of [a,b,c] is 3?”, the variable M is ungrounded.


?- len([a,b,c], 3). 

Arguments are not sufficiently instantiated

Key Points

  • The = symbol means unify, not assign. X=2+3 leaves X as 2+3.
  • The is operator is used to assign the result of evaluating an arithmetic expression. X is 2+3 leaves X as 5.
  • All variables in an arithmetic expression must have values assigned when an evaluation happens.
  • If there are unbound variables at evaluation then the entire prolog program is stopped. This is not the usual prolog failure which results in backtracking or a false response.
  • Prolog's strategy for executing multi-part rules is depth-first, then left to right. Understanding this is particularly important when writing recursive definitions.

at