转换为 DCG Semicontext 不起作用

Question

自此 uses list, I wanted to solve it using DCG. In the process I realized that semicontext could be used. (DCG Primer)

最初的问题是 return 对列表中的项目进行计数，但如果两个相同的项目彼此相邻，则不要增加计数。

虽然我的代码对某些测试用例有效，但对其他测试用例却失败了。这只是一个失败的条款。在使用调试器查看代码时，似乎第二个状态变量 returned 列表在调用该子句时被绑定，而我认为它应该是未绑定的。编辑解决了下面这部分问题。

我正在使用 SWI-Prolog 8.0.

导致问题的子句：

count_dcg(N0,N),[C2] -->
    [C1,C2],
    { N is N0 + 1 }.

注意：C1 被标记为 Singleton variables: [C1]

通常我会将 C1 更改为 _ 但在这种情况下，我需要指出当前正在处理的第一项和第二项是不同的。换句话说，就是在以统一失败为幌子。

查看使用 listing/1 的 DCG 显示使用 _ 这可能是问题所在，但不确定。

count_dcg(C, B, A, E) :-
    A=[_, F|D],
    B is C+1,
    G=D,
    E=[F|G].

使用DCG解决问题的正确方法是什么？

参见 follow-on 。

当前源代码

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

测试用例

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

运行测试

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

意识到需要对其中两个谓词进行尾调用

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

代码仍然无法正常工作，但这解释了为什么在我期望状态变量未绑定时绑定了状态变量。

编辑 2

虽然没有像我希望的那样使用 DCG 半上下文，但使用半上下文的变体作为前瞻，代码有效。不将此作为答案发布，因为我希望答案显示 DCG 代码与子句 header 上的半上下文一起工作或解释为什么这是错误的。

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.

Answer 1

不需要回推列表或前瞻的替代解决方案：

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 不起作用

Translation to DCG Semicontext not working

prolog

dcg

dcg-semicontext