What nonterminals should be included with Scryer?

[aarroyoc]

Right now we have DCGs, which are very useful for lots of applications. However, I end up repeating some basic nonterminals quite often through different projects. Maybe it is time to build a DCGs Util library with some common nonterminals. The question is: what nonterminals should be in that library? I will propose some nonterminals, but feel free to discuss more (or less) nonterminals.

library(dcgs) provides:

• seq//1 - Describes a sequence. It is generous (meaning that shorter matches have higher priority)
• seqq//1 - Describes a sequence of sequences. Also generous.
• ... //0 - Describes a sequence but discards the unification

Some additions I propose:

• generous//2 - Takes a DCG and tries to apply it generously. The shorter matches have higher priority.
• greedy//2 - Takes a DCG and tries to apply it greedily. The longer matches have higher priority.
• exactly//3 - Takes a DCG and tries to apply it exactly N times.
• at_least//3 - Takes a DCG and tries to apply it at least N times.
• blanks//0 - Describes whitespaces and tabs, zero or more
• digit//1 - Describes a digit
• integer//1 - Decribes an integer number
• float//1 - Describes a float number
• number//1 - Describes a number (integer and floats)
• string//1 - Describes a string. The difference between string and seq is that string checks explicitly that the members of the list are char atoms.
• string_without//2 - Describes a string without some specific chars
• eol//0 - Describes the end of a line

What more nonterminals should be present? Some nonterminal in the list is not right?

[triska]

Thank you for starting this discussion! Scryer Prolog is an ideal system for working with DCGs, and I agree that having a few often needed non-terminals seems very useful!

One general question I have, if we consider for example integer//1 as an example: What answer do we expect from:

?- phrase(integer(I), Cs).

Is this simply an instantiation error? I suppose so. And what about:

?- phrase(integer(12), Cs).

Should this yield Cs = "12"? And then also Cs = "012", Cs = "0012" etc.?

[aarroyoc]

Good point. For the first one, it's probably ok to throw an instantiation error. For the second, it depends if we accept zeros on the left on integers or not. However, if we allow zeros on the left, the right approach would be to report them infinitely I think, cause otherwise, we would have a case where the DCG used to generate cannot generate all combinations it can accept.

[UWN]

What does generous mean in the context? I never heard it before. And what would be the opposite?

[aarroyoc]

I've used generous as opposite to greedy. They don't affect the number of solutions, only the order. Most nonterminals in DCG Utils would be generous anyway.

generous(_Goal,[]) -->
    [].
generous(Goal,[X|Xs]) -->
    call(Goal,X),
    generous(Goal,Xs).

greedy(Goal,[X|Xs]) -->
    call(Goal,X),
    greedy(Goal,Xs).
greedy(_,[]) -->
    [].

[UWN]

When non-terminals are extended as far as possible then it is said that the eager consumer rule applies. Younger people call it maximal munch.

In any case, a definition favoring a fair enumeration is mostly preferable and does not need some special mentioning. Instead, the actual meaning should be the name of this non-terminal. Only the other version might have some suffix to highlight the rather unexpected.

Also note that you are mixing non-terminals and regular goals here.

[UWN]

... //0 - Describes whatever

This describes a sequence. Not whatever. And note the space.

Whatever is call(_^_^true).

[aarroyoc]

Sorry, you're right

[UWN]

shorter matches

Match? A match is when a (repeat: a, that is any) substitution θ results in something identical. We have never such matches in the presence of general variables, we have only substitutions that are most general unifiers. As long as one side is variable free, there is no difference and it makes sense to talk about matching, but in the general case as here, it is not. If we would only talk about a given list of chars, matching is OK. But not if that list contains variables as well.

[aarroyoc]

You're right too, probably not the best wording. What I was trying to explain with generous/greedy is that it allows you to change the order of the solutions you get.

[pmoura]

In regular expressions lingo, "non-greedy" is sometimes referred to as "lazy".

[UWN]

star(NT__0) --> [] | NT__0, star(NT__0).

[UWN]

...and what is now the eager version?

[UWN]

?- phrase(seqq(Ess), Es).
   Es = [], Ess = []
;  Es = [], Ess = [[]]
;  Es = [], Ess = [[],[]]
;  Es = [], Ess = [[],[],[]]
;  ...

In what sense is this generous? It is not even fair.

[UWN]

Instead of blanks//0: layout_char//0, layout_chars//0. And there should probably be an eager version.

[triska]

For reference:

6.5.4 Layout characters

layout char (* 6.5.4 *)
   = space char (* 6.5.4 *)
   | horizontal tab char (* 6.5.4 *)
   | new line char (* 6.5.4 *) ;

space char (* 6.5.4 *) = " " ;
horizontal tab char (* 6.5.4 *)
   = implementation dependent ;
new line char (* 6.5.4 *)
   = implementation dependent ;

[UWN]

(//\\)//2:

:- op(  950,  xfx, //\\).  % ASCII approximation for ∩ - 2229;INTERSECTION

(NT1 //\\ NT2) -->
     call(Xs0^Xs^(phrase(NT1,Xs0,Xs),phrase(NT2,Xs0,Xs))).

Or with better typed variables:

(NT1__0 //\\ NT2__0) -->
     call(Xs0^Xs^(phrase(NT1__0,Xs0,Xs),phrase(NT2__0,Xs0,Xs))).

[triska]

Regarding exactly//3 and at_least//3: Ideally, both of these predicates should be subsumed by a single non-terminal that takes an integer or CLP(ℤ) variable as its first argument: That argument can either be a ground integer, or a variable whose integer domain denotes how many times something at least occurs. Relatedly, see How to write this DCG more elegantly and in particular: https://stackoverflow.com/a/68698451. We will need more programming practice with DCGs and constraints to decide what exactly to include in library(dcgs).

For the other nonterminals, we would also benefit from more usage experience and a careful consideration of conventions. For example, string//1 is a good name. What about chars//1 though, is it preferable? We already have must_be(chars, ...) in library(error). Should that become must_be(string, ...), or should string//1 become chars//1? Similarly, digit//1 is decimal_digit//1, in analogy to char_type/2 from library(charsio).

eol//0 seems a bit platform-specific. On Unix systems, we can simply write "\n", which is only one character longer.

It would maybe be helpful to consider a more concrete proposal for the actual implementations, and also a careful description of what the arguments are. For example, a recent DCG draft uses grammar-rule-body for what in the current description is referred to as a "DCG".

I think at the moment, a good conservative addition to library(dcgs) from these proposals would be the nonterminal layout_char//0, and also layout_chars//0 which would generate and parse arbitrarily many layout characters. The version that greedily parses layout characters would likely need a different name. A consistent naming convention for the greedy versions would be nice.

[UWN]

Greedy? Eagerly.