¿Por qué esta función Prolog Fibonacci causa un "instanciaiation_error"?

logic declarative

Question

Estoy tratando de calcular la serie de Fibonacci usando la siguiente función:

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

Esto tiene la intención de funciona así:

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

Pero cuando intento esto, se queja:

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

¿Alguien entiende por qué está pasando esto?

Answer 1

Ahora que sabe que es un error, ¿le importa saber si es posible responder a su consulta?

¿Cómo abordarías el problema? Tu función está bien, ¿no? Exactamente, porque es una función , y no una relación , obtienes el error.

¡Es un poco complicado resolverlo, pero CLP puede hacerlo!

Vea este fascinante ejemplo de la documentación de CLP (FD) (citado aquí)

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

Necesitamos algo como esto, pero para fibonacci. Vea lo fácil que es:

:- [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).

es decir, reemplazar is / 2 por #= / 2 y obtenemos

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

nota, después de la primera respuesta, ¡el programa se repite! ¿Ves una forma de corregirlo? O podría valer otra pregunta ...

Answer 2

En la segunda cláusula:

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

N es una variable que se debe disminuir, y en su llamada a:

fib(What, 6765).

La variable aún no está definida, por lo que obtiene el error de instanciación en N1 is N - 1 .

En swipl incluso obtengo el error:

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

Answer 3

Una definición de predicado más clara y más natural puede ser:

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

También es una definición con un solo predicado: fib / 2