English constraint free grammar prolog

Question

I ran into an infinite recursion problem while trying to implement a very simple constraint free grammar in prolog.

Here are my rules: (vp -> verb phrase, np -> noun phrase, ap -> adj phrase, pp -> prep phrase)

    verb(S) :- member(S, [put,  pickup, stack, unstack]).
    det(S) :- member(S, [the]).
    adj(S) :- member(S, [big, small, green, red, yellow, blue]).
    noun(S) :- member(S, [block, table]).
    prep(S) :- member(S, [on, from]).

    vp([V|R]) :- verb(V), pp(PP), np(NP), append(NP, PP, R).
    np([D, N]) :- det(D), noun(N).
    np([D|R]) :- det(D), ap(AP), noun(N), append(AP, [N], R).
    ap([A]) :- adj(A).
    ap([A|R]) :- adj(A), ap(R).
    pp([P|R]) :- prep(P), np(R).

The problem im running into is that the rule for ap can produce arbitrarily long strings of adjectives, so at some point, i get stuck trying to satisfy the query by trying all these infinite possibilities.

For example, the following query will never produce S = [put, the, red, block, on, the, green, block] because it will first expand the adjective phrase on the left "red" to infinite possibilities before ever trying on the right.

?- vp(S)
S = [put, the, red, green, block, on, the, block] ;

Answer 1

The short answer is: Use Definite Clause Grammars (dcg) to represent your grammar. See this answer for a typical encoding.

But now to your actual problem in your program. Not only will you not get the desired answer ; the situation is worse: even in a much simpler fragment of your program will you have the very same problems. Here is the smallest fragment of your program that still does not terminate:

verb(S) :- member(S, [put,  pickup, stack, unstack]).
det(S) :- member(S, [the]).
adj(S) :- member(S, [big, small, green, red, yellow, blue]).
noun(S) :- false, member(S, [block, table]).
prep(S) :- member(S, [on, from]).

vp([V|R]) :- verb(V), pp(PP), false, np(NP), append(NP, PP, R).
np([D, N]) :- false, det(D), noun(N).
np([D|R]) :- det(D), ap(AP), false, noun(N), append(AP, [N], R).
ap([A]) :- false, adj(A).
ap([A|R]) :- adj(A), ap(R), false.
pp([P|R]) :- prep(P), np(R), false.

?- vp([put, the, red, green, block, on, the, block]).

By inserting goals false we got a small fragment of your program that still does not terminate. The actual source is ap/1 which is recursive but not limited by the actual input. See failure-slice for more examples.

There is no easy way out to fix your program. The easiest way out is to use grammars.

Answer 2

Seems like you're are abusing of Prolog generative power, placing append at last position. I tried to change to a more sensible place:

...
vp([V|R]) :- verb(V), append(NP, PP, R), pp(PP), np(NP).
np([D, N]) :- det(D), noun(N).
np([D|R]) :- det(D), append(AP, [N], R), ap(AP), noun(N).
...

and now your parser apparently works.

?- vp([put, the, red, green, block, on, the, block]).
true .

but I suggest, as already false did (+1), to switch to DCG for parsing.

Answer 3

The fundamental problem is that Prolog is defined to do a DFS over rules, so when it comes to generation problems across an infinite search space (as with your case), parts of the space can get untouched. A platform-independent fix is to augment the grammar with a depth bound, and decrement the depth at each recursive call. Once the depth reaches 0, fail. By incrementally increasing the depth with repeated queries (e.g., vp(S, 1). vp(S, 2).), you guarantee that all parts of the state space will get touched eventually.

This is basically just iterative deepening. If you're on SWI-PL, you can also use the call_with_depth_limit/3 predicate to do the exact same thing without modifying the grammar.