Linear Problems with Prolog IV

Let us give a couple of examples of using linear constraints. We will first define a predicate which can generate (and test) natural numbers.

nat(0).
nat(N):-
   gtlin(N, 0),
   nat(N-1).

This can be read as ``zero is a natural number, and any number greater than zero is a natural number, provided that is predecessor is also a natural number''. Note that we are using the actual number zero to represent zero. This is an example of a recursive definition, in which a problem (in this case, knowing when something is a natural number) is solved by reducing the initial problem to a similar, but in some sense smaller or simpler task. After loading the above code, Prolog IV returns a series of integer numbers:

?- nat(X).
   X = 0 ;
   X = 1 ;
   X = 2 ;

And it can also test whether a given number is or not natural:

?- nat(3.4).
   false

?- nat(-8).
   false

This is one of the most important properties of CLP languages: as logical properties are written without paying attention^3.1 to the internal operations of the language, the code can be used in various modes: it can either generate or test, or perform a mixture of both:

?- gelin(3, X), nat(X).
   X = 0;
   X = 1;
   X = 2;
   X = 3.

?- gelin(3, X), nat(X+5).
   X = -5;
   X = -4;
   X = -3;
   X = -2;
   X = -1;
   X =  0;
   X =  1;
   X =  2;
   X =  3.

The definition above can also be written as

nat(0).
nat(N + 1):-
   gelin(N, 0),
   nat(N).

and it works exactly in the same way.

Problem 3.1   How, and why, will the following code

nt(0).
nt(N):-
   nt(N-1).

behave if queried

?- nt(3.4). 
  (???) 

?- nt(-8). 
   (???)

$\blacklozenge$

In a similar way to the natural numbers, even numbers can be defined as

even(0).
even(N+2):-
   gtlin(N+2, 0),
   even(N).

which is to be read as ``zero is an even number, and any even number plus two is also an even number''.

Problem 3.2   Write code, similar to the one for even/1, which can generate odd numbers and test for oddity. Call the predicate odd/1. $\blacklozenge$

Problem 3.3   Write an alternative definition for odd/1 which uses the definition of even/1, but which is not based on it. It should not contain any recursive call. $\blacklozenge$

Problem 3.4   Write a predicate multiple(A, B) which tests if a number A is an integer multiple of another number B. $\blacklozenge$

Problem 3.5   It should be trivial to give definitions for odd/1 and even/1 using multiple/2. $\blacklozenge$

Problem 3.6   Find whether a number N is congruent modulo K to some other number M ( $M \equiv N \bmod K$). This means that the remainder of the integer division of M by K is the same as the remainder of the integer division of N by K: $12 \equiv 7 \bmod 5$, $32 \equiv 2 \bmod 2$, $32 \equiv 2 \bmod 30$, .... Call the predicate congruent(M, N, K). $\blacklozenge$

$\mathbf\therefore$

A more involved example is generating the value of e based on a (slowly) convergent series: $\frac{e}{4} = \frac{1}{1} - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \cdots$. The predicate which implements this is called is_E(N, E), where N is the number of terms to add, and E is the value of e. We will make this toplevel call an interface to a predicate which will actually perform the calculation:

is_E(N, E4*4):- is_E(N, 1, 1, E4).

is_E(0, Mult, Sign, 0).
is_E(N, Mult, Sign, Sign/Mult + RestE):-
   gtlin(N, 0),
   is_E(N-1, Mult+1, -Sign, RestE).

The bulk of the work is performed by is_E/4, which has in its first argument the number of elements in the series remaining to be added, in the second argument the denominator for each element of the series, in the third argument the sign (+1 or -1) to be used, and in the last argument the result of adding the rest of the series. Operationally, the predicate works by finding out the first element of the series (which is Sign/Mult), and stating (in the head of the clause) that the whole series is to be calculated by adding this first element with the rest of the series; then, a recursive call works out the value of this rest of the series. All mathematical operations are solved when possible (i.e., when a sufficient number of variables have been reduced to definite values).

Finding an approximation of e is as easy as writing:

?- is_E(10, E).
   E = 1627/630.

The problem, in that case, is that we do not have any idea of the accuracy of this approximation. A better control can be obtained by forcing two successive approximations of e to differ by a small amount^3.2. So, an easy possibility is writing:

?- lelin(abs(E1 - E2), 0.1), is_E(N, E1), is_E(N+1, E2), !.
   N = 39,
   E2 = 3637485804655193/1335732864265800,
   E1 = 3771059091081773/1335732864265800.

Thirtynine elements may seem a lot for an accuracy of only 0.1, but if one thinks carefully, the 40 ^th element is $\frac{1}{40}$, and since the series itself returns $\frac{e}{4}$, the difference among the 39 ^th and the 40 ^thelement is just 0.1; concerning the accuracy of the approximation, it is not really meaningful, and should be looked mainly as an exercise of using CLP in innovative ways, not possible in other languages.

Some primitives not yet explained are used in this example: abs/1 returns the absolute value of a number. The ! sign forces Prolog IV (and any other Prolog or CLP language) to stop after finding the first answer to a query. We will return to them (especially to !) later.

Problem 3.7   There is some redundancy in this example. Two of the arguments perform similar roles: the first one counts the number of elements in the series still to be worked out, and it thus goes from N to 0; the second one has the denominator of the fractions, and it goes from 1 to N. The only reason for doing that is automatically calculating whether to add or substract each element in the series by reversing the sign of the third argument. CLP can help to have a simpler program: we can start at $\frac{1}{N}$ and progress towards $\frac{1}{1}$, leaving undetermined the sign of every element of the series, but reversing its sign, until the first element is reached. Write this program. $\blacklozenge$