问题描述
由于这个问题使用列表，我想用DCG解决它.在这个过程中，我意识到可以使用半上下文.(DCG 入门)
Since this question uses list, I wanted to solve it using DCG. In the process I realized that semicontext could be used. (DCG Primer)
最初的问题是返回列表中项目的计数，但如果两个相同的项目彼此相邻，则不要增加计数.
The original problem is to return count of items in a list but if two identical items are next to each other then don't increment the count.
虽然我的代码适用于某些测试用例，但它不适用于其他测试用例.这只是一个失败的条款.在使用调试器查看代码时，似乎第二个状态变量，即返回的列表，在我认为它应该未绑定时，在调用该子句时被绑定.编辑在下面解决了这部分问题.
While my code works for some of the test cases, it fails for others. It is just one clause that is failing. In looking at the code with a debugger it appears that the second state variable, the returned list, is bound upon a call to the clause when I am thinking that it should be unbound. EDIT Resolved this part of problem below.
我正在使用 SWI-Prolog 8.0.
I am using SWI-Prolog 8.0.
导致问题的子句:
count_dcg(N0,N),[C2] -->
[C1,C2],
{ N is N0 + 1 }.
注意:C1 被标记为 单例变量:[C1]
Note: C1 is flagged as Singleton variables: [C1]
通常我会将 C1 更改为 _ 但在这种情况下，我需要指出当前正在处理的第一个和第二个项目是不同的.也就是说，它是在以统一失败为警戒.
Normally I would change C1 to _ but in this case I need to indicate that the first and second items currently being processed are different. In other words it is using the failure of unification as a guard.
查看使用 Listing/1 的 DCG 发现使用 _ 可能是问题但不确定.
Looking at the DCG using listing/1 reveals the use _ which might be the problem but not sure.
count_dcg(C, B, A, E) :-
A=[_, F|D],
B is C+1,
G=D,
E=[F|G].
使用 DCG 解决问题的正确方法是什么?
What is the correct way to solve the problem using DCG?
请参阅后续问题.
当前源代码
% empty list
% No semicontext (push back) needed because last item in list.
count_dcg(N,N) --> [].
% single item in list
% No semicontext (push back) needed because only one item removed from list.
count_dcg(N0,N) -->
[_],
+ [_],
{ N is N0 + 1 }.
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N,N),[C] -->
[C,C].
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C2] -->
[C1,C2],
{ N is N0 + 1 }.
count(L,N) :-
DCG = count_dcg(0,N),
phrase(DCG,L).
测试用例
Test cases
:- begin_tests(count).
test(1,[nondet]) :-
count([],N),
assertion( N == 0 ).
test(2,[nondet]) :-
count([a],N),
assertion( N == 1 ).
test(3,[nondet]) :-
count([a,a],N),
assertion( N == 1 ).
test(4,[nondet]) :-
count([a,b],N),
assertion( N == 2 ).
test(5,[nondet]) :-
count([b,a],N),
assertion( N == 2 ).
test(6,[nondet]) :-
count([a,a,b],N),
assertion( N == 2 ).
test(7,[nondet]) :-
count([a,b,a],N),
assertion( N == 3 ).
test(8,[nondet]) :-
count([b,a,a],N),
assertion( N == 2 ).
:- end_tests(count).
运行测试
Running of test
?- run_tests.
% PL-Unit: count ..
ERROR: c:/question_110.pl:80:
test 3: failed
ERROR: c:/question_110.pl:84:
test 4: failed
ERROR: c:/question_110.pl:88:
test 5: failed
ERROR: c:/question_110.pl:92:
test 6: failed
ERROR: c:/question_110.pl:96:
test 7: failed
ERROR: c:/question_110.pl:100:
test 8: failed
done
% 6 tests failed
% 2 tests passed
false.
编辑 1
EDIT 1
意识到需要对两个谓词进行尾调用
Realized that need tail call for two of the predicates
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C] -->
[C,C],
count_dcg(N0,N).
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C2] -->
[C1,C2],
{
C1 == C2,
N1 is N0 + 1
},
count_dcg(N1,N).
代码仍然无法正常工作，但这解释了为什么状态变量在我预期它未绑定时被绑定.
Code still not working, but this explains why state variable was bound when I expected it to be unbound.
编辑 2
虽然没有像我希望的那样使用 DCG 半上下文，但使用半上下文的变体作为前瞻，代码可以工作.不将此作为答案发布，因为我希望答案要么显示 DCG 代码与子句标题上的半上下文一起使用，要么解释为什么这是错误的.
While not using DCG semicontext as I was hoping, using a variation of semicontext as a lookahead, the code works. Not posting this as an answer because I would like the answer to either show DCG code working with the semicontext on the clause header or explain why that is wrong.
lookahead(C),[C] -->
[C].
% empty list
% No lookahead needed because last item in list.
count_3_dcg(N,N) --> [].
% single item in list
% No lookahead needed because only one in list.
count_3_dcg(N0,N) -->
[_],
+ [_],
{ N is N0 + 1 }.
% Lookahead needed because two items in list and
% only want to remove first item.
count_3_dcg(N0,N) -->
[C1],
lookahead(C2),
{ C1 == C2 },
count_3_dcg(N0,N).
% Lookahead needed because two items in list and
% only want to remove first item.
count_3_dcg(N0,N) -->
[C1],
lookahead(C2),
{
C1 == C2,
N1 is N0 + 1
},
count_3_dcg(N1,N).
count(L,N) :-
DCG = count_3_dcg(0,N),
phrase(DCG,L).
运行测试
?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.
推荐答案
不需要后推列表或前瞻的替代解决方案:
An alternative solution that doesn't require push-back lists or lookahead:
count_dcg(N0,N) -->
[C], {N1 is N0 + 1}, count_dcg(N1,N,C).
count_dcg(N,N) -->
[].
count_dcg(N0,N,C) -->
[C],
count_dcg(N0,N,C).
count_dcg(N0,N,C) -->
[C1],
{C == C1, N1 is N0 + 1},
count_dcg(N1,N,C1).
count_dcg(N,N,_) -->
[].
count(L,N) :-
phrase(count_dcg(0,N),L).
这篇关于翻译为 DCG Semicontext 不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！