为什么这个Prolog Fibonacci函数会导致"instantiation_error"？

Question

我正在尝试使用以下函数计算Fibonacci series：

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)

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

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

Answer 2

既然您知道这是一个错误，那么您是否介意知道是否确实可以回答您的问题呢？

你将如何处理这个问题？你的函数没问题，不是吗？没错，因为它是一个函数，而不是一个关系，所以你会得到错误。

要解决这个问题有点复杂，但是CLP可以做到！

看看这个来自CLP(FD) documentation的有趣的例子(在这里引用)

:- 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

请注意，在第一次响应之后，程序循环！你有办法纠正它吗？或者另一个问题可能值得..。

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