Prolog参数算术实现归纳谓词异常的原因及解决方案

Prolog 中算术表达式不会被自动求值，+、-这类符号本质是普通的二元函子，和自定义的普通复合结构没有区别：你写的N-1、N+1在Prolog内部会被解析为-(N, 1)、+(N, 1)的结构化数据，而非计算后的数值。只有调用is/2、=:=/2这类专门的算术谓词时，Prolog才会对传入的表达式做数值计算。

两种写法的运行逻辑差异来自Prolog的合一（unification）规则：

• 写法(1)触发栈溢出的原因

i(0).
i(N) :- i(N-1).

第二条规则的头部是单个变量N，可以匹配任意类型的参数（数字、复合结构、列表等）。当查询i(3)时，首先匹配第二条规则，N绑定为整数3，接下来递归调用i(3-1)——这里的3-1是结构-(3,1)，不是数字2。下一层递归中，这个结构再次匹配第二条规则的N，继续递归调用i( -(3,1) - 1 )即嵌套结构-(-(3,1), 1)，嵌套层级会无限加深，永远无法和事实i(0)匹配，最终触发栈溢出。

• 写法(2)返回false的原因

i(0).
i(N+1) :- i(N).

第二条规则的头部是复合结构+(N,1)，只能匹配参数为「+开头的二元复合结构」的目标。当查询i(3)时，首先尝试匹配i(0)，整数3和0无法合一，匹配失败；接着尝试匹配第二条规则，需要把整数3（常量）和复合结构+(N,1)合一，二者数据结构完全不同，根本无法进入规则体，直接返回false。

最通用、可移植性最好的方案是使用整数约束逻辑编程库clpfd，所有主流Prolog实现（SWI-Prolog、SICStus Prolog等）都内置该库。它会自动处理算术表达式的约束传播和求值，不需要手动用is/2计算中间值，还支持双向查询：

% 导入clpfd库
:- use_module(library(clpfd)).
i(0).
i(N) :- N #> 0, i(N-1).

这个写法和你预期的写法(1)形式几乎一致，可以直接正常响应i(3)查询返回true；反向查询i(X)时还能按顺序生成0、1、2、3……所有自然数，比原生is/2写法的灵活性更高。

如果不想依赖扩展库，部分Prolog支持自定义编译期项扩展（term expansion），可以在编译阶段自动把i(N-1)这类写法转换为M is N-1, i(M)的标准形式，但这属于非标准语法特性，会降低代码可移植性，不推荐在通用场景使用。

注：你最初写的第三种带is/2的写法是标准Prolog的规范实现，虽然需要显式声明中间变量，但语义明确、无兼容问题，是工业级Prolog代码的常规写法。

内容的提问来源于stack exchange，提问作者silver