prologlogic-programminglogical-purity# Purity of Prolog predicates that use impure primitives

I know that `var/1`

, `nonvar/1`

and `!/0`

are impure primitives, but does their use make *every* program that uses them impure?

I wrote the following predicate `plus/3`

that behaves as if it were pure or at least that is what I claim. The predicate is demonstrative, not designed to be efficient.

```
% nat(X) is true if X is a natural number
nat(0).
nat(X):- nonvar(X), !, X > 0.
nat(X):- nat(X1), X is X1 + 1.
% plus(A, B, C) is true if A,B and C are natural numbers and A+B=C
plus(A, B, C):-
nat(A),
(nonvar(C), C < A, !, false ; true),
plus_(B, A, C).
plus_(A, B, C):-
nat(A),
(nonvar(C), C < A, !, false ; true),
C1 is A + B,
(C = C1 ; nonvar(C), C < C1, !, false).
```

I have two questions:

- Is the above predicate
`plus/3`

really pure? - In general, how can you prove that a particular relation has logical purity?

This question follows the discussion on this answer.

Solution

- Is the above predicate plus/3 really pure?

It has some odd behavior: Sometimes it accepts arithmetic expressions, and sometimes not ; and this although all arguments are evaluated:

```
?- plus(3,5-3,5).
true
; false.
?- plus(3,2,3+2).
false.
?- plus(3,2,3+b).
error(type_error(evaluable,b/0),(is)/2).
?- plus(3,2,3+Z).
error(instantiation_error,(is)/2).
```

I would rather be concerned about the inefficiency of `nat/1`

for cases like:

```
?- time( ( nat(X), X > 9999 ) ).
% 50,025,002 inferences, 27.004 CPU in 27.107 seconds (100% CPU, 1852480 Lips)
X = 10000 ;
% 10,006 inferences, 0.015 CPU in 0.015 seconds (99% CPU, 650837 Lips)
X = 10001 ;
% 10,005 inferences, 0.016 CPU in 0.016 seconds (99% CPU, 631190 Lips)
X = 10002 ...
```

So, it looks to me that your definition is pure. However, this very style of programming makes it quite difficult to guarantee this property. A minimal change will have disastrous effects.

- In general, how can you prove that a particular relation has logical purity?

The easiest way is by construction. That is, by using only pure monotonic building blocks. I.e., Prolog without any built-ins and using only conjunction and disjunction of regular goals. Any program built this manner will be pure and monotonic, too.
Then, execute this program with Prolog flag occurs check set to `true`

or `error`

.

Add to this pure built-ins like `(=)/2`

and `dif/2`

.

Add to this built-ins that try to emulate pure relations and that produce instantiation errors when they are unable to do so. Think of `(is)/2`

and the arithmetic comparison predicates. Some of these are quite on the borderline like `call/N`

which might call some impure predicates.

Add `library(clpfd)`

with flag `clpfd_monotonic`

set to `true`

.

Many constructs are fine and pure for certain uses, but impure for others. Think of if-then-else which is perfect for arithmetic comparison:

```
..., ( X > Y -> ... ; ... ), ...
```

but which does not work together with a pure goal like

```
..., ( X = Y -> ... ; ... ), ... % impure
```

What remains are impure built-ins that can be used to construct predicates that behave in a pure manner ; but whose definition as such is no longer pure.

As an example, consider truly green cuts. These are extremely rare, and even rarer here on SO. See this and that.

Another common pattern to provide a pure relation are conditionals like:

```
..., ( var(V) -> something with var ; the equivalent with nonvar ), ...
```

And to guard against cases that are not cleanly covered, errors can be thrown.

- Turbo Prolog: Create a palindrome by adding the smallest number of characters to the list
- Prolog order of clause body gives different results when using negation
- Problem With a Predicate to Check if X Occurs Exactly Four Times in a List
- Most General Unifier (Prolog)
- In prolog, functors vs predicates, and goals
- Solving N-queens with Constraint Handling Rules
- 'if' in prolog?
- Are there any Prolog compilers that can optimize by targeting specific queries?
- gprolog: Getting a stacktrace after an exception
- Efficient solution for the same-fringe problem for binary trees
- Understanding prolog \+ and the engine's solution space search
- Prolog, X element before element Y on list
- What is the difference between once and cut in prolog?
- Getting the seed set by the ECLiPSe on loading
- Get simple Prolog example to work
- How to do recursion in a L-system inspired rewrite System, without DCG
- Maximum number of atoms in SICStus Prolog 4
- How to create a list dynamically in Prolog?
- Prolog Syntax for Dependent Conditions
- Guard clauses in prolog?
- phrase_from_stream/2 nontermination (Stream from http_open/3)
- SWI-Prolog: [FATAL ERROR: Could not find system resources]
- DCG LaTeX printer for FOL prover
- Prolog: a person is a sibling of himself?
- When can I safely avoid storing temporary calculations in Prolog?
- Prolog - Solution of a riddle
- Is the structure of my Prolog expression isomorphic to the structure of the Liar Paradox?
- Syntax error: Operator expected in Prolog
- Assertion Failure in SWI-Prolog When Using pyswip to Consult a Prolog File
- Retract by partial match?