prolog dcg restriction

Question

I would like to use DCGs as a generator. As of now, the syntax is

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

I would like to generate all s where the length of a is < someNumber.

Using ?- phrase(a,X),length(X,Y),Y<4. i can get all a with less than 4 items. However, when all combinations are exhausted, the system (SWI-Prolog 6.2.5) seems to stall. Sometimes ago, a similar question was asked here. However, being new to Prolog i am not able to make it work with the grammar above. Any ideas?

Update: There was a comment by (canrememberthename) which got deleted, somehow. Anyway, it was suggested to use between(1,4,Y),length(X,Y),phrase(a,X). to set limits. This worked nicely, after changing my code to a-->c,a.

Christman

I deleted the answer because was wrong. You have spotted the problem by yourself while I was debugging... – Overture

Answer 1

the nonterminal a//0 is both left recursive and 'epsilon' (generate the empty sequence), and phrase/2 will loop immediately after the empty production.

You can solve your problem bounding list' length:

?- between(1,4,Y),length(X,Y),phrase(a,X).

and, as you have already done, removing the left recursion.

Overture

Answer 2

The first steps into Prolog are often a bit difficult. But you are on the right track:

Currently, your problem is that you get some answers/solutions as expected but then the system stalls ; in fact, it is in an infinite loop. You found that out by patiently hitting SPACE. That might work with a tiny set of solutions but it will be tedious with a larger one. Just think of looking at all sentences shorter than 20.

There is a simple keyboard and carpal tunnel friendly way to simulate hitting space: Simply add a goal false at the end like so:

?- phrase(a,X),length(X,Y),Y<4, false.

What could Prolog answer to such a question? Since there is false at the end, Prolog has not much choice: Either it answers false itself ; or it loops (or produces an error or produces some side-effect). And in this case, it loops.

Now, we can narrow down the problem, by adding further false goals into your program.

?- phrase(a,X),length(X,Y),false, Y<4, false.
   loops.

To make this better readable, I will only use one false goal and strike through the remaining part of the query:

?- phrase(a,X),length(X,Y),false, Y<4.
   loops.

Let's reduce that even further:

?- phrase(a,X),false,length(X,Y),Y<4.
   loops.

They all loop! But we get some interesting insight: Since these false-adorned queries do not terminate, also the original program does not terminate. So when you look at a query, and the very first goal does not terminate for itself, it follows that the entire query will not terminate (see the fine print at the end for more).

Therefore: You have to address the first goal somehow!

My first attempt is to exchange length and phrase:

?- length(X,Y), phrase(a,X), Y<4.

Will this work? Just look at the first goal which loops:

?- length(X,Y), false, phrase(a,X), Y<4.
   loops.

So this again will not terminate.

You have to change the program again:

?- between(1,3,Y), length(X,Y), false, phrase(a,X).
   false.

So this terminates. And if there will be a termination problem, phrase(a,X) has now to take the blame:

?- between(1,3,Y), length(X,Y), phrase(a,X), false.
   loops.

You might be tempted to look at actual answers:

?- between(1,3,Y), length(X,Y), phrase(a,X).
   Y = 1, X = [t1]
;  Y = 1, X = [t2]
;  resource_error(local_stack). % ERROR: Out of local stack

And you might conclude that this behavior is worse than your original definition. After all, we have now less answers than before. But exactly that kind of reasoning does not help you to improve termination: With false both are of the same kind of incorrectness and you have to address this first. So by hiding the answers you can better concentrate on the rest.

But why is your grammar problematic? We can continue with our technique to insert goals false to narrow it down. But this time within your grammar. Your program adorned with goals false is called a failure-slice.

Just a practical remark: When I insert goals false into your program, I will save the program and type make in SWI: In this manner the program is rapidly recompiled.

After trying a bit, I got the following minimal failure-slice. Note that within a DCG, false has to be written as {false}.

?- between(1,3,Y), length(X,Y), phrase(a,X), false

s--> {false}, a,b.

a-->[], {false}.
a-->a,{false},  c.

c-->{false}, [t1].
c-->{false}, [t2].

b-->{false}, [t3].
b-->{false}, [t4].

Almost all your codebase are belong to false! So you have to address the tiny visible remaining part. It would be pointless to change something somewhere else. This a --> a, ... must be changed! And in fact changing it to a --> c, s solves the problem.

Why did you write a --> a, c. in the first place? I suspect that you wanted to enumerate all solutions in a fair manner. The new version doesn't:

?- phrase(a,X).
   X = []
;  X = [t1]
;  X = [t1,t1]
;  X = [t1,t1,t1]
;  X = [t1,t1,t1,t1]
;  X = [t1,t1,t1,t1,t1]
;  X = [t1,t1,t1,t1,t1,t1]
;  X = [t1,t1,t1,t1,t1,t1,t1]
;  ... .

That looks very intimidating. In fact, it looks wrong. Doesn't it? But don't let you confuse by this: We have here an infinite set of sentences. So the only correct response by Prolog is to produce infinitely many answers. For, if they would be finite, some list would be missing! But of course, you want to see them enumerated in a fair manner. To get this, simply write:

?- length(X,N),  phrase(a,X).
   X = [], N = 0
;  X = [t1], N = 1
;  X = [t2], N = 1
;  X = [t1,t1], N = 2
;  X = [t1,t2], N = 2
;  X = [t2,t1], N = 2
;  X = [t2,t2], N = 2
;  X = [t1,t1,t1], N = 3
;  ... .

This is a major point in Prolog programs: Always go for the best (possible) termination property first. And do not look at the precise order how Prolog enumerates answers. For, if a program has better termination properties, it is next-to-trivial to use it to enumerate all solutions in a fair manner. But: A program that enumerates infinitely many solutions in a fair manner at the expense of termination cannot be used in more interesting cases.

_{Fine Print
See this answer.}

Branen

"all your codebase are belong to false" is perhaps the best statement I've read in a Prolog answer on StackOverflow. Thanks for the smile – Morphogenesis