Как перечислить комбинации с использованием DCG с CLP(FD) и несколькими ограничениями

Этот вопрос начинается с ответа Мэта на улучшение Алгоритма для перечисления двоичных деревьев, у которого есть только одно входное значение, которое определяет количество всех узлов для двоичного дерева, и необходимость иметь возможность иметь два входных значения, причем одно является числом унарных узлов а другой - количество двоичных узлов.

Хотя я смог найти решение, используя листинг / 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,[]).

Примечание: см. Вывод Пролога ниже.

Я не был удовлетворен использованием длины / 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].

Ссылки на исходный код SWI-Prolog

Если вы хотите увидеть источник, переводящий clp(fd) или DCG в стандартный пролог, вот ссылки.

Заметки

Думайте об этом как о моих личных заметках на случай, если мне придется вернуться к этому вопросу в будущем. Нет смысла хранить их при себе, если они могут помочь другим.

Что касается

Когда требуется использование длины / 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.

Любой способ полезен, у меня есть личное предпочтение тем, которые сгенерированы из ограничений по причинам, связанным с проектом, который их использует.

Следующая эволюция пришла, вернувшись к ответу Мэта.

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. Когда требуется использование длины / 2 для ограничения размера результатов DCG и когда можно использовать CLP(FD)?
  3. Какие другие средства доступны, чтобы вызвать итеративное углубление с DCG?
  4. Как бы я преобразовал решение без DCG обратно в версию DCG?
  5. Поскольку моя DCG становится более сложной, мне понадобятся дополнительные переменные ограничения. Есть ли стандартная практика, как с этим справиться, или просто следуйте методике полоскания и повторения?
Источник

2 ответа

Решение

Основной синтаксический анализатор выражений дерева со счетчиками

Предполагая составное представление термина для бинарных унарных деревьев (например, 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 первый пункт, который не делает рекурсию. Таким образом, Пролог первым поразит терминалы в процессе изучения возможных решений.

Пример исполнения:

| ?- 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 начинал лучше, пытаясь организовать логику для обхода терминалов в первую очередь.

Источник

@lurker уже дал отличный ответ, и я хотел бы сделать несколько дополнительных замечаний.

Во-первых, было бы очень полезно, если бы вы опубликовали новые вопросы, если возникнет необходимость обсудить конкретную тему более подробно. Я вижу, что все вопросы, которые вы сейчас затронули, тематически связаны, и теперь я хотел бы дать общее описание, которое, я надеюсь, затрагивает основные аспекты. Тем не менее, каждая из этих тем может обсуждаться гораздо более подробно, и было бы очень полезно подать новые вопросы, чтобы было больше места для более сложных описаний.

Я начну с версии, которую я назову вашей первоначальной версией:

e_b (т, 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 # = 
Это решает первый вопрос:
Можно ли использовать CLP(FD) с этим решением, и если да, то как?
Да, CLP(FD), очевидно, можно использовать: мы уже делаем это. Обратите внимание, что я сознательно называю эту версию "начальной", потому что я просто игнорирую все попытки, которые используют (is)/2 или же (=:=)/2, Просто использовать (#=)/2 рассуждая над целыми числами, и получайте выгоду от его большей общности над арифметикой низкого уровня.
Основная проблема этой версии заключается в том, что запросы, которые должны завершаться , не завершаются:
? - e_b (1, 2, Es), false.nontermination
Почему это так? Чтобы найти причину, я использую фрагменты сбоев, превращая всю программу в фрагменты, которые мне легче понять. Для этого я просто вставляю вызовы false/0 в некоторые моменты в программе.
Вы можете попробовать произвольные точки. Например, давайте сохраним e_b/3 без изменений, и изменить e_b/5 чтобы:
e_b (т, 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 (1, 2, Es), false.nontermination
Это означает, что следующая упрощенная версия программы все еще демонстрирует отсутствие термина!
e_b (т, 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 (т, _1066);
Es = b(u(_1070), _1066);
Es = b(b(т, _1072), _1066) .

Но, как я уже сказал, наш запрос также не завершаетсяуниверсально даже с этой упрощенной программой:
? - e_b (1, 2, Es), false.nontermination
Чтобы исправить проблему в начальной версии, мы должны исправить это также в этом фрагменте. Там нет никакого способа обойти это! Иными словами, до тех пор, пока эта проблема завершения существует в упрощенной версии, исходная версия также не будет завершена.
Поэтому давайте сосредоточимся на упрощенной версии и сначала настроим переменные так, чтобы больше не появлялось одноэлементных переменных. Эти проблемы возникли, потому что мы удалили некоторые цели, и теперь мы просто снова правильно связываем пары:
e_b (т, 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 (т, 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 (т, B, B, U, U).
e_b(b(E0, _), B0, B, U0, U):-
        B1 #= B0 + 1,
        e_b(E0, B1, B, U0, U).
Итак, почему эта упрощенная версия не заканчивается?
Для справки, вот вся программа, о которой мы сейчас говорим:
e_b (т, 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 # = 
С проблемным запросом все еще:
? - e_b (1, 2, Es).nontermination
Теперь, в этом случае, мы снова не получаем решения, хотя ожидаем его. Как мы можем отладить это? Давайте сделаем самое очевидное (если вы об этом думаете): давайте спросим у Пролога, какие решения вообще существуют. Мы делаем это, представляя самый общий запрос, где все аргументы являются свежими переменными:
? - e_b (A, B, Es). Es = t,
А в инф..0,
B в инф..0;
Es = b(т, _3532),
А в инф..0,
Б в инф..1;
Es = b(b(т, _3550), _3544),
А в инф..0,
Б в инф..2 .
Теперь уже есть первые признаки проблем в этих ответах. Например, кто нибудь слышал о деревьях с отрицательной глубиной?
Давайте обеспечим более разумные требования, разместив:
? - A #> = 0, B #> = 0, e_b (A, B, Es).
A = B, B = 0,
Es = т;
А = 0,
Es = b(т, _8094),
B в 0,1;
А = 0,
Es = b(b(т, _8112), _8106),
B в 0..2 .
Это уже выглядит намного лучше, но не решает основной проблемы. Чтобы получить завершающее поведение для более конкретных запросов, вам нужно найти способ ограничить поиск. Сейчас я оставляю это как упражнение и призываю вас подать новый вопрос, если вы хотите получить больше информации об этом. Сфокусируйтесь на этом простом фрагменте сейчас!
Теперь ко второму вопросу:
Когда требуется использование длины /2 для ограничения размера результатов DCG и когда можно использовать CLP(FD)?
length/2 может использоваться для создания списков увеличивающейся длины. DCG всегда описывают списки. В Прологе естественно использовать длину списка в качестве меры для чего-либо. Например, мы можем использовать длину списка в качестве меры для глубины терминов, которые вы пытаетесь найти. Это подходит, потому что 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]]). 
' '(оп (добавить),'.'('.'(_18'.'(_19,[])),[]))
Это показывает, что это довольно расточительное представление и в то же время предотвращает единообразную обработку всех генерируемых вами выражений, сочетая в себе несколько недостатков.
Вы можете сделать это более компактным, например, используя Left+Rightили сделать все термины единообразно доступными, используя, например, op_arguments(add, [Left,Right]), op_arguments(number, [1]) и т.п.
Источник
Другие вопросы по тегам