DCG bug or nuanced behavior?

[jjtolton]

I am toying around with using DCGs as regular expressions in a command line tool thanks to some interesting comments regarding DCGs lately by @UWN and @hurufu. I wanted to split the stdin into lines and then process the lines with a DCG from the argv/1, but I'm running into strange behavior when I try to use maplist/3 as a secondary processing step with phrase/3!

Is this a bug or some nuanced Prolog behavior that I'm not fully understanding?

Below I show that parse_lines//1 is nominally working, and that neither phrase/3 nor maplist/3 fully explain the behavior I am seeing unless used together.

:- use_module(library(dcgs)).

parse_lines([]) --> [].
parse_lines([Line|Lines]) -->
        seq(Line), "\n",
        parse_lines(Lines).

% splitting lines
?- phrase(parse_lines(Lines), "hey\nwhat\nis\nup\n", []).
   Lines = ["hey","what","is","up"]
;  Lines = ["hey","what","is\nup"]
;  Lines = ["hey","what\nis","up"]
;  Lines = ["hey","what\nis\nup"]
;  ... .

% the culprit is not phrase/3
?- phrase(parse_lines(Lines), "hey\nwhat\nis\nup\n", []),
   phrase((...,["what"]), Lines, Rest).
   Lines = ["hey","what","is","up"], Rest = ["is","up"]
;  Lines = ["hey","what","is\nup"], Rest = ["is\nup"]
;  false.

