How to enumerate combinations using DCGs with CLP(

问题:

This question starts from Mat's answer to Algorithm improvement for enumerating binary trees which has only one input value that determines the number of all nodes for the binary tree, and the need to be able to have two input values with one being the number of unary nodes and the other being the number of binary nodes.

While I was able to derive a solution by using listing/1 and threading extra state variables:

e(t, B, B, U, U).

e(u(E), B0, B1, [_|U0], U1) :-
    e(E, B0, B1, U0, U1).

e(b(E0, E1), [_|B0], B2, U0, U2) :-
    e(E0, B0, B1, U0, U1),
    e(E1, B1, B2, U1, U2).

e(U,B,Es) :-
    length(Bs, B),
    length(Us, U),
    e(Es,Bs,[],Us,[]).

Note: See Prolog output below.

I was not satisfied with the use of length/2 as a constraint in that it is not obvious in it's use and that it was not using DCG. From previous other attempts at other problems I knew using numbers as a constraint would fail, e.g.

e_a(t, B, B, U, U).

e_a(u(E), B0, B1, U0, U2) :-
    U1 is U0 + 1,
    e_a(E, B0, B1, U1, U2).

e_a(b(E0, E1), B0, B3, U0, U2) :-
    B1 is B0 + 1,
    e_a(E0, B1, B2, U0, U1),
    e_a(E1, B2, B3, U1, U2).

e_a(U,B,Es) :-
    U =:= Us,   % Arguments are not sufficiently instantiated 1=:=_2692
    B =:= Bs,
    e_a(Es,0,Bs,0,Us).

?- e_a(1,2,Es).

However upon searching I found the use of CLP(FD) with DCG, and decided to try that.

:-use_module(library(clpfd)).

e_b(t, B, B, U, U).

e_b(u(E), B0, B1, U0, U2) :-
    U1 #= U0 + 1,
    e_b(E, B0, B1, U1, U2).

e_b(b(E0, E1), B0, B3, U0, U2) :-
    B1 #= B0 + 1,
    e_b(E0, B1, B2, U0, U1),
    e_b(E1, B2, B3, U1, U2).

e_b(U,B,Es) :-
    U #=< Us,
    B #=< Bs,
    e_b(Es,0,Bs,0,Us).

?- e_b(1,2,Es).

however that results in an infinite loop returning no results.
Note: I understand the concepts of CLP(FD) but my practical use with it is next to none.

So the questions are:

1. Can CLP(FD) be used with this solution and if so how?
2. How would I convert the non DCG solution back into a DCG version?

Supplement

Starting code and listing

e(number)        --> [].
e(u(Arg))        --> [_], e(Arg).
e(b(Left,Right)) --> [_,_], e(Left), e(Right).

?- listing(e).
e(t, A, A).
e(u(A), [_|B], C) :-
        e(A, B, C).
e(b(A, C), [_, _|B], E) :-
        e(A, B, D),
        e(C, D, E).

Prolog output

?- e(1,2,Es).
Es = u(b(t, b(t, t))) ;
Es = u(b(b(t, t), t)) ;
Es = b(t, u(b(t, t))) ;
Es = b(t, b(t, u(t))) ;
Es = b(t, b(u(t), t)) ;
Es = b(u(t), b(t, t)) ;
Es = b(u(b(t, t)), t) ;
Es = b(b(t, t), u(t)) ;
Es = b(b(t, u(t)), t) ;
Es = b(b(u(t), t), t) ;
false.

Listing of answer

For those not familiar with DCG one import tool to have in your Prolog tool box is listing/1 which will convert the DCG to standard Prolog.

e.g.

?- listing(expression).  

For the following listings I also changed the name of the variables by hand so that they are easier to follow and understand. When DCG is converted to standard Prolog two extra variables may appear as the last two arguments to a predicate. Here I have changed their names. They will start with S0 as the second to last argument and then progress as S1, S2, and so on until they are the last argument. Also if one of the input arguments is threaded through the code I have changed the name, e.g. U to U0 and so on. I have also added as comments the clp(fd) constraints.

Using listing/1 on part of the answer:

% DCG
expression(U, B, E) -->
      terminal(U, B, E)
    | unary(U, B, E)
    | binary(U, B, E).


% Standard Prolog
expression(U, B, E, S0, S1) :-
        (   terminal(U, B, E, S0, S1)
        ;   unary(U, B, E, S0, S1)
        ;   binary(U, B, E, S0, S1)
        ).

% DCG
terminal(0, 0, t) --> [t].

% Standard Prolog
terminal(0, 0, t, [t|S0], S0).

% DCG
unary(U, B, u(E)) -->
    {
        U1 #>= 0,
        U #= U1 + 1
    },
    ['u('],
    expression_1(U1, B, E),
    [')'].

% Standard Prolog
unary(U0, B, u(E), S0, S4) :-
        true,
        clpfd:clpfd_geq(U1, 0),               % U1 #>= 0
        (   integer(U0)
        ->  (   integer(U1)
            ->  U0=:=U1+1                     % U #= U1 + 1
            ;   U2=U0,
                clpfd:clpfd_equal(U2, U1+1)   % U #= U1 + 1
            )
        ;   integer(U1)
        ->  (   var(U0)
            ->  U0 is U1+1                    % U #= U1 + 1
            ;   U2 is U1+1,                   % U #= U1 + 1
                clpfd:clpfd_equal(U0, U2)
            )
        ;   clpfd:clpfd_equal(U0, U1+1)       % U #= U1 + 1
        ),
        S1=S0,
        S1=['u('|S2],
        expression_1(U1, B, E, S2, S3),
        S3=[')'|S4].

% DCG
binary(U, B, b(E1, E2)) -->
    {
        U1 #>= 0,
        U2 #>= 0,
        U #= U1 + U2,
        B1 #>= 0,
        B2 #>= 0,
        B #= B1 + B2 + 1
    },
    ['b('],
    expression_1(U1, B1, E1),
    expression_1(U2, B2, E2),
    [')'].

% Standard Prolog
binary(U0, B0, b(E1, E2), S0, S5) :-
        true,
        clpfd:clpfd_geq(U1, 0),                 % U1 #>= 0
        true,
        clpfd:clpfd_geq(U2, 0),                 % U2 #>= 0
        (   integer(U0)
        ->  (   integer(U1),
                integer(U2)
            ->  U0=:=U1+U2                      % U #= U1 + 1
            ;   U3=U0,
                clpfd:clpfd_equal(U3, U1+U2)    % U #= U1 + 1
            )
        ;   integer(U1),
            integer(U2)
        ->  (   var(U0)
            ->  U0 is U1+U2                     % U #= U1 + 1
            ;   U3 is U1+U2,                    % U #= U1 + 1
                clpfd:clpfd_equal(U0, U3)
            )
        ;   clpfd:clpfd_equal(U0, U1+U2)        % U #= U1 + 1
        ),
        true,
        clpfd:clpfd_geq(B1, 0),                 % B1 #>= 0
        true,
        clpfd:clpfd_geq(B2, 0),                 % B2 #>= 0
        (   integer(B0)
        ->  (   integer(B1),
                integer(B2)
            ->  B0=:=B1+B2+1                    % B #= B1 + B2 + 1
            ;   B3=B0,
                clpfd:clpfd_equal(B3, B1+B2+1)  % B #= B1 + B2 + 1
            )
        ;   integer(B1),
            integer(B2)
        ->  (   var(B0)
            ->  B0 is B1+B2+1                   % B #= B1 + B2 + 1
            ;   B3 is B1+B2+1,                  % B #= B1 + B2 + 1
                clpfd:clpfd_equal(B0, B3)
            )
        ;   clpfd:clpfd_equal(B0, B1+B2+1)      % B #= B1 + B2 + 1
        ),
        S1=S0,
        S1=['b('|S2],
        expression_1(U1, B1, E1, S2, S3),
        expression_1(U2, B2, E2, S3, S4),
        S4=[')'|S5].

References to SWI-Prolog source code

If you wan to see the source that translates clp(fd) or DCG to standard prolog here are the links.

• clp(fd)
• dcg

Notes

Think of these as my personal notes in case I have to come back to this question in the future. No sense in keeping them to myself if they can help others.

With regards to

When is the use of length/2 required to constrain the size of DCG results and when can CLP(FD) be used?

After looking at the listing of the code that uses clp(fd) as a constraint I can start to understand why building parallel list and using length/2 is used. I did not expect the code to be that complex.

With regards to how clp(fd) avoids causing the error

Arguments are not sufficiently instantiated 1=:=_2692

it can be seen that it checks if the variable is bound or not

e.g.

integer(U1)
var(U0)

Evolution of code

Based on the answer by @lurker I was able evolve the code into this, which is to be able to generate all combinations of unique unary-binary trees given a list of unary ops, a list of binary ops and a list of terminals. While it can generate the combinations of the expressions, it still needs an intermediate step to rearrange the order of the items in the three lists before being used to generate the expressions I need.

% order of predicates matters
e(    Uc     , Uc , Bc     , Bc , [Terminal|Terminal_s], Terminal_s  , Unary_op_s             , Unary_op_s  , Binary_op_s              , Binary_op_s  , t         , Terminal             ).

e(    [_|Uc0], Uc1, Bc0    , Bc1, Terminal_s_0         , Terminal_s_1, [Unary_op|Unary_op_s_0], Unary_op_s_1, Binary_op_s_0            , Binary_op_s_1, u(E0)     , [op(Unary_op),[UE]]  ) :-
    e(Uc0    , Uc1, Bc0    , Bc1, Terminal_s_0         , Terminal_s_1, Unary_op_s_0           , Unary_op_s_1, Binary_op_s_0            , Binary_op_s_1, E0        , UE                   ).

e(    Uc0    , Uc2, [_|Bc0], Bc2, Terminal_s_0         , Terminal_s_2, Unary_op_s_0           , Unary_op_s_2, [Binary_op|Binary_op_s_0], Binary_op_s_2, b(E0, E1), [op(Binary_op),[L,R]] ) :-
    e(Uc0    , Uc1, Bc0    , Bc1, Terminal_s_0         , Terminal_s_1, Unary_op_s_0           , Unary_op_s_1, Binary_op_s_0            , Binary_op_s_1, E0       , L                     ),
    e(Uc1    , Uc2, Bc1    , Bc2, Terminal_s_1         , Terminal_s_2, Unary_op_s_1           , Unary_op_s_2, Binary_op_s_1            , Binary_op_s_2, E1       , R                     ).

e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls) :-
    length(Bs, Bc),
    length(Us, Uc),
    e(Us,[], Bs,[], Terminal_s, _, Unary_op_s, _, Binary_op_s, _, Es, Ls).

