DCG and left recursion

Question

I am trying to implement a dcg that takes a set of strings of the form {a,b,c,d}*.The problem i have is if I have a query of the form s([a,c,b],[]),It returns true which is the right answer but when i have a query of the form s([a,c,f],[]),It does not return an answer and it runs out of local stack.

s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].

Answer 1

Use phrase/2

Let's try phrase(s,[a,b,c]) in place of s([a,b,c],[]). The reason is very simple: In this manner we are making clear that we are using a DCG (dcg) and not an ordinary predicate. phrase/2 is the "official" interface to grammars.

So your first question is why does phrase(s,[a,c,f]) not terminate while phrase(s,[a,b,c]) "gives the right answer" — as you say. Now, that is quick to answer: both do not terminate! But phrase(s,[a,b,c]) finds a solution/answer.

Universal termination

These are two things to distinguish: If you enter a query and you get an answer like true or X = a; you might be interested to get more. Usually you do this by entering SPACE or ;ENTER at the toplevel. A query thus might start looping only after the first or several answers are found. This gets pretty confusing over time: Should you always remember that this predicate might produce an answer ; another predicate produces two and only later will loop?

The easiest way out is to establish the notion of universal termination which is the most robust notion here. A Goal terminates iff Goal, false terminates. This false goal corresponds to hitting SPACE indefinitely ; up to the moment when the entire query fails.

So now try:

?- phrase(s,[a,c,f]), false.
** LOOPS **

But also:

?- phrase(s,[a,b,c]), false.
** LOOPS **

From the viewpoint of universal termination both queries do not terminate. In the most frequent usage of the words, termination is tantamount to universal termination. And finding an answer or a solution is just that, but no kind of termination. So there are queries which look harmless as long as you are happy with an answer but which essentially do not terminate. But be happy that you found out about this so quickly: It would be much worse if you found this out only in a running application.

Identify the reason

As a next step let's identify the reason for non-termination. You might try a debugger or a tracer but most probably it will not give you a good explanation at all. But there is an easier way out: use a failure-slice. Simply add non-terminals {false} into your grammar ; and goals false into predicates. We can exploit here a very beautiful property:

If the failure-slice does not terminate then the original program does not terminate.

So, if we are lucky and we find such a slice, then we know for sure that termination will only happen if the remaining visible part is changed somehow. The slice which is most helpful is:

?- phrase(s,[a,b,c]), false

s --> [], {false}.
s --> s, {false}, num.

There is not much left of your program! Gone is num//0! Nobody cares about num//0. That means: num//0 could describe anything, no matter what — the program would still loop.

To fix the problem we have to change something in the visible part. There is not much left! As you have already observed, we have here a left recursion. The classical way to fix it is:

Reformulate the grammar

You can easily reformulate your grammar into right recursion:

s --> [].
s --> num, s.

Now both queries terminate. This is the classical way also known in compiler construction.

But there are situations where a reformulation of the grammar is not appropriate. This simple example is not of this kind, but it frequently happens in grammars with some intended ambiguity. In that case you still can:

Add termination inducing arguments

?- Xs = [a,b,c], phrase(s(Xs,[]), Xs).

s(Xs,Xs) --> [].
s([_|Xs0],Xs) --> s(Xs0,Xs1), num, {Xs1=Xs}.

Inherently non-terminating queries

Whatever you do, keep in mind that not every query can terminate. If you ask: »Tell me all the natural numbers that exist – really all of them, one by one!« Then the only way to answer this is by starting with, say, 0 and count them up. So there are queries, where there is an infinity of answers/solutions and we cannot blame poor Prolog to attempt to fulfill our wish. However, what we most like in such a situation is to enumerate all solutions in a fair manner. We can do this best with a grammar with good termination properties; that is, a grammar that terminates for a list of fixed length. Like so:

?- length(Xs, M), phrase(s, Xs).

For about other examples how to apply failure-slices, see tag failure-slice.

Answer 2

I don't know if this is any help, because the prolog I'm using seems to have a very different syntax, but I just wrote the following program to try and match yours and it works ok.

Program

s([]).
s([X|Xs]) :- num(X), s(Xs).

num(a).
num(b).
num(c).
num(d).

Output

?- [prologdcg].
% prologdcg compiled 0.00 sec, 2,480 bytes
true.

?- s([a,c,b]).
true.

?- s([a,c,f]).
false.

Run using SWI-prolog.