Better line//1 and lines//1

[bakaq]

The definitions of the line//1 and lines//1 non-terminals from the DCG Primer (which I will be calling line_cut//1 and lines_cut//1 here) bugged me since the first time I've seen them. Because they use cuts, they aren't monotonic. For example, in the general case they lose a lot of answers:

?- [user].
:- use_module(library(dcgs)).

eos_raw([], []).
eos --> call(eos_raw).

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


?- phrase(line_cut(Line), Ls).
   Line = [], Ls = "\n".
?- phrase(line_cut(Line), "What about this one?\n").
   Line = "What about this one ...".

I've been stuck at day 1 of Advent of Code 2023 for the entire month because of this. I've been striving to do actual application code with fully monotonic high level Prolog, and those definitions were breaking this goal. Part of the motive for doing everything like that is to experience first hand the hardships that people encounter when trying to write "real world" monotonic Prolog, and then this puts me in a position to try to potentially improve that experience with new building blocks. So here my implementation of these predicates:

:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(reif)).

eos_t(T) --> call(eos_t_raw(T)).
eos_t_raw(T, Rest, Rest) :-
    if_(Rest = [], T = true, T = false).

% This lifts if_/3 to a non-terminal.
% The condition is a reified predicate.
if_(If, Then, Else) --> call(if_raw(If, Then, Else)).
if_raw(If, Then, Else, Ls0, Ls) :-
    if_(
        If,
        phrase(Then, Ls0, Ls),
        phrase(Else, Ls0, Ls)
    ).

% This lifts if_/3 to a non-terminal.
% The condition is a reified non-terminal.
if__(If__1, Then, Else) --> call(if__raw(If__1, Then, Else)).
if__raw(If__1, Then, Else, Ls0, Ls) :-
    if_(
        phrase_t(If__1, Ls0, Ls1),
        phrase(Then, Ls1, Ls),
        phrase(Else, Ls1, Ls)
    ).

% I think I'm not following the _t naming convention of reif correctly here.
phrase_t(NT, Ls0, Ls, T) :-
    % Is there a better way of "adding an argument"?
    NT =.. NTArgs,
    append(NTArgs, [T], NTArgs1),
    NT1 =.. NTArgs1,
    phrase(NT1, Ls0, Ls).

lines(Lines) -->
    if__(
        eos_t,
        { Lines = [] },
        (
            { Lines = [Line|Lines1] },
            line(Line),
            lines(Lines1)
        )
    ).

line(Line) -->
    if__(
        eos_t,
        { Line = [] },
        (
            [C],
            if_(
                C = '\n',
                { Line = [] },
                (
                    { Line = [C|Cs] },
                    line(Cs)
                )
            )
        )
    ).

% The old definitions are bellow for reference
eos_raw([], []).
eos --> call(eos_raw).

lines_cut([]) --> eos, !.
lines_cut([L|Ls]) --> line_cut(L), lines_cut(Ls).

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

With this I introduce if_//3 and if__//3 as two different liftings of if_/3 to a non-terminal, and eos_t//1 for use with if__//3. These new definitions are monotonic and can be used to reason about lines in many different ways:

?- phrase(line(Line), Ls).
% This actually lists all possibilities.
   Line = [], Ls = []
;  Line = [], Ls = "\n"
;  Line = [_A], Ls = [_A], dif:dif(_A,'\n')
;  Line = [_A], Ls = [_A|"\n"], dif:dif(_A,'\n')
;  Line = [_A,_B], Ls = [_A,_B], dif:dif(_A,'\n'), dif:dif(_B,'\n')
;  Line = [_A,_B], Ls = [_A,_B|"\n"], dif:dif(_A,'\n'), dif:dif(_B,'\n')
;  ... .
?- phrase(line(Line), [a,b,c,d,E]).
% E can be a newline.
   Line = "abcd", E = '\n'
;  Line = [a,b,c,d,E], dif:dif(E,'\n').
?- phrase(line(Line), [a,b,c,d,E,f]).
% Here E can't be a newline anymore.
   Line = [a,b,c,d,E|"f"], dif:dif(E,'\n').
?- phrase(line(Line), [a,b,c,d,E,F]).
% E can't be a newline, but F can.
   Line = [a,b,c,d,E], F = '\n', dif:dif(E,'\n')
;  Line = [a,b,c,d,E,F], dif:dif(E,'\n'), dif:dif(F,'\n').
?- phrase(line("abcd\n"), Ls).
% "abcd\n" is not a possible parsing of a line.
   false.
?- phrase(line("abcd"), Ls).
% There are two different strings that can be parsed as the line "abcd".
   Ls = "abcd"
;  Ls = "abcd\n"
;  false.

The version with cut gives the wrong answer for all of those. All of this comes with an performance hit, obviously. In my measures, line//1 is about 50-60x slower than line_cut//1, and lines//1 is about 10x slower than lines_cut//1 in the mode of parsing. This would probably improve when if_/3 is optimized with goal expansion, but in many use cases this doesn't actually matter that much, and in a few use cases you really need the more general monotonic functionality anyway.

[triska]

It's awesome to have a more correct and more general implementation of such a frequently needed non-terminal, thank you a lot for working on this!

Is this a good candidate for inclusion in library(charsio)? It could maybe become a part of a library with more non-terminals that are frequently needed when describing input. library(strings) maybe?

[triska]