e(Unary_op_s, Binary_op_s, Terminal_s, Es, Ls) :-
    length(Unary_op_s,Uc),
    length(Binary_op_s,Bc),
    length(Terminal_s,Ts),
    Tc is Bc + 1,
    Ts == Tc,
    e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls).

This is the part I need

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],_,Ls);true.
Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(ln), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]], [number(2)]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]], [number(2)]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[op(ln), [[number(1)]]]]], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [op(sub), [[number(1)], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]], [number(2)]]] ;
true.

And this is a nice quick way to see that they are unique.

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],Es,_);true.
Es = u(u(b(t, b(t, t)))) ;
Es = u(u(b(b(t, t), t))) ;
Es = u(b(t, u(b(t, t)))) ;
Es = u(b(t, b(t, u(t)))) ;
Es = u(b(t, b(u(t), t))) ;
Es = u(b(u(t), b(t, t))) ;
Es = u(b(u(b(t, t)), t)) ;
Es = u(b(b(t, t), u(t))) ;
Es = u(b(b(t, u(t)), t)) ;
Es = u(b(b(u(t), t), t)) ;
Es = b(t, u(u(b(t, t)))) ;
Es = b(t, u(b(t, u(t)))) ;
Es = b(t, u(b(u(t), t))) ;
Es = b(t, b(t, u(u(t)))) ;
Es = b(t, b(u(t), u(t))) ;
Es = b(t, b(u(u(t)), t)) ;
Es = b(u(t), u(b(t, t))) ;
Es = b(u(t), b(t, u(t))) ;
Es = b(u(t), b(u(t), t)) ;
Es = b(u(u(t)), b(t, t)) ;
Es = b(u(u(b(t, t))), t) ;
Es = b(u(b(t, t)), u(t)) ;
Es = b(u(b(t, u(t))), t) ;
Es = b(u(b(u(t), t)), t) ;
Es = b(b(t, t), u(u(t))) ;
Es = b(b(t, u(t)), u(t)) ;
Es = b(b(t, u(u(t))), t) ;
Es = b(b(u(t), t), u(t)) ;
Es = b(b(u(t), u(t)), t) ;
Es = b(b(u(u(t)), t), t) ;
true.

