Runtime impact of using DCG semicontext notation with SWI

126 views
Skip to first unread message

Stefan Kral

unread,
Feb 18, 2016, 1:43:55 PM2/18/16
to SWI-Prolog
Hi all,

First, let me confess: yes, in the distant past I abused DCGs as a state-monad-substitute...

Let's move on: In his DCG primer (http://www.metalevel.at/prolog/dcg.html) Markus wrote about semicontext notation, and how it could be used for passing around state. However, as he also wrote "Since a DCG must always describe a list, we wrap the state into a list and thus describe a list containing a single element.", I was a bit apprehensive... how much costs does it incur? Let's find out!

:- set_prolog_flag(toplevel_print_anon, false).

call_time
(G,T) :- statistics(runtime,[T0|_]), G, statistics(runtime,[T1|_]), T is T1 - T0.

gen_sample_tree_
(nil, N) :- N =< 0.
gen_sample_tree_
(node(_,X,X), N) :- N > 0, N0 is N-1, gen_sample_tree_(X, N0).

num_leavesA
(Tree, N) :- num_leavesA_(Tree, 0, N).

num_leavesA_
(nil, N0, N) :- N is N0 + 1.
num_leavesA_
(node(_,Left,Right), N0, N) :- num_leavesA_(Left, N0, N1), num_leavesA_(Right, N1, N).

num_leavesB
(Tree, N) :- phrase(num_leavesB_(Tree), [0], [N]).

num_leavesB_
(nil), [N] --> [N0], { N is N0 + 1 }.
num_leavesB_
(node(_,Left,Right)) --> num_leavesB_(Left), num_leavesB_(Right).

Let's roll!

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.17)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI
-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- compile(semi_dcg).
true.

?- length(_, Depth),
   
Depth > 20,
   gen_sample_tree_
(_Tree, Depth),
   call_time
(num_leavesA(_Tree,_N1), T1),
   call_time
(num_leavesB(_Tree,_N2), T2),
   
( _N1 =:= _N2 -> true ; throw(up) ).
Depth = 21, T1 =  405, T2 =  279 ;
Depth = 22, T1 =  809, T2 =  563 ;
Depth = 23, T1 = 1576, T2 = 1095 ;
Depth = 24, T1 = 3143, T2 = 2190 ;
Depth = 25, T1 = 6301, T2 = 4378 ...

Not bad! Not at all! What do you think about that?

Regards, Stefan.

Jan Burse

unread,
Feb 19, 2016, 9:22:53 AM2/19/16
to SWI-Prolog
Can reproduce the same figures.

Maybe some argument copying problem of the interpreter deep down
in the way it calls predicates, so that unintentionally the DCG solution is
more efficient, since it somehow shares the [_] as if it would be a value holder.

Jan Burse

unread,
Feb 19, 2016, 9:27:24 AM2/19/16
to SWI-Prolog
Probably happening in the second clause of num_leavesB_/3
respectively
num_leavesA_/3. Since a binary
tree has 2^n leaves and 2^n-1 nodes. So the pressure
on the second clause is equally high as on the first clause.

Markus Triska

unread,
Feb 19, 2016, 4:52:34 PM2/19/16
to SWI-Prolog
Hi Stefan, all,

nice!

So far, the section about semicontext notation has probably triggered more emotional responses than any other section of this page. Here are some examples of the feedback I have received so far from different participants:

1) "Wrapping the state in a list is an overhead I am very willing to accept (for the sake of portability of the DCG)."
2) "You should use DCG notation only for parsing; using it to pass around a state is horrible!"
3) "Passing around a state in this way is extremely convenient and makes my code very readable!"
4) "Wrapping the state in a list is an overhead I cannot accept."

