3

这个问题从 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 输出。

我对使用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) 的概念，但我对它的实际使用几乎没有。

所以问题是：

  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 /1，它将 DCG 转换为标准 Prolog。

例如 

?- listing(expression).

对于以下清单，我还手动更改了变量的名称，以便更容易理解和理解。当 DCG 转换为标准 Prolog 时，两个额外的变量可能会作为谓词的最后两个参数出现。在这里，我改变了他们的名字。它们将从S0倒数第二个参数开始，然后按S1、S2等顺序进行，直到它们成为最后一个参数。此外，如果输入参数之一通过代码进行线程化，我已经更改了名称，例如UtoU0等等。我还添加了 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 个部分，但不是为该答案创建一个新问题，而是删除了该问题的部分内容，以便 lurker 给出的答案可以保留在这里。

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

2 回答 2

4

@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 #=< 我们，
        B #=< Bs,
        e_b(Es, 0, Bs, 0, Us)。

这就解决了第一个问题：

CLP(FD) 可以与此解决方案一起使用吗？如果可以，如何使用？

是的，显然可以使用 CLP(FD)：我们已经在这样做了。请注意，我有意将此版本称为“初始”版本，因为我只是忽略了所有使用(is)/2or的尝试(=:=)/2。在对整数进行推理时简单地使用(#=)/2，并受益于它在低级算术上增加的通用性。

这个版本的主要问题是应该终止的查询不会终止：

?- e_b(1, 2, Es), 错误。
不终止

为什么会这样？为了找到原因，我使用了故障切片，将整个程序简化为我更容易理解的片段。为此，我只是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,
        假,
         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)。

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

?- e_b(1, 2, Es), 错误。
不终止

这意味着以下简化版本的程序仍然显示不终止！

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), 错误。
不终止

要更正初始版本中的问题，我们必须在此片段中也进行更正。没有办法解决它！换句话说，只要简化版本存在终止问题，初始版本也不会终止。

因此，让我们关注简化版本，首先调整变量，使不再出现单例变量。这些问题的出现是因为我们删除了一些目标，现在我们只是再次正确地链接这些对：

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), 错误。
不终止

事实上，以下更简单的版本 仍然表现出不终止：

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 #=< 我们，
        B #=< Bs,
        e_b(Es, 0, Bs, 0, Us)。

有问题的查询仍然是：

?- e_b(1, 2, Es)。
不终止

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

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

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

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

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

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

现在到第二个问题：

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

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

对整数进行推理时，请使用CLP(FD) 约束。因此，如果您决定使用整数作为衡量指标，请使用 CLP(FD) 约束。

这就引出了第三个问题：

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

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

最后两个问题是相关的：

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

每次看到V0→ V1→ V2→…→形式的模式，V即在子句主体中简单传递的变量时，您可以使用 DCG半上下文符号来隐式传递它。您的代码展示了这种模式，因此 DCG 是适用的。

对于一个变量，使用一个包含仅包含该变量的单个元素的列表。如果您想传递多个变量，请使用包含表单的单个术语的列表 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])。

于 2017-03-10T16:08:24.860 回答
3

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

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

于 2017-03-08T17:45:15.043 回答