CODEWITHSUNDEEP
prologdcgdcg-semicontext
Guy Coder
Guy Coder

Reputation: 24976

Translation to DCG Semicontext not working

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.

I am using SWI-Prolog 8.0.

The clause causing the problem:

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

Note: C1 is flagged as Singleton variables: [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.

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

What is the correct way to solve the problem using DCG?

See follow-on question.

Current source code

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

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.

EDIT 2

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

Running of test

?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.

Upvotes: 2

Views: 169

Answers (2)

TessellatingHeckler
TessellatingHeckler

Reputation: 28983

I believe the problem in your code here:

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

is that the pushback happens once the body is completed, so the recursive count_dcg never sees the [C] pushback because that hasn't happened yet.

To work around this, deduplicate the head of the list using semicontext pushback. Because the body must complete before the pushback happens we can't have a recursive call to self, and must have a bounce between two differently named rules:

% dedupe squashes head repeatedly, then stops.
dedupe       --> ((squash, dedupe) | stop), !.

% removes duplicate from list head.
squash,  [A] --> [A, A].

% stop when head is not a duplicate, or one item remains.
stop, [A, B] --> [A, B], { dif(A, B) }.
stop,    [A] --> [A].


% e.g. (NB. this uses phrase/3 and pushback leaves
% the list-to-be-counted in Rest)
?- phrase(dedupe, [1,1,1,1,2,3], Rest).
Rest = [1, 2, 3]

Then a plain DCG recursive counter which takes one item off the list and increments, counting from 0 at empty list:

count(C) --> [_], count(B), { succ(B, C) }, !.
count(0) --> [].

% e.g.
?- phrase(count(C), [a,b,c,d])
C = 4

Then merge the two by changing the first count rule to dedupe the head, count one, repeat:

count(C) --> dedupe, [_], count(B), { succ(B, C) }, !.

e.g. count uniques:

?- phrase(count(C), [1,1,1,2,3,3]).
C = 3

Upvotes: 1

Paulo Moura
Paulo Moura

Reputation: 18663

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

Upvotes: 1

Related Questions