为什么这个 Prolog Fibonacci 函数会导致“instantiation_error”错误？

Question

我想使用以下函数计算斐波那契数列：

fib(0,A,_,A).
fib(N,A,B,F) :-
    N1 is N-1, Sum is A+B, fib(N1, B, Sum, F).
fib(N, F) :- fib(N, 0, 1, F).

这是设计的工作方式：

| ?- fib(20,Result).

Result = 6765 ? 

但是当我尝试这样做时，它报错了：

| ?- fib(What,6765).
uncaught exception: error(instantiation_error,(is)/2)

有人知道为什么会发生这种情况吗？

- Hanfei Sun

Answer 1

在第二个从句中：

fib(N,A,B,F) :-
    N1 is N-1, Sum is A+B, fib(N1, B, Sum, F).

N是一个要递减的变量，在您的调用中：

fib(What, 6765).

变量尚未定义，因此您会在 N1 is N - 1 上出现实例化错误。

在swipl中，我甚至会收到错误提示：

?- fib(W, 6765).
ERROR: fib/4: Arguments are not sufficiently instantiated

- Rubens

Answer 2

现在你已经知道这是一个错误，您是否想了解是否实际上可以回答您的查询？

你会如何应对这个问题？你的函数是好的，不是吗？确切地说，因为它是一个函数而不是一个关系，所以你得到了错误。

解决它有点复杂，但CLP可以做到！

请参阅CLP（FD）的文档（在此引用）中的这个迷人的例子。

:- use_module(library(clpfd)).

n_factorial(0, 1).
n_factorial(N, F) :-
        N #> 0, N1 #= N - 1, F #= N * F1,
        n_factorial(N1, F1).

我们需要类似于这样的东西，但针对斐波那契数列。 看起来很简单：

:- [library(clpfd)].

fib(0,A,_,A).
fib(N,A,B,F) :-
    N #> 0,
    N1 #= N-1,
    Sum #= A+B,
    fib(N1, B, Sum, F).
fib(N, F) :- fib(N, 0, 1, F).

即将 is/2 替换为 #=/2，我们得到以下内容。

?- fib(20,Result).
Result = 6765 .

?- fib(X,6765).
X = 20 ;
^C

注意，在第一次响应后程序会循环！你有没有想到如何纠正它？或者另一个问题可能更有价值...

- CapelliC

Answer 3

一个更清晰、更自然的谓词定义可能是：

//The two base steps
fib1(0,0). 
fib1(1,1).
//the recursive step
fib1(N,F) :- 
        N >= 0, M is N-2, O is N-1, fib1(M,A), fib1(O,B), F is A+B.

这也是一个只有一个谓词的定义：fib/2

- Saffie