prolog - 合并生成器结果并将结果写入流

Question

目前我可以生成表达式树。

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

其中每个序列号都是唯一的，并且从0or开始是连续的，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 问题

• Prolog中失败谓词的用途是什么？
• 如何使用回溯在 Prolog 中无限增加变量
• 枚举二叉树的算法改进
• 如何使用具有 CLP(FD) 和多个约束的 DCG 枚举组合

Answer 1

收回回溯

总结这个问题，你想：

• 使用使用迭代深化的生成器生成表达式
• 用连续整数为每个解编号。

因此，您面临的核心问题是保留信息而不是回溯。

这在纯 Prolog 中当然是不可能的：这样做会破坏我们期望从关系中得到的最基本属性，特别是我们期望回溯会撤消当前计算分支中发生的一切。

因此，一个纯粹的解决方案是消除回溯！

我不是在开玩笑：我们现在将更改对解决方案的整个搜索，使每个解决方案都无需回溯即可找到，即使程序看起来好像使用回溯。事实上，程序甚至会保持不变，但我们对它的解释与普通 Prolog 的解释不同。这种策略允许我们随身携带一个计数器，并为我们找到的每个解决方案配备连续整数。

本质上，我现在是在Prolog 中实现回溯，即我在不使用 Prolog 的内置回溯机制的情况下实现回溯，因此我可以随意扩展它。

物化回溯

to reify =“使它成为一件事”（来自拉丁语：res，rei f. = 物质，事物，事件）

首先，我将用不同的方式表示整个程序，以便更容易推理。我将使用的表示避免了常规 Prolog 目标的默认表示，而是使用目标列表。我将每个子句表示为以下形式的事实：

head_body（头，[目标1，目标2，...，目标n ]）。

这种变化纯粹是语法上的（尽管它极大地有助于我们程序中的进一步处理），并且可以很容易地自动化：

head_body(表达式树([_|N_s],N_s, [number(0)]), [])。
head_body(表达式树([_|N_s0],N_s1, [op(neg),[E1]]),
          [表达式树（N_s0，N_s1，E1）]）。
head_body(表达式树([_|N_s0],N_s2, [op(add), [E1, E2]]),
          [表达式树（N_s0，N_s1，E1），
           表达式树（N_s1，N_s2，E2）]）。

我们可以使用如下的元解释器来解释这个程序：

米（[G-[]|_]，G）。
米（[Gs0|休息]，G）：-
        findall(G0-Body, (Gs0 = G0-[First|Others],
                          head_body(First, Body0),
                          append(Body0, Others, Body)), Nexts, Rest),
        米（下一个，G）。

注意，这个解释器在搜索解时不再发生回溯，除了收集所有匹配的子句，并实际报告任何解，这只是接口的一部分，而不是核心逻辑。

另请注意，可以通过在子句表示中使用列表差异append/3来消除调用。我把它作为一个非常简单的练习。

要使用此解释器，我们将主要谓词更改为：

生成表达式（N_c，E）：-
        长度（N，N_c），
        mi([E-[表达式树(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来表示表达式，或者更好但更简单的形式的 Prolog 术语(+)/2等。

枚举解决方案

现在回到重点：使用元解释器的关键优势在于它可以让我们改变普通 Prolog 执行此类程序的方式。

在我们的案例中，现在是时候为解决方案引入计数器了。我们的第一次尝试可能如下所示：

mi(Alts0, S0, S, G) :-
        ( Alts0 = [G0-[]|休息] ->
            ( S #= S0,
                G = G0
            ; S1 #= S0 + 1,
                mi（休息，S1，S，G）
            )
        ; Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[First|Others],
                               head_body(First, Body0),
                               append(Body0, Others, Body)), Alts, Rest),
            英里（Alts，S0，S，G）
        ）。

调用谓词如下所示：

生成表达式（N_c，S，E）：-
        长度（N，N_c），
        mi([E-[表达式树(N,[],E)]], 0, S, E)。

这几乎解决了这个问题，但我们仍然有以下问题：

?- generate_expression(_, 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，并且对于正在尝试的每个新长度，计数器都会重置。

从一开始就公平

因此，我们现在更改解释器以从一开始就实施公平的计算策略。公平地说，我们的意思是最终 找到每一个存在的解决方案。

迭代深化就是这样一种策略。我将此作为练习，并在此示例中实现广度优先搜索。获得广度优先搜索很容易：我们只需添加新的替代方案。事实上，既然我们现在即将实现公平作为解释器的基本属性，我们还可以将程序简化为：

头体（表达式树（[编号（0）]），[]）。
头体（表达式树（[op（否定），[E1]]），
          [表达式树（E1）]）。
head_body(表达式树([op(add), [E1, E2]]),
          [表达式树（E1），表达式树（E2）]）。

一个公平的元解释器，实现广度优先搜索和枚举解决方案：

mi(Alts0, S0, S, G) :-
        ( Alts0 = [G0-[]|休息] ->
            ( S #= S0,
                G = G0
            ; S1 #= S0 + 1,
                mi（休息，S1，S，G）
            )
        ; Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[First|Others],
                               head_body(First, Body0),
                               附加（Body0，其他，Body）），Alts1），
            追加（休息，Alts1，Alts），
            英里（Alts，S0，S，G）
        ）。

我们的主要谓词：

generate_expression(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)]]]。

保持纯洁的人们！

使用这种纯粹的方法来解决问题让我们有希望将其推广到其他组合器，因为不同的问题可以相对孤立地解决，并且原始程序可以保持原样。

另请注意，我让顶层进行打印。如有必要，我总是可以在任何我想使用不纯谓词的地方编写这些解决方案，但首先，每个解决方案都可以用作我可以在 Prolog 中实际推理的谓词参数。

Answer 2

从纯粹实用的角度来看，一个计数器很容易实现（在 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).

Answer 3

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