Fair Tree Enumeration?

[jjtolton]

From @triska's videos (I can't remember which one), he shows how to wrangle an "unfair enumeration".

Something along the lines of:

xy --> [].
xy --> ( "x" | "y" ), xy.

genxy(In) :-
        length(In, N),
        phrase(xy, In).

?- genxy(Xy).

%@    Xy = []
%@ ;  Xy = "x"
%@ ;  Xy = "y"
%@ ;  Xy = "xx"
%@ ;  Xy = "xy"
%@ ;  Xy = "yx"
%@ ;  Xy = "yy"
%@ ;  Xy = "xxx"
%@ ;  Xy = "xxy"
%@ ;  Xy = "xyx"
%@ ;  Xy = "xyy"
%@ ;  ... .

In his DCG tutorial and video he also shows semicontext notation, used to sum up the leaves on a tree:

num_leaves(Tree, N) :-
        phrase(num_leaves_(Tree), [0], [N]).

num_leaves_(nil), [N] --> [N0], { N #= N0 + 1 }.
num_leaves_(node(_,Left,Right)) -->
        num_leaves_(Left),
        num_leaves_(Right).


?- num_leaves(node(a,node(b,nil,nil),
                     node(c,nil,
                            node(d,nil,nil))), N).
%@ N = 5.

However, I am scratching my head at how we might accomplish fair enumeration for this tree:

?- num_leaves(T, N).
%@    T = nil, N = 1
%@ ;  T = node(_A,nil,nil), N = 2
%@ ;  T = node(_A,nil,node(_B,nil,nil)), N = 3
%@ ;  T = node(_A,nil,node(_B,nil,node(_C,nil,nil))), N = 4
%@ ;  T = node(_A,nil,node(_B,nil,node(_C,nil,node(_D,nil,nil)))), N = 5
%@ ;  ... .

🤔

[triska]

With the following building block, we can fairly enumerate the trees with iterative deepening, by constraining the length of the list of nodes:

nodes(nil) --> [].
nodes(node(Node,L,R)) --> [Node], nodes(L), nodes(R).

Yielding:

?- length(Ls, _), phrase(nodes(Tree), Ls).
   Ls = [], Tree = nil
;  Ls = [_A], Tree = node(_A,nil,nil)
;  Ls = [_A,_B], Tree = node(_A,nil,node(_B,nil,nil))
;  Ls = [_A,_B], Tree = node(_A,node(_B,nil,nil),nil)
;  ... .
?- length(Ls, _), phrase(nodes(Tree), Ls), num_leaves(Tree, N).
   Ls = [], Tree = nil, N = 1
;  Ls = [_A], Tree = node(_A,nil,nil), N = 2
;  Ls = [_A,_B], Tree = node(_A,nil,node(_B,nil,nil)), N = 3
;  Ls = [_A,_B], Tree = node(_A,node(_B,nil,nil),nil), N = 3
;  Ls = [_A,_B,_C], Tree = node(_A,nil,node(_B,nil,node(_C,nil,nil))), N = 4
;  ... .

Finding good names is often an interesting challenge. For example, in the case of "gen"xy, what about genxy("xy")? A better name may by xys/1, since the name fits in all usage modes of the predicate:

?- xys("xy").
   true
;  false.

[jjtolton]

About terminology here: I think you meant "predicates". a(1,2,3) is a Prolog term in all contexts (specifically a compound term, and it has functor a/3), but if it's callable (that is, it is a goal) then it's also a predicate a/3. For example, =/2 is a predicate that unifies it's two arguments, but it can also be used as the functor of a compound term in just data representation if you want:

Ok I'm so glad you brough this up. I've been really shy to ask but I cannot figure out the difference between a predicate and a functor.

For instance:

fact(1).

In this case, fact/1 is both a functor and a predicate, yes? Or is a functor specifically a "non-callable" compound term? Because it is not a "rule" but it is still "callable" or queryable as in ?- fact(X). or ?- fact(1).

My confusion is maximized when I think about Datalog as a "functor free subset of Prolog". If a functor is "just" data, then ... 😰 ... what is the data part of the datalog?

[jjtolton]

Oh, I see, maybe that's the point that datalog cannot have compound terms, and a functor is a compound term?

[bakaq]

As I understand it, a functor is a "template" of a compound term. a/3 is a functor (and maybe a predicate), a(1,2,3) is a compound term (and maybe a goal) with functor a/3. There are other kinds of terms (data) in Prolog that are not compound terms (and so don't have functors), like atoms and numbers. I think what is meant by "datalog is the functor free subset of Prolog" is that you can't use functors unless you are using them as a predicate in a goal.

fact(1).

rule(X) :-
    % This is ok because fact/1 is a predicate
    fact(1). 

rule2(X) :-
    % This is not ok because fact/1 here is being used as just data
    % and is not being executed as a part of a goal.
    % Equivalent to =(X, fact(1))
    X = fact(1).

[jjtolton]

Ok. I would like to continue to deepen my nuanced understanding of this, because I think it's especially important for writing "clean" representations and properly using "clean" representations.

I realized I did not understand the nuance correctly when I was trying to implement this, uh, predicate?

:- use_module(library(clpz)).


elt_position_in_list(H, 0, [H | _]).
elt_position_in_list(Elt, N, [_|T]) :-
        #Next #= #N - 1,
        #N #>= 1,
        elt_position_in_list(Elt, Next, T).

?- elt_position_in_list(X, N, "hey").
%@    X = h, N = 0
%@ ;  X = e, N = 1
%@ ;  X = y, N = 2
%@ ;  false.

I tried multiple variations before finally arriving at the one above, such as:

elt_position_in_list(H, 0, [H | _]).
elt_position_in_list(Elt, #N, [_|T]) :-
        #Next #= #N - 1,
        #N #>= 1,
        elt_position_in_list(Elt, #Next, T).

?- elt_position_in_list(Elt, N, "hey").
%@    Elt = h, N = 0
%@ ;  false.

?- elt_position_in_list(Elt, #N, "hey").
%@    false. 

This version also has problems:

elt_position_in_list(H, 0, [H | _]).
elt_position_in_list(Elt, #N, [_|T]) :-
        #Next #= #N - 1,
        #N #>= 1,
        elt_position_in_list(Elt, Next, T).

?- elt_position_in_list(Elt, N, "hey").
%@    Elt = h, N = 0
%@ ;  Elt = e, N = #1
%@ ;     error(type_error(integer,#_654912),unknown(#_654912)-1).

So, my takeaway here is "the clp(z) # (functor/predicate/operator???) goes IN the rule body but NOT in rule declaration arguments nor the predicate invocation parameters" ... but, that's probably not entirely precise.

[jjtolton]

As yet another aside, am I doing something "wrong" with the fact that the last goal is false?

:- use_module(library(clpz)).


elt_position_in_list(H, 0, [H | _]).
elt_position_in_list(Elt, N, [_|T]) :-
        #Next #= #N - 1,
        #N #>= 1,
        elt_position_in_list(Elt, Next, T).

?- elt_position_in_list(X, N, "hey").
%@    X = h, N = 0
%@ ;  X = e, N = 1
%@ ;  X = y, N = 2
%@ ;  false.

@bakaq I remember from our discussions with the iterator that returning false for the final result was considered not exhibiting determinism, or something? So I'm wondering if I'm doing something wrong with my implementation here?

[bakaq]

(Starting another thread for this to better organize)

So, my takeaway here is "the clp(z) # (functor/predicate/operator???) goes IN the rule body but NOT in rule declaration arguments nor the predicate invocation parameters" ... but, that's probably not entirely precise.

The (#)/1 functor is used in library(clpz) to cleanly represent integers, this helps with monotonicity (especially if you activate the monotonic mode by defining/asserting clpz:monotonic/0). Here are some examples of why this is useful:

?- X #= 2, X = 1 + 1.
   false.
?- X = 1 + 1, X #= 2, X = 1 + 1.
   % Not monotonic! Adding an additional contraint made the set of solutions bigger!
   X = 1+1.

   % This happens because, by default, library(clpz) treats unbound variables as 
   % "something that could be an integer", but technically it accepts expressions
   % there too (it's an "defaulty" representation). Maybe this is easier to understand:

?- 1 + 1 #= 2.
   true.
?- X #= 2.
   X = 2. % This misses correct solutions like the 1 + 1 above.
 
   % The point of (#)/1 is that when it sees a compound term of the form #N, it
   % assumes that N is "something that could be an integer" (it could already be 
   % an integer, or an variable that can be bound to an integer). This removes all
   % the ambiguity because, in particular, N can't be an expression. The same
   % examples as earlier but using (#)/1 to to signal to library(clpz) that X can
   % only be an integer and not an expression:

?- #X #= 2, X = 1 + 1.
   false.
?- X = 1 + 1, #X #= 2, X = 1 + 1.
   % This basically means "I expected an integer but you gave me 1+1".
   % An error here doesn't break monotonicity because it can be understood as
   % "the system couldn't find a set of solutions". The same applies to
   % non-termination. It's fine (and even desirable) for monotonic predicates to
   % error or not terminate if they can't find solutions without preserving
   % monotonicity, and that is the entire idea behind library(si).  
   error(type_error(integer,1+1),must_be/2).

?- #(1+1) #= 2.
   % 1+1 is not an integer.
   error(type_error(integer,1+1),must_be/2).
?- #2 #= 2.
   true.
?- #X #= 2.
   % In this case this is really the full set of solutions, because we
   % explicitly ruled out expressions with (#)/1.
   X = 2.

   % We can define/assert clpz:monotonic/0 to put library(clpz) in monotonic mode.
   % In this mode it refuses naked variables so that it doesn't use the defaulty
   % representation and therefore end up with non-monotonic behavior.

?- assertz(clpz:monotonic).
   % You can also just put a "clpz:monotonic." fact in your program.
   true.
?- X #= 2.
   % This query that was problematic because it didn't list expressions now is
   % just refused with an instantiation error. Remember, errors don't break
   % monotonicity.
   error(instantiation_error,instantiation_error(unknown(_47),1)).
?- #X #= 2.
   % This still works, because with the clean representation using (#)/1, we know
   % that X can only be an integer.
   X = 2.
?- #1 #= 2.
   % "Could be an integer" also includes "actual integers", but you don't really need
   % (#)/1 here.
   false.

[bakaq]

As yet another aside, am I doing something "wrong" with the fact that the last goal is false?

Not at all! Having an extra false means nothing logically, in practice it just means "the system couldn't find other solutions". It does have an implication however, and that is that the predicate isn't deterministic. A predicate being deterministic means it terminates with no "useless" choicepoints (that is, a choicepoint that will inevitably give a false). Choicepoints take up memory, so it's usually a good idea to minimize them for efficiency reasons. There are many techniques for that, but first let's take a look at your predicate:

% A good naming convention for monotonic predicates is to simply list the arguments
% if it's obvious what relation between them you are representing.
element_pos_list0(H, 0, [H | _]).
element_pos_list0(Elt, N, [_|T]) :-
        #N #>= 1,
        #Next #= #N - 1,
        element_pos_list0(Elt, Next, T).

The way Scryer executes this predicate is something like checking every single alternate definition you gave it. So for example:

?- element_pos_list0(E, 0, [1,2,3]).
   % Makes a choicepoint to check all implementations you gave
   %     - Check first implementation:
           element_pos_list0(H, 0, [H | _]).
           element_pos_list0(1, 0, [1 | [2,3]]). % Match! H = E and H = 1, so E = 1
   E = 1
   %     - Check second implementation:
   %       element_pos_list0(Elt, N, [_|T])
   %       element_pos_list0(E, 0, [1 | [2,3]]) % Match! Elt = E, N = 0 and T = [2,3]
   %         - Check first goal of body:
   %           #N #>= 1
   %           #0 #>= 1 % False!!!            
;  false.

As you can imagine, there is no need to check the second implementation if the first passed, they are mutually exclusive. There are many ways to do this, let's see some of them.

Cuts ! (DON'T DO THIS)

One way to do this is to use a cut !, as it cancels a choicepoint earlier (which is exactly what we want to do here), but this is very hard to do because it can be very easy to give up monotonicity and just have clearly wrong results in some modes of usage. It also limits the usage of other execution strategies like tabling. For example, the obvious cut to do here would be this:

element_pos_list_cut(H, 0, [H | _]) :- !. % If picked this solution, you don't need to look at others!
element_pos_list_cut(Elt, N, [_|T]) :-
        #N #>= 1,
        #Next #= #N - 1,
        element_pos_list0(Elt, Next, T).

But this is literally wrong:

?- element_pos_list_cut(E, 0, [1,2,3]).
   % Yay! Now it's deterministic!
   E = 1.
?- element_pos_list_cut(E, 1, [1,2,3]).
   % Also works for other positions!
   E = 2.
?- element_pos_list_cut(E, P, [1,2,3]).
   % But if we generalize we don't get all answers!
   % This is clearly wrong, where is "E = 2, P = 1" that we just checked
   % is an accepted solution for this?
   E = 1, P = 0.
   
   % Easier way to see non-monotonicity:
?- element_pos_list_cut(E, P, [1,2,3]), P = 1.
   false.
?- P = 1, element_pos_list_cut(E, P, [1,2,3]), P = 1.
   % Not monotonic! Adding an additional constraint made the set of solutions bigger!
   P = 1, E = 2.

I could do a similar walkthrough of the choicepoints and explain why this goes wrong, and how to fix it with "green", "blue" or whatever colors of cuts people have invented over the years, but I really don't think it's worth it because it's really hard to do right (even when you actually understand well how all of this works) and because it hinders other execution strategies. There are much better ways to deal with this.

Indexing

You may have heard of "first argument indexing". This is an optimization that many Prolog systems do that can help with exactly this problem of determinism. A way to think about this is that before checking all your definitions of a predicate, the system checks your first argument's functor and automatically skips all the definitions of the predicate where the functor of the first argument doesn't match. Scryer actually has a stronger version of that, but first argument indexing is a subset of that so all that I will talk here applies. So for example:

% Using portray_clause/1 from library(format) to be able to
% see when we have tried a definition.
no_indexing(X) :- portray_clause("Definition 1"), X = 1.
no_indexing(X) :- portray_clause("Definition 2"), X = 2.
no_indexing(X) :- portray_clause("Definition 3"), X = a(1,2).
no_indexing(X) :- portray_clause("Definition 4"), X = b(1,2,3).

indexing(1) :- portray_clause("Definition 1").
indexing(2) :- portray_clause("Definition 2").
indexing(a(1,2)) :- portray_clause("Definition 3").
indexing(b(1,2,3)) :- portray_clause("Definition 4").

?- no_indexing(1).
   % Matches definition 1...
"Definition 1".
   true
   % ..But then tries every other one, because it can't rule them out.
   % Maybe X is actually bound to 1 in the body of one of them, who knows?
;  "Definition 2".
"Definition 3".
"Definition 4".
false.
?- indexing(1).
   % Matches definition 1, and doesn't even try the others. Deterministic!
   % It can see that a(1,2) is never going to unify with 1 anyway, for example.
"Definition 1".
   true.
?- indexing(a(X,Y)).
   % Similarly, only tries definition 3. Deterministic!
"Definition 3".
   X = 1, Y = 2.

Many times it's very natural to exploit argument indexing, but for your predicate it's not so clear. What you want is some way to index between 0 and non-zero numbers. The monotonic way to say things are different in Prolog is using dif/2, you could rewrite your predicate like this:

element_pos_list_dif(H, 0, [H | _]).
element_pos_list_dif(Elt, N, [_|T]) :-
        dif(N,0),
        #N #>= 1,
        #Next #= #N - 1,
        element_pos_list_dif(Elt, Next, T).

This is equivalent (so still not deterministic), because #N #>= 1 already deals with that in this case. But dif/2 is more general because it works with things other than integers. This situation of having two mutually exclusive definitions on a argument being either something or different from something is very common actually, so it would be good if we found a way to "index dif/2".

Indexing dif/2

Yes, this is the paper that introduced library(reif). The predicate if_/3 does literally what we want deterministically! So I think the best way to implement your predicate deterministically is this:

element_pos_list_reif(Elt, N, [H|T]) :-
    if_(
        N = 0, % Condition
        true, % Here the condition is true, that is, N = 0
        (
            % Here the condition is false, that is, dif(N, 0)
            #N #>= 1,
            #Next #= #N - 1,
            element_pos_list_reif(Elt, Next, T).
        )
    ).

This is equivalent to element_pos_list_dif/3 above but it indexes the mutual exclusivity of 0 and non-zero.

?- element_pos_list_reif(E, 0, [1,2,3]).
   % Deterministic!
   E = 1.
?- element_pos_list_reif(E, P, [1,2,3]).
   % Right answers...
   E = 1, P = 0
;  E = 2, P = 1
;  E = 3, P = 2
   % But ops! Not deterministic for this mode yet!
;  false.

The problem now is the list. When T = [], the recursive call to element_pos_list_reif/3 fails, because the list argument needs to always be a non-empty list ([H|T]). You could use if_/3 for this too, but this is easy enough to do with just argument indexing so it's a good example of how to do that:

% We separate the head and tail of the non-empty list and call an auxiliary
% predicate that has the tail as it's first argument, so that we can use
% first argument indexing.
element_pos_list_reif2(Elt, N, [H|T]) :-
    element_pos_list_reif2_(T, H, Elt, N).

% Because of first argument indexing, only one of those definitions will
% ever be used if we know the functor of the argument. If the first argument
% is a variable, both will run as expected.

% In this case the list has one element, so this is the only valid
% configuration of arguments.
element_pos_list_reif2_([], H, H, 0). 

% In this case we know that the tail is non-empty.
element_pos_list_reif2_([Th|Tt], H, Elt, N) :-
    if_(
        N = 0, 
        Elt = H, % N = 0
        (
            % dif(N, 0)
            #N #>= 1,
            #Next #= #N - 1,
            element_pos_list_reif2_(Tt, Th, Elt, Next)
        )
    ).

?- element_pos_list_reif2(E, 0, [1,2,3]).
   % Still deterministic!
   E = 1.
?- element_pos_list_reif2(E, P, [1,2,3]).
   % Now this is deterministic too!
   E = 1, P = 0
;  E = 2, P = 1
;  E = 3, P = 2.
?- element_pos_list_reif2(E, P, L).
   % The general query also lists all possible solutions for this.
   % It may seem strange that P = 0, L = [E,_A|_B] is a solution
   % because there is no constraint that _B needs to be a list, which
   % is required for L to be a list, but this is because this predicate
   % implemented doesn't "traverse the whole list" when consuming, which
   % means that when generating it doesn't "create a whole list" either.  
   P = 0, L = [E]
;  P = 0, L = [E,_A|_B]
;  P = 1, L = [_A,E]
;  P = 1, L = [_A,E,_B|_C]
;  P = 2, L = [_A,_B,E]
;  P = 2, L = [_A,_B,E,_C|_D]
;  P = 3, L = [_A,_B,_C,E]
?- element_pos_list_reif2(E, 0, [1,2|what]).
   % This is an example that works and falls into the P = 0, L = [E,_A|_B]
   % general solution above. This may be intended behavior. If you want to
   % guarantee that the last argument needs to be a list you need to put
   % extra constraints to ensure that.
   E = 1.

[jjtolton]

This is an absolutely brilliant write-up, I will be linking back to this frequently!! We'll need to get this up on the new tutorial section that @aarroyoc just put in!

That is so satisfying! I knew there had to be a way to fix that, but it's such an esoteric question! Let me tell you, ChatGPT and the like were absolutely no help on this question!