[m-users.] Problem with DCG producing false negative

[Mark Brown]

On Tue, Oct 18, 2022 at 12:01 AM Razetime <rraghu.11502 at gmail.com> wrote:
>
> sorry for the confusion.
>
> File: https://github.com/razetime/aoc/blob/main/16/t_a07.m
> Library: https://github.com/razetime/aoc/blob/main/16/alib.m
>
> The use of seq is to describe a sequence of an arbitrary number of characters.
> I use it as per Markus Triska's Prolog DCG Primer:
> https://www.metalevel.at/prolog/dcg
> in order to describe that and get it as a list for future use.
>
> The rules for a string that should be matched by tls are
> a) an [A,B,B,A] pattern outside [] must exist
> b) no [A,B,B,A] patterns must exist inside []
>
> The use of tls is
> a) as a checking predicate to see if a string fits that spec
> b) sequences inside [] go into [Y0|Y]
> c) sequences outside [] go into [X0|X]
> I was planning to use it in filter_map, like tls(A,B,L,[]), returning
> {A,B} from the higher order predicate.

That makes sense. I would express that intended meaning in a comment
for the predicate something like this:

% tls(Xs, Ys)
%
% Consume a char list of any length from the DCG input.
%
% Xs is the list of maximal sequences of chars occurring outside
% square brackets in the char list, including those at the start and
% end, in order of occurrence. One of these sequences contains
% a sequence matching [A, B, B, A], where A \= B.
%
% Ys is the list of maximal sequences of chars occurring inside
% matching square brackets, in order of occurrence. None of
% these sequences contains a sequence matching the above.
%
:- pred tls...

