Объединение результатов генератора и запись результата в поток

В настоящее время я могу генерировать деревья выражений.

expression_tree([_|N_s],N_s, [number(0)]).
expression_tree([_|N_s0],N_s1, [op(neg),[E1]]) :-
    expression_tree(N_s0,N_s1, E1).
expression_tree([_|N_s0],N_s2, [op(add), [E1, E2]]) :-
    expression_tree(N_s0,N_s1, E1),
    expression_tree(N_s1,N_s2, E2).

generate_expression(N_c, E) :-
    length(N, N_c),
    expression_tree(N,[], E).

?- generate_expression(N,E).
N = 1,
E = [number(0)] ;
N = 2,
E = [op(neg), [[number(0)]]] ;
N = 3,
E = [op(neg), [[op(neg), [[number(0)]]]]] ;
N = 3,
E = [op(add), [[number(0)], [number(0)]]] ;
N = 4,
E = [op(neg), [[op(neg), [[op(neg), [[number(0)]]]]]]] ;
N = 4,
E = [op(neg), [[op(add), [[number(0)], [number(0)]]]]] ;
N = 4,
E = [op(add), [[number(0)], [op(neg), [[number(0)]]]]] ;
N = 4,
E = [op(add), [[op(neg), [[number(0)]]], [number(0)]]] ;
N = 5,
E = [op(neg), [[op(neg), [[op(neg), [[op(neg), [[number(0)]]]]]]]]]

где N - количество узлов для дерева.

Я также могу самостоятельно генерировать порядковые номера.

sequence_number(Sequence_number) :-
    sequence_numbers(1, Sequence_number).

sequence_numbers(I, I).
sequence_numbers(I, K) :-
    J is I + 1,
    sequence_numbers(J, K).

