Push-back lists on DCG rule heads

[Paulo Moura]

Hi!

I'm implementing a DCG parser for Logtalk. Right now I'm trying to find
some explanation on the intended meaning and usefulness of push-back
lists on DCG rule heads, as well as test cases. My current parser
translates a DCG rule such as:

p, [a, b] --> [c], {write(hello), nl}

to the clause:

p(A, [a, b| B] :- A = [c| C], write(hello), nl, C = B.

Is this translation correct? Any help is appreciated.

TIA,

Paulo


-----------------------------------------------------------
Paulo Jorge Lopes de Moura
Dep. of Informatics Office 4.3 Ext. 3257
University of Beira Interior Phone: [phone]
6201-001 Covilhã Fax: [phone]
Portugal

<mailto:***@di.ubi.pt>
<http://www.logtalk.org/pmoura.html>
-----------------------------------------------------------



----------------
* To UNSUBSCRIBE, please use the HTML form at

http://www.swi-prolog.org/mailinglist.html

or send mail to prolog-***@swi.psy.uva.nl using the Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/

[Richard A. O'Keefe]

Paulo Moura <***@di.ubi.pt> asks about DCG rule push-back lists.
Right now I'm trying to find some explanation on the intended
meaning and usefulness of push-back lists on DCG rule heads, as
well as test cases.

They come from Metamorphosis grammars, originally.
If you can find Fernando Pereira on the net, he can probably
give you the most authoritative answer.

If you are trying to process a natural language, with things like
topicalisation, extraction, slash categories, move-alpha, or however you
think of it, then push-back has some use. Otherwise, probably not.
For natural language processing, XGs are better; there are theoretical
problems with them otherwise (the language accepted includes the
push-back tokens).

Practically the only use I ever make of them is
peek(X), [X] --> X.
peek(X, Y), [X,Y] --> [X,Y].
which translate to
peek(X, [X|S], [X|S]).
peek(X, Y, [X,Y|S], [X,Y|S]).

My current parser translates a DCG rule such as:

p, [a, b] --> [c], {write(hello), nl}

to the clause:

p(A, [a, b| B] :- A = [c| C], write(hello), nl, C = B.

Is this translation correct?

The Quintus Prolog manual says (page G-151):

Terminals on the left-hand side of a rule, enclosed in square brackets,
translate into 'C'/3 goals, with the first and third arguments reversed.
For example,
is(N), [not] --> [aint].
becomes
is(N, S0, S) :-
'C'(S0, aint, S1),
'C'(S, not, S1).

What's the point of 'C'/3? Why not do unifications in the head?

There is a subtle and delicate point concerning cuts.
The placement of cuts is to be taken literally. Terminal matching
must not be promoted back over a cut. And pushback is understood
to happen _after_ everything else in a rule.

Consider
p(a), [X] --> !, [X,a], q(X).

This should be translated as

p(a, S0, S) :- !,
/* note that the cut is done *exactly* where it appears */
S0 = [X,a|S1],
q(S1, S2),
S = [X|S2].


----------------
* To UNSUBSCRIBE, please use the HTML form at

http://www.swi-prolog.org/mailinglist.html

or send mail to prolog-***@swi.psy.uva.nl using the Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/

[Paulo Moura]

On Quarta, Jun 11, 2003, at 05:30 Europe/Lisbon, Richard A. O'Keefe

Post by Richard A. O'Keefe
If you are trying to process a natural language, with things like

Not really. That's up to the Logtalk users. I just want to support the
definition of DCG rules inside objects (and categories).

Post by Richard A. O'Keefe
topicalisation, extraction, slash categories, move-alpha, or however you
think of it, then push-back has some use. Otherwise, probably not.
For natural language processing, XGs are better; there are theoretical
problems with them otherwise (the language accepted includes the
push-back tokens).
Practically the only use I ever make of them is
peek(X), [X] --> X.
peek(X, Y), [X,Y] --> [X,Y].
which translate to
peek(X, [X|S], [X|S]).
peek(X, Y, [X,Y|S], [X,Y|S]).

With the current version of the Logtalk DCG rule translator I get:

peek(X, Y, S0, S) :-
S0 = [X,Y|S1],
S = [X,Y|S1].

Supporting push-back lists complicates the otherwise simple translation
of rule heads. Coding for the special case above in order to get a fact
instead of a rule does not seam to be worthwhile, but...

Post by Richard A. O'Keefe
Terminals on the left-hand side of a rule, enclosed in square brackets,
translate into 'C'/3 goals, with the first and third arguments reversed.
For example,
is(N), [not] --> [aint].
becomes
is(N, S0, S) :-
'C'(S0, aint, S1),
'C'(S, not, S1).
What's the point of 'C'/3? Why not do unifications in the head?
There is a subtle and delicate point concerning cuts.
The placement of cuts is to be taken literally. Terminal matching
must not be promoted back over a cut. And pushback is understood
to happen _after_ everything else in a rule.
Consider
p(a), [X] --> !, [X,a], q(X).
This should be translated as
p(a, S0, S) :- !,
/* note that the cut is done *exactly* where it appears */
S0 = [X,a|S1],
q(S1, S2),
S = [X|S2].

I get the same translation. My current set of test cases (and the
corresponding translations) are:

p-->!, [a]
p(A, B):-!, A=[a|B]

p-->[a], !, {fail}
p(A, B):-A=[a|C], !, fail, C=B

p-->[]
p(A, A)

p-->[x]->[];q
p(A, B):-A=[x|C]->C=B;q(A, B)

p-->[a];[b]
p(A, B):-A=[a|B];A=[b|B]

p-->q;r
p(A, B):-q(A, B);r(A, B)

p-->{3}
p(A, B):-3, A=B

p-->[97, 98, 99];[113]
p(A, B):-A=[97, 98, 99|B];A=[113|B]

p-->q;[]
p(A, B):-q(A, B);A=B

p-->{a}, {b}, {c}
p(A, B):-a, b, c, A=B

p-->{q}->[a];[b]
p(A, B):-q->A=[a|B];A=[b|B]

p-->{q}->[];b
p(A, B):-q->A=B;b(A, B)

p-->[foo], {write(x)}, [bar]
p(A, B):-A=[foo|C], write(x), C=[bar|B]

p-->[foo], {write(hello)}, {nl}
p(A, B):-A=[foo|C], write(hello), nl, C=B

p-->[foo], {write(hello), nl}
p(A, B):-A=[foo|C], write(hello), nl, C=B

p, [a, b]-->[foo], {write(hello), nl}
p(A, B):-A=[foo|C], write(hello), nl, B=[a, b|C]

p(a), [C]-->!, [C, a], q
p(a, A, B):-!, A=[C, a|D], q(D, E), B=[C|E]

p(A, B), [A, B]-->[A, B]
p(A, B, C, D):-C=[A, B|E], D=[A, B|E]

You probably recognize most of them ;-) I believe that the translation
results are correct. Do you have other test cases that you are willing
to share? Thanks for your feedback.

Cheers,

Paulo


-----------------------------------------------------------
Paulo Jorge Lopes de Moura
Dep. of Informatics Office 4.3 Ext. 3257
University of Beira Interior Phone: [phone]
6201-001 Covilhã Fax: [phone]
Portugal

<mailto:***@di.ubi.pt>
<http://www.logtalk.org/pmoura.html>
-----------------------------------------------------------



----------------
* To UNSUBSCRIBE, please use the HTML form at

http://www.swi-prolog.org/mailinglist.html

or send mail to prolog-***@swi.psy.uva.nl using the Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/

[Paulo Moura]

On Quinta, Jun 12, 2003, at 03:30 Europe/Lisbon, Richard A. O'Keefe

Do you have other test cases that you are willing to share?
I'd be willing if I did, but I don't.
More precisely, I have some, but I've lost them.
I've got the residues of file structures from 6 different machines,
imperfectly melded...

Oops! For what is worth, where is my current version of the Logtalk DCG
translator:


% '$lgt_dcgrule_to_clause'(@dcgrule, -clause)
%
% converts a DCG rule to a normal clause


'$lgt_dcgrule_to_clause'(Rule, Clause) :-
catch(
'$lgt_dcg_rule'(Rule, Clause),
Error,
throw(error(Error, dcgrule(Rule)))).



% '$lgt_dcg_rule'(@dcgrule, -clause)
%
% converts a DCG rule to a normal clause

'$lgt_dcg_rule'((RHead --> RBody), CHead) :-
RBody == [],
!,
'$lgt_dcg_head'(RHead, CHead, _, _, S, S, _).

'$lgt_dcg_rule'((RHead --> RBody), (CHead :- CBody)) :-
'$lgt_dcg_head'(RHead, CHead, Body, Body2, S0, S, S1),
'$lgt_dcg_body'(RBody, Body, S0, S),
'$lgt_dcg_fold_unifications'(Body2, CBody, S1).



% '$lgt_dcg_head'(@dcghead, -head, @goal, -goal, @var, @var, -var)
%
% translates DCG rule head to a Prolog clause head
% (the last argument returns the variable representing the ouput list)

'$lgt_dcg_head'(RHead, _, _, _, _, _, _) :-
var(RHead),
throw(instantiation_error).

'$lgt_dcg_head'((_, Terminals), _, _, _, _, _, _) :-
\+ '$lgt_proper_list'(Terminals),
throw(type_error(list, Terminals)).

'$lgt_dcg_head'((Nonterminal, Terminals), CHead, Body, (Body,Goal), S0,
S, S1) :-
!,
'$lgt_dcg_terminals'(Terminals, Goal, S1, S),
'$lgt_dcg_goal'(Nonterminal, CHead, S0, S1).

'$lgt_dcg_head'(Nonterminal, CHead, Body, Body, S0, S, S) :-
'$lgt_dcg_goal'(Nonterminal, CHead, S0, S).



% '$lgt_dcg_body'(@dcgbody, -body, @var, @var)
%
% translates DCG rule body to a Prolog clause body

'$lgt_dcg_body'(Var, phrase(Var, S0, S), S0, S) :-
var(Var),
!.

'$lgt_dcg_body'(::Goal, ::phrase(Goal, S0, S), S0, S) :-
!.

'$lgt_dcg_body'(Object::Goal, Object::phrase(Goal, S0, S), S0, S) :-
!.

'$lgt_dcg_body'((RGoal,RGoals), (CGoal,CGoals), S0, S) :-
!,
'$lgt_dcg_body'(RGoal, CGoal, S0, S1),
'$lgt_dcg_body'(RGoals, CGoals, S1, S).

'$lgt_dcg_body'((RGoal1 -> RGoal2), (CGoal1 -> CGoal2), S0, S) :-
!,
'$lgt_dcg_body'(RGoal1, CGoal1, S0, S1),
'$lgt_dcg_body'(RGoal2, CGoal2, S1, S).

'$lgt_dcg_body'((RGoal1;RGoal2), (CGoal1;CGoal2), S0, S) :-
!,
'$lgt_dcg_body'(RGoal1, CGoal1, S0, S),
'$lgt_dcg_body'(RGoal2, CGoal2, S0, S).

'$lgt_dcg_body'({Goal}, (CGoal, S0=S), S0, S) :-
!,
(var(Goal) -> CGoal = call(Goal); CGoal = Goal).

'$lgt_dcg_body'(!, (!, S0=S), S0, S) :-
!.

'$lgt_dcg_body'(\+ RGoal, CGoal, S0, S) :-
!,
'$lgt_dcg_body'((RGoal -> {fail};{true}), CGoal, S0, S).

'$lgt_dcg_body'([], (S0=S), S0, S) :-
!.

'$lgt_dcg_body'([Terminal| Terminals], CGoal, S0, S) :-
!,
'$lgt_dcg_terminals'([Terminal| Terminals], CGoal, S0, S).

'$lgt_dcg_body'(Non_terminal, CGoal, S0, S) :-
'$lgt_dcg_goal'(Non_terminal, CGoal, S0, S).



% '$lgt_dcg_goal'(@goal, -goal, @var, @var)
%
% translates DCG goal to Prolog goal

'$lgt_dcg_goal'(RGoal, _, _, _) :-
\+ '$lgt_callable'(RGoal),
throw(type_error(callable, RGoal)).

'$lgt_dcg_goal'(RGoal, CGoal, S0, S) :-
RGoal =.. RList,
'$lgt_append'(RList, [S0, S], CList),
CGoal =.. CList.



% '$lgt_dcg_terminals'(@list, -goal, @var, @var)
%
% translate list of terminals

'$lgt_dcg_terminals'(Terminals, S0=List, S0, S) :-
'$lgt_dcg_terminals'(Terminals, S, List).


'$lgt_dcg_terminals'([], S, S).

'$lgt_dcg_terminals'([Terminal| Terminals], S, [Terminal| Rest]) :-
'$lgt_dcg_terminals'(Terminals, S, Rest).



% '$lgt_dcg_fold_unifications'(+goal, -goal, @var)
%
% folds redundant calls to =/2 by calling the unification
% goals execept for output unifications

'$lgt_dcg_fold_unifications'((Goal1 -> Goal2), (SGoal1 -> SGoal2), S) :-
!,
'$lgt_dcg_fold_unifications'(Goal1, SGoal1, S),
'$lgt_dcg_fold_unifications'(Goal2, SGoal2, S).

'$lgt_dcg_fold_unifications'((Goal1;Goal2), (SGoal1;SGoal2), S) :-
!,
'$lgt_dcg_fold_unifications'(Goal1, SGoal1, S),
'$lgt_dcg_fold_unifications'(Goal2, SGoal2, S).

'$lgt_dcg_fold_unifications'((Goal1,Goal2), SGoal, S) :-
!,
'$lgt_dcg_fold_unifications'(Goal1, SGoal1, S),
'$lgt_dcg_fold_unifications'(Goal2, SGoal2, S),
'$lgt_dcg_simplify_and'((SGoal1,SGoal2), SGoal).

'$lgt_dcg_fold_unifications'(S1=S2, S1=S2, S) :-
(S1 == S; S2 == S),
!.

'$lgt_dcg_fold_unifications'(S1=S2, true, _) :-
var(S2),
!,
S1 = S2.

'$lgt_dcg_fold_unifications'(Goal, Goal, _).



% '$lgt_dcg_simplify_and'(+goal, -goal)
%
% removes redundant calls to true/0 and flats a conjunction of goals

'$lgt_dcg_simplify_and'((Goal1 -> Goal2), (SGoal1 -> SGoal2)) :-
!,
'$lgt_dcg_simplify_and'(Goal1, SGoal1),
'$lgt_dcg_simplify_and'(Goal2, SGoal2).

'$lgt_dcg_simplify_and'((Goal1;Goal2), (SGoal1;SGoal2)) :-
!,
'$lgt_dcg_simplify_and'(Goal1, SGoal1),
'$lgt_dcg_simplify_and'(Goal2, SGoal2).

'$lgt_dcg_simplify_and'(((Goal1,Goal2),Goal3), Body) :-
!,
'$lgt_dcg_simplify_and'((Goal1,(Goal2,Goal3)), Body).

'$lgt_dcg_simplify_and'((true,Goal), Body) :-
!,
'$lgt_dcg_simplify_and'(Goal, Body).

'$lgt_dcg_simplify_and'((Goal,true), Body) :-
!,
'$lgt_dcg_simplify_and'(Goal, Body).

'$lgt_dcg_simplify_and'((Goal1,Goal2), (Goal1,Goal3)) :-
!,
'$lgt_dcg_simplify_and'(Goal2, Goal3).

'$lgt_dcg_simplify_and'(Goal, Goal).


Some notes:

1. The "funny" functors are a consequence of these predicates being
part of the internals of Logtalk.

2. The predicate '$lgt_dcg_head'/7 is based on a similar definition
found on a DCG translator posted by Richard A. O'Keefe a long time ago
in a mailing list discussion on DCGs. I've extended its definition to
return the variable that represents the output list of terminals in the
head. I need this variable to later fold redundant calls to =/2.

3. The flattening of conjunctions and removing of redundant calls to
true/0 is performed while folding redundant calls to unification goals.

4. We need a standard for DCG rule translation. I'm yet to find two
Prolog compilers compiling DCG rules in the same way (regarding open
source compilers, I've tried YAP, SWI-Prolog, GNU Prolog).

5. Logtalk is open source code, including the code above... that's of
course based on other open source and public domain code (the code for
folding unifications is invented by my... hope that it's not a silly
invention ;-).


Cheers,

Paulo


-----------------------------------------------------------
Paulo Jorge Lopes de Moura
Dep. of Informatics Office 4.3 Ext. 3257
University of Beira Interior Phone: [phone]
6201-001 Covilhã Fax: [phone]
Portugal

<mailto:***@di.ubi.pt>
<http://www.logtalk.org/pmoura.html>
-----------------------------------------------------------



----------------
* To UNSUBSCRIBE, please use the HTML form at

http://www.swi-prolog.org/mailinglist.html

or send mail to prolog-***@swi.psy.uva.nl using the Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/