If you have been reading the comments then you know that one can use this with just one list as a constraint or no list as a constraint.

If you disable the list as constraints using

e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls) :-
    e(_,[], _,[], Terminal_s, _, Unary_op_s, _, Binary_op_s, _, Es, Ls).

You get

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],_,Ls);true.
Ls = [number(0)] ;
Ls = [op(neg), [[number(0)]]] ;
Ls = [op(neg), [[op(ln), [[number(0)]]]]] ;
Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [number(1)]]]]]]] ;
Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(ln), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [number(1)]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[number(1)]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [number(1)]]]]] ;
Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]], [number(2)]]]]] ;
Ls = [op(neg), [[op(add), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]], [number(2)]]]]] ;
Ls = [op(add), [[number(0)], [number(1)]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[number(1)]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[op(ln), [[number(2)]]]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [number(2)]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[op(ln), [[number(1)]]]]], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [number(1)]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]] ;
Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [op(sub), [[number(1)], [number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(neg), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[number(2)]]]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[op(ln), [[number(2)]]]]]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [op(ln), [[number(2)]]]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]], [number(2)]]] ;
Ls = [op(add), [[op(sub), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]], [number(2)]]] ;
true.

and

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],Es,_);true.
Es = t ;
Es = u(t) ;
Es = u(u(t)) ;
Es = u(u(b(t, t))) ;
Es = u(u(b(t, b(t, t)))) ;
Es = u(u(b(b(t, t), t))) ;
Es = u(b(t, t)) ;
Es = u(b(t, u(t))) ;
Es = u(b(t, u(b(t, t)))) ;
Es = u(b(t, b(t, t))) ;
Es = u(b(t, b(t, u(t)))) ;
Es = u(b(t, b(u(t), t))) ;
Es = u(b(u(t), t)) ;
Es = u(b(u(t), b(t, t))) ;
Es = u(b(u(b(t, t)), t)) ;
Es = u(b(b(t, t), t)) ;
Es = u(b(b(t, t), u(t))) ;
Es = u(b(b(t, u(t)), t)) ;
Es = u(b(b(u(t), t), t)) ;
Es = b(t, t) ;
Es = b(t, u(t)) ;
Es = b(t, u(u(t))) ;
Es = b(t, u(u(b(t, t)))) ;
Es = b(t, u(b(t, t))) ;
Es = b(t, u(b(t, u(t)))) ;
Es = b(t, u(b(u(t), t))) ;
Es = b(t, b(t, t)) ;
Es = b(t, b(t, u(t))) ;
Es = b(t, b(t, u(u(t)))) ;
Es = b(t, b(u(t), t)) ;
Es = b(t, b(u(t), u(t))) ;
Es = b(t, b(u(u(t)), t)) ;
Es = b(u(t), t) ;
Es = b(u(t), u(t)) ;
Es = b(u(t), u(b(t, t))) ;
Es = b(u(t), b(t, t)) ;
Es = b(u(t), b(t, u(t))) ;
Es = b(u(t), b(u(t), t)) ;
Es = b(u(u(t)), t) ;
Es = b(u(u(t)), b(t, t)) ;
Es = b(u(u(b(t, t))), t) ;
Es = b(u(b(t, t)), t) ;
Es = b(u(b(t, t)), u(t)) ;
Es = b(u(b(t, u(t))), t) ;
Es = b(u(b(u(t), t)), t) ;
Es = b(b(t, t), t) ;
Es = b(b(t, t), u(t)) ;
Es = b(b(t, t), u(u(t))) ;
Es = b(b(t, u(t)), t) ;
Es = b(b(t, u(t)), u(t)) ;
Es = b(b(t, u(u(t))), t) ;
Es = b(b(u(t), t), t) ;
Es = b(b(u(t), t), u(t)) ;
Es = b(b(u(t), u(t)), t) ;
Es = b(b(u(u(t)), t), t) ;
true.

