问题描述
这是来自 Mat 的 回答
从这里开始
e([number(0)] , t1 , Uc0 , Uc0, Bc0 , Bc0) -->[].e([number(1)] , t2 , Uc0 , Uc0, Bc0 , Bc0) -->[].e([number(2)] , t3 , Uc0 , Uc0, Bc0 , Bc0) -->[].e([op(neg),[Arg]] , u1(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->[_],e(Arg, E, Uc0, Uc1, Bc0, Bc1).e([op(ln),[Arg]] , u2(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->[_],e(Arg, E, Uc0, Uc1, Bc0, Bc1).e([op(add),[Left,Right]], b1(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->[_,_],e(左, E0, Uc0, Uc1, Bc0, Bc1),e(右,E1,Uc1,Uc2,Bc1,Bc2).e([op(sub),[Left,Right]], b2(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->[_,_],e(左, E0, Uc0, Uc1, Bc0, Bc1),e(右,E1,Uc1,Uc2,Bc1,Bc2).e(U,B,EL,Es) :-长度(UL,U),长度(BL,B),短语(e(EL,Es,UL,[],BL,[]),_).e(N,EL,Es) :-长度([_|Ls],N),短语(e(EL,Es,_,[],_,[]),Ls).e_count(E,计数):-长度([_|Ls],E),findall(., 短语(e(_,_,_,[],_,[]), Ls), Sols),长度(溶胶,计数).
然后阅读
对于一个变量,使用一个包含一个元素的列表那个变量.如果您想传递多个变量,请使用包含 f(...) 形式的单个术语的列表,捕获所有您想要传递的变量.这也很值得自己的问题.
演变成这个
e( f([number(0)], t1, Uc0, Uc0, Bc0, Bc0) ) -->[].e( f([number(1)], t2, Uc0, Uc0, Bc0, Bc0) ) -->[].e( f([number(2)], t3, Uc0, Uc0, Bc0, Bc0) ) -->[].e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->[_],e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->[_],e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).e( f([op(add), [Left,Right]], b1(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) -->[_,_],e(f(左, E0, Uc0, Uc1, Bc0, Bc1) ),e(f(右,E1,Uc1,Uc2,Bc1,Bc2)).e( f([op(sub), [Left,Right]], b2(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) -->[_,_],e(f(左, E0, Uc0, Uc1, Bc0, Bc1) ),e(f(右,E1,Uc1,Uc2,Bc1,Bc2)).e(U,B,EL,Es) :-长度(UL,U),长度(BL,B),短语(e(f(EL,Es,UL,[],BL,[])),_).e_N(N,EL,Es) :-长度([_|Ls],N),短语(e(f(EL,Es,_,[],_,[])),Ls).e_count(E,计数):-长度([_|Ls],E),findall(., 短语(e(f(_,_,_,[],_,[])), Ls), Sols),长度(溶胶,计数).
哪个有效,但要注意使用一个包含f(...)形式的单个术语的列表
,这里是f(...)
不在列表中.
我是不是哪里出错了?
补充
参考文献
- 在美国思考 作者:Markus Triska
- Prolog DCG Primer by Markus Triska
- 额外参数 立即学习 Prolog!
隐式状态传递的变量名称约定
通常在使用 implicit-state-passing 变量被命名
S0
→S1
→…→S
但是对于我的一元二叉树示例,我将它们命名为
S0
→S1
→…→Sn
以 Sn
而不是 S
结尾.
例如
标准
e(S0,S) :-
这里
e(S0,S2) :-
原因是这个例子有一个相当罕见的属性,即每个 DCG 谓词的长度增加,
例如
e([number(0)] , t1 , Uc0 , Uc0, Bc0 , Bc0) -->e([op(neg),[Arg]] , u1(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->e([op(add),[Left,Right]], b1(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->
所以以 xn
结尾让我再一次检查准确性.
参考:ISO/IEC DTR 13211–3:2006 定句语法规则
6.1.3 终端序列的变量名约定
此 TR 使用名为 S0、S1、...、S 的变量来表示终端序列在处理语法规则或扩展时用作参数语法规则变成从句.在这种表示法中,变量 S0、S1、...,S可以看成是一个状态序列,其中S0代表初始状态和代表最终状态的变量 S.因此,如果变量 Si 表示给定的终端序列状态,变量 Si+1 将代表剩余的用语法规则解析 Si 后的终端序列.
DCG 总是描述一个列表.
但是哪个列表呢?您必须决定如何使用该机制!
在上述情况下,似乎您已经使用了 DCG 来描述一个列表,您将其长度用作搜索深度的度量.
这完全没问题,而且非常自然地使用 DCG.
但是,您只能描述一个列表,不能同时描述两个,至少不能以主要"方式描述.您当然可以通过 DCG arguments 同时描述任意多个术语.然而,DCG body 仅限于通过调用非终结符和使用终结符来描述 一个 列表.
有一种直接的方法可以将 DCG 转换为常规的 Prolog 代码没有 DCG,或者通过常规的 Prolog 解释 DCG 规则.有关详细信息,请参见例如 ISO 草案.
例如,让我们只看这个片段:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->[_],e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->[_],e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).让我们摆脱 DCG 语法,将其 例如写成:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1, [_|Rest0], Rest) ) :-e( f(Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest) ).e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1, [_|Rest0], Rest) ) :-e( f(Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest) ).(请注意,您当然不应该依赖任何特定的扩展方法,而是始终使用 phrase/2
接口来调用 DCG.不过,以上是一种执行这种扩展的方法,获得常规的Prolog代码.)
切换参数
假设我们想返回再次使用 DCG 表示法,因为它非常方便.例如,在使用 DCG 表示法时,我们显然需要考虑更少的变量,而这本身就已经是一个巨大的优势了.
所以,我们当然可以回到我们最初的 DCG,使用终端代替我们引入的用于描述列表差异的最后两个新 参数.
但我们也可以做别的事情!
例如,在上面的代码片段中,我们注意到 Bc0
和 Bc1
是只穿插:没有一个子句真正关心这些论点.所以,假设我们用 DCG 机制来描述这两个论点.
这可能如下所示:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).这里,我从常规的Prolog版本开始,引入了DCG符号,简单地将Bc0
和Bc1
变成了implicit参数!它们不再出现at all.只有当我们再次将其扩展回 Prolog 时,它们才会变得可见,或者至少这是一种方法.
但是,还有两个问题:
首先,如果我们真的想要访问这些参数怎么办?当然不是 all 子句只能像这样穿过它们.我们还需要在某处访问它们.其次,还有一个更基本的问题:我们想讨论一个参数,它可以是任何 term,但 DCG 总是描述一个列表!
那么,我们如何调和这一切呢?
最重要的是,我们要讲列表,所以解决方法很简单:我们讲一个单一元素的列表,即列表 [Bc0]和 .这使得 DCG 表示法在这种情况下适用在 all.
接下来,我们如何在DCG中表达
Bc0
和Bc1
之间的关系?为此,我们使用半上下文符号:它让我们谈论以前不在我们描述的列表中的元素.
如 DCG 入门中所述,以下形式的非终结符将很有用:
状态(S0,S),[S] --> [S0].你可以将非终结符state(S0, S)
读作:当前状态为S0
,从此为 S
.
因此,if 您想实际访问 Bc0
并将其与您的一个子句中的 Bc1
相关联,您可以这样做:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->状态(Bc0, Bc1),...(涉及 Bc0 和 Bc1)...e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).主要优点是:这种表示法让您隐藏附加参数,并且仍然让您可以显式访问它们如果您需要 它,使用 state//2
(或直接使用半上下文符号).
这显然变得越来越有吸引力在你的代码中实际使用的参数越少.如果几乎所有子句都访问参数,那么隐藏它们是没有意义的.但是,您经常会描述贯穿的术语,而只有极少数 DCG 子句实际访问它们.在这种情况下,请考虑使用 DCG 表示法来隐式传递它们.
但是还有一个问题:如果我们想要传递的不仅仅是一个项,而是两个或更多?有一个非常简单的解决方案:让我们仍然传递一个包含单个元素的列表,但让该元素简单地成为 f(Arg1,Arg2,...,Arg_n)
.因此,您对非终端的调用 e//N
可能如下所示:
?- 短语(e(Arg1,Arg2,...,Arg_N), [f(B1,B2,...,B_M)], [Result]).这里,B1
、B2
等是您想要隐式传递的参数,以列表的形式结合所有这些参数的单个元素.
假设这回答了您的问题,合适的标题可能是:应用半上下文符号来传递附加参数".实际问题很清楚,而且我认为在这种情况下至关重要的是,您希望应用半上下文符号来传递其他参数即使您已经使用 DCG 符号来描述其他内容.总而言之,一个解决方案是首先释放 DCG 符号,以便您可以使用描述的列表来传递其他参数.
请注意,还有其他解决方案:例如,您可以设计自己的 自定义表示法,与 DCG 表示法完全类似,但扩展为允许您描述 两个同时独立 列表.我把它留作练习.
This is a follow-on question from an earlier question from Mat's answer
Starting with this
e([number(0)] , t1 , Uc0 , Uc0, Bc0 , Bc0) --> [].
e([number(1)] , t2 , Uc0 , Uc0, Bc0 , Bc0) --> [].
e([number(2)] , t3 , Uc0 , Uc0, Bc0 , Bc0) --> [].
e([op(neg),[Arg]] , u1(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->
[_],
e(Arg , E , Uc0, Uc1, Bc0, Bc1).
e([op(ln),[Arg]] , u2(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->
[_],
e(Arg , E , Uc0, Uc1, Bc0, Bc1).
e([op(add),[Left,Right]], b1(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->
[_,_],
e(Left, E0, Uc0, Uc1, Bc0, Bc1),
e(Right, E1, Uc1, Uc2, Bc1, Bc2).
e([op(sub),[Left,Right]], b2(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->
[_,_],
e(Left, E0, Uc0, Uc1, Bc0, Bc1),
e(Right, E1, Uc1, Uc2, Bc1, Bc2).
e(U,B,EL,Es) :-
length(UL, U),
length(BL, B),
phrase(e(EL,Es,UL,[],BL,[]), _).
e(N,EL,Es) :-
length([_|Ls], N),
phrase(e(EL,Es,_,[],_,[]),Ls).
e_count(E, Count) :-
length([_|Ls], E),
findall(., phrase(e(_,_,_,[],_,[]), Ls), Sols),
length(Sols, Count).
then reading
evolved into this
e( f([number(0)], t1, Uc0, Uc0, Bc0, Bc0) ) --> [].
e( f([number(1)], t2, Uc0, Uc0, Bc0, Bc0) ) --> [].
e( f([number(2)], t3, Uc0, Uc0, Bc0, Bc0) ) --> [].
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->
[_],
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).
e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->
[_],
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).
e( f([op(add), [Left,Right]], b1(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) -->
[_,_],
e(f(Left, E0, Uc0, Uc1, Bc0, Bc1) ),
e(f(Right, E1, Uc1, Uc2, Bc1, Bc2) ).
e( f([op(sub), [Left,Right]], b2(E0,E1) ,Uc0, Uc2, [_|Bc0], Bc2) ) -->
[_,_],
e(f(Left, E0, Uc0, Uc1, Bc0, Bc1) ),
e(f(Right, E1, Uc1, Uc2, Bc1, Bc2) ).
e(U,B,EL,Es) :-
length(UL, U),
length(BL, B),
phrase(e(f(EL,Es,UL,[],BL,[])), _).
e_N(N,EL,Es) :-
length([_|Ls], N),
phrase(e(f(EL,Es,_,[],_,[])),Ls).
e_count(E, Count) :-
length([_|Ls], E),
findall(., phrase(e(f(_,_,_,[],_,[])), Ls), Sols),
length(Sols, Count).
which works but it is noted use a list that contains a single term of the form f(...)
, and here f(...)
is not in a list.
Did I go wrong somewhere?
Supplement
References
- Thinking in States by Markus Triska
- Prolog DCG Primer by Markus Triska
- Extra Arguments with Learn Prolog Now!
Variable names convention with implicit state passing
Normally when using implict-state-passing the variables are named
S0
→ S1
→…→ S
However for my uniary-binary tree examples I name them like
S0
→ S1
→…→ Sn
ending with Sn
instead of S
.
e.g.
standard
e(S0,S) :-
here
e(S0,S2) :-
the reason being that this example has a rather rare property of each DCG predicate having increasing length,
e.g.
e([number(0)] , t1 , Uc0 , Uc0, Bc0 , Bc0) -->
e([op(neg),[Arg]] , u1(E) , [_|Uc0], Uc1, Bc0 , Bc1) -->
e([op(add),[Left,Right]], b1(E0,E1) , Uc0 , Uc2, [_|Bc0], Bc2) -->
so ending with xn
gives me one more check on accuracy.
Reference: ISO/IEC DTR 13211–3:2006 Definite clause grammar rules
解决方案 A DCG always describes a list.
But which list? You have to decide how to dedicate the mechanism!
In the above cases, it seems you have already dedicated DCGs to describe a list whose length you use as a measure for the depth of the search.
That's completely OK, and a very natural use of DCGs.
However, you can only describe one list, not two at the same time, at least not in the "primary" way. You can of course describe arbitrarily many terms at the same time via DCG arguments. However, the DCG body is limited to describing just one list, by invoking nonterminals, and using terminals.
There is a straight-forward way to convert DCGs to regular Prolog code without DCGs, or to interpret DCG rules via regular Prolog. See for example the ISO draft for more information.
For example, let us take just this snippet:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->
[_],
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).
e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1) ) -->
[_],
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1) ).
Let's get rid of the DCG syntax, and write it for example as:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, Bc0, Bc1, [_|Rest0], Rest) ) :-
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest) ).
e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, Bc0, Bc1, [_|Rest0], Rest) ) :-
e( f(Arg, E, Uc0, Uc1, Bc0, Bc1, Rest0, Rest) ).
(Note of course that you should not rely on any particular expansion method, but always use the phrase/2
interface to invoke a DCG. Still, the above is one way to perform such an expansion, obtaining regular Prolog code.)
Switching arguments
Suppose we want to go back to using DCG notation again, because it is so convenient. For example, we obviously need to think about fewer variables when using DCG notation, and that can in itself already be a huge advantage.
So, we can of course go back to our initial DCG, using terminals instead of our last two new arguments that we introduced to describe a list difference.
But we can also do something else!
For example, in the snippet above, we note that Bc0
and Bc1
are only threaded through: None of the clauses really cares about these arguments. So, suppose we dedicate the DCG mechanism to describe these two arguments.
This could for example look as follows:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->
e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).
e( f([op(ln) , [Arg]], u2(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->
e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).
Here, I have started from the regular Prolog version, introduced DCG notation, and simply turned Bc0
and Bc1
into the implicit arguments! They no longer appear at all here. Only if we again expand this back into Prolog do they become visible, or at least that's one way to do it.
But, there are two problems that remain:
First, what if we actually want to access these arguments? Certainly not all clauses only thread them through like this. We also need to access them somewhere. And second, there's an even more fundamental problem: We want to talk about a single argument, which can be any term, but DCGs always describe a list!
So, how do we reconcile all this?
Most importantly, we need to talk about lists, so the solution is simple: Let us talk about a list with a single element, i.e., the list [Bc0]
and [Bc1]
. This makes DCG notation applicable at all in this case.
Next, how do we express the relation between Bc0
and Bc1
within the DCG? For this, we use semicontext notation: It lets as talk about elements that previously were not in the list we are describing.
As noted in the DCG primer, a nonterminal of the following form will be useful:
state(S0, S), [S] --> [S0].
You can read the nonterminal state(S0, S)
as: The current state is S0
, and henceforth it is S
.
Thus, if you want to actually access Bc0
and relate it to Bc1
in one of your clauses, you could do it like this:
e( f([op(neg), [Arg]], u1(E), [_|Uc0], Uc1, [_|Rest0], Rest) ) -->
state(Bc0, Bc1),
... (something involving Bc0 and Bc1) ...
e( f(Arg, E, Uc0, Uc1, Rest0, Rest) ).
The major advantage is this: This notation lets you hide the additional arguments, and still lets you access them explicitly if you need it, using state//2
(or semicontext notation directly).
This obviously becomes more and more attractive the less the arguments are actually used in your code. If almost all of your clauses access the arguments, there is no sense in hiding them. However, quite frequently, you will describe terms that are threaded through while only very few of your DCG clauses actually access them. In such cases, consider using DCG notation to pass them around implicitly.
But there's still one problem: What to do if we want to pass around not only one term, but two or more? There's a very easy solution for this: Let us still pass around a list with a single element, but let that element simply be a compound term of the form f(Arg1,Arg2,...,Arg_n)
. Thus, your invocation of your nonterminal e//N
might look like this:
?- phrase(e(Arg1,Arg2,...,Arg_N), [f(B1,B2,...,B_M)], [Result]).
Here, B1
, B2
etc. are the arguments that you would like to pass around implicitly, in the form of a list with a single element that combines all these arguments.
Assuming this answers your question, a suitable title could be: "Applying semicontext notation for passing additional arguments". The actual question makes clear, and I think that is critical in this case, that you want to apply semicontext notation for passing additional arguments even though you have already dedicated the DCG notation to describe something else. To summarize, a solution for this is to first free the DCG notation so that you can use the described list for passing around additional arguments.
Note that there are also other solutions: For example, you can devise your own custom notation, completely analogous to DCG notation, but expanded in such a way that it lets you describe two independent lists at the same time. I leave this as an exercise.
这篇关于应用半上下文来传递附加参数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!