如何在Prolog后继算术中实现支持全参数模式的斐波那契谓词

问题根源 #

原fib/2是朴素递归实现，当第二个参数固定、第一个参数为自由变量时，递归的第一个子目标fib(N, F1)会无限制生成越来越大的N，无法判断当前计算的斐波那契数已经超过目标值，最终耗尽资源。

全参数模式兼容实现 #

利用后继算术的天然单调性（数值越大嵌套的s/1层数越多），采用迭代递推+前置剪枝的方案改写，计算过程中实时判断当前结果是否超过目标值，避免无效递归：

% 对外主谓词
fib(N, F) :-
    fib_iter(0, 0, s(0), N, F).

% 迭代辅助谓词：参数顺序为 当前计数、当前项值、下一项值、目标N、目标F
fib_iter(CurrN, CurrF, _, CurrN, CurrF).
fib_iter(CurrN, CurrF, NextF, TargetN, TargetF) :-
    % 剪枝判断：N未绑定/当前计数小于目标N 且 F未绑定/当前项小于目标F 才继续递推
    (var(TargetN) ; lt(CurrN, TargetN)),
    (var(TargetF) ; lt(CurrF, TargetF)),
    sum(CurrF, NextF, NewNextF),
    fib_iter(s(CurrN), NextF, NewNextF, TargetN, TargetF).

% 后继算术小于比较谓词
lt(0, s(_)).
lt(s(X), s(Y)) :- lt(X, Y).

% 求和谓词复用原有实现
sum(0, N, N).
sum(s(N1), N2, s(S)) :-
    sum(N1, N2, S).

效果验证 #

所有参数模式的查询都可以正常返回、不会超时：

• 双参数绑定查询

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

• N绑定、F自由查询

  ?- fib(s(s(s(0))), F).
  F = s(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)) ;
  …
  

• F绑定、N自由查询

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

内容的提问来源于stack exchange，提问作者Géry Ogam