Monkey and banana in Thinking as Computation

Question

I am reading the book Thinking as Computation and wrote the code as chapter 9.4:

plan(L) :-
   initial_state(I),
   goal_state(G),
   reachable(I, L, G).

initial_state([]).

legal_move(S, A, [A | S]) :-
    poss(A, S).

goal_state(S) :-
    has_bananas(S).

reachable(S, [], S).
reachable(S1, [M | L], S3) :-
    legal_move(S1, M, S2),
    reachable(S2, L, S3).

location(box, loc3, []).
location(box, L, [push(L) | _]).
location(box, L, [A | S]) :-
    \+ A = push(L),
    location(box, L, S).
location(bananas, loc1, _).
location(monkey, loc2, []).
location(monkey, L, [push(L) | _]).
location(monkey, L, [go(L) | _]).
location(monkey, L, [climb_off | S]) :-
    location(monkey, L, S).
location(monkey, L, [A | S]) :-
    \+ A = push(_), \+ A = go(_), location(monkey, L, S).

on_box([climb_on | _]).
on_box([A | S]) :- \+ A = climb_off, on_box(S).

has_bananas([grab | S]) .
has_bananas([_ | S]) :- has_bananas(S).

poss(climb_off, S) :- on_box(S).
poss(go(_), S) :- \+ on_box(S).
poss(grab, S) :-
    on_box(S), location(box, L, S), location(bananas, L, S).

poss(push(_), S) :- poss(climb_on, S).
poss(climb_on, S) :-
    \+ on_box(S), location(box, L, S), location(monkey, L, S).

But I found that the program never stops... After printing the stack info, I found that goal_state generates lists of infinite length. I tried to constrain the length of the lists in has_banana

has_bananas([grab | S], N) :- length(S, NS), NS is N - 1.
has_bananas([_ | S], N) :- \+ N = 0, has_bananas(S, N - 1).

which N refers to the length of L in plan(L) (e.g. N is 4 when query plan([M1, M2, M3, M4])) But it doesn't work.

Is there any solution?

`has_bananas/1` generates lists that have one instance of `grab` and the rest are anonymous, uninstantiated variables, and an uninstantied tail. Is that what you want that predicate to do? — lurker, Mar 22 '16 at 18:36

false · Accepted Answer · 2016-03-23T09:39:40.537

Non-termination is a very tricky business in Prolog, in particular if you are used to different more command-oriented programming languages. It is very tempting to try to understand the issue step-by-step. But very often that leads to nowhere in Prolog.

Instead, consider to modify your program. Just a little bit. And in a manner that it is easy to predict what the effect of your modifications will be. For example, add false goals into your program. What will their effect be? Well, not much: These goals will reduce the number of inferences. And maybe, they will also reduce the set of solutions found. But for the moment, let's stick to the number of inferences. You have encountered a case, where your program does not terminate for:

?- length(L, 4), plan(L).

In fact, you find a plan, but then it all goes into a loop. In terms of numbers of inferences, you have infinitely many¹.

To localize the responsible part, let's add some false goals into your program. Add them such that the numbers of inferences is still infinite.

This is what I came up with:

?- length(L, 4), plan(L).

plan(L) :-
   initial_state(I),
   goal_state(G), false,
   reachable(I, L, G).

initial_state([]).

goal_state(S) :-
   has_bananas(S), false.

has_bananas([grab | S]) :- false.
has_bananas([_ | S]) :-
   has_bananas(S), false.

This fragment of your program (called a failure-slice) alone is responsible for non-termination. If you are unhappy with it, you will have to modify something in the remaining visible part. If not, there is no hope to remove the non-termination.

My suggestion is that you change the order of the two goals in plan to:

plan(L) :-
   initial_state(I),
   reachable(I, L, G),
   goal_state(G).

1) That's an idealization for all will crumble to dust in no time compared to infinity.

Monkey and banana in Thinking as Computation

1 Answers1