如何使用具有CLP（FD）和多个约束的DCG枚举组合

Question

这个问题从Mat对枚举二叉树的算法改进的回答开始，二叉树只有一个决定二叉树所有节点数的输入值，需要能够有两个输入值，一个是一元节点数，另一个是二元节点数。

虽然我能够通过使用列表/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工具箱中的一个导入工具是清单/1，它将把DCG转换成标准Prolog。

例如

?- listing(expression).  

对于下面的清单，我还手动更改了变量的名称，以便更容易理解和理解。当DCG转换为标准Prolog时，两个额外的变量可能会作为谓词的最后两个参数出现。在这里我改变了他们的名字。它们将以S0作为倒数第二个参数开始，然后以S1、S2等方式进行，直到它们成为最后一个参数。此外，如果其中一个输入参数通过代码执行，我已经更改了名称，例如U为U0等等。我还添加了clp（fd）约束作为注释。

在部分答案中使用列表/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].

如果您想查看将 clp（fd） 或 DCG 转换为标准 prolog 的源代码，这里是链接。

• clp（fd）
• 直流发电机

把这些当成我的个人笔记，以防我将来不得不回到这个问题上来。如果他们能帮助别人，把他们藏在心里是没有意义的。

关于

何时需要使用长度/2来限制DCG结果的大小，何时可以使用CLP（FD）？

在查看了使用clp（fd）作为约束的代码列表后，我可以开始理解为什么使用构建并行列表和使用长度/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个部分，但是没有为这个答案创建一个新问题，而是删除了这个问题的一部分，这样潜伏者给出的答案就可以留在这里。

1. CLP（FD）是否可以与此解决方案一起使用？如果可以，如何使用
2. 何时需要使用长度/2来限制DCG结果的大小，何时可以使用CLP（FD）
3. 还有什么其他方法可以引起DCG的迭代深化
4. 如何将非DCG解决方案转换回DCG版本
5. 随着我的DCG变得越来越复杂，我将需要更多的约束变量。对于如何处理这一问题，是否有一个标准的做法，或者只是遵循漂洗和重复方法




Answer 1

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

假设二元一元树的复合项表示(例如< code>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）为我提供一元和二元项计数的更多关系推理。我所做的另一件事是将更简单的表达式/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，可以将这些标记或字符映射到复合术语本身。例如，我们可以将复合树术语< code>b(t，u(b(t，t)))表示为< code>[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),
    [')'].

同样，我将终端//3作为表达式//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 ?
...

希望这回答了第一个问题，也可能回答了第四个问题。然而，将任何谓词集转换成DCG的一般问题要困难得多。正如我上面提到的，DCG实际上是用来处理序列的。

使用长度/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 ? ;
...

因此，如果您有一个通用术语的递归定义，< code>Term，它可以表示为一个序列(因此，使用DCG)，那么< code>length/2可以以这种方式来约束解决方案，并按序列的长度对它们进行排序，这对应于原始术语的某种排序。事实上，< code>length/2的引入可能会阻止您的DCG在没有任何解决方案的情况下无限递归，但我仍然希望通过尝试组织逻辑首先遍历终端，使DCG一开始就表现得更好。

Answer 2

匿名用户

@lurker已经给出了一个极好的答案，我想做几个补充观察。

首先，如果您在需要讨论特定主题时发布新问题，这将非常有帮助

我从这个版本开始，我称之为你们的初始版本:

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

这就解决了第一个问题：

CLP(FD)能否用于此解决方案，如果可以，如何使用？

是的，CLP(FD)显然可以使用:我们已经在这样做了。请注意，我有意将这个版本称为“初始”版本，因为我忽略了所有使用< code>(is)/2或< code>(=:=)/2的尝试。在对整数进行推理时，只需使用< code>(#=)/2，并受益于它比低级算术更高的通用性。

这个版本的主要问题是应该终止的查询没有

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

为什么会这样？为了找到原因，我使用失败切片，将整个程序简化为我更容易理解的片段。为此，我只需在程序中的某些点插入false/0的调用。

您可以尝试任意点。例如，让我们保持e_b/3不变，并将e_b/5更改为：

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

我正在使用 删除线 文本来标记不会导致不终止的目标。即使有了这个修改后的版本，我们也得到了：

?- e_b(1, 2, Es), false.
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).

我这样做只是为了将问题分解为更易于管理的部分。这种可能性存在于

现在，简化版确实报告了答案:

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

但是，正如我所说，即使有这个简化的查询，我们的查询也不会普遍终止

?- e_b(1, 2, Es), false.
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).

这又是一个问题:

?- e_b(1, 2, Es), false.
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).

这里，我简单地删除了整个子句，使其等同于:

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

有问题的查询仍然是：

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

现在，在这种情况下，我们再次没有得到解决方案，即使我们期望有一个解决方案。我们如何进行调试？让我们做最明显的事情（如果您考虑

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

现在这些答案中已经出现了问题的最初迹象。例如，谁听说过负面的树木

让我们通过发布以下内容来执行更合理的要求：

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

这看起来已经好多了，但它并没有修复核心

现在来看第二个问题:

何时需要使用长度/2来限制DCG结果的大小，何时可以使用CLP（FD）？

长度/2可用于生成长度不断增加的列表。DCG总是描述列表。在Prolog中，使用列表的长度作为某物的度量是很自然的。例如，我们可以使用列表的长度作为您试图查找的术语深度的度量。这是合适的，因为Prolog为列表提供了很好的语法，并且象征性推理比数字推理更方便。

对整数进行推理时，请使用CLP（FD）约束。因此，如果您决定使用整数作为某事物的度量，请使用CLP（FD）

这就给我们带来了第三个问题:

还有什么其他方法可以引起DCG的迭代深化？

长度/2描述长度不断增加的列表是迄今为止最自然的

最后两个问题是相关的：

如何将非 DCG 解决方案转换回 DCG 版本？随着我的DCG变得越来越复杂，我将需要更多的约束变量。是否有如何处理这个问题的标准做法，或者只是遵循冲洗和重复方法？

每当您看到V0→V1→V2 →…→ V形式的模式时，即在子句中简单传递的变量

对于一个变量，请使用包含仅包含该变量的单个元素的列表。如果您想传递多个

关于代表权的选择，我还有最后一点意见。请尝试以下方法，例如使用 GNU

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

这表明，这是一种相当浪费的表示，同时也防止了对生成的所有表达式的统一处理，这结合了几个缺点。

您可以使用< code>Left Right使其更加简洁，或者使用< code>op_arguments(add，[Left，Right])、< code>op_arguments(number，[1])等使所有术语统一可用。