How to check how many elements you've already consumed in Prolog DCGs

Question

Say I have these DCGs:

zorbs([H|T]) --> zorb(H), zorbs(T).
zorbs([]) --> [].
    
zorb(a) --> [1,2].
zorb(b) --> [3].
zorb(c) --> [6,1,2,2].

I can do this:

?- phrase(zorbs(X), [1,2,3,6,1,2,2]).
X = [a, b, c] .

I can also "reverse" this by doing:

phrase(zorbs([a,b,c]), X).
X = [1, 2, 3, 6, 1, 2, 2].

Now, what I want to do is find a list of numbers with length less than 4 (for example) which these elements "parse" into, returning the rest.

So, for example, given [a,b,c], which would normally relate to [1, 2, 3, 6, 1, 2, 2], I want it to relate to [1, 2, 3] (which has length less than 4) and also give the remainder that couldn't be "reversed," so [c]. I don't really know where to start, as it seems there's no way to reason about the number of elements you've already consumed in a DCG.

Here's a sort-of solution:

X in 0..4,
indomain(X),
Q = [_|_],
prefix(Q, [a,b,c]),
length(A, X),
phrase(zorbs(Q), A).

but I think this is very inefficient, because I think it basically iterates up from nothing, and I want to find the solution with the biggest Q.

Answer 1

There is no direct way how to do this in this case. So your approach is essentially what can be done. That is, you are enumerating all possible solutions and (what you have not shown) selecting them accordingly.

Questions about the biggest and the like include some quantification that you cannot express directly in first order logic.

However, sometimes you can use a couple of tricks.

Sometimes, a partial list like [a,b,c|_] may be helpful.

?- Xs = [_,_,_,_|_], phrase(zorbs(Xs),[1,2,3,6,1,2,2]).
   false.

So here we have proven that there is no list of length 4 or longer that corresponds to that sequence. That is, we have proven this for infinitely many lists!

And sometimes, using phrase/3 in place of phrase/2 may help. Say, you have a number sequence that doesn't parse, and you want to know how far it can parse:

?- Ys0 = [1,2,3,6,1,2,7], phrase(zorbs(Xs),Ys0,Ys).
   Ys0 = [1,2,3,6,1,2,7], Xs = [], Ys = [1,2,3,6,1,2,7]
;  Ys0 = [1,2,3,6,1,2,7], Xs = "a", Ys = [3,6,1,2,7]
;  Ys0 = [1,2,3,6,1,2,7], Xs = "ab", Ys = [6,1,2,7]
;  false.

(This is with the two DCG-rules exchanged)

Answer 2

Can use:

% Like "between", but counts down instead of up
count_down(High, Low, N) :-
    integer(High),
    integer(Low),
    count_down_(High, Low, N).

count_down_(H, L, N) :-
    compare(C, H, L),
    count_down_comp_(C, H, L, N).

count_down_comp_('=', _H, L, N) :-
    % All equal, final
    N = L.
% Accept H as the counting-down value
count_down_comp_('>', H, _L, H).
count_down_comp_('>', H, L, N) :-
    H0 is H - 1,
    % Decrement H towards L, and loop
    count_down_(H0, L, N).

... and then start with:

count_down(4, 1, Len), length(Lst, Len), phrase...

Answer 3

Another method is to use freeze to limit a list's length, element-by-element:

max_len_freeze(Lst, MaxLen) :-
    compare(C, MaxLen, 0),
    max_len_freeze_comp_(C, Lst, MaxLen).

max_len_freeze_comp_('=', [], 0).
max_len_freeze_comp_('>', [_|Lst], MaxLen) :-
    succ(MaxLen0, MaxLen),
    !,
    freeze(Lst, max_len_freeze(Lst, MaxLen0)).
max_len_freeze_comp_('>', [], _).

... and then start with:

max_len_freeze(Lst, 4), phrase...

This will work to find the longest list (maximum length 4) first, since your DCG is greedy (i.e. matching [H|T] before []).