What's the idiomatic way of developing DCGs?

Help!
1

I’m using: SWI-Prolog version 8.2.3 for x86_64-darwin

I’m new to Prolog and am learning how to use DCGs. I’m having trouble figuring out how to play with them.

My end goal here is to be able to parse a file (phrase_from_file/2), but I’d like to be able to generate strings in the meantime to ensure my DCG is correct.

I expected something like this to work:

a(X) --> integer(X), "foo".

?- phrase(a(1), S). %% expected "1foo"
S = [49, f, o, o].

?- phrase(a(N), "1foo"). %% works as I expected
N = 1

Switching to backticks instead of double-quotes seems to get me closer, but then I need to do conversions with string_chars/2 and everything I find on the web about DCGs seems to use strings.

(Note: I am aware there was a change to how double-quotes work in a recent version and have updated prolog to be on a recent version.)

Here are some of the things I’ve tried:

Is there an easier workflow to play with DCGs when developing them? I’m more interested in what is the idiomatic way of doing this and less interested in “set some flag and you can do it the way you want to” (unless that is how people generally do it).

2

TL;DR: use the top level to interactively (and iteratively) write/test/debug a rule. Esp. if you are just parsing, don’t worry about generating output just yet. It is strictly more difficult IMHO.

A trick I saw just a couple of days back here is to use portray_text/1. It is hiding here: https://www.swi-prolog.org/pldoc/doc/_SWI_/library/portray_text.pl

Here is what happens:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.14-26-g81109f540)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- X = `foo`.
X = [102, 111, 111].

?- portray_text(true).
true.

?- X = `foo`.
X = `foo`.

This addresses a part of your question.

“How to develop DCGs”… well, this is a bigger topic. I am sure there is a lot of personal preferences here. I do prefer a bottom up approach. If I look at the input you are trying to parse, I would probably first define a DCG that parses a line (including the newline at the end), like this:

password_rule(policy_password(Lower, Upper, Char, Password)) -->
    integer(Lower), "-", integer(Upper), " ", [Char], ": ",
    nonblanks(Password),
    "\n".

In order to write that, if I can’t just type it in straight away, I would usually start from the beginning, using the 3-argument version of phrase to see what is left to parse. I would do this directly on the top level. So here is what my interactive session might look like:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.14-26-g81109f540)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- portray_text(true).
true.

?- use_module(library(dcg/basics)).
true.

?- phrase(integer(Lower), `1-3 b: cdefg`, Rest).
Lower = 1,
Rest = `-3 b: cdefg`.

?- phrase(( integer(Lower), "-", integer(Upper), ": " ), `1-3 b: cdefg`, Rest).
false. % WAT?

?- phrase(( integer(Lower), "-", integer(Upper), ":" ), `1-3 b: cdefg`, Rest).
false. % WAT? Oh yeah I forgot the letter before the colon, silly me

?- phrase(( integer(Lower), "-", integer(Upper) ), `1-3 b: cdefg`, Rest).
Lower = 1,
Upper = 3,
Rest = ` b: cdefg`.

?- phrase(( integer(Lower), "-", integer(Upper), " ", [Char], ": " ), `1-3 b: cdefg`, Rest).
Lower = 1,
Upper = 3,
Char = 98,
Rest = `cdefg`.

?- phrase(( integer(Lower), "-", integer(Upper), " ", [Char], ": ", nonblanks(Password) ), `1-3 b: cdefg`, Rest).
Lower = 1,
Upper = 3,
Char = 98,
Password = `cdefg`,
Rest = [].

Great, seems I am done with one line. I just need to remember to add the newline for the complete rule.

Now, to parse the whole file, I would need to just parse a sequence of lines. An “idiom” that you can find in the implementation of library(dcg/basics) would look like this:

all_rules([R|Rules]) -->
    password_rule(R),
    !,
    all_rules(Rules).
all_rules([]) --> [].

Now you can use phrase_from_file/2 like this:

parse_rules(File, Rules) :-
    phrase_from_file(all_rules(Rules), File).

With the example I found on the website, I get:

?- parse_rules("d02-example.input", Rules).
Rules = [policy_password(1, 3, 97, `abcde`),
         policy_password(1, 3, 98, `cdefg`),
         policy_password(2, 9, 99, `ccccccccc`)
        ].
1 Like
3

Just to clarify that AFAIK there is no idiomatic way of developing DCGs. I wish there were. As Boris notes

There have been many discussions about how to do DCGs on this forum and if you start to get really involved in writing DCGs and using answers from here and elsewhere you will find yourself very confused. One of the biggest problems with questions related to DCGs is that many examples work on the system of the person who wrote the answer at the time they wrote the answer. However the answer often does not convey all of the needed configurations to get it work exactly the way the answer is presented for use so another person can copy and paste the code into their system.

1 Like
4

@EricGT I misread your reply. You are correct that I didn’t show a fully reproducible example. Here is the input file I used:

% cat d02-example.input 
1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

The program in its entirety consists of these three predicates, copy-pasted from above, plus the dcg/basics import:

:- use_module(library(dcg/basics)).

parse_rules(File, Rules) :-
    phrase_from_file(all_rules(Rules), File).

all_rules([R|Rules]) -->
    password_rule(R),
    !,
    all_rules(Rules).
all_rules([]) --> [].

password_rule(policy_password(Lower, Upper, Char, Password)) -->
    integer(Lower), "-", integer(Upper), " ", [Char], ": ",
    nonblanks(Password),
    "\n".

I do not use a custom startup file or configuration, it is vanilla SWI-Prolog.

1 Like
5

Sorry if you thought the reply was specifically for you, it was not. It is more of a truism when it comes to DCGs.

I can’t recall all of the variables off the top of my head but these are the things I know to be concerned about.

  1. Which Prolog is used, e.g. SWI-Prolog, Turbo Prolog, etc.
  2. What are the settings of the Prolog flags, e.g. double_quotes, and others (can’t remember the ones to pay attention to with DCGs).
  3. Is the DCG using closed list or open list.
  4. Are any modules needed, e.g. library(dcg/basics).
  5. Are higher order predicates being used.
  6. Where are the location of the files; use pwd/0 to check.
  7. Are test cases in a different module, e.g. begin_tests/1
  8. If using SWI-Prolog did check_installation/0 show any problems?
  9. Are you trying to use a hierarchy of modules with Prolog’s flat module system? May need meta_predicate/1.
  10. Is posix needed for line endings?
  11. Should one use phrase/2 or phrase/3 ?
1 Like
6

@Boris, this is spectacular. This was really painful for me before, but I was working on it yesterday and it was much more fun! Thanks so much for the walkthrough, that was exactly what I needed. Those tips/tricks are invaluable to a novice.

7

@EricGT, thanks for the words of caution here, that explains why I’ve seen such wildly different stuff on other sites.

1 Like
8

For some reason, I find it easier to make hard-to-spot typos with DCGs … I find that using listing/1 to see how the DCG rules were translated to regular Prolog often helps in seeing those typos.

It should also be noted that DCGs are just a special case of accumulators and they’re not just restricted to strings (lists of character codes). You can also have multiple accumulators using the EDCG pack (which was originally developed to simplify compiler writing).

And if you want to go wild with DCG-style programming and various extensions, there’s the Logic Grammars book by Abramson and Dahl.

1 Like
9

Thanks again for the help everybody. In case anyone’s interested, here’s what I came up with for a solution to the puzzle I was working on.
problem statement: https://adventofcode.com/2020/day/2
my solution: https://github.com/bmaddy/advent-of-code/blob/efe4494110e858777531a6eceb75724bdb430eb8/2020/day02.pl