作为计算的思维中的猴子和香蕉

Question

我正在阅读 Thinking as Computation 一书，并将代码编写为第 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).

但我发现程序永远不会停止...打印堆栈信息后，我发现goal_state 生成了无限长度的列表。我试图限制 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).

其中N指的是plan(L)中L的长度（如查询plan([M1, M2, M3, M4])时N为4）但是不行.

有什么解决办法吗？

Answer 1

非终止在 Prolog 中是一个非常棘手的事情，特别是如果您习惯了不同的更面向命令的编程语言。尝试逐步理解问题是非常诱人的。但通常这会导致 Prolog 无处可去。

相反，考虑修改您的程序。一点点。并且以一种很容易预测你的修改会产生什么影响的方式。例如，将 false 目标添加到您的计划中。它们的作用是什么？好吧，不多：这些目标将减少推理的数量。也许，他们还会减少找到的解决方案集。但就目前而言，让我们坚持推断的数量。您遇到过这样的情况，您的程序在以下时间不会终止：

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

事实上，你找到了一个计划，但随后一切都陷入了循环。就推理的数量而言，你有无限多个¹.

为了本地化负责的部分，让我们在您的程序中添加一些 false 目标。添加它们使得推理的数量仍然是无限的。

这是我想出的：

?- 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.

您的程序的这个片段（称为 failure-slice）单独负责非终止。如果您对此不满意，您将不得不在剩余的可见部分中进行一些修改。如果没有，就没有希望去掉不终止了。

我的建议是你将计划中两个目标的顺序改为：

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

1) 与无限相比，一切都会瞬间化为灰烬，这是一种理想化。

作为计算的思维中的猴子和香蕉

Monkey and banana in Thinking as Computation

prolog

non-termination

failure-slice