Consolidating overlapping DCG rules

[dnmfarrell]

Yesterday I wrote a string pattern-matching library as a DCG but one wart it had was overlapping rules, which required an extra predicate `reg_char/1':

patt([])        --> [].
patt(['*'|Cs])  --> word([]), patt(Cs).
patt(['?'|Cs])  --> [C], patt(Cs).
patt(['\\'|Cs]) --> same(Cs).
patt([C|Cs])    --> [C], { reg_char(C) }, patt(Cs).
...

I was able to resolve this by combining all the rules into a single rule, but I couldn't express it as a DCG as I'm unable to replicate the if/then semantics (I think that's the reason).

patt([])        --> [].
patt([C|Cs])    -->
  (  { wildcard(C) },
     !,
     word([]),
     patt(Cs)
  )
  |
  (  { placeholder(C) },
     !,
     [C],
     patt(Cs)
  )
  |
  (  { escape(C) },
     !,
     same(Cs)
  )
  |
  (  [C],
     patt(Cs)
  ).

I added the cuts after the first predicate in an attempt to be like if/then. But the test suite fails.

My question is, is it possible to fix overlapping rules in DCGs using if/then or another technique?

Thanks.

[dnmfarrell]

Aha, this seems to work!

patt([])     --> [].
patt([C|Cs]) -->
  wildcard([C|Cs]) | placeholder([C|Cs]) | escape([C|Cs]) | regular([C|Cs]).

wildcard(['*'|Cs])     --> word([]), patt(Cs).
placeholder(['?'|Cs])  --> [_], patt(Cs).
escape(['\\'|Cs])      --> same(Cs).
regular([C|Cs])        --> [C], patt(Cs).

[triska]

However, the arrows get expanded even before that term_expansion is run

DCGs are themselves implemented with term_expansion/2:

scryer-prolog/src/lib/dcgs.pl

Line 217 in c39ea48

user:term_expansion(Term0, Term) :-

This may be the reason you see this expansion: This term_expansion/2 is defined in(to) the user module and therefore affects all terms that appear after library(dcgs) is loaded somewhere.

[jjtolton]

I couldn't figure out a way to make the arrow term expansion occur before the DCG term expansion in this time window, but it would be great if possible! If not I'm sure there's another way to "mark" predicates, even with a prefix like :- op(1199, fx, defpattern) or something.

[triska]

It's all just terms, you can easily denote a set of terms that, when added to a Prolog source file, expand to anything you want via term_expansion/2. Prolog rules have the shape :-(Head, Body).. DCG rules have the shape -->(Head, Body). If you want, you can devise custom rules with a different functor that are expanded differently, for instance to rules or DCG nonterminals.

[jjtolton]

What I mean is, I think the arrows are compiled away before the user has access to match against them. Try this:

user:term_expansion(Pat, _) :- write(Pat), nl, false.
a --> [b].

in my history buffer:

['/tmp/ediprolog6xENEP'].
a(_1061,_1059):-_1061=[b|_1059]
   true.
?- 

I can't be entirely sure the test isn't contaminated somehow, but I haven't been able to find a way to match against the arrows yet.

[jjtolton]

Two other options came to mind, though:

user:term_expansion((Pat -=> B), (Pat --> B)) :-
        prolog_load_context(module, patterns),
        functor(Pat, F, _),
        bb_get(my_table, Table0),
        put_assoc(F, Table0, whatever, Table),
        bb_put(my_table, Table)
        .

as([a|Cs]) -=> [a], pat(Cs).

bs([b|Cs]) -=> [b], pat(Cs).

bangs(['!'|Cs]) -=> ['!'], pat(Cs).

and

user:term_expansion((:- defpat(F)), (:- initialization(true))) :-
        prolog_load_context(module, patterns),
        bb_get(my_table, Table0),
        put_assoc(F, Table0, whatever, Table),
        bb_put(my_table, Table)
        .

:- defpat(as).
as([a|Cs]) --> [a], pat(Cs).

:- defpat(bs).
bs([b|Cs]) --> [b], pat(Cs).

:- defpat(bangs).
bangs(['!'|Cs]) --> ['!'], pat(Cs).