% the culprit is not maplist/3
?- phrase(parse_lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(=, Lines, After).
   Lines = ["hey","what","is","up"], After = ["hey","what","is","up"]
;  Lines = ["hey","what","is\nup"], After = ["hey","what","is\nup"]
;  Lines = ["hey","what\nis","up"], After = ["hey","what\nis","up"]
;  Lines = ["hey","what\nis\nup"], After = ["hey","what\nis\nup"]
;  ... .

% somehow maplist with phrase/3 produces strange results!
?- phrase(parse_lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(phrase((...,[W])), Lines, After).
   Lines = ["hey","what\nis\nup"], W = h, After = ["ey","at\nis\nup"] 
   /* unexpected! why isn't this Lines = ["hey","what","is","up"]?? It is as if we are beginning on "iteration 4" */
;  Lines = ["hey\nwhat","is\nup"], W = '\n', After = ["what","up"]
;  Lines = ["hey\nwhat\nis\nup"], W = h, After = ["ey\nwhat\nis\nup"]
;  ... .

[UWN]

seq(Line) describes any sequence. Including a sequence that itself contains a newline. Thus your program is too general. Specialize it with an additional goal seq(Line),{maplist(dif('\n'),Line)}

[UWN]

Procedurally, this is not the best solution, since seq(Line) still considers all possibilities. A better way would be a lazy maplist/2, or a new non-terminal combining both.

[jjtolton]

This has sent me down a research black hole...

[bakaq]

Probably relevant: #2260

[jjtolton]

Interesting, thats a really solid implementation of a line parser. It also strengthens my hypothesis there is some kind of issue with maplist/{2,3} when used with phrase/{2,3}, and it is related to the metapredicates.

Will update when I have something more concrete

[jjtolton]

So what I think I've determined is that using in-line goals with metapredicates, but in particular maplist/* with phrase/* is tricky. Interestingly this is quite similar to my findings on using lambda with reif that best practice is to use named predicates and DCGs where possible, it is significantly easier to reason about that "in-line" predicates and goals.

:- use_module(library(format)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

parse_lines([]) --> [].
parse_lines([Line|Lines]) -->
        { maplist(dif('\n'), Line) },
        seq(Line), 
        parse_lines(Lines).

lines([])     --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).

line([])     --> ( "\n" | call(eos) ), !.
line([C|Cs]) --> [C], line(Cs).

eos([], []).


?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(=, Lines, After).
   Lines = ["hey","what","is","up"], After = ["hey","what","is","up"].

?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(phrase((..., [_])), Lines).
   false.
   
last --> ..., [_].

?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(phrase(last),Lines,Out).
   Lines = ["hey","what","is","up"], Out = ["ey","hat","s","p"]
;  Lines = ["hey","what","is","up"], Out = ["ey","hat","s",[]]
;  Lines = ["hey","what","is","up"], Out = ["ey","hat",[],"p"]
;  ... .

[UWN]

This has termination issues:

parse_lines([]) --> {false}, [].
parse_lines([Line|Lines]) -->
        { maplist(dif('\n'), Line), false },
        seq(Line), 
        parse_lines(Lines).

[jjtolton]

Whoops, that should not have been included. I removed that predicate. This is what I meant:

:- use_module(library(format)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

lines([])     --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).

line([])     --> ( "\n" | call(eos) ), !.
line([C|Cs]) --> [C], line(Cs).

eos([], []).


?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(=, Lines, After).
   Lines = ["hey","what","is","up"], After = ["hey","what","is","up"].

?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(phrase((..., [_])), Lines).
   false.
   
last --> ..., [_].

?- phrase(lines(Lines), "hey\nwhat\nis\nup\n", []),
   maplist(phrase(last),Lines,Out).
   Lines = ["hey","what","is","up"], Out = ["ey","hat","s","p"]
;  Lines = ["hey","what","is","up"], Out = ["ey","hat","s",[]]
;  Lines = ["hey","what","is","up"], Out = ["ey","hat",[],"p"]
;  ... .

[haijinSk]

As a Scryer/Prolog outsider (only a very naive user), I tend to use this "bottom-up" definition:

str_lines("",[]).
str_lines([C],[[C]]) :- dif(C,'\n').
str_lines(['\n'|Str],[[]|Ls]) :- str_lines(Str,Ls). 
str_lines([C|Str],[[C|Cs]|Ls]) :- dif(C,'\n'), str_lines(Str,[Cs|Ls]).

with something like this (because we can have more than one \n between lines):

[...] 
str_lines(Str,LinesWithEmpties), 
tfilter(dif([]),LinesWithEmpties,Lines).

Yes, of course, I was using DCGs (a "simpler", more top-down definition) for str_lines/2 before. Then I wanted to try something more in a view "Prolog as a language of inductive [bottom-up] definitions" (Marc Denecker, David S. Warren).

Originally I wanted to create a (pure) predicate for splitting a string ("string to words") that would work in Scryer and Trealla without consuming too much memory or being very slow with a "long" input text, and still being relatively simple (for me to create, because I use only "simple" Prolog).

The "bottom-up" idea (constructing a set by mathematical induction) helped me to think in a new way about Prolog, and about programming in general (note: it's orthogonal/independent to the idea of top-down/bottom-up decomposition of a problem at hand). If nothing else, the idea re-invented Prolog and logic programming for me...

In these days I realized that I'm not the right person for Prolog, but it was a great adventure and very, very useful, important to and for me (thank you all), even if I will not use Prolog.

[jjtolton]

As a Scryer/Prolog outsider (only a very naive user), I tend to use this "bottom-up" definition:

bruh if you are commenting on this board you are definitely an insider 😆

In these days I realized that I'm not the right person for Prolog, but it was a great adventure and very, very useful, important to and for me (thank you all), even if I will not use Prolog.

I'm probably not the right person either, but it is very addictive! Even if you don't use it you should still hang out and keep commenting! I enjoy your contributions!

[triska]

I would like to second what @jjtolton wrote: Even if you do not use Prolog, I hope you continue posting here! Thank you a lot! I do not believe there are any outsiders in here, though maybe there are a few insiders out there?

[jjtolton]

So I do think there is some nuanced behavior that should have been obvious in retrospect.

?- maplist(phrase((..., [W])), [[1,2,3], [5,4,3]]).
   W = 3
;  false.

?- maplist(phrase((..., [W])), [[1,2,3], "hey"]).
   false.

In the first case, W always unifies with 3, therefore it holds.
In the second case, W cannot unify with both 3 and y, therefore it does not hold and there is nowhere else to backtrack so the result is false.

In the example presented, there are other ways to backtrack over W which lead to multiple results.

Everything else was just me flailing and misunderstanding the problem!

[UWN]

Here are generalizations to better show why there is failure:

?- maplist(phrase((..., [W])), [[1,2,3], "hey"]).
   false.
?- maplist(phrase((..., [W])), [[1,2,3], "hey"|_]).
   false.
?- maplist(phrase((..., [W])), [[_,_,3], "hey"|_]).
   false.
?- maplist(phrase((..., [W])), [[_,_,3], [_,_,y]|_]).
   false.
?- dif(X,Y), maplist(phrase((..., [W])), [[_,_,X], [_,_,Y]|_]).
   false.