Either way is useful, I just have a personal preference for the ones generated from the constraints for reasons related to the project that uses them.

The next evolution came by referring back to Mat's answer.

e([number(0)]           , t1        ) --> [].
e([number(1)]           , t2        ) --> [].
e([number(2)]           , t3        ) --> [].
e([op(neg),[Arg]]       , u1(E)     ) --> [_],   e(Arg,E).
e([op(ln),[Arg]]        , u2(E)     ) --> [_],   e(Arg,E).
e([op(add),[Left,Right]], b1(E0,E1) ) --> [_,_], e(Left,E0), e(Right,E1).
e([op(sub),[Left,Right]], b2(E0,E1) ) --> [_,_], e(Left,E0), e(Right,E1).

e(EL,Es) :-
    length(Ls, _), phrase(e(EL,Es), Ls).

es_count(M, Count) :-
    length([_|Ls], M),
    findall(., phrase(e(_,_), Ls), Sols),
    length(Sols, Count).

I won't show the results or explain this in detail as it should be trivial at this point. Of note is that it generates two different types of results, the first as a list and the second as compound terms.

Original 5 questions

The original question had 5 parts, but instead of creating a new question for that answer, parts of this question were removed so that the answer given by lurker could stay here.

1. Can CLP(FD) be used with this solution and if so how?
2. When is the use of length/2 required to constrain the size of DCG results and when can CLP(FD) be used?
3. What other means are available to cause iterative deepening with DCG?
4. How would I convert the non DCG solution back into a DCG version?
5. As my DCG get more complex I will be needing more constraint variables. Is there a standard practice on how to handle this, or just follow the rinse and repeat methodology?