I kid you not: Feedback (2) was sent to me almost literally, from a top-level Prolog programmer I very much respect. It happened several years ago, and to me this event has really hammered home the point that even extremely smart and experienced Prolog programmers need time to adopt such ideas, or may never adopt them at all. Hence, it may be even harder for average users. That's OK: Prolog can be quite useful even if you never use semicontext notation. It's just much more useful with it and allows you to solve problems that would otherwise be too complex to handle.

To the above list, we can now add your very interesting and surprising observation.

Thank you for actually measuring this!

All the best,
Markus

P.S.: Almost the same responses I got 5 years ago in the context of DCGs are now sent to me in the context of CLP(FD). That's also OK! I wonder what messages I will get in 5 years from now. Maybe a great outcry about CLP(B), followed by its adoption in user programs ;-)

Stefan Kral

unread,
Feb 19, 2016, 5:02:51 PM2/19/16
to SWI-Prolog
On Friday, February 19, 2016 at 3:22:53 PM UTC+1, Jan Burse wrote:
> Can reproduce the same figures.
Good.

> Maybe some argument copying problem of the interpreter deep down
> in the way it calls predicates, so that unintentionally the DCG solution is
> more efficient, since it somehow shares the [_] as if it would be a value holder.

Interesting! Sounds to me like your hypothesis could be tested fairly easily (using the right `statistics/2` keys).

Also, I ran the same test with SICStus and observed (1) it was a lot faster but (2) the semicontext DCG code was moderately slower than its explicit counterpart. But that could get faster with further JIT improvements... why not?

