prologfailure-slicesuccessor-arithmetics# Finding whether a number is a multiple of another

Looking at the code below:

```
multiple(X,0).
multiple(X,Y) :- lt(0,X), lt(0,Y), diff(Y,X,D), multiple(X,D).
```

There happens to be something wrong. For your reference:

lt/2 is whether the first argument is less than the second.

diff/3 is whether the third argument is equal to the first argument minus the second.

lt/2 and diff/3 are defined correctly.

Is there a logical mistake in the definition? Is assuming that 0 is the multiple of every number problematic or is the logical mistake somewhere else? I get correct answers but the query goes to infinite loop I think.

EDIT:

here are the other definitions.

```
natNum(0).
natNum(s(X)) :- natNum(X).
lt(0,s(X)) :- natNum(X).
lt(s(X),s(Y)) :- lt(X,Y).
sum(0,X,X).
sum(s(X),Y,s(Z)) :- sum(X,Y,Z).
diff(X,Y,Z) :- sum(Z,Y,X).
?- multiple(X, s(s(s(s(s(s(0))))))).
```

where `s(0)`

is 1, `s(s(0))`

is 2 etc. It gives all the desired answers for X but after the last answer, it gets stuck. I assume in an infinite recursive loop?

Solution

What is happening in your program? Does it loop forever, or does it only take some time since you haven't updated your hardware in recent decades? We cannot tell. (Actually, we could tell by looking at your program, but that is much too complex for the moment).

What we can do with ease is narrow down the source of this costly effort. And this, without a deep understanding of your program. Let's start with the query:

```
?- multiple(X, s(s(s(s(s(s(0))))))).
X = s(0)
; X = s(s(0))
; X = s(s(s(0)))
; X = s(s(s(s(s(s(0))))))
; loops. % or takes too long
```

Isn't there an easier way to do this? All this semicolon typing. Instead, simply add ** false** to your query. In this manner the solutions found are no longer shown and we can concentrate on this annoying looping. And, if we're at it, you can also add

`false`

~~multiple(_X,0) :-~~. multiple(X,Y) :- lt(0,X),falsefalse,~~lt(0,Y), diff(Y,X,D), multiple(X,D)~~.~~natNum(0) :-~~. natNum(s(X)) :- natNum(X),falsefalse. lt(0,s(X)) :- natNum(X),false.~~lt(s(X),s(Y)) :-~~. ?- multiple(X, s(s(s(s(s(s(0))))))),false, lt(X,Y)false. loops.

Do your recognize your program? Only those parts remained that are needed for a loop. And, actually in this case, we have an infinite loop.

To fix this, we need to modify something in the remaining, visible part. I'd go for `lt/2`

whose first clause can be generalized to `lt(0, s(_))`

.

But wait! Why is it OK to generalize away the requirement that we have a natural number? Look at the fact `multiple(X,0).`

which you have written. You have not demanded that `X`

is a natural number either. This kind of **over-generalizations** often appears in Prolog programs. They improve termination properties at a relatively low price: Sometimes they are too general but all terms that additionally fit into the generalization are not natural numbers. They are terms like `any`

or `[a,b,c]`

, so if they appear somewhere you know that they do not belong to the solutions.

So the idea was to put ** false** goals into your program such that the resulting program (failure-slice) still loops. In the worst case you put

`false`

`diff/3`

. So no need to understand it (for the moment). It suffices to look at the remaining program.- 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?