?- sequence_number(N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 5 ;
N = 6

Я также могу генерировать и выводить выражения, но не с правильными порядковыми номерами

print_expression(Stream, Prefix, Suffix, Sequence_number, E) :-
    write(Stream,Prefix),
    format(Stream, '~|~`0t~d~7+', Sequence_number),
    write(Stream,", "),
    write(Stream,E),
    write(Stream,Suffix),
    nl(Stream).



print_expressions_a(Stream, Prefix, Suffix, Sequence_number, N) :-
    generate_expression(N, E),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_a :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    Sequence_number = 1,
    N = 4,
    print_expressions_a(Stream, Prefix, Suffix, Sequence_number, N).

?- print_expressions_a.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000001, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
true ;
(0000001, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
true ;
(0000001, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])
true ;
false.

Обратите внимание, что все порядковые номера 0000001,

Который генерирует точки выбора, поэтому я изменил его, используя forall

print_expressions_b(Stream, Prefix, Suffix, Sequence_number, N) :-
    forall(
        generate_expression(N, E),
        print_expression(Stream, Prefix, Suffix, Sequence_number, E)
    ).

print_expressions_b :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    Sequence_number = 1,
    N = 4,
    print_expressions_b(Stream, Prefix, Suffix, Sequence_number, N).

?- print_expressions_b.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
(0000001, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
(0000001, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
(0000001, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])
true.

Я ищу вывод

(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
(0000002, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
(0000003, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
(0000004, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])

Где каждый порядковый номер является уникальным и последовательным, начиная с 0 или же 1 и может быть записан в файл. Для этого примера поток установлен в user_output упростить вопрос.

Если я добавлю генератор порядкового номера в смесь

print_expressions_c(Stream, Prefix, Suffix, N) :-
    generate_expression(N, E),
    sequence_number(Sequence_number),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_c :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    print_expressions_c(Stream, Prefix, Suffix, N).

?- print_expressions_c.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000002, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000003, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000004, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000005, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;

порядковые номера теперь правильные, но новые выражения никогда не генерируются, потому что генератор порядковых номеров использует точку выбора для генерации следующего порядкового номера и, следовательно, предикат sequence_number, не возвращается к generate_expression Предикат, чтобы получить новое выражение.

Итак, могу ли я использовать два генератора, которые полагаются на последовательный возврат? Если так, то как?

дополнение

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

Связанные вопросы SO

Источник

3 ответа

Решение

Откат назад

Чтобы подвести итог вопроса, вы хотели бы:

  • генерировать выражения с помощью генератора, который использует итеративное углубление
  • нумеруйте каждое решение последовательными целыми числами.

Таким образом, основная проблема, с которой вы сталкиваетесь, заключается в сохранении информации в обратном направлении.

Это, конечно, невозможно в чистом Прологе: это разрушит самые элементарные свойства, которые мы ожидаем от отношений, в частности, наше ожидание того, что обратное отслеживание отменяет все, что произошло в текущей ветви вычисления.

Таким образом, чистым решением является устранение возврата!

Я не шучу: теперь мы изменим весь поиск решений таким образом, что каждое решение будет найдено без возврата, даже если программа выглядит так, как будто она использует возврат. На самом деле, программа останется прежней, но мы интерпретируем ее иначе, чем простой Пролог. Эта стратегия позволяет нам иметь при себе счетчик и снабжать каждое найденное решение последовательными целыми числами.

По сути, я сейчас внедряю возвратный просмотр в Prolog, т. Е. Внедряю возвратный контроль без использования встроенного механизма Prolog для обратного отслеживания, так что я могу свободно расширять его по своему желанию.

Реайтинг

reify = "сделать это вещь" (от латинского: res, rei f. = материя, вещь, дело)

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

head_body (Голова, [Цель 1, Цель 2,..., Цель n ]).

Это изменение носит чисто синтаксический характер (хотя оно очень помогает для дальнейшей обработки в наших программах) и может быть легко автоматизировано:

head_body (выражение_дерево ([_|N_s],N_s, [число (0)]), []).
head_body(expression_tree([_|N_s0],N_s1, [op(neg),[E1]]),
          [expression_tree(N_s0,N_s1, E1)]).
head_body(expression_tree([_|N_s0],N_s2, [op(add), [E1, E2]]),
          [expression_tree(N_s0,N_s1, E1),
           выражение_дерево (N_s1,N_s2, E2)]).

Мы можем интерпретировать эту программу с помощью мета-интерпретатора следующим образом:

ми ([G-[]|_], G).
ми ([Gs0| Отдых], G):-
        findall(G0-Body, (Gs0 = G0-[Первая | Другие],
                          head_body(First, Body0),
                          append(Body0, Others, Body)), Nexts, Rest),
        ми (Nexts, G).

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

Обратите внимание также, что append/3 вызов может быть устранен с помощью списка различий в представлении предложения. Я оставляю это как очень простое упражнение.

Чтобы использовать этот интерпретатор, мы изменим наш основной предикат следующим образом:

выражение_генерирования (N_c, E):-
        длина (N, N_c),
        mi ([E- [expression_tree (N, [], E)]], E).

Пример запроса:

? - генерировать выражение (N, E).
N = 1,
E = [число (0)];
N = 2,
E = [op(neg), [[number(0)]]];
N = 3,
E = [op(neg), [[op(neg), [[number(0)]]]]];
N = 3,
E = [op(add), [[number(0)], [number(0)]]];
N = 4,
E = [op(neg), [[op(neg), [[op(neg), [[number(0)]]]]]]] .

Это эквивалентно тому, что у вас уже есть, и поэтому это не очень помогает в настоящее время. Кстати, может быть, сейчас самое время избавиться от этой нотации "хватит ли еще скобок", чтобы будущие решения было немного легче читать. Рассмотрим, например, условия формы op_arguments/2 представлять выражения, или, еще лучше, просто пролог в терминах формы (+)/2 и т.п.

Перечисление решений

Теперь вернемся к основному вопросу: ключевое преимущество использования мета-интерпретатора состоит в том, что он позволяет нам изменять то, как простой Prolog будет выполнять такие программы.

В нашем случае сейчас самое время ввести счетчик решений. Наша первая попытка может выглядеть так:

mi (Alts0, S0, S, G): -
        (Alts0 = [G0 - [] | Rest] ->
            (S # = S0,
                G = G0; S1 # = S0 + 1,
                ми (Отдых, S1, S, G));   Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[Первая | Другие],
                               head_body(First, Body0),
                               append(Body0, Others, Body)), Alts, Rest),
            mi(Alts, S0, S, G)).

С предикатом вызова, похожим на это:

Генерировать выражение (N_c, S, E):-
        длина (N, N_c),
        mi ([E- [expression_tree (N, [], E)]], 0, S, E).

Это почти решает проблему, но у нас все еще есть следующая проблема:

? - генерировать выражение (_, S, _).
S = 0;
S = 0;
S = 0;
S = 1;
S = 0;
S = 1; 
 S = 2; 
 S = 3;
S = 0;
S = 1; 
 S = 2; 
 S = 3; 
 S = 4; 
 S = 5; 
 S = 6; 
 S = 7; 
 S = 8;
S = 0;
S = 1.

Итак, решения перечислены, но есть и обратный путь: возврат происходит в length/2 и для каждой новой длины счетчик сбрасывается.

Ярмарка с самого начала

Поэтому мы теперь изменим интерпретатор, чтобы реализовать правильную вычислительную стратегию с самого начала. Справедливо, мы имеем в виду, что каждое существующее решение в конце концов найдено.

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

head_body (expression_tree ([number (0)]), []).
head_body (expression_tree ([op (neg), [E1]]),
          [Expression_tree (Е1)]).
head_body (expression_tree ([op (add), [E1, E2]]),
          [Expression_tree (Е1), expression_tree (Е2)]).

Справедливый мета-интерпретатор, реализующий решения поиска и перечисления в ширину:

mi (Alts0, S0, S, G): -
        (Alts0 = [G0 - [] | Rest] ->
            (S # = S0,
                G = G0; S1 # = S0 + 1,
                ми (Отдых, S1, S, G));   Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[Первая | Другие],
                               head_body (First, Body0),
                               append (Body0, Others, Body)), Alts1),
            append (Rest, Alts1, Alts),
            mi (Alts, S0, S, G)).

