Re: Suggestions for dcg_basics (was: Detecting the presence of a pattern in an atom)

On 16/10/2013, at 8:53 PM, Boris Vassilev wrote:

> There is one small detail about string//1 that bothers me, probably because
> I don't understand how to use it properly:
> 
> in its current implementation, it takes as few tokens as possible, and
> takes more on backtracking.  So, for a n-token string, it will fail and
> backtrack n-1 times.

The definition is just

    string([]) -->
        [].
    string([X|Xs]) -->
        [X],
        string(Xs).

(By the way, string//1 is a *bad* name for this predicate because it is
*NOT* in any way restricted to strings.  It will match a list of XML
elements as happily as anything else.  And yes, it does make a lot of
sense to use DCG with sequences of XML terms.)

I really don't see what it _could_ do other than what it does.

The *semantics* of string(Xs) is "matches when Xs is a prefix of the input".
It corresponds to the SNOBOL 'ARB' pattern.

> string_without//2 on the other hand is deterministic.

Again, the name is bad (because it is in NO way limited to strings),
and the documentation is unfortunate, because it suggests that the
first argument is (or might be) an element of the sequence being
matched.  In fact it's a set of possible elements.

    string_without(Set, [X|Xs]) -->
        [X], {\+memberchk(X, Set)},
        !,
        string_without(Set, Xs).
    string_without(_, []) -->
        [].

The *semantics* of string_without(Set, Xs) is "matches when Xs is a
maximally long prefix of the input not containing any element of Set".

Because of its semantics, if Ys is a proper prefix or suffix of Xs
and string_without(Set, Xs) matches, string_without(Set, Ys) cannot match.
This corresponds to the SNOBOL 'BREAK' pattern.

One could imagine a non-deterministic version of this.
In fact, one can imagine *several* of them.  One version would be
"exclusive_string(Set, Xs) matches when Xs is a prefix of the input
and does not contain any element of Set."

    exclusive_string(_, []) -->
        [].
    exclusive_string(Set, [X|Xs]) -->
        [X], {\+memberchk(X, Set)},
        exclusive_string(Set, Xs).

Another version would be <not-set>*(<set><not-set>*)*,
which turns out to be the same as string//1, unless you
rule that the <non-set>* parts are as long as possible.