Tree methods going on infinite loop

Question

So all of my tree code is not working properly when I instantiate my integer variables. Here's an example of what I mean:

% 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).

I'm not actually using that but here's my definition of a tree:

% Definition of a Binary Tree

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

So if run the following query tree_order(Tree, 2). it gives me a solution then when it backtracks it goes on an infinite loop. It's honestly baffling me, because I've run the program in my head a thousand times and I still can't find an answer.

One possibility is that Prolog is adding infinitely many nodes to the left of the tree and it doesn't realize that it actually leads to the tree having order greater than 2.

But if that's the case, how can I tell prolog to stop adding more than 2 nodes to the tree? I've thought about using CLP but the only methods I know reason about numerical domains and lists but not predicates.

Thanks in advance!

CLP(FD) is deeper waters than what you might initially think by just looking at the surface. Prepare for a lot of rabbit holes if you decide to use constraints when they are not strictly necessary. — TA_intern, Oct 19 '21 at 04:17
Just to make it clear, **you are using CLP(FD)** in the code in your question already. You are not "instantiating your integer variables", you are putting constraints on them. — TA_intern, Oct 19 '21 at 04:28
@TA_intern what do you mean by not strictly necessary? Isn't it good practice that every Prolog predicate is as general as possible? Oh, and, yes, what I meant about using CLP(FD) was using other methods to try and solve my problem which is something I'm still learning to do. — Luiz, Oct 19 '21 at 12:00
Yes, as general as possible, but this is often a judgement call. And as your question nicely shows, you don't necessarily get everything you think you do just by throwing in CLP(FD). — TA_intern, Oct 20 '21 at 05:40

false · Answer 1 · 2022-08-11T10:15:14.143

4

The reason for non-termination of tree_order(T, 2). is the following 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.

In order to make this terminating, you need to specialize this program somehow. Like by adding T = tree(_,empty,empty) in front of the query.

Or by adding the redundant constraint Right_Subtree_Order #>=0.

Note that strictly speaking, this is no longer an example of finite domains but rather (potentially) infinite domains. Not all clpfd implementations support this. SICStus, Scryer, and SWI do support it. But only in Scryer and SWI does unification of such terms always terminate.

edited Aug 11 '22 at 10:15

answered Oct 19 '21 at 15:53

false

10,264
13
101
209

Interesting! I hadn't thought about it like an infinite domain. Although, I find it rather confusing the failure-slice. It's a concept I read about but haven't understood it very well :S – Luiz Oct 20 '21 at 02:23
@Luiz "failure slice" is as simple and as powerful as the "ubiquitous binary search". – TA_intern Oct 20 '21 at 05:38
@Luiz: Start with [failure-slices for successor-arithmetics](https://stackoverflow.com/questions/tagged/failure-slice%2bsuccessor-arithmetics?tab=Frequent). There, problems are much more clean cut whereas the constraint mechanism in SWI is [still prone to errors](https://stackoverflow.com/questions/69607377/prolog-how-to-create-all-possible-combinations-without-repetitions/69622372#comment123091991_69622372). – false Oct 20 '21 at 10:14

score 2 · Accepted Answer · answered Oct 19 '21 at 03:24

2

Better to constraint every free variable involved:

/*  File:    tree_order.pl
    Author:  Carlo,,,
    Created: Oct 19 2021
    Purpose: https://stackoverflow.com/q/69623834/874024
*/

:- module(tree_order,
          [tree_order/2
          ]).
:- use_module(library(clpfd)).

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

yields

[debug]  ?- tree_order(T,2).
T = tree(_, empty, tree(_, empty, empty)) ;
T = tree(_, tree(_, empty, empty), empty) ;
false.

answered Oct 19 '21 at 03:24

CapelliC

59,646
5
47
90

Good answer. Just a nitpick, all variables involved had constraints already, just the domains were not strict enough. In this solution you made them explicitly non-negative. Non-termination as in the question is still very unexpected. – TA_intern Oct 19 '21 at 04:35
@TA_intern So can non-termination still happen, even when everything is properly constrained? How to completely avoid it? – Luiz Oct 19 '21 at 12:03
1

@Luiz: generally speaking, termination of programs is non decidable, but the situation is complex. Citing Markus Triska, the author of library(clpfd) `Moreover, since all CLP(FD) constraints always terminate, placing them earlier can at most improve, never worsen, the termination properties of your programs`. Look for relevant thoughts in section `A.9.4 Example: Factorial relation`, in [online documentation](https://www.swi-prolog.org/pldoc/man?section=clpfd) – CapelliC Oct 19 '21 at 12:19
1

@Luiz: personally, I think that `tree_order/3` should always terminate, but since Prolog is a general purpose programming language (Turing complete), you can always write nonterminating programs in it. CLP(FD) is a [leaky abstraction](https://en.wikipedia.org/wiki/Leaky_abstraction) – CapelliC Oct 19 '21 at 12:25
@CapelliC Oh, I see. More or less. I only realise now that we can't be too sure of anything! Or something like that – Luiz Oct 19 '21 at 13:32
1

@Luiz: well, not that bad... you can trust CLP(FD) implementation, but constraint programming it's a bit of a black art, mixing it with Prolog requires further experience. Don't give up, and don't be afraid to ask when in doubt. After all, it's an interesting technology. Maybe you could also be interested in [clpBNR](https://www.swi-prolog.org/pack/list?p=clpBNR) or advancements in Prolog knowledge engineering with [s(CASP)](http://ceur-ws.org/Vol-2970/gdepaper1.pdf) – CapelliC Oct 19 '21 at 19:32
@CapelliC: Which particular leak in CLPFD are you referring to? Apart from the limits of undecidability. – false Oct 19 '21 at 20:13
@false: in my experience, both the binding state of variables *and* the control flow (backtracking and cuts) are leaking concepts, and the main problem is that such leakage happens *without warning* both in modelling and searching phases. – CapelliC Oct 20 '21 at 07:12
1

@CapelliC Thank you for the words of encouragement! Just yesterday I couldn't understand `failure-slices` and some problems in constraint modelling but now it seems I'm able to make small programs work like I intend them to. – Luiz Oct 21 '21 at 03:28

Tree methods going on infinite loop

2 Answers2

Linked