(I have not run that test with the JIT turned off, so I can't tell if the JIT is the main reason why SICStus is faster.)

Here's another possible use of that semicontext notation: handling state changes that update some part(s) of the state a lot more often than others---one part is hot (say for counting leaves), the other one is not hot (say for record bookkeeping of various statistics). What do you think about that?

Abramo Bagnara

unread,
Feb 19, 2016, 5:26:15 PM2/19/16
to swi-p...@googlegroups.com
Il 18/02/2016 19:43, Stefan Kral ha scritto:
> Hi all,
>
> First, let me confess: yes, in the distant past I abused DCGs as a
> state-monad-substitute...
>
> Let's move on: In his DCG primer
> (http://www.metalevel.at/prolog/dcg.html) Markus wrote about semicontext
> notation, and how it could be used for passing around state. However, as
> he also wrote "Since a DCG must always describe a list, we wrap the
> state into a list and thus describe a list containing a single
> element.", I was a bit apprehensive... how much costs does it incur?
> Let's find out!
>
> |
> :-set_prolog_flag(toplevel_print_anon,false).
>
> call_time(G,T):-statistics(runtime,[T0|_]),G,statistics(runtime,[T1|_]),T isT1
> -T0.
>
> gen_sample_tree_(nil,N):-N =<0.
> gen_sample_tree_(node(_,X,X),N):-N >0,N0 isN-1,gen_sample_tree_(X,N0).
>
> num_leavesA(Tree,N):-num_leavesA_(Tree,0,N).
>
> num_leavesA_(nil,N0,N):-N isN0 +1.
> num_leavesA_(node(_,Left,Right),N0,N):-num_leavesA_(Left,N0,N1),num_leavesA_(Right,N1,N).
>
> num_leavesB(Tree,N):-phrase(num_leavesB_(Tree),[0],[N]).
>
> num_leavesB_(nil),[N]-->[N0],{N isN0 +1}.
> num_leavesB_(node(_,Left,Right))-->num_leavesB_(Left),num_leavesB_(Right).
> |
>
> Let's roll!
>
> |
> $ swipl
> Welcometo SWI-Prolog(Multi-threaded,64bits,Version7.3.17)
> Copyright(c)1990-2015Universityof Amsterdam,VU Amsterdam
> SWI-Prologcomes withABSOLUTELY NO WARRANTY.Thisisfree software,
> andyou are welcome to redistribute it under certain conditions.
> Pleasevisit http://www.swi-prolog.org for details.
>
> Forhelp,use?-help(Topic).or?-apropos(Word).
>
> ?-compile(semi_dcg).
> true.
>
> ?-length(_,Depth),
> Depth>20,
> gen_sample_tree_(_Tree,Depth),
> call_time(num_leavesA(_Tree,_N1),T1),
> call_time(num_leavesB(_Tree,_N2),T2),
> (_N1 =:=_N2 ->true;throw(up)).
> Depth=21,T1 = 405,T2 = 279;
> Depth=22,T1 = 809,T2 = 563;
> Depth=23,T1 =1576,T2 =1095;
> Depth=24,T1 =3143,T2 =2190;
> Depth=25,T1 =6301,T2 =4378...
> |
>
> Not bad! Not at all! What do you think about that?

If you check compiled code with vm_list you will see that the fact that
B version is faster is only due to an optimizer vagary for arithmetic in
the two cases.

Running your example with swipl -O you will get very different results.

--
Abramo Bagnara

Stefan Kral

unread,
Feb 19, 2016, 5:31:02 PM2/19/16
to SWI-Prolog
Hi Markus,

thank you for sharing the responses / reactions you got!

What's next? Two things come to mind:

- the SICStus JIT could get even better performance once the right optimization(s) are in place; matsC or perM could probably hack that over the weekend:)
- updating different parts of the threaded state with different frequencies (some parts being hot, other not so) should be do-able with that notation quite easily and efficiently. Partial deforestation, kind of.

DCGs are exciting.

Best regards,
Stefan.

Stefan Kral

unread,
Feb 19, 2016, 6:38:41 PM2/19/16
to SWI-Prolog
Hi Abramo,

thank you for your answer! I wouldn't have expected that SWI has the brakes on by default:)

Of course, I immediately had to re-run the tests with `swipl -O`... Here's what I got:

?- length(_, Depth),
   
Depth > 20,
   gen_sample_tree_
(_Tree, Depth),
   call_time
(num_leavesA(_Tree,_N1), T1),
   call_time
(num_leavesB(_Tree,_N2), T2),
   
( _N1 =:= _N2 -> true ; throw(up) ).
Depth = 21, T1 =  283, T2 =  278 ;
Depth = 22, T1 =  562, T2 =  549 ;
Depth = 23, T1 = 1109, T2 = 1096 ;
Depth = 24, T1 = 2201, T2 = 2195 ...

Apparently, `swipl -O` accelerated "variant A" so that both variants run at the equal speed.

To me, this more modest result is still astounding: the semi-context DCG variant is as fast as its more explicit counterpart!

TIL: With SICStus Prolog 4.3.2, it depends on whether the JIT is enabled or not:

?- <the same query as above>.

% JIT=disabled                           %% JIT=on
Depth = 21, T1 =   80, T2 =   90 ? ;     %% Depth = 21, T1 =  40, T2 =   40 ? ;
Depth = 22, T1 =  180, T2 =  190 ? ;     %% Depth = 22, T1 =  70, T2 =   80 ? ;
Depth = 23, T1 =  350, T2 =  340 ? ;     %% Depth = 23, T1 = 120, T2 =  160 ? ;
Depth = 24, T1 =  660, T2 =  670 ? ;     %% Depth = 24, T1 = 250, T2 =  300 ? ;
Depth = 25, T1 = 1320, T2 = 1490 ? ;     %% Depth = 25, T1 = 480, T2 =  650 ? ;
Depth = 26, T1 = 2610, T2 = 2590 ? ...   %% Depth = 26, T1 = 960, T2 = 1280 ? ...

Curiouser and curiouser:)

Best Regards,
Stefan.

Abramo Bagnara

