Legitimate uses of (\+)//1

Question

In grammar rules (dcg), there are several predefined constructs: (',')//2 meaning concatenation, ('|')//2 meaning alternation etc. One construct which is supported by several but not all Prolog systems is (\+)//1.

Personally, I have used it only for the sake of using it. I have never seen it in code written by others.

So, are there legitimate uses of (\+)//1?

Edit: And additionally, are there legitimate uses of (\+)//1 within a query phrase(nt, L) with L an uninstantiated variable.

Pipeline

Answer 1

\+ can be used to create grammars that are less ambiguous. The advantage of using \+ over ! for example, is a certain declarativity of \+, so that for example the resulting DCG rules can be reordered.

Lets make an example, consider the following grammar:

s([X|Y]) --> t(X), s(Y).               % 1
s([])    --> [].                       % 2

t(2)     --> [a,a].                    % 3
t(1)     --> [a].                      % 4

The above grammar is highly ambiguous, for example I get multiple parses for the following input:

?- phrase(s(A),[a,a,a,a,a]).
A = [2,2,1] ;
A = [2,1,2] ;
A = [2,1,1,1] ;
etc..

Now assume I want to prefer the long parse of t over the short parse of t. I can do this with a cut as follows:

t(2)     --> [a,a], !.                 % 5
t(1)     --> [a].                      % 6

?- phrase(s(A),[a,a,a,a,a]).
A = [2,2,1] ;
No

Unfortunately I cannot reorder. Since doing the following does not give the desired result. Although s(A) now yields the results in a different order, we are back to square one, since the grammar is ambiguous again:

t(1)     --> [a].                      % 7
t(2)     --> [a,a], !.                 % 8

?- phrase(s(A),[a,a,a,a,a]).
A = [1,1,1,1,1] ;
A = [1,1,1,2] ;
A = [1,1,2,1] ;
etc...

Now lets try the same with \+. We can replace the cut by the following negation:

t(2)     --> [a,a].                    % 9
t(1)     --> [a], \+ [a].              % 10

?- phrase(s(A),[a,a,a,a,a]).
A = [2,2,1] ;
No

Now lets try whether we can reorder. We reorder the grammar rules of t//1:

t(1)     --> [a], \+ [a].              % 11
t(2)     --> [a,a].                    % 12

?- phrase(s(A),[a,a,a,a,a]).
A = [2,2,1] ;
No

The declarativity is very useful. It means for example that we can use \+ in a right-to-left chart parser that picks the grammar rules in an arbitrary order. The declarativity assures that the bottom up forward chaining of the chart parser yields the same result independently of the input order of the DCG rules.

It is then possible to apply the DCG technique in large natural language (NL) projects and it scales well. The NL grammars can be empirically tuned into determinism. The more deterministic a grammar the more efficient its parsing. Complex NL grammars that are otherwise intractable become feasible.

Bye

Apologete

+1, but I am very sceptical about your claim of declarativity: phrase(s([1]),[a]). succeeds, but phrase(s([1]),L) fails. Exactly that kind of impureness is what bothers me. – Pipeline

That is: How do you draw the line between legitimate uses and not legitimate ones? – Pipeline

I don't claim general declarativity. I wrote "certain declarativity". You can establish declarativity against an adorment (= database lingo for Prolog mode declaration). The techniques can be also applied to grammars. See also: ftp.inf.ethz.ch/doc/tech-reports/1xx/177.pdf – Apologete

Answer 2

When L is not instantiated then the grammar is used for text generation. Then you don't need the grammar \+ at all. Since there is no more problem of ambiguity from some text.

Lets make an example, consider the following grammar:

s([X|Y]) --> t(X), s(Y).               % 1
s([])    --> [].                       % 2

t(2)     --> [a,a].                    % 3
t(1)     --> [a].                      % 4

Each different parse has a different parse tree. And there is no ambiguity in using phrase/2 to generate text. The following queries give exactly one answer:

?- phrase(s([2,1]),L).
L = [a,a,a]
?- phrase(s([1,2]),L).
L = [a,a,a]
?- phrase(s([1,1,1]),L).
L = [a,a,a]

But there is a little reuse problem. Assume I have a NL grammar with \+ for parsing. I then cannot use it for unparsing. Since the instantiation pattern of the \+ goal will be different, and therefore the semantic of the construct changes.

The way out is probably just to use two grammars. One for parsing and one for unparsing. I guess parsing and unparsing are two different cognitive capabilities. Remember in school, there were reading exercises and writting exercises. The same happens in computer science.

I think it is also in some cases possible to use a single grammar, and view \+ as an annotation for disambiguation, that is dropped during unparse or differently handled. One could build such a mechanism. But the issues with unparsing versus parsing are deeper: Bidirectionallity of auxiliary conditions ({}/1), left recursion during unparsing, etc...

Bye

Apologete

Again some deductive database technology can help here. Establishing bidirectional adorment (= database lingo for Prolog mode declaration) is a first step. But this is not normal Prolog anymore. – Apologete