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

Question

这道题从Mat的 to 开始，只有一个输入值决定了二叉树所有节点的个数，需要能够有两个输入值，其中一个是一元节点，另一个是二进制节点的数量。

虽然我能够通过使用 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 输出。

我对使用 length/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) 的概念，但我对它的实际使用仅次于 none.

所以问题是：

CLP(FD) 可以与此解决方案一起使用吗？如果可以，如何使用？
如何将非 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/1，它将 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 转换为标准序言的源代码，请点击此处的链接。

clp(fd)
dcg

备注

将这些视为我的个人笔记，以防我将来不得不回到这个问题。如果他们可以帮助别人，我就没有必要把它们留给自己。

关于

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

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

关于 clp(fd) 如何避免导致错误

Arguments are not sufficiently instantiated 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 个部分，但没有为该答案创建一个新问题，而是删除了这个问题的部分内容，以便 lurker 给出的可以保留在这里。

CLP(FD) 可以与此解决方案一起使用吗？如果可以，如何使用？
什么时候需要使用length/2来限制DCG结果的大小，什么时候可以使用CLP(FD)？
还有哪些方法可以用DCG进行迭代加深？
如何将非 DCG 解决方案转换回 DCG 版本？
随着我的 DCG 变得越来越复杂，我将需要更多的约束变量。是否有关于如何处理此问题的标准做法，或者只是遵循 rinse and repeat 方法？

Answer 1

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

假设二元树的复合术语表示（例如，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 表现得更好。

Answer 2

@lurker 已经给出了很好的回答，我想补充几点。

首先，如果需要更详细地讨论特定主题，post新问题将大有帮助。我看你现在提出的问题都是主题相关的，我现在想做一个整体的描述，希望能够解决核心问题。但是，每个这些主题都可以更详细地讨论，提交新问题非常值得，以便为更详细的描述留出更多空间。

我从我将称为您的初始版本的版本开始：

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

第一个问题解决了：

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

是，显然可以使用CLP(FD)：我们已经在这样做了。请注意，我有意识地将 this 版本称为 "initial" 版本，因为我只是忽略了所有使用 (is)/2 或 (=:=)/2 的尝试。在对整数进行推理时只需使用 (#=)/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) .

但是，正如我所说，我们的查询 also 不会终止 universally 即使使用这个简化的程序：

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

现在，在这种情况下，我们再次没有解决方案，尽管我们期望有一个解决方案。我们如何着手调试？让我们做最明显的事情（如果你仔细想想）：让我们问 Prolog 有什么解决方案。我们通过提出 最一般的查询 来做到这一点，其中所有参数都是新变量：

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

现在这些答案中已经有了问题的初步迹象。例如，谁听说过 负深度 的树？

让我们通过 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 .

这看起来已经好多了，但并没有解决核心问题。要获得更具体查询的终止行为，您需要找到一种方法来保持搜索有界。我现在将其留作练习，如果您想了解更多信息，鼓励您提出新问题。现在专注于这个简单的片段！

现在第二个问题：

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

length/2 可用于生成列表 增加长度 。 DCG 总是描述列表。在 Prolog 中，很自然地使用列表的长度作为某物的度量。例如，我们可以使用列表的长度来衡量您要查找的术语的深度。这是合适的，因为 Prolog 为列表提供了很好的语法，并且 symbolically 推理比 numerically.

推理更方便
当对整数进行推理时，使用 CLP(FD) 约束 。因此，如果您决定使用整数作为某些事物的度量，请使用 CLP(FD) 约束。

这就引出了第三个问题：

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

length/2 描述长度递增的列表是迄今为止最自然的方式，如果 DCG 本身在其描述的列表中考虑了这种度量。但是，您也可以使用其他方式，如果您使用专用的参数或参数对来传递度量的状态。

后两题相关：

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?

每次看到 V0 形式的模式时 → V1→ V2 →...→ V 即在子句主体中简单传递的变量，您可以使用 DCG 半上下文表示法 将其隐式传递.您的代码表现出这种模式，因此 DCG 是适用的。

对于一个变量，使用 list 和一个仅包含该变量的元素。如果您想传递多个变量，请使用包含 f(...) 形式的单个术语的列表，捕获您想要传递的所有变量。这也很值得自己提出问题。

关于表示形式的选择，我有一个最后的注意事项。请尝试以下操作，例如使用 GNU Prolog 或任何其他符合 Prolog 的系统：

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

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

您可以使用 Left+Right、或使它更紧凑，例如使用 op_arguments(add, [Left,Right])、op_arguments(number, [1]) 使所有术语统一可用等等

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

How to enumerate combinations using DCGs with CLP(FD) and multiple constraints

prolog

dcg

clpfd

implicit-state-passing

补充