>From this documentation we can already see that it is not fully
specified. We haven't properly defined what will happen for the case
of non-matching or nested brackets, but that's okay if it's never
called that way (e.g., if it's checked beforehand).

Now to look at the clauses, which I have reformatted for clarity:

tls([X], [])        --> {alp(X)}, seq(X).
tls([X0|X], [Y0|Y]) --> {alp(X0),alp(Y0),\+abba(Y0)},
    seq(X0), ['['], seq(Y0), [']'],
    tls(X,Y),
    {any_true(abba,[X0|X])}.

Bug 1: the first clause is incorrect according to the intention: it is
true even if Xs doesn't contain the required pattern.

Bug 2: the clauses don't cover all the atoms intended to be true.
Consider input that starts with "xyzzy[]", which should have at least
one answer, namely Xs = ["xyzzy", ""] and Ys = [""]. It contains
non-alpha characters (the brackets), so the first clause doesn't cover
it. The second clause starts by matching "xyzzy[]", with X0 = "xyzzy"
and Y0 = "". Then it recursively calls tls on the remaining input, but
the remaining part may not contain the required pattern. In this case
tls is intended to fail, thus we don't always produce the expected
answer.

A solution? Change the intended meaning of tls to remove the part that
says Xs must contain the pattern. That's something that can be checked
at the end (e.g., rename the above to tls1 and define tls to first
call tls1 then perform the extra check).

Hope this was edifying to someone!

Mark

>
>
> On 10/17/22, Mark Brown <mark at mercurylang.org> wrote:
> > On Mon, Oct 17, 2022 at 10:20 PM Volker Wysk <post at volker-wysk.de> wrote:
> >>
> >> Hmm... I think I misunderstood what you're trying to do with seq/3. You
> >> probably *want* it to be multi and not det. Is that so?
> >
> > That was my take on it. I assume seq(A, B, C) is intended to mean that
> > A ++ B = C (i.e., it is append/3 with the last two arguments swapped).
> >
> > But that reinforces my point that people need to know the programmer's
> > intention.
> >
> > Mark
> >
> >>
> >> Am Montag, dem 17.10.2022 um 12:54 +0200 schrieb Volker Wysk:
> >> > Hi. Please post your source code, as complete as necessary. Mark the
> >> > lines
> >> > which are named in compile error messages, so we can see what's going
> >> > on.
> >> >
> >> > Regarding your determinism errors, you have this:
> >> >
> >> > :- pred seq(list(T),list(T),list(T)).
> >> > :- mode seq(out,in,out) is multi.
> >> > seq([])     --> [].
> >> > seq([E|Es]) --> [E], seq(Es).
> >> >
> >> > This isn't deterministic, because the first rule will always succeed.
> >> > The []
> >> > pattern doesn't mean the end of the input, but a pattern that will
> >> > always
> >> > succeed. That seq should be written like this:
> >> >
> >> > :- pred seq(list(T),list(T),list(T)).
> >> > :- mode seq(out,in,out) is det.
> >> > seq(L) -->
> >> >    ( if   [E]
> >> >      then seq(Es),
> >> >           { L = [E|Es] }
> >> >      else { L = [] }
> >> >    ).
> >> >
> >> > With this deterministic seq, the tls rule will possibly also be
> >> > deterministic. Try it out.
> >> >
> >> > Have fun,
> >> > Volker
> >> >
> >> >
> >> > Am Montag, dem 17.10.2022 um 15:56 +0530 schrieb Razetime:
> >> > > hm, it makes sense that the dcg rule should be semidet or det. These
> >> > > are the problems I had when trying to change the rules.
> >> > >
> >> > > 1)
> >> > > a07.m:011: In `tls'(out, out, in, out):
> >> > > a07.m:011:   error: determinism declaration not satisfied.
> >> > > a07.m:011:   Declared `semidet', inferred `nondet'.
> >> > > a07.m:011:   The reasons for the difference are the following.
> >> > > a07.m:012:   Disjunction has multiple clauses with solutions.
> >> > > a07.m:013:   Call to `alib.seq'(out, in, out) can succeed more than
> >> > > once.
> >> > > a07.m:014:   Call to `alib.seq'(out, in, out) can succeed more than
> >> > > once.
> >> > >
> >> > > 2) after changing alib.seq to semidet (changing to det also gives the
> >> > > same error)
> >> > > a07.m:011: In `tls'(out, out, in, out):
> >> > > a07.m:011:   error: determinism declaration not satisfied.
> >> > > a07.m:011:   Declared `semidet', inferred `nondet'.
> >> > > a07.m:011:   The reason for the difference is the following.
> >> > > a07.m:012:   Disjunction has multiple clauses with solutions.
> >> > >
> >> > > I assume that `any_true(abba,[X0|X])' is causing this but i do not
> >> > > know how to fix it. For now I am separating the logic from the DCG.
> >> > >
> >> > > On 10/17/22, Volker Wysk <post at volker-wysk.de> wrote:
> >> > > > Hi
> >> > > >
> >> > > > I don't fully understand what you're doing here. But you should try
> >> > > > to make
> >> > > > the DCG rules det or semidet. Then you can let the compiler spot
> >> > > > your
> >> > > > errors, when it doesn't agree with the determinism category which
> >> > > > you have
> >> > > > declared.
> >> > > >
> >> > > > Hope that helps,
> >> > > > Volker
> >> > > >
> >> > > >
> >> > > > Am Montag, dem 17.10.2022 um 00:14 +0530 schrieb Razetime:
> >> > > > > I have created the following predicate tls to match lines that
> >> > > > > satisfy
> >> > > > > the conditions given in Advent of Code Day 7:
> >> > > > > https://adventofcode.com/2016/day/7 (Spoilers)
> >> > > > >
> >> > > > > For some reason during testing ,the DCG fails when given
> >> > > > > L="fslvgbiibdkhchajyb[zpbhqrokrbfuqrowop]gqqzoqvfsdfcjcdurrs[xhqfcfytbbekivnvod]jxjwuxivnyhppvfhaol[evfnrmrjnnhychtpv]emiyjcjsnojxexs",
> >> > > > > tls(X,Y,to_char_list(L),[])
> >> > > > > and I am not sure why it is giving that result. What is done wrong
> >> > > > > here?
> >> > > > >
> >> > > > > :- pred tls(list(cl)::out,list(cl)::out,cl::in,cl::out) is
> >> > > > > nondet.
> >> > > > > tls([X],[])        --> {alp(X)},seq(X).
> >> > > > > tls([X0|X],[Y0|Y]) --> {alp(X0),alp(Y0),\+abba(Y0)},
> >> > > > >
> >> > > > > seq(X0),['['],seq(Y0),[']'],tls(X,Y),{any_true(abba,[X0|X])}.
> >> > > > >
> >> > > > > :- pred seq(list(T),list(T),list(T)).
> >> > > > > :- mode seq(out,in,out) is multi.
> >> > > > > seq([])     --> [].
> >> > > > > seq([E|Es]) --> [E], seq(Es).
> >> > > > >
> >> > > > > :- pred alp(cl::in) is semidet.
> >> > > > > alp(L):-all_true(is_alpha,L).
> >> > > > >
> >> > > > > :- pred abba(cl::in) is semidet.
> >> > > > > abba([A,B,B,A|L]):-A\=B.
> >> > > > > abba([_,A,B,C|L]):-abba([A,B,C|L]).
> >> > > > > _______________________________________________
> >> > > > > users mailing list
> >> > > > > users at lists.mercurylang.org
> >> > > > > https://lists.mercurylang.org/listinfo/users
> >> > > >
> >> > > >
> >> >
> >> > _______________________________________________
> >> > users mailing list
> >> > users at lists.mercurylang.org
> >> > https://lists.mercurylang.org/listinfo/users
> >>
> >> _______________________________________________
> >> users mailing list
> >> users at lists.mercurylang.org
> >> https://lists.mercurylang.org/listinfo/users
> >