Prolog parsing is running out of stack

Question

I have this code

s(W) :- append(W1,W2,W), np(W1), vp(W2).

vp(W) :- append(W1,W2,W), v(W1), np(W2).

np(W) :-
   (  append(W1,W2,W), pn(W1), ph(W2)
   ;  append(W1,W2,W), det(W1), n(W2)
   ).

pn([hans]).

ph([]).

v([beobachtet]).

n([mann]).
n([fernrohr]).

p([mit]).

det([den]).
det([dem]).

when I cast something like np(X). vp(X). or pp(X) get one possible parse and then an out of stack error. when I cast s(X). I don't even get a parse. I know that is because there is some infinite loop running, but I just cant point out at which point it gets looped. i figured it might happen because of using the same names for all my variables, but then I changed them to individual ones and it didn't change anything.

any one got a hint?

thanks in advance!

Answer 1

Reason for out of stack

Let's look at the following line from your code:

vp(W) :- append(W1,W2,W), v(W1), np(W2).

Running append(W1, W2, W) in isolation gives the following:

?- append(W1, W2, W).
W1 = [],
W2 = W ;
W1 = [_G1108],
W = [_G1108|W2] ;
W1 = [_G1108, _G1114],
W = [_G1108, _G1114|W2] ;
W1 = [_G1108, _G1114, _G1120],
W = [_G1108, _G1114, _G1120|W2] .

As you can see, W1 is a list of increasing length. Only for length 1 does it give a solution (since v(W1)). After this first instantiation, W1 gets longer and longer and longer and ..., but v(W1) will not succeed for lists of longer length.

DCG grammar

In Prolog you can use DCG notation to create a grammar. Your grammar would look as follows:

s --> np, vp.
np --> pn.
np --> det, n.
vp --> v, np.

det --> [den].
det --> [dem].

n --> [mann].
n --> [fernrohr].

pn --> [hans].

v --> [beobachtet].

Example of use

?- phrase(s, S).
S = [hans, beobachtet, hans] ;
S = [hans, beobachtet, den, mann] ;
S = [hans, beobachtet, den, fernrohr] ;
S = [hans, beobachtet, dem, mann] ;
S = [hans, beobachtet, dem, fernrohr] ;
S = [den, mann, beobachtet, hans] ;
S = [den, mann, beobachtet, den, mann] ;
S = [den, mann, beobachtet, den, fernrohr] ;
S = [den, mann, beobachtet, dem, mann] ;
S = [den, mann, beobachtet, dem, fernrohr] ;
S = [den, fernrohr, beobachtet, hans] ;
S = [den, fernrohr, beobachtet, den, mann] ;
S = [den, fernrohr, beobachtet, den, fernrohr] ;
S = [den, fernrohr, beobachtet, dem, mann] ;
S = [den, fernrohr, beobachtet, dem, fernrohr] ;
S = [dem, mann, beobachtet, hans] ;
S = [dem, mann, beobachtet, den, mann] ;
S = [dem, mann, beobachtet, den, fernrohr] ;
S = [dem, mann, beobachtet, dem, mann] ;
S = [dem, mann, beobachtet, dem, fernrohr] ;
S = [dem, fernrohr, beobachtet, hans] ;
S = [dem, fernrohr, beobachtet, den, mann] ;
S = [dem, fernrohr, beobachtet, den, fernrohr] ;
S = [dem, fernrohr, beobachtet, dem, mann] ;
S = [dem, fernrohr, beobachtet, dem, fernrohr].

Answer 2

Non-termination is often a bit difficult to understand in Prolog. Take as example the query pn(X). Obviously, there should be:

?- pn(X).
   W = [hans]
;  W = [den,mann]
;  W = [den,fernrohr]
;  W = [dem,mann]
;  W = [dem,fernrohr].

as solutions, (regardless of [den,fernrohr] not being German). But Prolog finds only a single one and then loops. In a sense you can consider yourself happy, for you detected that problem early on. But imagine a situation where there are many answers before the loop. So you have the impression that everything is fine, but it is not.

To find those problems a bit faster, ask pn(X), false instead. While this query will never be true, it will terminate in exactly the same way as pn(X) but it will not produce all those irritating solutions.

You can go even a step further by inserting false into your program, the resulting program is called a failure slice. With a pure, monotonic program as yours, the following holds:

If a failure slice does not terminate (for a particular query) then the original program does not terminate for that query.

Failure slices are typically much shorter, so they are faster to read and understand. In the case of np(X)

?- np(X), false.

np(W) :-
   (  append(W1,W2,W), false,  pn(W1), ph(W2)
   ;  false, append(W1,W2,W), det(W1), n(W2)
   ).

So you no longer need to waste your time searching pn/1, ph/1, det/1, or n/1 for loops. Above failure-slice alone is already producing non-termination. Thus: As long as this does not get fixed it is pointless to look at the remaining program.

A straight-forward fix would be to put append/3 at the end. That works for np/1. But it does not work for recursive non-terminals with a list of fixed length.

Before Prolog was born, people did consider exactly such encodings. They were puzzled by this mismatch: Both grammars and predicate logic are declarative formalism. But while many grammars can be parsed very efficiently, proving that a sentence is described by grammar seems to imply a gigantic search space. Where is this effective method to use logic here?

The answer was a particular encoding that permitted resolution to parse simple grammars as efficiently as handwritten parsers which thus gave birth to Prolog. To this date, this encoding is used in Prolog to implement Definite Clause Grammars. See @WouterBeeks's answer how this is done.