回答1:

Basic tree expression parser with counters

Assuming a compound term representation for binary-unary trees (e.g., b(t,u(b(t,t,)))), here is a basic parser. CLP(FD) is generally recommended for reasoning over integers.

expression(U, B, E) :-
    terminal(U, B, E).
expression(U, B, E) :-
    unary(U, B, E).
expression(U, B, E) :-
    binary(U, B, E).

terminal(0, 0, t).

unary(U, B, u(E)) :-
    U1 #>= 0,
    U #= U1 + 1,
    expression(U1, B, E).

binary(U, B, b(E1,E2)) :-
    U1 #>= 0, U2 #>= 0,
    U #= U1 + U2,
    B1 #>= 0, B2 #>= 0,
    B #= B1 + B2 + 1,
    expression(U1, B1, E1),
    expression(U2, B2, E2).

There are a couple of things I've done intentionally here. One is to use CLP(FD) to give me more relational reasoning over the counts for unary and binary terms. The other thing I've done is put the simpler expression/3 clause first which doesn't do recursion. That way, Prolog will hit terminals first in the process of exploring possible solutions.

Example executions:

| ?- expression(1,2,E).

E = u(b(t,b(t,t))) ? a

E = u(b(b(t,t),t))

E = b(t,u(b(t,t)))

E = b(t,b(t,u(t)))

E = b(t,b(u(t),t))

E = b(u(t),b(t,t))

E = b(u(b(t,t)),t)

E = b(b(t,t),u(t))

E = b(b(t,u(t)),t)

E = b(b(u(t),t),t)

(1 ms) no

| ?- expression(U, B, E).

B = 0
E = t
U = 0 ? ;

B = 0
E = u(t)
U = 1 ? ;

B = 0
E = u(u(t))
U = 2 ? ;
...

Using a DCG for sequential representation

A DCG is used for parsing sequences. The compound term can be parsed as a sequence of tokens or characters, which can, through the use of a DCG, be mapped to the compound term itself. We might, for example, represent the compound tree term b(t,u(b(t,t))) as [b, '(', t, u, '(', b, '(', t, t, ')', ')', ')']. Then we can use a DCG and include that representation. Here's a DCG that reflects the above implementation with this sequence format:

expression(U, B, E) -->
    terminal(U, B, E) |
    unary(U, B, E) |
    binary(U, B, E).

terminal(0, 0, t) --> [t].

