如何使用具有CLP(FD)和多个约束的DCG枚举组合 [英] How to enumerate combinations using DCGs with CLP(FD) and multiple constraints

查看：98
本文介绍了如何使用具有CLP(FD)和多个约束的DCG枚举组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

此问题从Mat的答案到 listing/1来得出解决方案和线程化额外的状态变量:

 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,[]).

注意:请参见下面的Prolog输出.

我不满意使用长度/2 作为一个约束，因为它的使用不明显并且未使用DCG.从先前针对其他问题的其他尝试中，我知道将数字用作约束会失败，例如

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

但是，通过搜索，我发现CLP(FD)与DCG的用途，并决定尝试使用这种方式.

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

但是，这将导致无限循环不返回结果.
注意:我了解CLP(FD)的概念，但是我的实际使用几乎没有.

所以问题是:

  1. 可以将CLP(FD)与该解决方案一起使用吗?
  2. 如何将非DCG解决方案转换回DCG版本?

补充

起始代码和清单

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

序言输出

 ?- 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.

答案列表

对于不熟悉DCG的用户，Prolog工具框中提供的一种导入工具是 ?- listing(expression).

对于以下清单，我还手动更改了变量的名称，以使它们更易于理解.当DCG转换为标准Prolog时，可能会有两个额外的变量作为谓词的最后两个参数.在这里，我更改了他们的名字.它们将以S0作为第二个倒数第二个参数，然后以S1，S2依次类推，以此类推，直到它们成为最后一个参数.另外，如果输入参数之一通过代码进行了线程处理，我也会更改名称，例如U到U0，依此类推.我还添加了clp(fd)约束作为注释.

在部分答案中使用 listing/1 :

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

对SWI-Prolog源代码的引用

如果您想查看将clp(fd)或DCG转换为标准prolog的源代码，则为链接.

注释

把这些当作我的个人笔记，以防将来我不得不再次提出这个问题.如果他们可以帮助别人，把他们留给我自己是没有意义的.

关于

什么时候需要使用length/2来限制DCG结果的大小?什么时候可以使用CLP(FD)?

查看了使用clp(fd)作为约束的代码清单之后，我可以开始理解为什么要使用构建并行列表并使用length/2的原因.我没想到代码会那么复杂.

关于clp(fd)如何避免引起错误

没有足够实例化参数1 =:= _ 2692

可以看出它检查了变量是否绑定

例如

 integer(U1)
var(U0)

代码演变

基于@lurker的回答，我能够将代码扩展为该代码，从而能够生成给定的一元操作列表，二元操作列表和列表，从而生成唯一一元二进制树的所有组合.终端.尽管它可以生成表达式的组合，但是在用于生成我需要的表达式之前，它仍然需要一个中间步骤来重新排列三个列表中项目的顺序. 

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

这是我需要的部分

 ?- 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.

这是查看它们唯一性的一种好方法.

 ?- 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.

如果您一直在阅读评论，那么您知道可以只将一个列表作为约束条件，而没有列表作为约束条件.

如果您使用禁用列表作为约束

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

你得到

 ?- 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.

和

 ?- 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.

这两种方法都很有用，出于个人原因，我只是偏爱从约束生成的约束.

下一个演变是通过回溯到Mat的答案得出的.

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

我不会显示结果或对此进行详细解释，因为此时它应该是微不足道的.值得注意的是，它会生成两种不同类型的结果，第一种为列表，第二种为复合词.

最初的5个问题

原始问题有5个部分，但是并未为此问题创建一个新问题，而是删除了该问题的部分内容，以便潜行者给出的答案可以留在这里.

  1. 可以将CLP(FD)与该解决方案一起使用吗?
  2. 什么时候需要使用length/2来限制DCG结果的大小?什么时候可以使用CLP(FD)?
  3. 还有哪些其他方法可以导致DCG迭代加深?
  4. 如何将非DCG解决方案转换回DCG版本?
  5. 随着DCG变得越来越复杂，我将需要更多约束变量.是否有关于如何处理此问题的标准方法，或者只是遵循冲洗并重复方法?

解决方案

带有计数器的基本树表达式解析器

假定二进制一元树(例如，b(t,u(b(t,t,))))的复合项表示形式，这是一个基本的解析器.通常建议使用CLP(FD)进行整数推理.

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

我在这里故意做了几件事.一种是使用CLP(FD)为我提供更多有关一元和二进制项计数的关系推理.我做过的另一件事是将更简单的expression/3子句放在第一位，该子句不执行递归.这样，Prolog将在探索可能的解决方案的过程中首先打入终端.

执行示例:

 | ?- 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 ? ;
...

使用DCG进行顺序表示

DCG用于解析序列.可以将复合术语解析为标记或字符的序列，可以通过使用DCG将其映射到复合术语本身.例如，我们可以将复合树术语b(t,u(b(t,t)))表示为[b, '(', t, u, '(', b, '(', t, t, ')', ')', ')'].然后，我们可以使用DCG并包含该表示形式.这是一个DCG，它使用以下序列格式反映了上述实现:

 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),
    [')'].

同样，我将terminal//3作为对expression//3的第一门查询过程.您可以看到此版本与非DCG版本之间的并行性.这是执行示例.

 | ?-  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 ?
...

希望这可以回答问题1，举例来说，也许可以回答问题4.但是，将任何谓词集转换为DCG的一般问题更加困难.如上所述，DCG实际上是用于处理序列的.

使用length/2控制解决方案的顺序

为回答#2，现在我们有了一个可以正确生成解决方案的DCG解决方案，我们可以控制使用length/2给出的解决方案的顺序，该解决方案将按长度而不是深度优先的顺序提供解决方案.您可以从一开始就限制长度，这比在递归的每个步骤中限制长度更有效和高效，这是多余的:

 ?- 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 ? 
...

如果我将一元二叉树的顺序表示形式用于约束解决方案，而不是用于解析，则我将摆脱括号，因为在表示形式中它们不是必需的:

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

由于与无效序列相对应的列表长度较少，因此效率可能更高一些.结果是:

 | ?- 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 ? ;
...

因此，如果您有一个通用术语Term的递归定义，可以将其表示为一个序列(因此，使用DCG)，则可以按这种方式使用length/2来约束解，并且按照序列的长度对它们进行排序，这与原始术语的某种排序相对应.确实，length/2的引入可能会阻止DCG无限递归而不提供任何解决方案，但是我仍然希望通过尝试组织逻辑来首先行走终端来使DCG表现得更好. >

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.

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?

解决方案

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.

这篇关于如何使用具有CLP(FD)和多个约束的DCG枚举组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