CODEWITHSUNDEEP
prolog
num1
num1

Reputation: 4975

Why does this query not terminate?

I've written a generator which generates a string of digits given a description of them:

:- use_module(library(clpfd)).
some(_Int, 0) --> [].
some(Int, Count) --> {Count #> 0, Count1 #= Count - 1}, [Int], some(Int, Count1).

many([]) --> [].
many([some(X, N)|Rest]) --> some(X, N), many(Rest).

This works when run forward:

?- phrase(many([some(0, 3), some(1, 2)]), Some).
Some = [0, 0, 0, 1, 1] ;
false.

Well, it leaves a choicepoint, but at least it first gives the correct result. It loops forever when asked to generate a description for a given string of digits:

?- phrase(many([Some|Rest]), [0, 0, 0, 1, 1]).
OOPS

What am I doing wrong?

Upvotes: 2

Views: 66

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

I'm going to give you a slightly "operational" perspective on what your problem is. Dijkstra forgive me.

The crux of the problem is that there is a way for you to do nothing in many//2 and then again in some//2. Your first clause of many//2 is happy to eat none of the input. But, in your second clause, you sort of assume that some//2 is going to eat some of your input--but it doesn't have to, and then you are recurring back into your first clause of many//2, which still doesn't have to eat any input. So you find yourself in a recursive call to many//2, back in the second clause of many//2 once again, with precisely the same input as when you started. This is your loop!

The solution is to ensure that some//2 definitely does some work: the first clause has to go:

some(Int, 1) --> [Int].
some(Int, Count) --> {Count #> 0, Count1 #= Count - 1}, [Int], some(Int, Count1).

This is not as aggressive as you'd probably like in folding together some/2 structures, but it does work and it terminates:

?- phrase(many([Some|Rest]), [0, 0, 0, 1, 1]).
Some = some(0, 1),
Rest = [some(0, 1), some(0, 1), some(1, 1), some(1, 1)] ;
Some = some(0, 1),
Rest = [some(0, 1), some(0, 1), some(1, 2)] ;
Some = some(0, 1),
Rest = [some(0, 2), some(1, 1), some(1, 1)] ;
Some = some(0, 1),
Rest = [some(0, 2), some(1, 2)] ;
Some = some(0, 2),
Rest = [some(0, 1), some(1, 1), some(1, 1)] ;
Some = some(0, 2),
Rest = [some(0, 1), some(1, 2)] ;
Some = some(0, 3),
Rest = [some(1, 1), some(1, 1)] ;
Some = some(0, 3),
Rest = [some(1, 2)] .

Upvotes: 3

Related Questions