unread,
Feb 20, 2016, 3:48:31 AM2/20/16
to swi-p...@googlegroups.com, Jan Wielemaker
Il 20/02/2016 00:38, Stefan Kral ha scritto:
> Hi Abramo,
>
> thank you for your answer! I wouldn't have expected that SWI has the
> brakes on by default:)
>
> Of course, I immediately had to re-run the tests with `swipl -O`...
> Here's what I got:
>
> |
> ?-length(_,Depth),
> Depth>20,
> gen_sample_tree_(_Tree,Depth),
> call_time(num_leavesA(_Tree,_N1),T1),
> call_time(num_leavesB(_Tree,_N2),T2),
> (_N1 =:=_N2 ->true;throw(up)).
> Depth=21,T1 = 283,T2 = 278;
> Depth=22,T1 = 562,T2 = 549;
> Depth=23,T1 =1109,T2 =1096;
> Depth=24,T1 =2201,T2 =2195...
> |
>
> Apparently, `swipl -O` accelerated "variant A" so that both variants run
> at the equal speed.

As I firmly believe they *can't* run at the equal speed, I think you've
found an optimizer "bug" (well not a bug, let say that it misses an
opportunity to generate faster code).

I've CC'ed Jan as I think he will be interested.

Please try the following tiny variant:

:- set_prolog_flag(toplevel_print_anon, false).

call_time(G,T) :- statistics(runtime,[T0|_]), G,
statistics(runtime,[T1|_]), T is T1 - T0.

gen_sample_tree_(nil, N) :- N =< 0.
gen_sample_tree_(node(_,X,X), N) :- N > 0, N0 is N-1,
gen_sample_tree_(X, N0).

num_leavesA(Tree, N) :- num_leavesA_(Tree, 0, N).

%num_leavesA_(nil, N0, N) :- N is N0 + 1.
% The use of intermediate variable X make a remarkable difference.
num_leavesA_(nil, N0, N) :- X is N0 + 1, N = X.
num_leavesA_(node(_,Left,Right), N0, N) :- num_leavesA_(Left, N0, N1),
num_leavesA_(Right, N1, N).

num_leavesB(Tree, N) :- phrase(num_leavesB_(Tree), [0], [N]).

num_leavesB_(nil), [N] --> [N0], { N is N0 + 1 }.
num_leavesB_(node(_,Left,Right)) --> num_leavesB_(Left),
num_leavesB_(Right).

You can see what causes the difference from vm_list output:

Original source:

0 h_atom(nil)
2 i_enter
3 b_var2
4 a_enter
5 a_var1
6 a_integer(1)
8 a_add
9 a_is
10 i_exit


Modified source:

0 h_atom(nil)
2 i_enter
3 a_add_fc(3,1,1)
7 b_unify_vv(2,3)
10 i_exit

The point is that when the result of an arithmetic expression is not
dispatched to a fresh variable, the generated code is suboptimal.

--
Abramo Bagnara

Samer Abdallah

unread,
Feb 20, 2016, 4:39:10 AM2/20/16
to Markus Triska, SWI-Prolog
Hi Markus, all

I would say I’m very much in the (3) camp.
As I think I may have said before at some point, DCG notation
is way too convenient and expressive to be restricted to parsing.
And I don’t see why I should wrap my state in a singleton list.
Once you start playing that game, then you are already going
against the spirit, if not the letter, of the law (the one that says
DCGs are for parsing lists). Who are you kidding? (I don’t mean
you personally - I mean ‘who is one kidding?’, but that sounds
ridiculous.) Why can’t we just accept that DCG notation is a great way
to handle any kind of state? I also find extremely convenient the
fact that any binary predicate or callable with the right argument
order (e.g. succ/2, select(X)/2, etc) can be used in a DCG extremely
convenient. This means that whenever I notice the characteristic
argument threading behaviour in a predicate definition, I can
immediately switch to DCG notation with very little fuss.

It’s not really about computational overhead - if that were the case,
then any proof that the overhead is minimal would be enough
to overturn my argument. It’s more about conceptual overhead -
why should I clutter up my code with all these singleton lists when
they add nothing and only serve to obscure the underlying simplicity
of the computational process?

