DCGrep Challenge!

[jjtolton]

Alright everyone, inspired by some very interesting discussions the past few days regarding subjects related to DCGs, I have been secretly working on... dcgrep, a DCG-based "grep" tool!

It raises so many interesting topics about how to use Prolog and DCGs effectively on numerous threads. Here is my best (but so far not working) effort towards a dcgrep-like interface:

:- use_module(library(format)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Feel free to modify params as necessary to get a good text search 
   Possible invocation:
   
   cat dcgrep.pl | scryer-prolog -g run dcgrep.pl -- '(last --> ...,[_])'
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

% note: this doesn't work, but might give you some ideas
run :-
        '$toplevel':argv([DCG|_]), % https://github.com/mthom/scryer-prolog/discussions/1909
        phrase(( DCG,"."), DCGs), 
        read_term_from_chars(DCGs, DcgTerm, []),
        expand_term(DcgTerm1, Expanded),
        assertz(Expanded),
        current_input(In),
        get_chars(In, Cs),
        phrase(lines(Lines), Cs),
        maplist(phrase(Head),Lines,Out),
        write(Out), nl.


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   See https://www.metalevel.at/prolog/dcg
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
lines([])     --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).

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

eos([], []).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   See https://github.com/mthom/scryer-prolog/issues/2867
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */        
get_chars(Stream, []) :- at_end_of_stream(Stream), !. 
get_chars(Stream, [Char|Cs]) :-
        get_char(Stream, Char),
        get_chars(Stream, Cs).

There are many, MANY ways to go with this, I would love to see everyone's great ideas!

Some important considerations:

• Semantics: What should the semantics of dcgrep be? Full text or line by line? Should it offer similar functionality to regex, or be completely different?
• Techniques: What are the best ways to structure DCGs to accomplish these tasks? For instance, (..., "something", ...) is tempting, but is not a great technique for matching text because the ... consumes more than you probably think it does. Or is it?
• What else??

[UWN]

For instance, (..., "something", ...) is tempting, but is not a great technique ...

?

Note that in your version, your are copying the entire file content into Cs. That means 16 times the file size, and only then you start ... . With phrase_from_file/2 the space requirements for above is currently ± the file size, because the content is represented with partial strings, and — in case of GC as in SWI — the effort requires constant space. A ... //0 at the end could be implemented in a more sophisticated manner without affecting the code as such. And, there is still another option, that is #251. You might also add {whatever} directly after the pattern.

In short, by using phrase_from_file/2 you would also encourage improvements to its implementation (and test it more extensively) which would be profitable for everyone.

For your code, note that there is SICStus 4 that produces for a file echo -n a > a the list [a, end_of_file]. This is not what you found in #2867.

---

For information, please read 3. Pure I/O via DCGs of Declarative language extensions for Prolog courses by Neumerkel, Triska, Wielemaker, FDPE 2008.

[triska]

In addition to the memory overhead, reading individual characters yields very bad I/O performance.

It is more efficient to read larger blocks, as phrase_from_file/2 does.

[UWN]

A sketch for a faster ... at the end only.

...@(S0,S) :-
   (  S \== [] -> representation_error(ending_nonterminal)
   ;  '$skip_max_list'(_, _, S0,S1),
      (  nonvar(S1) -> ...(S1,S)
      ;  '$unattributed_var'(S1) -> ...(S1,S)
      ;  sometestforpio(S1) -> true % for JJ
      ;  ...(S1,S) % does this ever happen?
      )
   ).
      

[triska]

Awesome, thank you a lot! I filed a draft PR for this at #3093, please have a look!

The remaining issue is:

?- phrase_from_file(...@, "pio.pl").
   freeze:freeze(_A,user:render_step(true,'$dropped_value',position_and_lines_read(0,0),_A)).

[jjtolton]

  ;  sometestforpio(S1) -> true % for JJ

🤣🤣🤣

brilliant!!!

[jjtolton]

Amazing!! This is a result of many comments in the "Meta-DCGs" and "Dcg bug or nuanced behavior?".

One of the biggest pain points is that redirecting from a pipe to current_input(In) does not really work at all using library(pio) or get_char/2! So, it can't really be used as a replacement for grep yet.

But this is already a better version of grep with more powerful syntax! With a few command line flags it could be very versatile!

$ scryer-prolog -g run dcgrep.pl -- /tmp/words.txt '...,[Last]'.
JiuJitsu is a mousetrap.  ...,['.']
The moustrap is not a JiuJitsu mousetrap.  ...,['.']
But, when JiuJitsu puts the mouse in the cheese,  ...,[',']
JiuJitsu the mousetrap cheese mouse WHATVER LOLLLLL  ...,['L']

