Prolog阶乘谓词

Question

我有一个阶乘谓词fact（N，F），其中N或F或两者都绑定到一个数字。

例如，我可以有fact（3，F）或fact（N，6）。 这是我的谓词，它能够工作但我并不真正理解它的原理。我使用了trace，但仍然有困惑。

fact(0,1).
fact(N,F) :-
        fact(N1,F1),
        N is N1 + 1,
        F is N * F1.

- zaig

---

你也可以手动“步进”它：fact(3, F)与fact(0, 1)不匹配（因为3和0不能统一），所以Prolog将使用下一个子句fact(N, F)与N = 3进行匹配。然后，它再次调用fact(N1, F1)，根据第一个子句得出N1 = 0和F1 = 1，依此类推。请注意，在找到解决方案后，它会尝试查找更多解决方案而不终止，导致堆栈溢出。 - lurker

我很好奇：如果你不知道它是如何工作的，那么你是如何编写这个谓词的呢？ - lurker

@lurker：这非常可以理解：另一个版本可能会产生一个实例化错误。 - false

@lurker：好的，我从这个版本开始：factorial(0, 1). factorial(N, F):- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1.，一直尝试直到得到了结果。 - zaig

Answer 1

你可以尝试逐步了解程序的运行过程，但这将非常缓慢且不太可靠。或者，你可以让Prolog来（部分）完成这项工作。因此，想法是稍微修改程序，然后看看Prolog对它的看法。

这就是我查看你的程序时看到的情况 - 这被称为失败片段。

fact(0,1) :- false.
fact(N,F) :-
        fact(N1,F1), false,
        N is N1 + 1,
        F is N * F1.

这个片段什么时候会终止？看看剩下的可见部分！N只在头部出现一次：没有人关心第一个参数！F也是如此。因此，无论你有什么参数，这个程序都不会终止。因此，对于您的原始程序也是如此！ 在原始版本中，这并不那么清楚。注意：

?- fact(29,F).
   F = 8841761993739701954543616000000 

起初看起来很好，但如果你要求下一个答案（使用空格或;），你会陷入循环中，即等待永远不会到来的答案。更糟糕的是，错误的查询会立即进入循环：

?- fact(29,1).
   loops.

那么，如果你不了解具体情况，如何找到这些问题呢？这就是 false 的作用。一个永远不为真的目标。如果你像这样添加它 fact(29,F), false. 你将不会被美丽的答案分心。

为什么把所有的算术都放在最后呢？我怀疑是因为之前出现了一些错误。有一个简单的方法可以避免所有这样的错误：

:- use_module(library(clpfd)).

现在你可以使用#=代替is，并且需要一些限制，比如N #>= 1。我可以离开你吗？

- false

---

无论你有什么样的参数，这个程序都不会终止。因此，对于你的原始程序也是如此！（只是一个侧面说明）然后，你立即给出了一个示例调用，原始程序确实终止。 - Will Ness

@Will：请继续阅读！引用一下：“起初看起来很不错，但如果你要求下一个答案（使用空格或分号），你就会陷入循环中。”所以起初你会觉得这个程序会终止，但是通过按下空格键，你会发现情况并非如此。 - false

@Will：你的更正是RP吗？无论如何，“LOOPS”只是无效的语法... - false

关于“循环”的问题，因为它是无效语法，所以很明显这是一个元注释。“loops.”是有效语法，因此令人困惑。请问RP是什么？ - Will Ness

RP - false

请注意，这里的内容是答案“描述”。因此，它与任何答案一样具有元注释的作用。只需想象一个答案 L = [_E]。它需要一些量化。等等。 - false