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 ==> 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 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.
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:
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
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.
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.
@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:
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.
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 =>.
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:
I’m reconsidering this. I’m working on code where both SSU and DCGs are quite useful. This uses DCGs in generative mode, i.e., producing a list rather than consuming one.
For the pushback list we have no ambiguity as far as I can tell, as this must be a list and, although lists are a goal (hence ?- [file]. works), DCGs already interpret them differently. We do have various problems though. For example, when parsing we might want to write e.g.
ast(Statement), keyword(while) ==> ...
where keyword(while) is interpreted as a non-terminal. While generating we’d like to write
ast(while(Cond, Action)), atom(Cond) ==> ...
where Cond is a guard on the term. We can solve this ambiguity using {}, as in
ast(while(Cond, Action)), {atom(Cond)} ==> ...
Now we interpret the rule as “PlainHead, DCGBody1 ==> DCGBody2.” This makes sense. Now we have a problem with lists that may either be a pushback list or a normal DCG terminal
I see the point for SSU generative DCG rules: they allow for simple code acting on an input term that may contain variables anywhere and as a bonus you get a precise error if you forgot a rule for a specific input rather than getting a silent failure. That is what I need
I do not yet see the point for parsing rules. It merely forces you to leave the head variables unbound and bind them in the body. It also replaces the cut with ==>, which seems a good idea because I have the impression people tend to place => correctly while many people are struggling with placing the cut in the right place. Unifying the output variable in the body is, considering steadfastness. a good idea. It is IMO a step back when considering readability though.
Do I miss advantages using SSU for parsing? If SSU DCGs have no value for parsing we can tailor the choices we need to make on generative DCGs.
P.s. I’ve pushed a patch that stops the DCG compiler moving unifications resulting from a literal as first element in the DCG body into the head. Since the compiler moves these unifications we no longer need to do so in the DCG compiler. This should make it easy to layer an SSU DCG on top of dcg_translate_rule/2.
