DCGs with single-sided unification?

I’ve made an experimental implementation of extended DCGs (edcg pack) that generates clauses with single-sided unification (=>) instead of full unification (:-).
(You can see the changes here).

I propose using the operator ==> instead of --> for this.

However, single-sided unification allows “guards” to the left of the =>, and I’m wondering how to represent guards with DCGs. (We can’t put them as-is on the left of the ==> (the way => does guard notation) because that syntax is already used for pushback lists or right-hand context.)
Any suggestions? Maybe something like this:

first_n_rev(0) ==> [].
first_n_rev(N), ?{N>0} ==> % N>0 is a guard
    [N],
    {N1 is N-1},
    first_n_rev(N1).

Thanks. I’m writing a lot of new code now for the ROS2 bridge I find myself using => more and more. It takes a while to get used to using guards. I’m using them more and more and I think they really help making the code readable. And yes, I also came across DCGs :slight_smile: ==> seems a natural choice.

Not sure push-pack lists are an issue. They are always a list, no? It seems ==> only makes sense for serializing terms as it aims at making the head matching more predictable while parsing does matching in the body. If this is the case I guess the guards can be normal Prolog code (implicitly using {}). In that case we do not need push-back lists as I don’t think these play a role in this mode.

I think you do have a reason to use ==> for parsing :slight_smile: I’m curious to what that is.

If the code is already available publicly, could you point to some examples. and perhaps add some thoughts as to the “getting used to” – how you would have thought about it and how it’s manifested now.

thank you,

Dan

See GitHub - SWI-Prolog/rclswi: ROS2 bridge for SWI-Prolog, for example rclswi/param.pl at 5c239e156ba034485aedabfe602d335929cdcb56 · SWI-Prolog/rclswi · GitHub

Tooling helps making it pretty:

You wont be anymore able to build the parse tree inside the head arguments of a DCG. Like this here wont work anymore:

read_clause(W, (V+L)) --> ...

Its the same problem with other Picat style rules that you need to insert (=)/2, unless you introduce Picat function notation as well. So you would need to do something like:

read_clause(W, R) ==> R = (V+L), ...

On the other hand, because you need to insert (=)/2, you get more steadfastness, especially if you do it after the (=>)/2 respectively (==>)/2.

Edit 26.03.2021:
What is Picat function notation? Well its the facility that Picat also allows (=)/2 in the head. But I did not yet figure out how Picat handles (=)/2 in the head. But for example Jan W. example:

value_type1(Value, Type), integer(Value) => Type = integer.

Could be written with Picat function notation as follows?

value_type1(Value) = integer, integer(Value) => true.

Not 100% sure what the semantic is. As seen above, Picat function notation has the benefit that it inserts the (=)/2 for you, and you don’t need to introduce the extra variable Type.

But current Picat implementation does a little bit more. You might need quoting ($)/1, and write value_type1(Value) = $integer. Not sure about this.

In DCGs, the push-back can be a goal:

look_ahead(T), [T] --> [T].

% is the same as:

look_ahead2(T), pb(T) --> [T].
pb(T) --> [T].

So, if we treat a goal in the head of a ==> rule as a guard, that could introduce subtle bugs when mechanically translating from --> to ==>.

I’ve almost never used push-back lists when parsing, so it’s not clear to me whether there’s any use for them with ==>. And I haven’t tried ==> for parsing, but I’m guessing it’d work, requiring some minor rewriting, such as:

