Prolog中非标准二进制表示的加法谓词非终止问题求助

你的add/3当前实现依赖incrR反向递推，这种方式在给定P1、P2求P3时，会因legal(A)的递归生成逻辑陷入无限回溯。以下是针对性的优化思路：

• 改用逐位带进位的加法逻辑：参考手工计算二进制加法的流程，从最低位（数字最外层的f0/f1）开始处理，引入带进位的辅助谓词（比如add_carry/4），参数包含两个操作数的当前位、输入进位、输出的结果位+新进位。分8种基础情况处理每一位的组合（0+0+0、0+0+1……1+1+1），比如：

  % 示例：1+1+0 → 结果位0，进位1
  add_carry(f1(X), f1(Y), f0(null), f0(Res), f1(null)) :- ...
  % 示例：0+1+1 → 结果位0，进位1
  add_carry(f0(X), f1(Y), f1(null), f0(Res), f1(null)) :- ...
  

• 处理数字的终止边界：当其中一个操作数到达null时，将其视为后续位都是0，继续与另一个操作数的剩余位和进位相加；当两个操作数都到null时，根据剩余进位决定是否在结果末尾添加f1（需符合合法数无末尾零的规则）。
• 用结构递归替代数值递推：当前实现通过incrR从P1反向推导到0，属于数值递推，容易无限生成更小的数。而逐位处理是跟着操作数的嵌套结构递归，每一步消耗一个f0/f1节点，不会无限展开。
• 保证结果合法性：在构建结果的过程中直接避免生成末尾零，或最后调用legal/1验证结果（前者更高效）。

你的现有incr/2和legal/1可以保留，作为辅助验证或其他场景使用，但加法逻辑需要重新设计。

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