:- use_module(library(format)).
:- use_module(library(pio)).
:- use_module(library(iso_ext)).
:- use_module(library(debug)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

writeln(Line-Term) :- format("~s ~t ~q", [Line,Term]), nl.

run :-
        '$toplevel':argv([Fname,DCG|_]),
        read_term_from_chars(DCG,DCGTerm, []),
        setup_call_cleanup(open(Fname,read,Stream,[]),
                           (   phrase_from_stream(lines(Lines), Stream),
                               matching_phrases(DCGTerm, Lines, Matching),
                               maplist(writeln, Matching)
                           ),
                           close(Stream)
                          ),
        halt.

matching_phrases(_Phrase, [], []).
matching_phrases(Phrase, [Line|Lines], Matching) :-
        copy_term(Phrase, Phrase1),
        if_(phrase_t(Phrase1, Line),
            Matching=[Line-Phrase1|Matching0],
            Matching=Matching0
           ),
        matching_phrases(Phrase,Lines,Matching0).


phrase_t(Phrase,In,T) :- phrase_t(Phrase,In,[],T).

phrase_t(Phrase,In,Out,T) :-
        (   phrase(Phrase,In,Out) ->
              T=true
        ;   T=false
        ).

%% https://www.metalevel.at/prolog/dcg

lines([])     --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).

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

eos([], []).

[triska]

If you describe the output with a DCG and emit it with phrase_to_stream/2, then a perfect implementation could write the output as soon as it becomes known, making it unnecessary to manifest the entire string in memory.

[triska]

And for only reading from files, consider using phrase_from_file/2. A perfect implementation will mmap files without 0-bytes (i.e., all the usual text files) to memory and process the contents from there, overhead-free with respect to Prolog terms, relying on the OS to perform the mapping. See #251.

[jjtolton]

If you describe the output with a DCG and emit it with phrase_to_stream/2, then a perfect implementation could write the output as soon as it becomes known, making it unnecessary to manifest the entire string in memory.

I feel like this version is really close but I'm not sure if the intermediate phrase/2 pulls everything into memory or not:

# /tmp/words.txt 
JiuJitsu is a mousetrap.
The moustrap is not a JiuJitsu mousetrap.
But, when JiuJitsu puts the mouse in the cheese,
JiuJitsu the mousetrap cheese mouse WHATVER LOLLLLL

$ scryer-prolog -g 'run' dcgrep.pl -- /tmp/words.txt '(...,"cheese",...)'.
But, when JiuJitsu puts the mouse in the cheese,
JiuJitsu the mousetrap cheese mouse WHATVER LOLLLLL

:- use_module(library(format)).
:- use_module(library(pio)).
:- use_module(library(iso_ext)).
:- use_module(library(debug)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

run :-
        '$toplevel':argv([Fname,DCG|_]),
        read_term_from_chars(DCG,DCGTerm, []),
        phrase_from_file(lines(Lines), Fname),
        current_output(Out),
        phrase(matching(DCGTerm, Lines), Matching), % does manifest full file?
        phrase_to_stream(lines(Matching), Out),
        halt.

phrase_t(Phrase,In,T) :- phrase_t(Phrase,In,[],T).

phrase_t(Phrase,In,Out,T) :-
        (   phrase(Phrase,In,Out) ->
              T=true
        ;   T=false
        ).

matching(Phrase, [Line|Lines]) -->
        { copy_term(Phrase, Phrase1) },
        { phrase_t(Phrase1, Line, T) },
        (   { T=true } ->
            [Line]
        ;   []
        ),
        matching(Phrase,Lines).
matching(_Phrase,[]) --> [].

lines([])     --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).

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

eos([], []).

[hurufu]

I'm observing developments, just wanted to add my 5 cents. One of the design choices of grep was to have a very succinct syntax – which made it suitable for interactive work via shell. So to be useful as an interactive every day tool dcgrep has to include a collection of high-level rules for common tasks:

1. Match for every word – not every line
2. Case-insensitive match
3. Skip white spaces
4. Character classes
5. Cartesian product: {a,b}{1,2} should produce a1 a2 b1 b2.
6. Context around the match (grep -A1 pattern)
7. Print file name where match was found – useful when working with multiple files in combination with find(1)
8. rule chaining (like grep pattern1 | grep pattern2 | grep pattern3).
9. Something akin grep pattern | sort | uniq | wc -l
10. Bonus point for fuzzy matching something what fzf(1) is doing.
11. Second bonus point for simplifying work with structured files (csv, json, yaml).

If dcgrep will have succinct way to specify all of this – it would motivate me to switching to it, because currently when I work on text I have to use a lot of different programs: grep, cut, awk, sed, jq, yq, fzf, ...