expr(plus(X,Y) --> expr(X), "+", expr(Y).

would need to be changed to

expr(Expr) ==> expr(X), "+", expr(Y), {Expr=plus(X,Y)}.

Markus Triska has written more about DCGs, including using push-back lists for implicitly passing states around – I don’t know whether that would work for ==> (and I don’t think it’s needed with EDCGs). I think that there are some other uses of push-back lists, such as for avoiding infinite loops.

PS: => isn’t indexed in the SWI-Prolog documentation (nor are :- or --> for that matter)

Yes, but then what is the value of ==> over -->? Assuming ==> commits as => and as we can only have variables in the head we commit to the first rule, no? We could use the guard construct as

expr(Expr), expr(X), "+", expr(Y) ==> {Expr=plus(X,Y)}.

But this is bad. The SSU on teh head has no value and the guard instantiates variables. I still only see value for serializing (unparsing) grammars.

There may be no value of ==> vs --> in this case, but I know I’ve used cuts in DCG parsers to avoid unnecessary backtracking, so I suspect that ==> can be used to avoid some cuts.

Anyway, as I said before, it seems dangerous to have a, b --> … and a, b ==> … treating b differently (as a push-back in the first case and as a guard in the second). That’s why I think that a, ?b ==> … might be a better notation for guards with ==>. (And – who knows? – in the future someone might figure out a use for push-backs with ==>.)

Yes, but then you need to adopt functional notation as a core part of the language. As we know, that is hard to get correct in an untyped language with lambda like constructs. To solve that Picat had to change so much to the language that is is barely recognizable as Prolog descendant and they gave up the code=data mapping. I suspect this is related to the introduction of functions. That is not where I want to go.

I want safer and later possibly faster function-like code as, while this should not be the reason for using Prolog, may real-world programs use Prolog’s relational magic at various places while the whole thing is connected to the rest of the world using function-like code. Think of data conversion, arithmetic if it is not a constraint problem, etc.

1 Like

Thanks.

value_type1(Value, Type), atom(Value), bool(value) => Type = bool.

So, anything after the first term is/are guards. Or, should it perhaps be written as:

value_type1(Value, Type), (atom(Value), bool(value)) => Type = bool.

Dan

I was wondering about this early on – lots of code I wrote had the form:

goal(X1, Y2, Z1) :-
once(pred1(X1, Y1, Z1)),
once(pred2(X1, Y21 Z1)), 
...

to ensure that no choice points were generated for pred1, pred2, since the flow logic here required each call to either succeed or to fail the whole thing – preferrabily raise an error.

The overall intent was to remove choice point creation to speed up the processing of this code – as if, its written in an imperative language.

I guess, now with $(Goal), something similar could be achieved.

Dan

@j4n_bur53 Regarding Picat: You can write following in Picat where integer(Value) and integer(Value) are conditions to the function rule.

go :- 
  println(value_type1(123)),
  nl.

value_type1(Value) = integer, integer(Value) => true.

The result (integer) is the returned when called (this is a function after all).

An alternative is to write it like this where the condition is moved to the body of the function.

value_type2(Value) = integer => integer(Value).

As I understand it the first version (with the condition in the head) is fastest.

Note: You don’t need to $ escape simple atoms such as integer or real. The escapes are needed only for terms that can be interpreted as functions. Example:

value_type2(Value) = $integer(Value), integer(Value) => true.

@hakank thanks for the clarification. BTW I took the example from Jan Ws screenshot, the predicate value_type1/2 there. I think the guard integer/1 needs to be placed before (=>)/2, otherwise it cannot go through all tests, until it finds a matching type.

My implementation of ==>> produces the following expansion, so there’s only SSU in the head of the => clauses (the trues are optimized away by the compiler and the C=B should also be optimized):

a(A, B) =>
    C=B,
    A=[b|D],
    true,
    c(D, C).
a(A, B) =>
    A=B,
    true.

This was the major change in the implementation: there’s a different version of _finish_acc/1 for the SSU case.

I’ve implemented “guards” with EDCGs. If anyone wants to play with it, install the latest version (0.9.1.5) of pack(edcg). It uses ==>> rather than --> (and you have to declare your expanded predicates using edcg:pred_info/3(*) — the dcg accumulator is built-in).

I decided to mark guards with ? even though I don’t think that push-back lists make sense with SSU. It’s not clear to me if ==>> makes sense for parsing; it might make sense to allow [...]-style guards, if the parser is deterministic. E.g., instead of

a --> [b], c.
a --> [].

we might want to write

edcg:pred_info(P, 0, [dcg]) :- P=a ; P=c. % declare a//0, c//0.
a, ? [b] ==>> c.
a ==>> [].

(*) The edcg:pred_info/3 is partly an artefact of how old the code is; one of these days, I intend to make it a bit more modern and remove the need for polluting the name space.

@peter.ludemann, thanks for this work, I think it will be useful. Does ==>> cut unwanted choice points like ==> does?

EDIT: Just looked at the readme, I see it uses ==> under the covers. Thanks again!

To be clear … I did not implement ==> and I don’t think anyone has (it be done by making similar modifications to dcg.pl). I modified the edcg.pl file in pack(edcg).

If you look at the examples.pl file, tests ssu and ssu2_guard show the generated code, which uses =>.

Now I understand what can be done with guards. The above translates this:

a --> [b], !, c.
a --> !, [].

Again, to be clear, I have not implemented guards that involve accumulator nor guards that require expansion – the only kind of guards that I have implemented are those with {...} around them (and, with EDCGs, the {...} is optional if the predicate isn’t declared using edcg:pred_info/3).

My use case is something like this, for traversing trees with complex nodes:

edcg:pred_info(node, 1, [accum1,accum2]).
node(complicated_term_containing(X)), ? {additional_check(X)) ==>> [X]:accum1.
node(complicated_term_containing(X)), ? {different_check(X)) ==>> [X]:accum2.
node(a_different_term(X,Y)) ==>> 
    do_something_different_with(X), 
    and something_with(Y).

This has two advantages over using -->>:

  • Doesn’t need cuts (they’re implicit with the term-expansion to =>).
  • Gets a run-time error if all possible terms aren’t covered.
1 Like