prolog - 无限循环的树方法

Question

所以当我实例化我的整数变量时，我所有的树代码都不能正常工作。这是我的意思的一个例子:

% relates a tree and the numbe of nodes in that tree(order)
tree_order(empty,0).
tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :- 
    Order #> 0,
    Order #= Left_Subtree_Order + Right_Subtree_Order + 1,
    tree_order(Left_Subtree, Left_Subtree_Order), tree_order(Right_Subtree, Right_Subtree_Order).

我实际上并没有使用它，但这是我对树的定义:

% Definition of a Binary Tree

tree(empty).
tree(tree(_, Left_Subtree, Right_Subtree)) :- 
    tree(Left_Subtree), tree(Right_Subtree).

因此，如果运行以下查询 tree_order(Tree, 2). 它会为我提供一个解决方案，然后当它回溯时会进入无限循环。老实说，这让我感到困惑，因为我已经在脑海中运行该程序一千次了，但我仍然找不到答案。

一种可能是 Prolog 向树的左侧添加了无限多的节点，但它没有意识到这实际上导致树的阶数大于 2。

但如果是这样的话，我如何告诉 prolog 停止向树中添加 2 个以上的节点？我考虑过使用 CLP，但我知道的唯一方法是关于数字域和列表而不是谓词。

提前致谢!

Answer 1

tree_order(T, 2).没有终止的原因如下failure-slice :

tree_order(empty,0) :- false.tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :-     Order #> 0,    Order #= Left_Subtree_Order + Right_Subtree_Order + 1,    tree_order(Left_Subtree, Left_Subtree_Order), false,    tree_order(Right_Subtree, Right_Subtree_Order).?- tree_order(T, 2).   loops.

为了使这个终止，你需要以某种方式专门化这个程序。就像在查询前面添加 T = tree(_,empty,empty) 一样。

或者通过添加冗余约束 Right_Subtree_Order #>=0。

请注意，严格来说，这不再是有限域的示例，而是(可能)无限域。并非所有的 clpfd 实现都支持这一点。 SICStus、Scryer 和 SWI 都支持它。但只有在 Scryer 和 SWI 中，此类术语的统一才会终止。