prolog - 如何在所有参数模式的后继算术中实现斐波那契数列？

Question

以下 Prolog 程序定义了一个谓词 fib/2 用于计算后继算术中整数的斐波那契数:

fib(0, 0).
fib(s(0), s(0)).
fib(s(s(N)), F) :-
  fib(N, F1),
  fib(s(N), F2),
  sum(F1, F2, F).

sum(0, N, N).
sum(s(N1), N2, s(S)) :-
  sum(N1, N2, S).

它适用于这种参数模式下的查询:

?- fib(s(0), s(0)).
   true
;  false.

它也适用于这种参数模式下的查询:

?- fib(s(0), F).
   F = s(0)
;  false.

它也适用于这种参数模式下的查询:

?- fib(N, F).
   N = F, F = 0
;  N = F, F = s(0)
;  N = s(s(0)), F = s(0)
;  N = s(s(s(0))), F = s(s(0))
;  N = s(s(s(s(0)))), F = s(s(s(0)))
;  …

但是在这种参数模式下它会耗尽资源:

?- fib(N, s(0)).
   N = s(0)
;  N = s(s(0))
;
Time limit exceeded

如何在所有参数模式的后继算术中实现斐波那契数列？

Answer 1

这个答案使用之前的两个计算值“自下而上”计算斐波那契数，因此它只会进行一次递归尾调用:

fib(0, 0).
fib(s(0), s(0)).
fib(s(s(X)), F):-
  fib(X, 0, s(0), F, F).
  
fib(0, F_2, F_1, _, F):-
  sum(F_2, F_1, F).
fib(s(X), F_2, F_1, s(Y), F):-
  sum(F_2, F_1, F_0),
  fib(X, F_1, F_0, Y, F).

sum(0, Y, Y).
sum(s(X), Y, s(Z)):- 
  sum(X, Y, Z).

至少在具有默认配置的 SWI 中，它耗尽了计算 fibonacci(37) 在 sum/3 中构建加法项的资源。