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

[Razetime]

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.


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
>