Translation to DCG Semicontext not working - follow on

Question

As a follow up to this question which poses the problem

Return count of items in a list but if two identical items are next to each other then don't increment the count.

This code is the closest I came to solving this with DCG and semicontext.

lookahead(C),[C] -->
    [C].

% empty list
% No lookahead needed because last item in list.
count_dcg(N,N) --> [].

% single item in list
% No lookahead  needed because only one in list.
count_dcg(N0,N) -->
    [_],
    \+ [_],
    { N is N0 + 1 }.

% Lookahead needed because two items in list and
% only want to remove first item.
count_dcg(N0,N) -->
    [C1],
    lookahead(C2),
    { C1 == C2 },
    count_dcg(N0,N).

% Lookahead needed because two items in list and
% only want to remove first item.
count_dcg(N0,N) -->
    [C1],
    lookahead(C2),
    {
        C1 \== C2,
        N1 is N0 + 1
    },
    count_dcg(N1,N).

count(L,N) :-
    DCG = count_dcg(0,N),
    phrase(DCG,L).

What is the correct way to solve the problem using DCG with semicontext on the clause head?

Would like to know if the variation with the semicontext on the clause head is possible or not. If possible then working example code is desired, if not possible then an explanation is desired.

This so far: You are using highly problematic constructs like `\+ [_],` which have only a procedural interpretation. — false, Mar 04 '19 at 16:07
@false I know it is problematic. Matching the end of a line or stream with DCG is what causes me the most problems. For me matching the end is more of a hack-a-thon than a coding session. I should ask a question about it, but wouldn't even know how to make it general enough that the idea works in all cases. — Guy Coder, Mar 04 '19 at 16:23
For those wondering about `\+ [_]` I picked it up [here](http://www.pathwayslms.com/swipltuts/dcg/) but as noted, am not happy with it. — Guy Coder, Mar 04 '19 at 16:26
@false Reduced size of question. As I often note, feel free to edit my questions or answer as needed, it is all creative commons. — Guy Coder, Mar 04 '19 at 17:19

user27815 · Accepted Answer · 2019-03-05T12:07:38.683

I think this is using semi context notation correctly. I am counting using 0,s(0),...

% Constraint Logic Programming
:- use_module(library(dif)).    % Sound inequality
:- use_module(library(clpfd)).  % Finite domain constraints

list([])     --> [].
list([L|Ls]) --> [L], list(Ls).

state(S), [state(S)] --> [state(S)].
state(S, s(S)), [state(s(S))] --> [state(S)].

keep_state(S,I),[state(S)] --> [state(S)],[I].
end_state(S)  -->[state(S)],[].

lookahead(C),[S,C] -->
    [S,C].

count_dcg(S,S) --> 
    state(S), %might not need this
    end_state(S).

/* Can be used get the length of a list
count_dcg(S,S2) --> 
    state(S,S1),
    keep_state(S1,_),
    count_dcg(S1,S2),
    {}.
*/

%last item.
count_dcg(S,S1) -->     
    state(S,S1),
    keep_state(S1,_C),
    list(R),
    {R = [state(_)]}.

%Two the same dont increase state 
count_dcg(S,S1) -->
    state(S), %might not need this
    keep_state(S,C1),
    lookahead(C1),
    count_dcg(S,S1).

%Two different increase state  
count_dcg(S,S2)  -->
    state(S,S1),
    keep_state(S1,C1),
    lookahead(C2),
    {
        dif(C1,C2)
    },
    count_dcg(S1,S2).

count(L,S) :-
    phrase(count_dcg(0,S),[state(0)|L]).

This does not work as well as I hoped for cases like:

65 ?- count([a,b,X,c],L).
X = b,
L = s(s(s(0))) ;
;
X = c,
L = s(s(s(0))) .

You can convert peano with:

natsx_int(0, 0). 
natsx_int(s(N), I1) :- 
  I1 #> 0, 
  I2 #= I1 - 1, 
  natsx_int(N, I2).

or you can change the state predicates:

state(S), [state(S)] --> [state(S)].
state(S, S2), [state(S2)] --> [state(S)],{S2#=S+1}.

This is a standard task, but you can also change the state predicate to count using clpfd if you want: `natsx_int(0, 0). natsx_int(s(N), I1) :- I1 #> 0, I2 #= I1 - 1, natsx_int(N, I2).` — user27815, Mar 05 '19 at 11:27
I have added a version of state that returns normal numbers for you. — user27815, Mar 05 '19 at 12:11

score 1 · Answer 2 · answered Mar 04 '19 at 17:52

1

How about:

:-use_module(library(clpfd)).

list([])     --> [].
list([L|Ls]) --> [L], list(Ls).

lookahead(C),[C] -->
    [C].

count_dcg(N,N) --> [].
count_dcg(N0,N) --> %last item.
    [_],
    list(R),
    {R = [], N #=N0+1}.
count_dcg(N0,N) -->
    [C1],
    lookahead(C1),
    count_dcg(N0,N).
count_dcg(N0,N) -->
    [C1],
    lookahead(C2),
    {
        dif(C1,C2),
        N1 #= N0 + 1
    },
    count_dcg(N1,N).

count(L,N) :-
    phrase(count_dcg(0,N),L).

answered Mar 04 '19 at 17:52

user27815

4,767
14
28

Thanks, I will give you an up-vote for the effort but can't give an accept vote. I am trying to understand semicontext and specifically with this question if semicontext can work for the problem with the semicontext in the head of the clause. I don't see any semicontext in the head of the `count_dcg` clauses. – Guy Coder Mar 04 '19 at 18:04
ah sorry, I will have a go at that. – user27815 Mar 04 '19 at 18:05

Translation to DCG Semicontext not working - follow on

2 Answers2

Linked