When stricter argument checking was introduced to phrase/3,
I asked Jan to include a non strict version for more general use, which
he named call_dcg/3, and which I am very happy with. I would also
be happy if, in the interests of abstraction of the state passing system
(i.e. not just assuming it’s the last two arguments), some sort of declaration
was needed to be able to use arbitrary binary predicates as DCG goals, e.g.:
:- dcg_callable succ, select(_).
that would allow the compiler to generate the right code when such goals
are called inside a DCG clause.

cheers,
Samer
> --
> 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.

signature.asc

Jan Burse

unread,
Feb 20, 2016, 5:37:07 AM2/20/16
to SWI-Prolog
Thanks for pointing out that with vm_list/1 we can inspect the internediate
code. Forget about that. Of course one can also inspect what the DCG
transformer does itself. Just use the ordinary listing/1:

?- listing(num_leavesA_/3).

num_leavesA_(nil, B, A) :-

A is B+1.

num_leavesA_(node(_, A, C), B, E) :-

num_leavesA_(A, B, D),

num_leavesA_(C, D, E).


?- listing(num_leavesB_/3).

num_leavesB_(nil, A, D) :-

A=[B|C],

E is B+1,

F=C,

D=[E|F].

num_leavesB_(node(_, A, C), B, E) :-

num_leavesB_(A, B, D),

num_leavesB_(C, D, E).


Strangely the DCG transformer of SWI-Prolog didn't move the various
unboxing and boxing of [_] into the head of the first clause. Nevertheless
without the -O option, this DCG code is faster.

My hypothesis was that a side effect of structure sharing is involved.
But now looking at vm_list/1, it seems that possibly it is not an indirect
effect of the second clause, but really the first clause:

?- vm_list(num_leavesA_/3).

----------------------------------------

clause 1 (<clause>(0x7fc21e3849e0)):

----------------------------------------

0 h_atom(nil)

2 i_enter

3 b_var2

4 b_functor((+)/2)

6 b_argvar(1)

8 b_smallint(1)

10 b_pop

11 i_depart((is)/2)

13 i_exit

?- vm_list(num_leavesB_/3).

----------------------------------------

clause 1 (<clause>(0x7fc21e38bea0)):

----------------------------------------

0 h_atom(nil)

2 i_enter

3 b_unify_var(1)

5 h_list_ff(3,4)

8 b_unify_exit

9 a_add_fc(5,3,1)

13 b_unify_fv(6,4)

16 b_unify_var(2)

18 h_list

19 h_var(5)

21 h_var(6)

23 h_pop

24 b_unify_exit

25 i_exit


It seems that the is/2 tail jump is contra productive. Is this the riddles
solution for the performance penalty?

Markus Triska

unread,
Feb 20, 2016, 5:57:53 AM2/20/16
to SWI-Prolog, tri...@logic.at
Hi Samer,

I see your point, and I am glad that use cases that you need are now reliably accommodated by call_dcg/3. I also agree that a more general state passing system is very desirable, and I hope we will find the right building blocks for it.

Regarding expansion methods for DCGs, there is one extremely important advantage in conceptually strictly separating DCGs from regular Prolog code, and using only semicontext notation to explicitly address the arguments instead of relying on a particular expansion method. I think this advantage has not yet been fully recognized, so here is a short explanation why this is so desirable:

Suppose we see Prolog code that passes around a state argument, like this:

r(S, S).
r(S0, S) :-
        x(S0, S1),
        y(S1, S2),
        r(S2, S).

x(N, s(N)).

y(N, d(N)).


Sample query:

?- r(0, C).
C = 0 ;
C = d(s(0)) ;
C = d(s(d(s(0)))) .


As you outline, every time we see Prolog code that passes around arguments as in the code above (S0 -> S1 -> ... S), we are considering using a DCG for convenience. The widely known and comparatively straight-forward way in which the DCG expansion happens makes it tempting to rely on it and then access the expanded version directly instead of using the DCG interface predicate phrase/3 to do it. For example, we may be tempted to eschew a clean separation between DCGs and regular Prolog clauses, and uncleanly intermingle them as in the following:

