如何在Prolog中自举实现setarg_with_occurs_check/3谓词

问题背景 #

目前Prolog有两种创建循环数据结构的方式，除了合一操作可以实现，setarg/3也可以：

/* SWI-Prolog 8.3.26 */
?- X = f(X).
X = f(X).

?- X = f(0), setarg(1,X,X).
X = f(X).

我们需要为setarg/3设计一个与unify_with_occurs_check/2功能对应的版本，避免赋值时产生循环结构，实现方案如下：

注：部分Prolog系统中setarg/3也被命名为change_arg/3，还有部分系统完全不提供该内置谓词。

实现逻辑 #

核心思路是在执行赋值操作前，先对要写入的新值做发生检查，确认值中没有引用目标复合项本身，从根源上避免生成循环结构。

参考实现代码 #

setarg_with_occurs_check(ArgIndex, Term, NewValue) :-
    % 入参校验：目标必须为复合项
    compound(Term),
    % 校验索引合法性，支持正负索引（SWI-Prolog风格，负索引从末尾计数）
    Arity = arity(Term),
    between(-Arity, Arity, ArgIndex),
    % 发生检查：确认新值中不存在目标项的引用
    \+ occurs(Term, NewValue),
    % 所有检查通过后执行原生赋值操作
    setarg(ArgIndex, Term, NewValue).

% 通用发生检查谓词：当Term在Structure中出现时返回成功
occurs(Term, Structure) :-
    Term == Structure.
occurs(Term, Structure) :-
    compound(Structure),
    functor(Structure, _, Arity),
    between(1, Arity, I),
    arg(I, Structure, SubTerm),
    occurs(Term, SubTerm).

效果验证示例 #

% 无循环的正常赋值可执行成功
?- X = f(0), setarg_with_occurs_check(1, X, 2).
X = f(2).

% 会生成直接循环的赋值直接失败
?- X = f(0), setarg_with_occurs_check(1, X, X).
false.

% 嵌套循环的场景也可以正常检测到
?- X = f(0), Y = g(h(X)), setarg_with_occurs_check(1, X, Y).
false.

补充说明 #

• setarg/3属于操作可变项的非纯内置谓词，纯Prolog没有修改已创建项的能力，因此setarg/3本身无法自举实现，本实现依赖系统提供的原生setarg/3。
• 部分Prolog系统的setarg自带发生检查开关，比如SWI-Prolog的setarg/4，第四个参数传true即可启用发生检查，无需自行实现上述逻辑。

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