some(higher level constructs to work with DCGs)

[aarroyoc]

Hi, I've been working with DCGs and inspired by other parsing frameworks I designed some abstractions on top of DCGs to help me parse and generate some stuff. I will list them and show how to use them so you can use them if you find them useful or leave feedback.

• char(Type, N)// this is a light wrapper over char_type/2 and allows us to only define a character in a character type. The order of the arguments is reversed compared to char_type, you'll see why in the next ones

  char(Type, N) -->
    [N], { char_type(N, Type) }.
  

• dif_char(Type, N)// the opposite version of char//2. It defines a character which is not of the specified character type.

  dif_char(Type, N) -->
    [N], { char_type(N, CType), dif(CType, Type) }.
  

• dif_seq(Not)// holds if the sequence is not present starting from that place. It compares Not with the the same length sequence and sees if they're different or not. I had to use an auxiliary push//1 to restore the consumed items, so further rules can consume them as expected. You may want to use this for example to check for some delimiters in certain file formats.

  dif_seq(Not) -->
    seq(X), { append(A, _, X), same_length(Not, A), dif(Not, A) },
    push(X).
  
  push([X|Xs]), [X] --> push(Xs).
  push([]) --> [].
  

• dif(N)// holds if N is not the following element in the list

  dif(N), [X] -->
    [X], { dif(X, N) }.
  

• at_least(N, T, Ls)// ensure that at least N Ts happen in the sequence. This is an important abstraction. This rule allows us to simplify many simple cases of recursion. It requires that T exposes the element in the last argument (hence why char//2 was swapped). The already defined seq//1 also works.

  at_least(N, T, [L0|Ls]) -->
    { N #> 0, NextN #= N - 1 },
    phrase(T, L0),
    at_least(NextN, T, Ls).
  at_least(0, _, []) --> [].
  at_least(0, T, [L0|Ls]) -->
    phrase(T, L0),
    at_least(0, T, Ls).
  

• any(T, Ls)// any is at_least with N = 0. It is similar to the regex operator *
• some(T, Ls)// some is at_least with N = 1. It is similar to the regex operator +
• repeat(N, T, Ls)// ensures N Ts happen in the sequence. It is similar to {N} in regex

  repeat(N, T, [L0|Ls]) -->
    { N #> 1, NextN #= N - 1 },
    phrase(T, L0),
    repeat(NextN, T, Ls).
  repeat(1, T, [L0]) -->
    phrase(T, L0).
  

• Also I've defined a version of some//2 that takes a separator. That way you can match sequences that are separated by something. However, I would like to generalize it to at_least//3

  some(T, Sep, [L0|Ls]) --> phrase(T, L0), any(prefix_sep(Sep, T), Ls).
  prefix_sep(Sep, T, X) --> Sep, call(T, X).
  

Example time:

?- phrase(char(alphanumeric, X), Y).
   X = '0', Y = "0"
;  X = '1', Y = "1"
;  X = '2', Y = "2"
;  ... .
- phrase(dif_char(alphanumeric, X), "<").
   X = (<)
;  ... .
?- phrase((dif_seq("<img>"), seq(X)), "<img>").
   false.
?- phrase((dif_seq("<img>"), seq(X)), "<xml>").
   X = "<xml>".
?- phrase((dif(error), seq(X)), [error, ok]).
   false.
?- phrase((dif(error), seq(X)), [ok, ok]).
   X = [ok,ok].
?- phrase((at_least(2, char(decimal_digit), Year), at_least(3, char(alpha), Y)), "12345ab").
   false.
?- phrase((at_least(2, char(decimal_digit), Year), at_least(3, char(alpha), Y)), "12345abcd").
   Year = "12345", Y = "abcd"
;  ... .
?- phrase((some(char(decimal_digit), Year), any(char(alpha), Y)), "12345abcd").
   Year = "12345", Y = "abcd"
;  ... .
?- phrase((some(char(decimal_digit), Year), any(char(alpha), Y)), "12345").
   Year = "12345", Y = []
;  ... .
?- phrase((some(char(decimal_digit), Year), any(char(alpha), Y)), "abcd").
   false.
?- phrase((some(char(decimal_digit), Year), repeat(3, char(alpha), Y)), "345abcd").
   false.
?- phrase((some(char(decimal_digit), Year), repeat(3, char(alpha), Y)), "345abc").
   Year = "345", Y = "abc"
?- phrase(some(some(char(alphanumeric)), ",", Names), "Adrián,Alain,王玉").
   Names = ["Adrián","Alain","王玉"]
;  ... .

I also plan to write a new tutorial for the website using some (no pun intended) of this constructs.

Greetings,
Adrián

[triska]

Very interesting, thank you a lot for working on this and for sharing this!

Regarding call//N: This is for calling Prolog predicates from within DCGs. To portably refer to DCG  nonterminals within DCGs, please consider the higher-order nonterminals phrase//[2,3]. Using them may also give you more flexibility in the argument order.

[aarroyoc]

Thanks for the feedback. I modified it and my code still works as expected. I think the argument order should still be based on the convention of last argument is the collected one.

[hurufu]

Good demonstration how clpz makes reasoning with numbers elegant, without relying on non-monotonic predicates. I think we should have somewhere a library of DCG rules, because common patterns are re-implemented over and over.

P.S. Isn't dif_seq//1 doing generate-and-test approach? Kinda sub-optimal.

[aarroyoc]

See #3106 (reply in thread)

[UWN]

?- phrase(dif_seq(""),"abc",Xs).
   false.
?- phrase(dif_seq("x"),"abc",Xs).
   Xs = "abc"
;  Xs = "abc"
;  Xs = "abc"
;  false.
?- phrase(dif_seq("xx"),"abc",Xs).
   Xs = "abc"
;  Xs = "abc"
;  false.
?- phrase(dif_seq("xxxx"),"abc",Xs).
   false.

(Any reason to prefer push//1 over unseq//1?)

[aarroyoc]

I see. I wasn't very satisfied with dif_seq//1 but I see it has some more problems than I thought. It cannot be defined with dif//1 because we need to check for the whole sequence ("ab" and "ac" both start with 'a' but as a whole they're different) and it needs to handle the case where the sequence stops earlier than the required length to make a comparison. And it cannot consume extra items than needed. I've tried several versions but I don't find the right code for this predicate.