If it helps: library(dcgs) will likely be loaded in any case, because it is so frequently needed.

[bakaq]

Yes, library(dcgs) is not a great offender here, but imagine something like library(clpz), or something even bigger that is not going to be loaded in a lot of cases.

[triska]

On the other hand, that's exactly what other Prolog systems such as B-Prolog and GNU Prolog do by default: Integer constraints are provided there by default.

My personal opinion: If loading a library has such tremendous performance impacts that whether to load it is worth even thinking about, then this is a good opportunity to improve the loading time, maybe by precompilation of the libraries that ship with Scryer Prolog: These could all be shipped compiled to WAM code or to native code. The library system should prevent naming conflicts of Scryer predicates with user-specific application code. Loading a system library should be so fast that the time should not have to be taken into consideration at all.

[infogulch]

Scryer could have a default set of libraries that are loaded automatically; maybe it would be good to have some way to disable loading them by default via cli flag or something.

[mthom]

I think Scryer should come with some sort of Build-a-Scryer interface allowing the user to tailor their instance according to the libraries they use. Also the interface should resemble old school BBSes

[UWN]

% Is there a better way of "adding an argument"?

What about call/2?

[bakaq]

Wait, I can't find any place in the DCG working draft that actually says that call//1 gives the list difference in this order.

More precisely taking semicontext into account, phrase(call(G_2), S0,S) is true iff phrase(G_2, S0,S) is true.

This doesn't actually fix the order of arguments to G_2 to be S0, S. I thought I read it somewhere that call//1 was the portable way to get a definite order here. @UWN, could you explain this?

[triska]

In your example of phrase(call(call(_)), Ls0, Ls), the outermost occurrence of call is the non-terminal call//1, this is portable, and calls (in your example) the predicate call/3. So far so good, with completely defined and dependable order of arguments. But that inner call then calls a non-terminal with additional arguments whose order or presence you cannot rely on. The portable way to invoke a non-terminal is phrase/N, not call/N!

[bakaq]

Ok, it seems I really just misunderstood what was the actual guarantees of call//1. Now phrase//N seems completely justified to me. But now I have another question: how do you actually get the list difference in a portable way? I thought call//1 did this, and this enables the implementation of a lot of really useful non-terminals, like eos//0¹, or even something like rest_of_string//1.

Footnotes

1. For eos//1 you don't actually need to know the order of the difference list I guess, but from the phrasing I think that the "2 extra arguments" could not be the list difference at all in a really weird implementation and actually encode some more metadata, so it doesn't work. ↩

[bakaq]

Wait, no, I'm even more confused. Rereading you explanation it seems that call//1 actually guarantees the order, the problem is that you really can't call a non-terminal with call/N because even if you have the list difference in the right order (with call//1 for example), you don't know (portably) what the non-terminal accepts in the 2 extra arguments.

[triska]

Yes exactly, call//1 guarantees the order of arguments, but you cannot (portably, i.e., so that it works in different Prolog implementations or even in future versions on the same implementation) rely on any order or even presence or any correspondence at all between DCG non-terminals and predicates, you can only rely on the Prolog predicates phrase/[2,3] to use a grammar rule body, and the non-terminal call//1 to access the list difference from within the grammar.

The point of the non-terminals phrase//[2,3] which I experimentally implemented is to enable portable higher-order reasoning in grammars, i.e., working with non-terminals that take additional arguments, in analogy to what we have with the standard call/N family of predicates for Prolog predicates, in such a way that we need not make any assumptions about how Prolog systems internally implement DCGs. In this way, they are free to implement custom optimizations (such as internally using a different argument order, or a completely different expansion altogether, or native code etc.) while existing programs remain portable between Prolog implementations because only standard DCG constructs are used.

[UWN]

More precisely taking semicontext into account, phrase(call(G_2), S0,S) is true iff phrase(G_2, S0,S) is true.

This doesn't actually fix the order of arguments to G_2 to be S0, S. I thought I read it somewhere that call//1 was the portable way to get a definite order here. @UWN, could you explain this?

It does fix the order because phrase/3 uses the logical expansion. A better formulation is to define this directly via call/3. But the deeper point is the following: There are several ways to read a standard, depending on what your actual interest is. People who just want to know the outcome use the logical expansion and thus have no problem here. Another reading is to ensure that non-terminals and grammar rule bodies are always executed as such. A cross-referencer would be interested in this. Another reading might be an implementer who wants to implement these differences differently. Or an implementer might consider to define cases for last-call optimization differently. For those the present definition is still the lynchpin they relate to, but they use it only as a basis to exploit more interesting properties.

[bakaq]

It does fix the order because phrase/3 uses the logical expansion.

What do you mean here by "logical expansion"? I thought that that was precisely what was implementation defined. Does this mean that phrase(NT, S0, S) is always interpreted as something like call(NT_canon, S0, S), where NT_canon is the equivalent of NT which accepts S0 and S in this exact order, while NT itself has 2 extra arguments that can be anything implementation defined?

This call(NT_canon, S0, S) is equivalent the Goal in dcg_body(GRBody, S0, S, Goal), call(Goal) in the definition of phrase/3 (8.18.1.1) if I understood correctly. I guess the part where this would be explained isn't in the working draft yet (section "10 Logical Expansion"), or at least not in the version I linked before.

[UWN]

What do you mean here by "logical expansion"?

https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dcgs/dcgs_exp.pl

And yes, you may use another one.