The hardest part is to design a good DSL that will work for all those use cases. If dcgrep will have some sort of a killer feature then it will have a chance to penetrate into already oversaturated ecosystem of Linux command line tools.

[UWN]

Also unicode string normalization must be supported

Why? It seems this will only bloat Scryer. There is UTF-8. What next, all the other encodings?

This comes at the price of less support for the core mechanisms. Just think of partial strings and resource errors.

[jjtolton]

I'm observing developments, just wanted to add my 5 cents. One of the design choices of grep was to have a very succinct syntax – which made it suitable for interactive work via shell. So to be useful as an interactive every day tool dcgrep has to include a collection of high-level rules for common tasks:

1. Match for every word – not every line

2. Case-insensitive match

3. Skip white spaces

4. Character classes

5. Cartesian product: {a,b}{1,2} should produce a1 a2 b1 b2.

6. Context around the match (grep -A1 pattern)

7. Print file name where match was found – useful when working with multiple files in combination with find(1)

8. rule chaining (like grep pattern1 | grep pattern2 | grep pattern3).

9. Something akin grep pattern | sort | uniq | wc -l

10. Bonus point for fuzzy matching something what fzf(1) is doing.

11. Second bonus point for simplifying work with structured files (csv, json, yaml).

If dcgrep will have succinct way to specify all of this – it would motivate me to switching to it, because currently when I work on text I have to use a lot of different programs: grep, cut, awk, sed, jq, yq, fzf, ...

The hardest part is to design a good DSL that will work for all those use cases. If dcgrep will have some sort of a killer feature then it will have a chance to penetrate into already oversaturated ecosystem of Linux command line tools.

I was also thinking something like a succinct notation would be good, these are great notes.

[hurufu]

Also unicode string normalization must be supported

Why? It seems this will only bloat Scryer. There is UTF-8. What next, all the other encodings?

This comes at the price of less support for the core mechanisms. Just think of partial strings and resource errors.

Let me explain. Unification example was just to emphasize my point. I would never think that unification mechanism shall be extended to allow unicode normalization in a core language, but a user-facing tool (dcgrep) should do it, because otherwise how can you reliably find all occurrences of ü? We should not expect a user of dcgrep to be a programmer or know about unicode.

[bakaq]

Also unicode string normalization must be supported

Why? It seems this will only bloat Scryer. There is UTF-8. What next, all the other encodings?

Unicode normalization is not a different encoding, it's a normalization of (sequences of) the Unicode codepoints themselves, because some letters (like the ü; I don't remember the proper term to describe this) have multiple encodings as sequences of Unicode codepoints (which is a different layer of abstraction from the encoding of codepoints as bytes, which is what UTF-8 is concerned with). We represent Unicode using the UTF-8 encoding, and we don't need to change that to have normalization. In fact there are good Rust implementations of the normalization algorithms that we can use: https://docs.rs/unicode-normalization/latest/unicode_normalization/.

This is indeed something that is needed for a good implementation of any text manipulation utility that is not just ASCII. My worry here is about having Scryer itself become Unicode aware (that is, know how to deal with the semantics of Unicode (character classes, normalization, etc...), not just being able to represent it with an encoding like UTF-8). Rust itself is not Unicode aware (and neither is Zig), and there are some good reasons for this in terms of having to update the Unicode standard and have all the algorithms and data embedded. Maybe Unicode awareness is better left as a (third party!) library, but I know there is some interest on having the core Prolog system be able to work with arbitrary Unicode (like being able to use japanese kanji as naked atoms), which will almost certainly need Unicode awareness in the engine to implement correctly.

[hurufu]

You can do normalization as a first step inside dcgrep itself, for example you can spawn external process, so Scryer engine will see already normalized text.

printf 'ü=u\u0308\n' | uconv -x any-nfc | od -tx1z

My comment was about tool not about core language.

[UWN]

Why? It seems this will only bloat Scryer. There is UTF-8. What next, all the other encodings?

Unicode normalization is not a different encoding

I should have mentioned that exactly such discussions happened also in other systems some decades ago. It is just a sink. And, the next step was to support all other encodings...

In any case, if we assume that files have to be in UTF-8, be can equally assume that they are normalized.

