2

我正在处理我的第一个 Prolog 任务，并且在递归问题上，我似乎无法停止溢出堆栈。就像上瘾一样；我不知道怎么停下来。

让我给你举个例子。我想创建一个函数来确定一个对象 Y 是否是另一个对象 X 的一部分。这是我正在使用的数据库：

% Parts Database
has(bicycle,wheel,2).
has(bicycle,handlebar,1).
has(bicycle,brake,2).
has(wheel,hub,1).
has(wheel,spoke,32).
has(bicycle,frame,1).

has(car,steering_wheel,1).
has(car,stereo,1).
has(car,tires,4).

从这里开始，我想编写一个函数partof(X,Y)，如果 Y 是 X 的一部分，则返回 true。这就是我目前拥有的：

% Determines if Y is a part of X
partof(X,Y) :-
    has(X,Y,_).
partof(X,Y) :-
    partof(X,Z),
    partof(Z,Y).

这适用于所有true查询，但会溢出堆栈而不是返回false.例如：

?- partof(wheel, spoke).
true ;
ERROR: Out of local stack

?- partof(bicycle, spoke).
true ;
ERROR: Out of local stack

?- partof(wheel, X).
X = hub ;
X = spoke ;
ERROR: Out of local stack

我知道你们都在想，“这个愚蠢的白痴，不知道什么是基本情况。不知道如何退出递归。” 好吧，我不怪你。我觉得很笨。不过，一些耐心的指导会很有帮助。提前致谢！

4

1 回答 1

3

Prolog 中的递归类似于在其他编程语言中的工作，但在 Prolog 中要复杂得多，因为在同一运行中有两个独立的控制流交织在一起。在传统的命令式语言中，递归要么有效（并产生结果）要么无效，因此循环可能会溢出一些堆栈。

但在 Prolog 中，我们可能首先会得到很多有趣的答案，但过了一会儿，我们就陷入了无限循环。您的查询很幸运，您在第一个解决方案/答案后立即发现了循环。想象一下，您会执行以下查询：

?- partof(X, Y).
   X = bicycle,
   Y = wheel
;  X = bicycle,
   Y = handlebar
;  X = bicycle,
   Y = brake
;  X = wheel,
   Y = hub
;  X = wheel,
   Y = spoke
;  X = bicycle,
   Y = frame
;  X = car,
   Y = steering_wheel
;  X = car,
   Y = stereo
;  X = car,
   Y = tires
;  X = bicycle,
   Y = hub
;  X = bicycle,
   Y = spoke
;
ERROR: Out of local stack

请注意，这些解决方案对我们来说并不是很有趣。我们只是在最后一条消息之后。在我们说查询终止之前，我们应该敲多少次空格？幸运的是，有一个更便宜的出路。我们只是添加false（一个永远不成立的条件）作为一个额外的目标。显然，查询绝不能有解决方案。剩下的唯一有趣的事情是查询是否终止：

?- partof(X, Y), false。
错误：超出本地堆栈

这个技巧可以扩展到你的整个程序1。只需添加false您喜欢的地方。剩下的称为故障切片的程序仍然与您原来的程序有很多共同之处：它需要更少（或相等）的推理来执行。因此，如果故障切片循环，则原始程序也会循环。这是您的程序的最小循环失败片段：

partof(X,Y) :- false ,
     has(X,Y,_)。
部分（X，Y）：-
    部分（X，Z），假，
    部分（Z，Y）。

注意has/3已经完全消除了。也就是说，无论如何修改has/3都不会停止这个循环！绝不！您需要先修改可见部分中的某些内容。所剩无几！

有经验的 Prolog 程序员会立即看到这些问题。在的帮助下，您可以学会自己识别这些部分。而且，相信我，对于非常复杂的程序，始终可以选择检查您的直觉是否正确是非常有用的。

这是使用closure/3and定义传递闭包的另一种方法library(lambda)：

partof(X, Y) :-
   closure(\A^B^has(A, B,_), X, Y).

1 实际上，这只适用于纯单调程序

于 2017-11-16T12:44:28.720 回答