r --> [].
r -->
        x,
        y,
        r.

x(N, s(N)).

y(N, d(N)).

Here, regular Prolog code and DCGs are conceptually uncleanly mixed, and we rely on the implicit but not guaranteed expansion to right the wrong. It does:

?- r(0, C).
C = 0 ;
C = d(s(0)) ;
C = d(s(d(s(0)))) .


However, suppose we restrain ourselves sufficiently to always use semicontext notation when accessing the implicit arguments, i.e., suppose we go just one step further in our translation and rewrite the two uncleanly accessed facts above into DCG rules too:

x, [s(N)] --> [N].

y, [d(N)] --> [N].


and use the dedicated DCG interface predicate phrase/3 to access such DCGs:

?- phrase(r, [0], [C]).
C = 0 ;
C = d(s(0)) ;
C = d(s(d(s(0)))) .

then - and that is the point! - the Prolog system is free to apply the following important optimization to all DCGs:

Instead of expanding the rules as above, the system is now completely free to expand DCGs in a totally different manner! For example, it may actually reverse the arguments that are passed around in the expansion. In several VMs, this would make accessing the arguments more efficient, because fewer arguments need to be stored (again) or shuffled around on the stacks.

In my view, a clean separation between plain Prolog clauses and DCGs is well justified for this reason alone already, and I hope that one day we see Prolog systems that are much more efficient when handling DCGs due to this benefit of being able to freely choose an expansion that suits their VM layout best, without breaking any user code.

Since the pattern above is so common, I suggest the nonterminals state//1 and state//2 in the document, which are meant for inclusion in a DCG library. Using these nonterminals, you can simply write the above DCG rules as:

x --> state(N, s(N)).

y --> state(N, d(N)).

Notice that no list wrappers at all appear now in the DCG rules! In total, we have moved from:

r(S, S).
r(S0, S) :-
        x(S0, S1),
        y(S1, S2),
        r(S2, S).

x(N, s(N)).

y(N, d(N)).


to:

r --> [].
r -->
        x,
        y,
        r.

x --> state(N, s(N)).

y --> state(N, d(N)).

while preserving portability and paving the way for a more efficient DCG expansions.

When working with DCGs and deciding on the proper interface predicates, please consider this opportunity for performance improvements that appears on the horizon every time you choose a clean separation.

All the best!
Markus

Jan Burse

unread,
Feb 20, 2016, 6:57:44 AM2/20/16
to SWI-Prolog, tri...@logic.at

Hi,

You could also go for state//1 only, if the DCG translator
supports arbitrary phrases in the DCG head push back:

r --> [].
r -->
        x,
        y,
        r.

x, state(s(N)) --> state(N).

y, state(s(N)) --> state(N).

If I recall correctly, arbitrary phrases in the DCG head push
back are indeed allowed according to the current DCG draft
standard. Can bring up reference if desired.