unary(U, B, u(E)) -->
    [u, '('],
    { U1 #>= 0, U #= U1 + 1 },
    expression(U1, B, E),
    [')'].

binary(U, B, b(E1, E2)) -->
    [b, '('],
    { U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1 },
    expression(U1, B1, E1),
    expression(U2, B2, E2),
    [')'].

Again, I put the terminal//3 as the first course of query for expression//3. You can see the parallelism between this and the non-DCG version. Here are example executions.

| ?-  phrase(expression(1,2,E), S).

E = u(b(t,b(t,t)))
S = [u,'(',b,'(',t,b,'(',t,t,')',')',')'] ? a

E = u(b(b(t,t),t))
S = [u,'(',b,'(',b,'(',t,t,')',t,')',')']

E = b(t,u(b(t,t)))
S = [b,'(',t,u,'(',b,'(',t,t,')',')',')']

E = b(t,b(t,u(t)))
S = [b,'(',t,b,'(',t,u,'(',t,')',')',')']

E = b(t,b(u(t),t))
S = [b,'(',t,b,'(',u,'(',t,')',t,')',')']

E = b(u(t),b(t,t))
S = [b,'(',u,'(',t,')',b,'(',t,t,')',')']

E = b(u(b(t,t)),t)
S = [b,'(',u,'(',b,'(',t,t,')',')',t,')']

E = b(b(t,t),u(t))
S = [b,'(',b,'(',t,t,')',u,'(',t,')',')']

E = b(b(t,u(t)),t)
S = [b,'(',b,'(',t,u,'(',t,')',')',t,')']

E = b(b(u(t),t),t)
S = [b,'(',b,'(',u,'(',t,')',t,')',t,')']

no

| ?-  phrase(expression(U,B,E), S).

B = 0
E = t
S = [t]
U = 0 ? ;

B = 0
E = u(t)
S = [u,'(',t,')']
U = 1 ? ;

B = 0
E = u(u(t))
S = [u,'(',u,'(',t,')',')']
U = 2 ?
...

Hopefully this answers question #1, and perhaps #4 by example. The general problem of converting any set of predicates to a DCG, though, is more difficult. As I mentioned above, DCG is really for handling sequences.

Using length/2 to control solution order

In answer to #2, now that we have a DCG solution that will generate solutions properly, we can control the order of solutions given by using length/2, which will provide solutions in order of length rather than depth-first. You can constrain the length right from the beginning, which is more effective and efficient than constraining the length at each step in the recursion, which is redundant:

?- length(S, _), phrase(expression(U,B,E), S).

B = 0
E = t
S = [t]
U = 0 ? ;

B = 0
E = u(t)
S = [u,'(',t,')']
U = 1 ? ;

B = 1
E = b(t,t)
S = [b,'(',t,t,')']
U = 0 ? ;

B = 0
E = u(u(t))
S = [u,'(',u,'(',t,')',')']
U = 2 ? ;

B = 1
E = u(b(t,t))
S = [u,'(',b,'(',t,t,')',')']
U = 1 ? ;

B = 1
E = b(t,u(t))
S = [b,'(',t,u,'(',t,')',')']
U = 1 ? ;

B = 1
E = b(u(t),t)
S = [b,'(',u,'(',t,')',t,')']
U = 1 ? 
...

If I were using the sequential representation of the unary-binary tree for constraining solutions, not for parsing, I would get rid of the parentheses since they aren't necessary in the representation:

unary(U, B, u(E)) -->
    [u],
    { U1 #>= 0, U #= U1 + 1 },
    expression(U1, B, E).

binary(U, B, b(E1, E2)) -->
    [b],
    { U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1 },
    expression(U1, B1, E1),
    expression(U2, B2, E2).

It's probably a little more efficient since there are a fewer number of list lengths that correspond to invalid sequences. This results in:

| ?- length(S, _), phrase(expression(U, B, E), S).

B = 0
E = t
S = [t]
U = 0 ? ;

B = 0
E = u(t)
S = [u,t]
U = 1 ? ;

B = 0
E = u(u(t))
S = [u,u,t]
U = 2 ? ;

B = 1
E = b(t,t)
S = [b,t,t]
U = 0 ? ;

B = 0
E = u(u(u(t)))
S = [u,u,u,t]
U = 3 ? ;

B = 1
E = u(b(t,t))
S = [u,b,t,t]
U = 1 ? ;

B = 1
E = b(t,u(t))
S = [b,t,u,t]
U = 1 ? ;

B = 1
E = b(u(t),t)
S = [b,u,t,t]
U = 1 ? ;

B = 0
E = u(u(u(u(t))))
S = [u,u,u,u,t]
U = 4 ? ;

B = 1
E = u(u(b(t,t)))
S = [u,u,b,t,t]
U = 2 ? ;
...

So, if you have a recursive definition of a general term, Term, which can be expressed as a sequence (thus, using a DCG), then length/2 can be used in this way to constrain the solutions and order them by length of sequence, which corresponds to some ordering of the original terms. Indeed, the introduction of the length/2 may prevent your DCG from infinitely recursing without presenting any solutions, but I would still prefer to have the DCG be better behaved to start with by attempting to organize the logic to walk the terminals first.

回答2:

@lurker has already given an excellent answer, and I would like to make a few complementary observations.

First, it would help tremendously if you would post new questions if the need arises to discuss a particular topic in more detail. I can see that the issues you have now raised are all thematically related, and I would now like to give an overall description that I hope addresses the core aspects. However, each of these topics can be discussed in much more detail, and filing new questions would be very worthwhile to allow more room for more elaborate descriptions.

I start with the version that I shall call your initial version:

e_b(t, B, B, U, U).
e_b(u(E), B0, B1, U0, U2) :-
        U1 #= U0 + 1,
        e_b(E, B0, B1, U1, U2).
e_b(b(E0, E1), B0, B3, U0, U2) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B2, U0, U1),
        e_b(E1, B2, B3, U1, U2).

e_b(U, B, Es) :-
        U #=< Us,
        B #=< Bs,
        e_b(Es, 0, Bs, 0, Us).

This settles the first question:

Can CLP(FD) be used with this solution and if so how?

Yes, CLP(FD) can obviously be used: We are already doing so. Note that I conciously call this version the "initial" one, because I simply ignore all attempts that use (is)/2 or (=:=)/2. Simply use (#=)/2 when reasoning over integers, and benefit from its increased generality over low-level arithmetic.

The major problem with this version is that queries that ought to terminate don't terminate:

?- e_b(1, 2, Es), false.
nontermination

Why is this the case? To find a reason, I use failure slices, reducing the whole program to fragments that I can more easily understand. For this, I simply insert calls of false/0 at some points in the program.

You can try arbitrary points. For example, let us keep e_b/3 unchanged, and change e_b/5 to:

e_b(t, B, B, U, U).
e_b(u(E), B0, B1, U0, U2) :-
        U1 #= U0 + 1,
        false,
        e_b(E, B0, B1, U1, U2).
e_b(b(E0, E1), B0, B3, U0, U2) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B2, U0, U1),
        false,
        e_b(E1, B2, B3, U1, U2).

I am using strikeout text to mark goals that cannot cause nontermination. Even with this modified version, we get:

?- e_b(1, 2, Es), false.
nontermination

This means the following simplified version of the program still exhibits the nontermination!

e_b(t, B, B, U, U).
e_b(u(E), B0, B1, U0, U2) :-
        U1 #= U0 + 1.
e_b(b(E0, E1), B0, B3, U0, U2) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B2, U0, U1).