Наш главный предикат:

выражение_генерирования (S, E): -
        mi ([E- [expression_tree (E)]], 0, S, E).

И здесь мы идем:

? - генерировать выражение (S, E).
S = 0,
E = [число (0)];
S = 1,
E = [op (neg), [[number (0)]]];
S = 2,
E = [op (neg), [[op (neg), [[number (0)]]]]];
S = 3,
E = [op (add), [[number (0)], [number (0)]]];
S = 4,
E = [op (neg), [[op (neg), [[op (neg), [[...]]]]]]];
S = 5,
E = [op (neg), [[op (add), [[number (0)], [number (0)]]]]];
S = 6,
E = [op (add), [[number (0)], [op (neg), [[number (0)]]]]];
S = 7,
E = [op (add), [[op (neg), [[number (0)]]], [number (0)]]].

Оставайтесь чистыми людьми!

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

Обратите внимание также, что я позволил верхнему уровню делать печать. При необходимости я всегда могу написать эти решения где угодно, используя нечистые предикаты, но в первую очередь каждое решение доступно в качестве аргумента предиката, о котором я могу рассуждать в рамках Пролога.

Источник

С чисто прагматической точки зрения, счетчик, который он легко реализует (в SWI-Prolog) с необратимым ассигмнентом:

print_expressions_d(Stream, Prefix, Suffix, N) :-
    generate_expression(N, E),
    inc(Sequence_number),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_d :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    nb_setval(counter,1),
    print_expressions_d(Stream, Prefix, Suffix, N).

inc(V) :- nb_getval(counter,V), C is V+1, nb_setval(counter,C).
Источник 
/* --
1. use `bagof` to obtain a list of the solutions to query `generate_expression(N, E)` .
2. use recursion to :
    2a. iterate each item in the list .
    2b. then assign it a sequence number .
    2c. then print it  .
-- */

/*
example usage :

?- print_expressions_f .
(0000001, generate_expression(4,[op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]]))
(0000002, generate_expression(4,[op(neg),[[op(add),[[number(0)],[number(0)]]]]]))
(0000003, generate_expression(4,[op(add),[[number(0)],[op(neg),[[number(0)]]]]]))
(0000004, generate_expression(4,[op(add),[[op(neg),[[number(0)]]],[number(0)]]]))
true ;
false.
*/

print_expressions_f :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    print_expressions_f(Stream, Prefix, Suffix, N).

print_expressions_f(Stream, Prefix, Suffix, N) :-
    Query = generate_expression(N, E) ,
    bagof(Query,Query,BagofE) ,
    print_expressions_f_every(Stream, Prefix, Suffix, BagofE) .

print_expressions_f_every(Stream, Prefix, Suffix, BagofE) :-
    print_expressions_f_each(Stream, Prefix, Suffix, BagofE, 10'1) .

print_expressions_f_each(Stream, Prefix, Suffix, BagofE, Sequence_number) :-
    [] = BagofE ,
    true .

print_expressions_f_each(Stream, Prefix, Suffix, BagofE, Sequence_number) :-
    [BagofE_head|BagofE_tail] = BagofE ,
    print_expression(Stream, Prefix, Suffix, Sequence_number, BagofE_head) ,
    Sequence_number_next #= Sequence_number + 1 ,
    print_expressions_f_each(Stream, Prefix, Suffix, BagofE_tail, Sequence_number_next) .
Источник
Другие вопросы по тегам