组合生成器结果并将结果写入流
Combing generator results and writing result to stream
目前我可以生成表达式树。
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 问题
- What are the uses of the fail predicate in Prolog?
收回回溯
为了总结这个问题，您想：
- 使用迭代加深的生成器生成表达式
- number个连续整数的解。
因此，您面临的核心问题是在回溯中保留信息。
这在纯序言中当然是不可能：这样做会破坏我们期望从关系中得到的最基本的属性，尤其是我们的期望回溯 撤消 当前计算分支中发生的所有事情。
因此，一个纯粹的解决方案是消除回溯！
我不是在开玩笑：我们现在将改变整个搜索解决方案的方式，即使程序看起来 无需回溯 即可找到每个解决方案=]好像它使用了回溯。事实上，该程序甚至 保持不变 ，但我们对它的解释与普通 Prolog 不同。这个策略允许我们随身携带一个计数器，并为我们找到的每个解决方案配备连续的整数。
本质上，我现在正在 within Prolog 中实现回溯，即，我正在 without 使用 Prolog 的内置机制实现回溯回溯，这样我就可以随意扩展它。
具体化回溯
to reify = "to make it a thing" (from Latin: res, rei f. = matter, thing, affair)
首先，我将以不同的方式表示整个程序，这样更容易推理。我将使用的表示 避免 常规 Prolog 目标的默认表示，而是使用 列表 目标。我将每个子句表示为 fact 形式：
head_body(Head, [Goal1,Goal2,...,Goaln]).
此更改纯粹是语法上的（尽管它对我们程序中的进一步处理有很大帮助），并且可以轻松实现自动化：
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)]]]]]]] .
这 等同于 您已有的，因此目前没有太大帮助。顺便说一句，也许现在是摆脱这种 "have we got enough brackets yet" 符号的好时机，这样未来的解决方案就更容易阅读了。例如，考虑 op_arguments/2 形式的术语来表示表达式，或者更好但更简单的 (+)/2 形式的 Prolog 术语等
枚举解决方案
现在回到要点：使用元解释器的主要优点是它让我们改变 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 中，并且对于正在尝试的每个新长度，计数器都会重置.
从一开始就公平
因此，我们现在更改解释器以从一开始就实施 公平 计算策略。 公平，我们的意思是每个存在的解决方案最终都会找到。
迭代深化就是这样一种策略。我将此留作练习，并在此示例中实施 广度优先搜索。获得广度优先搜索很容易：我们只需 append 新的备选方案。事实上，既然我们现在要实现公平作为解释器的基础属性，我们也可以简化程序阅读：
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)]]] .
保持纯洁！
使用这种 纯 方法来解决问题给了我们一些希望将其推广到其他组合器，因为不同的关注点可以相对隔离地解决，并且原始程序可以保持原样。
另请注意，我让 toplevel 进行打印。如有必要，我总是可以使用不纯谓词在任何我想写的地方写这些解决方案，但首先也是最重要的是，每个解决方案都可以作为谓词参数使用，我可以在 within Prolog 中实际推理。
从纯粹实用的角度来看，一个计数器很容易实现（在 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) .
目前我可以生成表达式树。
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 问题
- What are the uses of the fail predicate in Prolog?
收回回溯
为了总结这个问题，您想：
- 使用迭代加深的生成器生成表达式
- number个连续整数的解。
因此，您面临的核心问题是在回溯中保留信息。
这在纯序言中当然是不可能：这样做会破坏我们期望从关系中得到的最基本的属性，尤其是我们的期望回溯 撤消 当前计算分支中发生的所有事情。
因此，一个纯粹的解决方案是消除回溯！
我不是在开玩笑：我们现在将改变整个搜索解决方案的方式，即使程序看起来 无需回溯 即可找到每个解决方案=]好像它使用了回溯。事实上，该程序甚至 保持不变 ，但我们对它的解释与普通 Prolog 不同。这个策略允许我们随身携带一个计数器，并为我们找到的每个解决方案配备连续的整数。
本质上，我现在正在 within Prolog 中实现回溯，即，我正在 without 使用 Prolog 的内置机制实现回溯回溯，这样我就可以随意扩展它。
具体化回溯
to reify = "to make it a thing" (from Latin: res, rei f. = matter, thing, affair)
首先，我将以不同的方式表示整个程序，这样更容易推理。我将使用的表示 避免 常规 Prolog 目标的默认表示，而是使用 列表 目标。我将每个子句表示为 fact 形式：
head_body(Head, [Goal1,Goal2,...,Goaln]).
此更改纯粹是语法上的（尽管它对我们程序中的进一步处理有很大帮助），并且可以轻松实现自动化：
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)]]]]]]] .
这 等同于 您已有的，因此目前没有太大帮助。顺便说一句，也许现在是摆脱这种 "have we got enough brackets yet" 符号的好时机，这样未来的解决方案就更容易阅读了。例如，考虑 op_arguments/2 形式的术语来表示表达式，或者更好但更简单的 (+)/2 形式的 Prolog 术语等
枚举解决方案
现在回到要点：使用元解释器的主要优点是它让我们改变 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 中，并且对于正在尝试的每个新长度，计数器都会重置.
从一开始就公平
因此，我们现在更改解释器以从一开始就实施 公平 计算策略。 公平，我们的意思是每个存在的解决方案最终都会找到。
迭代深化就是这样一种策略。我将此留作练习，并在此示例中实施 广度优先搜索。获得广度优先搜索很容易：我们只需 append 新的备选方案。事实上，既然我们现在要实现公平作为解释器的基础属性，我们也可以简化程序阅读：
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)]]] .
保持纯洁！
使用这种 纯 方法来解决问题给了我们一些希望将其推广到其他组合器，因为不同的关注点可以相对隔离地解决，并且原始程序可以保持原样。
另请注意，我让 toplevel 进行打印。如有必要，我总是可以使用不纯谓词在任何我想写的地方写这些解决方案，但首先也是最重要的是，每个解决方案都可以作为谓词参数使用，我可以在 within Prolog 中实际推理。
从纯粹实用的角度来看，一个计数器很容易实现（在 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) .