I'm doing this all only to break down the problem into more managable parts. That this possibility exists at all is a major attraction of logic programming. Good luck applying such a technique to other programming languages, or even finding such an approach!

Now, the simplified version does report answers:

?- e_b(1, 2, Es).
Es = u(_1064) ;
Es = b(t, _1066) ;
Es = b(u(_1070), _1066) ;
Es = b(b(t, _1072), _1066) .

But, as I said, our query also does not terminate universally even with this simplified program:

?- e_b(1, 2, Es), false.
nontermination

To correct the problem in the initial version, we must correct it also in this fragment. There's no way around it! Put differently, as long as this termination problem exists in the simplified version, the initial version will not terminate either.

Let us therefore focus on the simplified version, and first adjust the variables so that no more singleton variables appear. These issues have arisen because we have removed some of the goals, and we are now simply linking the pairs properly again:

e_b(t, B, B, U, U).
e_b(u(_), B, B, U0, U1) :-
        U1 #= U0 + 1.
e_b(b(E0, _), B0, B, U0, U) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B, U0, U).

Here's the query again:

?- e_b(1, 2, Es), false.
nontermination

In fact, the following even simpler version still exhibits the nontermination:

e_b(t, B, B, U, U).
e_b(u(_), B, B, U0, U1) :-
        U1 #= U0 + 1.
