Preventing Backtracking with DCGs

Help!
1

I have this dcg code:

program([Node|Rest]) --> item(Node), (program(Rest) | {Rest = []}).

item(Node) --> lit(Node) | quote(Node) | pat_obj(Node) | word(Node). %| word_def(Node).

lit(num(N, L)) --> [lit(N, L)], {number(N)}.
lit(str(S, L)) --> [lit(S, L)], {string(S)}.
lit(true(L)) --> [word_s("t", L)].
lit(false(L)) --> [word_s("f", L)].
lit(atom(A, L)) --> [lit(A, L)], {atom(A)}.

word(word(right, Name, L)) --> [word(">", Name, L)].
word(word(left, Name, L)) --> [word("<", Name, L)].
word(word_s(Name, L)) --> [word_s(Name, L)].

quote(quote(Body, L)) --> [word_s("[", L)], program(Body), [word_s("]", _)].

% maybe allow nested objects?
pat_obj(pattern_obj(Pats, L)) --> [word_s("(", L)], pats(Pats), [word_s(")", _)].
pats([Pat|Rest]) --> pat(Pat), (pats(Rest) | {Rest = []}).
pat(quo_spl(left, Pats, R)) --> [word_s("[", _)], pats(Pats), [word_s("|<",_)], pat(R), [word_s("]", _)]. % too complicated?, also maybe change symbol for it
pat(quo_spl(right, Pats, R)) --> [word_s("[", _)], pat(R), [word_s("|>",_)], pats(Pats), [word_s("]", _)]. % too complicated?
pat(quote(Quote)) --> [word_s("[", _)], pats(Quote), [word_s("]", _)].
pat(lit(Lit)) --> [lit(Lit, _)].
pat(var(Name)) --> [word_s(Name, _)], {\+ (Name = "|>"), \+ (Name = "|<")}.

I want to prevent prolog from backtracking if it fails to find a match for quote, lit, par_obj, etc.
For example:
This is the current behavior for an invalid pat_obj

?- pparse("( |> )").
[word_s("(",1),word_s("|>",1),word_s(")",1)]
true .

|> is not a valid word for a pattern variable, so prolog goes all the way back and see that this cant be parsed as three words. How can I prevent this, because I want it to fail if it can’t match a pat_obj, not backtrack. I tried using cuts, and they didn’t seem to work (or I put them in the wrong place).

Any ideas? Thanks in advance

2

As a hint, the usual code for this is:

!, fail.

fail/0 means the same as false/0 - it just has slightly more relevant connotations in English.

3

I will try to figure out where to put this. Thanks

4

Hm. I added this clause to the ends of the pat clauses, and it still doesn’t want to fail
pat(_) --> !, {fail}.

5

Hm. I added this clause to the ends of the pat clauses, and it still doesn’t want to fail
pat(_) --> !, {fail}.?

It seems for prolog it is persistent and finds one solution that works, and the next one fails. How can I make it so it would ONLY fail.

6

A Minimal reproducible example - Wikipedia would be nicer for people (e.g. me) to look at.

7

This post has some other details of note.

8

What is pparse/1? It’s difficult to help you if we can’t run your program. :slight_smile:

If you don’t want backtracking, you can do something like this:

item(Node) --> lit(Node), !.
item(Node) --> quote(Node), !.
item(Node) --> pat_obj(Node), !.
item(Node) --> word(Node), !.

but I don’t know if that’s what you want to do. If it’s pat//1, maybe some refactoring (which makes the last clause of pat2//2 look suspicious):

pat(X) --> [word_s(C, _)], pat2(C, X).
pat(lit(Lit)) --> [lit(Lit, _)].

pat2("[", quo_spl(left, Pats, R)) --> pats(Pats), !, [word_s("|<",_)], pat(R), [word_s("]", _)].
pat2("[", quo_spl(right, Pats, R)) --> pat(R), !, [word_s("|>",_)], pats(Pats), [word_s("]", _)].
pat2("[", quote(Quote)) --> pats(Quote), [word_s("]", _)].
pat2(Name, var(Name)) --> {\+ (Name = "|>"), \+ (Name = "|<")}.

BTW, the last line can be:

pat2(Name, var(Name) --> {Name \= "|>", Name \= "|<"}.

PS: it could be that your pats//1 is wrong.

9

Thank you for your help, I will try these out and let you know. For further context, here is the code for the lexer and parser currently (didn’t make your changes yet)