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] ;

I think you mean context-free grammar. – Daniel Lyons Mar 27 '13 at 21:00 — Daniel Lyons, Mar 27 '13 at 21:00

score 5 · Answer 1 · edited May 23 '17 at 11:58

5

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.

edited May 23 '17 at 11:58

Community

1
1

answered Mar 27 '13 at 21:10

false

10,264
13
101
209

2

@DanielLyons: That is the very idea of failure-slices: You have to change **something** in the visible part. The strike-through part is irrelevant. – false Mar 27 '13 at 21:48
2

@DanieLyons: You are confusing termination with the accidental finding of an answer. Yes, *sometimes* you get answers. But you cannot predict easily when. Also adding `vp(_).` as a fact on top will do it... – false Mar 27 '13 at 22:02
2

@DanielLyons: The **entire** failure-slice is the reason why the program does not terminate. And please recall that both Prolog and DCGs were developed to precisely address this problem. – false Mar 27 '13 at 22:18
2

Having gone back I see now that I misread the OP's question. I apologize for the flamewar. – Daniel Lyons Mar 27 '13 at 22:42
2

@DanielLyons: That's fine! Did you remove your own comments? (I did not flag them; found them ok). But in any case: I think you could profit a lot from the notion of failure-slice behind. – false Mar 27 '13 at 22:44
2

I did, they're unnecessary clutter. I would like to know more about failure slices (that you're so keen on them is actually a pretty strong incentive). I keep meaning to sit down with O'Keefe's book and dig through them and the references you have. – Daniel Lyons Mar 27 '13 at 22:48
2

http://stackoverflow.com/questions/10139640/prolog-successor-notation-yields-incomplete-result-and-infinite-loop/10141181#10141181 contains a reference too. I am not sure what you mean by unnecessary clutter. With a failure-slice you can narrow down the size of your program to a source of non-termination. – false Mar 27 '13 at 22:54
2

I meant my comments were clutter. – Daniel Lyons Mar 27 '13 at 22:55

score 0 · Answer 2 · answered Mar 28 '13 at 07:44

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.

score 0 · Answer 3 · answered Jun 23 '14 at 06:38

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.

This question was about grammars, where the input list may be used to limit the search space considerably - often down to the minimal linear case. Iterative deepening is fine in general but applied naively leads to forbidding overheads. — false, Jun 23 '14 at 09:46

English constraint free grammar prolog

3 Answers3