Grammar problem.

[Jakub G.]

expression(_, int(X)) --> [int(X)].
expression(_, id(N)) --> [id(N)].
expression(_, X+Y) --> expression(_,X), [sep(+)], expression(_,Y).

condition(_, A>B) --> expression(_,A), [sep(>)], expression(_,B).
condition(_, A>B) --> expression(_,A), [sep(<)], expression(_,B).



?- phrase(condition(_,X), [id(N), sep(>), int(0)]).
X = (id(N)>(int(0))).


?- phrase(condition(_,X), [id(N), sep(<), int(0)]).
infinite loop...

Hi, I have a problem shown above (it's a part of grammar, that's why there is an empty argument of expression and condition. I think that it may be caused by the fact that the line with sep(<) is below sep(>) and the expression is called recursively all the time. But how can I change predicates to make it correct with these two cases?

[Martin Sondergaard]

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

There is an infinite loop in this:

    expression(_, X+Y) --> expression(_,X), [sep(+)], expression(_,Y).

Try changing it like this. You will need to define "expression1".


    expression(_, X+Y) --> expression1(_,X), [sep(+)], expression1(_,Y).

I don't understand why these two behave differently:

?- phrase(condition(_,X), [id(N), sep(>), int(0)]).
X = (id(N)>(int(0))).


?- phrase(condition(_,X), [id(N), sep(<), int(0)]).
infinite loop...

--
Martin Sondergaard,
London, U.K.

[Feliks Kluzniak]

I don't understand why these two behave differently: 

?- phrase(condition(_,X), [id(N), sep(>), int(0)]).
X = (id(N)>(int(0))).


?- phrase(condition(_,X), [id(N), sep(<), int(0)]).
infinite loop...




Perhaps because we have to backtrack out of the first clause for `condition`, and that makes us go into the infinite recursion in the third clause of `expression`?




BTW, the second argument in the head of the second clause for `condition` has a cut-and-paste error.




One can find more explanations in Sec. 3.5.2 (beginning on p. 83) in the old book available here:

http://www.site.uottawa.ca/~szpak/pub/P4P/P4P_03_Metamorphosis_grammars.pdf




Hope this helps,

-— Feliks

[Samer Abdallah]

To expand on Martin’s reply, the rule for expression//2 is ‘left recursive’: if called with the 

second argument unbound, it immediately calls itself under precisely the same conditions,

without consuming any tokens from the input. One can always rewrite a grammar to

get rid of left recursion while recognising the same sequences, but the implicit or explict

parse tree you get will be different and may not match the intended semantics.

An elegant way to deal with this in Prolog is to use tabling - in this case, declaring

expression//2 as tabled. Tabling is a kind of memoisation or dynamic programming,

and in Prolog, can handle left-recursion both in ordinary predicates and in DCG

grammar rules. As of not so long ago, SWI Prolog includes a tabling library.

Samer.

[Peter Ludemann]

Naive use of DCGs can cause quadratic behavior; there's an explanation in http://xsb.sourceforge.net/manual1/manual1.pdf , section 11.2.1 "Definite Clause Grammars and Tabling"

(in general left-recursion can be handled by tabling, but the extra DCG parameters complicate this; an alternative representation of DCGs avoids the inefficiency)

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

[Paulo Moura]

Hi,

> On 30 Apr 2018, at 08:58, Peter Ludemann <peter.l...@gmail.com> wrote:
>
> Naive use of DCGs can cause quadratic behavior; there's an explanation in http://xsb.sourceforge.net/manual1/manual1.pdf , section 11.2.1 "Definite Clause Grammars and Tabling"
> (in general left-recursion can be handled by tabling, but the extra DCG parameters complicate this; an alternative representation of DCGs avoids the inefficiency)

Mode-directed tabling should, IIRC, be able to handle it. Using YAP and adding the following directive to the beginning of the file:

:- table(expression(_, _, -, -)).

we get:

?- phrase(condition(_,X), [id(N), sep(<), int(0)]).

X = (id(N)>int(0)) ? ;
false.

?- phrase(condition(_,X), [id(N), sep(>), int(0)]).

X = (id(N)>int(0)) ? ;
false.

But in the case of SWI, after adding:

:- use_module(library(tabling)).
:- table(expression(_, _, -, -)).

both queries fail. I suspect this is due to a bad interaction between DCGs and tabling library term-expansion (YAP tabling support is native).

Cheers,
Paulo

> On 29 April 2018 at 12:19, Samer Abdallah <seventy...@gmail.com> wrote:
>
> To expand on Martin’s reply, the rule for expression//2 is ‘left recursive’: if called with the
> second argument unbound, it immediately calls itself under precisely the same conditions,
> without consuming any tokens from the input. One can always rewrite a grammar to
> get rid of left recursion while recognising the same sequences, but the implicit or explict
> parse tree you get will be different and may not match the intended semantics.
>
> An elegant way to deal with this in Prolog is to use tabling - in this case, declaring
> expression//2 as tabled. Tabling is a kind of memoisation or dynamic programming,
> and in Prolog, can handle left-recursion both in ordinary predicates and in DCG
> grammar rules. As of not so long ago, SWI Prolog includes a tabling library.
>
> Samer.
>
>> On 29 Apr 2018, at 10:17, Jakub G. <kuba.gr...@gmail.com> wrote:
>>
>> expression(_, int(X)) --> [int(X)].
>> expression(_, id(N)) --> [id(N)].
>> expression(_, X+Y) --> expression(_,X), [sep(+)], expression(_,Y).
>>
>> condition(_, A>B) --> expression(_,A), [sep(>)], expression(_,B).
>> condition(_, A>B) --> expression(_,A), [sep(<)], expression(_,B).
>>
>>
>>
>> ?- phrase(condition(_,X), [id(N), sep(>), int(0)]).
>> X = (id(N)>(int(0))).
>>
>>
>> ?- phrase(condition(_,X), [id(N), sep(<), int(0)]).
>> infinite loop...
>>
>> Hi, I have a problem shown above (it's a part of grammar, that's why there is an empty argument of expression and condition. I think that it may be caused by the fact that the line with sep(<) is below sep(>) and the expression is called recursively all the time. But how can I change predicates to make it correct with these two cases?
>>
>> --
>> You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

>> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.

>> Visit this group at https://groups.google.com/group/swi-prolog.
>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.

> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.

[Jan Wielemaker]

On 04/30/2018 10:15 AM, Paulo Moura wrote:
> Hi,
>
>> On 30 Apr 2018, at 08:58, Peter Ludemann <peter.l...@gmail.com> wrote:
>>
>> Naive use of DCGs can cause quadratic behavior; there's an explanation in http://xsb.sourceforge.net/manual1/manual1.pdf , section 11.2.1 "Definite Clause Grammars and Tabling"
>> (in general left-recursion can be handled by tabling, but the extra DCG parameters complicate this; an alternative representation of DCGs avoids the inefficiency)
>
> Mode-directed tabling should, IIRC, be able to handle it. Using YAP and adding the following directive to the beginning of the file:
>
> :- table(expression(_, _, -, -)).
>
> we get:
>
> ?- phrase(condition(_,X), [id(N), sep(<), int(0)]).
> X = (id(N)>int(0)) ? ;
> false.
> ?- phrase(condition(_,X), [id(N), sep(>), int(0)]).
> X = (id(N)>int(0)) ? ;
> false.
>
> But in the case of SWI, after adding:
>
> :- use_module(library(tabling)).
> :- table(expression(_, _, -, -)).
>
> both queries fail. I suspect this is due to a bad interaction between DCGs and tabling library term-expansion (YAP tabling support is native).

Works fine if you use

:- table expression//2.

Using

:- table expression(_,_,-,-).

You use mode-directed tabling. The interpretation of the mode arguments
vary between Prolog systems. Provided my table on
http://www.swi-prolog.org/pldoc/man?section=tabling-mode-directed
is correct, neither a variable nor `-` means anything to YAP, and it
probably just does full tabling.

`-` is defined by B-Prolog and used by SWI as compatibility and says to
keep only the first answer. This would be

:- table expression(_,_,first,first).

for YAP. Now this does still succeeds for YAP. I think that using this
declaration is wrong (tabling experts?) Not sure whether the different
result may subsequently be explained by (legally) different order in
which answers may be generated.

Cheers --- Jan

[Paulo Moura]

Hi,

Indeed tabling, like constraints, could use some standardization :(

But note that on YAP the '-' mode is recognized as an alias for 'first'. See:

https://github.com/vscosta/yap-6.3/blob/master/pl/tabling.yap#L310-L321

Isn't simple/normal (what is/should we call it?) tabling subsumed (conceptually) by mode-directed tabling?

Cheers,
Paulo

[Jan Wielemaker]

On 04/30/2018 11:31 AM, Paulo Moura wrote:
> Hi,
>

> Indeed tabling, like constraints, could use some standardization :(
>
> But note that on YAP the '-' mode is recognized as an alias for 'first'. See:
>
> https://github.com/vscosta/yap-6.3/blob/master/pl/tabling.yap#L310-L321

Thanks. I'll update my table :)

> Isn't simple/normal (what is/should we call it?) tabling subsumed (conceptually) by mode-directed tabling?

Not sure what you mean by that. I'm not a tabling expert myself (despite
rewriting most of Benoit's code in C). Fabrizio did most of the
mode-directed tabling. In my understanding though, modes are used only
on output arguments and determines an aggregated value from all
solutions produced for that argument. The mode (min, max, first, last,
sum, etc.) determines the aggregation.

I _think_ this conflicts with tabling DCGs as (...., -, -). The first
list is not an output argument (not sure what happens or should happen
in this case) and the second should allow for multiple solutions as
different parses may consume more or less from the input. As I said, I'm
just a beginner when it comes to tabling ...

So, I think this should simply be tabled as expression//2 as Samer
proposed.

[Fabrizio Riguzzi]

2018-04-30 11:43 GMT+02:00 Jan Wielemaker <j...@swi-prolog.org>:

On 04/30/2018 11:31 AM, Paulo Moura wrote:

Hi,

Indeed tabling, like constraints, could use some standardization :(

But note that on YAP the '-' mode is recognized as an alias for 'first'. See:

https://github.com/vscosta/yap-6.3/blob/master/pl/tabling.yap#L310-L321

Thanks.  I'll update my table :)

Isn't simple/normal (what is/should we call it?) tabling subsumed (conceptually) by mode-directed tabling?

Not sure what you mean by that. I'm not a tabling expert myself (despite
rewriting most of Benoit's code in C). Fabrizio did most of the
mode-directed tabling. In my understanding though, modes are used only
on output arguments and determines an aggregated value from all
solutions produced for that argument. The mode (min, max, first, last,
sum, etc.) determines the aggregation.

I _think_ this conflicts with tabling DCGs as (...., -, -). The first
list is not an output argument (not sure what happens or should happen
in this case) and the second should allow for multiple solutions as
different parses may consume more or less from the input. As I said, I'm
just a beginner when it comes to tabling ...

So, I think this should simply be tabled as expression//2 as Samer
proposed.

Tabling works

https://swish.swi-prolog.org/p/dcg-tab.pl

Mode-directed doesn't

https://swish.swi-prolog.org/p/dcg-mode.pl

because the first list argument should be used to distinguish different calls to expression, not simply to record answers.

In fact you get call

expression(_2468, _2448, [id(_1988), sep(>), int(0)], _2474)

that succeeds with

expression(_2368, id(_2460), [id(_1988), sep(>), int(0)], [sep(>), int(0)])

Then you have call 

expression(_2524, _2358, [int(0)], [])

that fails because it considers it in a loop with the first call because they have the same fully tabled arguments (the first list is not considered as it should)

Fabrizio

        Cheers --- Jan

Cheers,
Paulo

Cheers,
Paulo

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.


--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

[Jan Wielemaker]

On 01/05/18 10:52, Fabrizio Riguzzi wrote:
> Tabling works
> https://swish.swi-prolog.org/p/dcg-tab.pl
> Mode-directed doesn't
> https://swish.swi-prolog.org/p/dcg-mode.pl
> because the first list argument should be used to distinguish different
> calls to expression, not simply to record answers.
> In fact you get call
> expression(_2468, _2448, [id(_1988), sep(>), int(0)], _2474)
> that succeeds with
> expression(_2368, id(_2460), [id(_1988), sep(>), int(0)], [sep(>), int(0)])
> Then you have call 
> expression(_2524, _2358, [int(0)], [])
> that fails because it considers it in a loop with the first call because
> they have the same fully tabled arguments (the first list is not
> considered as it should)

Thanks for the analysis. Remains the question whether the fact that it
works for YAP is a bug in YAP and whether we should not raise an
uninstantiated error if you call a tabled predicate with an instantiated
argument in the location of a moded argument?

Cheers --- Jan

[Fabrizio Riguzzi]

I think it is a bug in Yap and we should not raise an exception because they call with a moded argument instantiated may be used to perform a check 

        Cheers --- Jan

[Jan Wielemaker]

On 01/05/18 12:18, Fabrizio Riguzzi wrote:
>
> Thanks for the analysis.  Remains the question whether the fact that it
> works for YAP is a bug in YAP and whether we should not raise an
> uninstantiated error if you call a tabled predicate with an instantiated
> argument in the location of a moded argument?
>
> I think it is a bug in Yap and we should not raise an exception because
> they call with a moded argument instantiated may be used to perform a check 

Hmmm. Suppose we have this completely no sense making program.

:- use_module(library(tabling)).
:- table p(max).

p(1).
p(2).
p(3).

Now,

?- p(X).
X = 3.

Good! Restarting with empty tables ...

?- p(1).
true.
?- p(X).
X = 1.

Not so good :( Does this change your mind?

Cheers --- Jan

P.s. Considering that tabling is still a library, but in fact the
library is almost empty and most of the code is in C in the
kernel, wouldn't it make more sense to move tabling.pl to
the preloaded core (and provide an empty library for
compatibility?).

[Fabrizio Riguzzi]

2018-05-01 13:08 GMT+02:00 Jan Wielemaker <j...@swi-prolog.org>:

On 01/05/18 12:18, Fabrizio Riguzzi wrote:
>
>     Thanks for the analysis.  Remains the question whether the fact that it
>     works for YAP is a bug in YAP and whether we should not raise an
>     uninstantiated error if you call a tabled predicate with an instantiated
>     argument in the location of a moded argument?
>
> I think it is a bug in Yap and we should not raise an exception because
> they call with a moded argument instantiated may be used to perform a check 

Hmmm.  Suppose we have this completely no sense making program.

        :- use_module(library(tabling)).
        :- table p(max).

        p(1).
        p(2).
        p(3).

Now,

        ?- p(X).
        X = 3.

Good!  Restarting with empty tables ...

        ?- p(1).
        true.
        ?- p(X).
        X = 1.

Not so good :(  Does this change your mind?

yes it does, better to raise an exception 

        Cheers --- Jan

P.s.    Considering that tabling is still a library, but in fact the
        library is almost empty and most of the code is in C in the
        kernel, wouldn't it make more sense to move tabling.pl to
        the preloaded core (and provide an empty library for
        compatibility?).

I think so 

[Jan Wielemaker]

On 01/05/18 13:24, Fabrizio Riguzzi wrote:
>
> Good!  Restarting with empty tables ...
>
>         ?- p(1).
>         true.
>         ?- p(X).
>         X = 1.
>
> Not so good :(  Does this change your mind?
>
> yes it does, better to raise an exception

Pushed a fix for this. If that were in place before a lot of this
discussion could have been avoided :)

>         Cheers --- Jan
>
> P.s.    Considering that tabling is still a library, but in fact the
>         library is almost empty and most of the code is in C in the
>         kernel, wouldn't it make more sense to move tabling.pl

> <http://tabling.pl> to

>         the preloaded core (and provide an empty library for
>         compatibility?).
>
> I think so

Pushed. Was a bit more work than just moving a file :(

Thanks for the input --- Jan