梳理生成器结果并将结果写入流

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

Run Code Online (Sandbox Code Playgroud)

其中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

Run Code Online (Sandbox Code Playgroud)

我也可以生成并输出表达式,但不能使用正确的序列号

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

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

注意序列号都是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.

Run Code Online (Sandbox Code Playgroud)

这仍然是错的.

我寻求的输出是

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

Run Code Online (Sandbox Code Playgroud)

其中每个序列号都是唯一的,顺序从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 ;

Run Code Online (Sandbox Code Playgroud)

序列号现在是正确的,但是从不生成新表达式,因为序列号生成器使用选择点来生成下一个序列号,因此谓词sequence_number不会回溯到generate_expression谓词以获得新表达式.

那么,我可以使用两台依赖于回溯的发电机吗？如果是这样,怎么样？

补充

这与我之前关于树生成器的问题有关.
我知道这应该用dcg完成,并且应该更改数据结构,但是当我试图理解这一点时,以这种方式看到它更容易理解.

撤回回溯

总结一下这个问题,您希望:

使用使用迭代深化的生成器生成表达式
将每个解决方案编号为连续整数.

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

这在纯Prolog 中当然是不可能的:这样做会破坏我们对关系的最基本属性,特别是我们期望回溯撤消计算当前分支中发生的所有事情.

因此,纯粹的解决方案是消除回溯!

我不是在开玩笑:我们现在将改变对解决方案的整个搜索,使得每个解决方案都可以在没有回溯的情况下找到,即使程序看起来好像使用了回溯.事实上,该程序甚至会保持不变,但我们对它的解释与普通Prolog所做的不同.这个策略允许我们携带一个计数器,并为我们找到的每个解决方案配备连续的整数.

从本质上说,我现在实行回溯内 Prolog的,即我在执行回溯不使用的Prolog内建的回溯机制,让我自由地扩展它,因为我想要的.

改善回溯

reify ="使它成为一件事"(来自拉丁语:res,rei f.=物质,事物,事件)

首先,我将以不同的方式表示整个程序,以便更容易推理它.我将使用的表示避免了常规Prolog目标的默认表示,而是使用目标列表.我将每个条款表示为以下形式的事实:

head_body(Head, [Goal₁,Goal₂,...,Goal_n]).

这种变化纯粹是语法上的(即使它对我们的程序中的进一步处理有很大帮助),并且可以很容易地自动化:

head_body(expression_tree([_|N_s],N_s, [number(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),
           expression_tree(N_s1,N_s2, E2)]).

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

mi([G-[]|_], G).
mi([Gs0|Rest], G) :-
        findall(G0-Body, (Gs0 = G0-[First|Others],
                          head_body(First, Body0),
                          append(Body0, Others, Body)), Nexts, Rest),
        mi(Nexts, G).

请注意,在搜索解决方案时,此解释器中不再出现回溯,除了收集所有匹配的子句,并实际报告任何解决方案,这只是接口的一部分而不是核心逻辑的一部分.

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

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

generate_expression(N_c, E) :-
        length(N, N_c),
        mi([E-[expression_tree(N,[],E)]], 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)]]]]]]] .

这相当于你已经拥有的,所以它目前没有多大帮助.顺便说一句,也许现在是摆脱这个"我们有足够的括号"符号的好时机,以便将来的解决方案更容易阅读.考虑例如op_arguments/2用于表示表达式的表单的术语,或者更好的是简单的表单的Prolog术语(+)/2等.

枚举解决方案

现在回到主要观点:使用元解释器的关键优势在于它可以让我们改变 Prolog执行此类程序的简单方式.

在我们的案例中,现在是时候介绍一个解决方案的计数器.我们的第一次尝试可能如下所示:

mi(Alts0, S0, S, G) :-
        (   Alts0 = [G0-[]|Rest] ->
            (   S #= S0,
                G = G0
            ;   S1 #= S0 + 1,
                mi(Rest, S1, S, G)
            )
        ;   Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[First|Others],
                               head_body(First, Body0),
                               append(Body0, Others, Body)), Alts, Rest),
            mi(Alts, S0, S, G)
        ).

调用谓词看起来像这样:

generate_expression(N_c, S, E) :-
        length(N, N_c),
        mi([E-[expression_tree(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,并且对于正在尝试的每个新长度,计数器被重置.

从一开始就公平

因此,我们现在改变解释器,从一开始就实现公平的计算策略.通过公平,我们的意思是每一个存在的解决方案最终被发现.

迭代深化是一种这样的策略.我将此作为练习,并在此示例中实现广度优先搜索.获得广度优先搜索很容易:我们只是添加新的替代品.实际上,由于我们现在要将公平作为解释器的基本属性来实现,我们还可以将程序简化为:

head_body(expression_tree([number(0)]), []).
head_body(expression_tree([op(neg), [E1]]),
          [expression_tree(E1)]).
head_body(expression_tree([op(add), [E1, E2]]),
          [expression_tree(E1),expression_tree(E2)]).

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

mi(Alts0, S0, S, G) :-
        (   Alts0 = [G0-[]|Rest] ->
            (   S #= S0,
                G = G0
            ;   S1 #= S0 + 1,
                mi(Rest, S1, S, G)
            )
        ;   Alts0 = [Gs0|Rest],
            findall(G0-Body, ( Gs0 = G0-[First|Others],
                               head_body(First, Body0),
                               append(Body0, Others, Body)), Alts1),
            append(Rest, Alts1, Alts),
            mi(Alts, S0, S, G)
        ).

我们的主要谓词:

generate_expression(S, E) :-
        mi([E-[expression_tree(E)]], 0, S, E).

现在我们开始:

?- generate_expression(S, E).
S = 0,
E = [number(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中实际推理的谓词参数.

在SWI-Prolog中,您需要使用`library(clpfd)`来使用CLP(FD)约束.你应该默认启用它,把它放在`.swiplrc`中.这样,CLP(FD)约束在所有程序中都可用,例如GNU Prolog. (2认同)

归档时间：	8 年，7 月前
查看次数：	181 次
最近记录：	6 年，10 月前

梳理生成器结果并将结果写入流

补充

相关的SO问题

撤回回溯

改善回溯

枚举解决方案

从一开始就公平

保持纯粹的人!