Here is a result in SWI-Prolog:

      Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.16)

      Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

      ?- [user].
      state(I, I, _).
      x, state(s(N)) --> state(N).

      ?- listing(x//0).
      x(A, C) :-
            state(B, A, D),
            state(s(B), C, D).

      ?- x(0, R).
      R = s(0).

Jan Burse

unread,
Feb 20, 2016, 7:05:22 AM2/20/16
to SWI-Prolog, tri...@logic.at
You could also define:

state(I, I, foo).

But beware, don't do:

..   --> ... p, q, state(S), r, s ...

You can't use state//1 to read the state via state(S), same
limitation with [S]. It would always have to be combined with
a push back.

On the other hand if you have the following in mind:

get(I,I,I).
set(O,I,O).

You departing from the [S] logic. You could do:

..   --> ... p, q, get(S), r, s ...

Or you could do:

..   --> ... p, q, get(S), r, s, set(S2), ...

Jan Burse

unread,
Feb 20, 2016, 8:45:43 AM2/20/16
to SWI-Prolog
One of the current drafts is here:

ISO/IEC DTR 13211-3:2006
De finite clause grammar rules
Jonathan Hodgson, November 10, 2015
https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dcgs/dcgsdraft-2015-11-10.pdf

The draft is very defensive about DCG head push back.
They call it semi-context. And primarily think of it as
lists. But leave it open to the implementation to support
more. See for example:

7.13.2 Format of grammar rules
NonTerminal, Semicontext --> GRBody.
7.13.3 Semicontext
A semicontext is a terminal-sequence

But we also find a note
"The eff ect of a Semicontext which is not a terminal-sequence
shall be implementation dependent."

Jan Burse

unread,
Feb 20, 2016, 5:44:53 PM2/20/16
to SWI-Prolog

Markus Triska wrote in Reference to Samer Abdallah:


> I see your point, and I am glad that use cases that you need are now
> creliably accommodated by call_dcg/3. I also agree that a more general
> state passing system is very desirable, and I hope we will find the right
> building blocks for it.

Just a crazy thought experiment. What if is/2 would be also
allowed in DCG translation, as if:
- The is/2 is first unraveled.
- Then the standard DCG translation is applied.

So for example in case of:

     -->  ..., p, q, X is get+1, r, s, ...

The unraveling of is/2 would give (not 100% correct):
         get(Y),
         +(Y,1,X).

And DCG-ing it would give:
         get(Y,I,H),
         +(Y,1,X,H,O)

Advantage here, if get//1 is the state accessor, we could
access the state in arithmetic expressions, disadvantage
what to do with +/2 etc.. ? Do we need extra DCG definition or
shouldn't we DCG translate the +/2.

Why coming up with such an idea. Well the SSL / NNTP
show case shows that state bearing DCGs can be used as
object like contexts. And was just glossing over Prolog++
which in contrast to Logtalk, does also compile arithmetic
expressions, and resolve context references in them.

So fsr the DCG standard is very defensive. The minimum is
basically translation of (,)/2, (;)/2, ... the reason probably being
that these control constructs are cut transparent, so you cannot
define them as non-terminals, the cut wouldn't work anymore.
And then there is the {}/1 escape to ordinary Prolog.

So was also thinking about allowing {}/1 in is/2. So we could
do the following:

       X is get+{2*3}

So the */2 would not be DCG contextualized. But still +/2 would
need some threatment. And the following escape, would also not work:

       X is {get+2*3}

Then get cannot anymore acess the context. So we are forced
to use the clumsy:

       get(Y),
       { X is Y+2*3 }

Whereby Prolog++ would probably allow something along (Have
to check, just a guess from the documentation):

       X is self+2*3.

Bye

Jan Wielemaker

unread,
Feb 21, 2016, 5:43:34 AM2/21/16
to Jan Burse, SWI-Prolog
On 02/20/16 11:37, Jan Burse wrote:
> It seems that the is/2 tail jump is contra productive. Is this the riddles
> solution for the performance penalty?

Seems you did not compile the non-DCG version with -O. If you do, I get:

0 h_atom(nil)
2 i_enter
3 b_var2
4 a_enter
5 a_var1
6 a_integer(1)
8 a_add
9 a_is
10 i_exit

The DCG version delays the unification, which first in <first-var> is
<var>+1,
for which it has the much faster add_vc instruction which opportunistically
assumes <var> is bound to a small integer, adds the constant and just writes
the result in the output. Only to return the a slow path if <var> is not a
small int.

In general, [State] must be slower as it involves matching and building a
term and creates garbage. What you see is a weird corner case that
indicates
that the system should probably make different assumptions for A is B+1 if
nothing is known about A.

Cheers --- Jan
Reply all
Reply to author
Forward
0 new messages