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

[Razetime]

My original workaround was to move all the logic out of the dcg, and
that worked good for both parts.
I was a bit mad that I was unable to make a multipurpose dcg for this
problem, but now I understand what was wrong. Thank you for the
explanation!

On 10/17/22, Mark Brown <mark at mercurylang.org> wrote:
> 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
>> >
>