e_b(b(E0, _), B0, B, U0, U) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B, U0, U).

Here, I have simply removed an entire clause, making this equivalent to:

e_b(t, B, B, U, U).
e_b(b(E0, _), B0, B, U0, U) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B, U0, U).

So, why does this simplified version not terminate?

For reference, here is the entire program we are talking about at this point:

e_b(t, B, B, U, U).
e_b(b(E0, _), B0, B, U0, U) :-
        B1 #= B0 + 1,
        e_b(E0, B1, B, U0, U).

e_b(U, B, Es) :-
        U #=< Us,
        B #=< Bs,
        e_b(Es, 0, Bs, 0, Us).

With the problematic query still being:

?- e_b(1, 2, Es).
nontermination

Now, in this case, we are again getting no solution, even though we expect one. How can we go about debugging this? Let us do the most obvious thing (if you think about it): Let us ask Prolog what solutions there are at all. We do this by posing the most general query, where all arguments are fresh variables:

?- e_b(A, B, Es).
Es = t,
A in inf..0,
B in inf..0 ;
Es = b(t, _3532),
A in inf..0,
B in inf..1 ;
Es = b(b(t, _3550), _3544),
A in inf..0,
B in inf..2 .

Now there are already first signs of problems in these answers. For example, who has ever heard of trees with negative depth?

Let us enforce more reasonable requirements by posting:

?- A #>= 0, B #>= 0, e_b(A, B, Es).
A = B, B = 0,
Es = t ;
A = 0,
Es = b(t, _8094),
B in 0..1 ;
A = 0,
Es = b(b(t, _8112), _8106),
B in 0..2 .

This looks a lot better already, but it does not fix the core issue. To obtain terminating behaviour for more specific queries, you need to find a way to keep the search bounded. I leave this as an exercise for now, and encourage you to file a new question if you want more information about this. Focus on this simple fragment for now!

Now to the second question:

When is the use of length/2 required to constrain the size of DCG results and when can CLP(FD) be used?

length/2 can be used to generate lists of increasing length. DCGs always describe lists. In Prolog, it is natural to use the length of a list as a measure for something. For example, we can use the length of a list as a measure for the depth of terms you are trying to find. This is suitable because Prolog provides nice syntax for lists, and it can be more convenient to reason symbolically than to reason numerically.

When reasoning over integers, use CLP(FD) constraints. Thus, if you decide to use an integer as the measure of something, use CLP(FD) constraints.

This brings us to the third question:

What other means are available to cause iterative deepening with DCG?

length/2 to describe lists of increasing length is by far the most natural way, if the DCG itself takes this measure into account in the list it describes. However, you can also use other ways, if you use a dedicated argument or argument pair to pass the state of the measure around.

The last two questions are related:

How would I convert the non DCG solution back into a DCG version? As my DCG get more complex I will be needing more constraint variables. Is there a standard practice on how to handle this, or just follow the rinse and repeat methodology?

Every time you see a pattern of the form V0 → V1 → V2 →…→ V that is, a variable that is simply passed along in a clause body, you can use DCG semicontext notation to pass it around implicitly. Your code exhibits this pattern, and so DCGs are applicable.

For one variable, use a list with a single element that contains just that variable. If you want to pass around more than one variable, use a list that contains a single term of the form f(...), capturing all variables you want to pass around. This is also well worth its own question.

---

I have one final note on the choice of representation. Please try out the following, using for example GNU Prolog or any other conforming Prolog system:

| ?- write_canonical([op(add),[Left,Right]]). 
'.'(op(add),'.'('.'(_18,'.'(_19,[])),[]))

This shows that this is a rather wasteful representation, and at the same time prevents uniform treatment of all expressions you generate, combining several disadvantages.

You can make this more compact for example using Left+Right, or make all terms uniformly available using for example op_arguments(add, [Left,Right]), op_arguments(number, [1]) etc.