some interest on having the core Prolog system be able to work with arbitrary Unicode (like being able to use japanese kanji as naked atoms

?- X = 漢字.
   X = 漢字.

What is missing here?

[haijinSk]

[...] Think of a text: a, space, combining diaresis, space, b. So are these two or three? What do you see? And I rather think of #2936

?- "ä"=[a,C], Ds = [a,' ',C,' ',b].
   C = '̈', Ds = "a ̈ b".

Yes, I see, the thing... One can perceive different things, it depends..., on conventions/expectations...

[UWN]

But the set of characters is too large:

?- Cs = "a\x308\", Cs = [_,C], char_type(C, T).
   Cs = "ä", C = '̈', T = alnum % alphanumeric char (* 6.5.2 *)
;  Cs = "ä", C = '̈', T = alpha % alpha char (* 6.5.2 *)
;  Cs = "ä", C = '̈', T = prolog % char (6.5)
;  Cs = "ä", C = '̈', T = lower("̈")
;  Cs = "ä", C = '̈', T = upper("̈")
;  false.
?- C = ä, char_type(C, T).
   C = ä, T = alnum % alphanumeric char (* 6.5.2 *)
;  C = ä, T = alpha % alpha char (* 6.5.2 *)
;  C = ä, T = alphabetic % from Unicode chapter 4, the Alphabetic property
;  C = ä, T = alphanumeric
;  C = ä, T = lower
;  C = ä, T = octet
;  C = ä, T = prolog % char (6.5)
;  C = ä, T = lower("Ä")
;  C = ä, T = upper("Ä")
;  false.
?-

Why is '\x308\' part of the set of characters? (It's currently classify as alpha char while not being an Alphabetic.)

Maybe add to #2664

[haijinSk]

In Raku, the diaresis will disappear in that context:

[0] > .raku with "a ̈ b".comb.map: *.uniname
("LATIN SMALL LETTER A", "SPACE", "SPACE", "LATIN SMALL LETTER B").Seq

[haijinSk]

[0] > "a ̈ b".chars
4
[1] > "a ̈ b".codes
5
[2] > "a ̈ b".ords
(97 32 776 32 98)
[3] > "a ̈ b".encode("utf-8")
utf8:0x<61 20 CC 88 20 62>

[jjtolton]

PS2: I apologize for my "out of topic" comments here, at least I'm using a different programming language here...

I can't speak for everyone here, but almost all of us are polyglot developers with proficiency in multiple languages, and I think that these comments are welcome. If Scryer and Prolog are so weak that they fall apart in the face of a comparative linguistics discussion then we have a big problem! I think that the comparative linguistics help to strengthen the discourse when done constructively.

As @triska has pointed out we will probably be continuing to develop Prolog for the next 50-100 years before we have all the correct answers worked out, for example the DCG Iso standard was just passed!

[UWN]

In Raku

It's the device where it is displayed that actually decides how it is rendered. My Ubuntu terminal makes it different to FF. As I said, a complete sink and waste of time.

[haijinSk]

Oh, I see, not about that "numbers/file thing"...

[haijinSk]

By "disappear" I mean numbers of chars (according to Raku) and ("LATIN SMALL LETTER A", "SPACE", "SPACE", "LATIN SMALL LETTER B"), no "DIAERESIS" here...

[haijinSk]

And the string is the Ds:

?- "ä"=[a,C], Ds = [a,' ',C,' ',b].
   C = '̈', Ds = "a ̈ b".

[UWN]

Not knowing what is the FF

Firefox. And on Chrome@Android, it looks different, again different on Samsung Internet.

[haijinSk]

Oh, thank you... I'm using FF... I was wondering what is FF in the context of Linux terminals... In the style of "fish cannot see water"...

[jjtolton]

Ok so to summarize what I am understanding, it sounds like Scryer Prolog itself should not be in the business of "unicode normalization" but a tool such as dcgrep probably should be?

[UWN]

Ok so to summarize what I am understanding, it sounds like Scryer Prolog itself should not be in the business of "unicode normalization" but a tool such as dcgrep probably should be?

Please, show me first the grep(1) that actually does such a beast as normalization!

ulrich@gupu:~$ grep . text.txt
Line with umlaut a:  ä
Line with diaresis:  ä
ulrich@gupu:~$ grep ä text.txt
Line with umlaut a:  ä
ulrich@gupu:~$ grep ä text.txt
Line with diaresis:  ä
ulrich@gupu:~$ echo $LANG
en_US.UTF-8

There is one (1) occurrence of UTF in the manual of grep. Seems you are searching here for something that does not exist.

If you really want to do this, it makes much more sense to adjust the pattern accordingly and not the input.

[jjtolton]

ahhh I see! We were placing unreasonable expectations on dcgrep! This is good. That will make dcgrep much more robust and we can rely on dedicated tools to do the normalization work if the user desires.

[UWN]

(And apart from that, umlaut a and diaresis are two different things in German. In, e.g. Latex, the diaresis dots are slightly higher than the umlaut dots (which are the remainder from a small e))

[hurufu]

If dcgrep will implement fuzzy finding with edit distance – then we can avoid all the nastiness of unicode. Just search for a word muller with maximum edit distance of 1 and it will find also müller.