Some [operational] notes on DCG semicontext notation (that were not obvious to me but probably should have been)

[jjtolton]

For the longest time I was not able to comprehend @triska's notes on semicontext notation:

num_leaves(Tree, N) :-
        phrase(num_leaves_(Tree), [0], [N]).

num_leaves_(nil), [N] --> [N0], { N #= N0 + 1 }.
num_leaves_(node(_,Left,Right)) -->
        num_leaves_(Left),
        num_leaves_(Right).

?- num_leaves(node(a,node(b,nil,nil),
                     node(c,nil,
                            node(d,nil,nil))), N).
N = 5.

The amount of witchcraft here seemed insurmountable. How on earth could one definition of num_leaves//1 have a semicontext... context while the other definition did not!! Where did the context go?? I've had more than one melt down about it. However, @hurufu's really interesting implementation of a stack machine using DCGs with semicontext notation renewed my interest, so I tried once more.

For some reason a few things finally started to click:

Operational Generalization

But how do we generalize this concept? How would we use it with more than one variable in the context?

Let's consider the following example:

If we unpack the call chain:

?- phrase(count([1,2,3]), [0], Result).                   % +1 (from second argument)
% >>> count([1|[2,3]]) --> state_processor, count([2,3]). % +1 (0 consumed)
% >>>> state_processor, [N] --> [N0], { N #= N0+1 }.      % +1 (1 consumed, 1 replaced)
% >>>> count([2|3]]) --> state_processor, count([2|3]).   % +1 (0 consumed)
% >>>>> state_processor, [N] --> [N0], { N #= N0+1 }.     % +1 (1 consumed, 1 replaced)
% >>>>> count([3]) --> state_processor, count([3]).       % +1 (0 consumed)
% >>>>>> state_processor, [N] --> [N0], { N #= N0+1 }.    % +1 (1 consumed, 1 replaced)
% >>>>>> count([]) --> state_processor.                   % +1 (0 consumed)
% >>>>>>> state_processor, [N] --> [N0], { N #= N0+1 }.   % +1 (1 consumed, 1 replaced)

We observe that semicontext is continually pushed back on the stack and maintained in equilibrium.

If we maintain this principle, we can attempt some more audacious semicontext maneuvers. But it's not as straightforward as you might think. Let's say we want a second semicontext var that maintains a list of terms encountered:

Oh no, we failed! But why? Well if we use the previous analysis, the reason becomes obvious quickly:

?- phrase(count([1,2,3]), [0, []], Xs).                                % +2 (from second argument)
% >>> count([X|Xs]) --> [X], state_processor, count(Xs).               % +1 (1 consumed)
% >>>> state_processor, [N, [X|Xs]] --> [X], [N0, Xs0], { N #= N0+1 }. % -2 (3 consumed, but only +1 available!)

Apparently the --> [X] was meant to "push" something onto the stack, but it had the opposite effect! The most obvious way to solve this is with a slight adjustment:

Here, we injected the desired X as an argument to state_processor//1. But the outcome is strange, what happend?

?- phrase(count([1,2,3]), [0, []], Xs). % +2
% >>> count([1|[2,3]]) --> state_processor(1), count([2,3]).              % +2
% >>>> state_processor(1), [1, [1]] --> [0,Xs], { 1 #= 0+1 }.             % +2 (+2,-2)
% >>>> count([2|3]]) --> state_processor(2), count([2|3]).                % +2
% >>>>> state_processor(2), [2, [2|[1]]] --> [1,[1]], { 2 #= 1+1 }.       % +2 (+2,-2)
% >>>>> count([3]) --> state_processor(3), count([]).                     % +2
% >>>>>> state_processor(3), [3, [3|[2,1]]] --> [2,[2,1]], { 3 #= 2+1 }.  % +2 (+2,-2)
% >>>>>> count([]) --> state_processor.                                   % +2
% >>>>>>> state_processor, [N,Xs] --> [].                                 % +4 (2 pushed, 0 consumed!)

The well intentioned rule of state_processor, [N,Xs] --> []. did not have the intended effect of "preserving the context"!

And now finally we have the correct formulation:

Except it is a bit disappointing that the elements come out backwards. However, our "mistake" in the previous round that revealed to us that we can use the terminal state_processor//1 rule to do a "final pass" over the context, opening up some interesting options for more ambitious transformations:

:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(queues)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).

state_processor, [N,Xs] --> [N,Q0], { list_queue(Xs,Q0) }.
state_processor(X), [N, Ys] --> [N0, Xs],
        { N #= N0+1,
          queue_last(X,Xs,Ys)
        }.

count([]) --> state_processor.
count([X|Xs]) --> state_processor(X), count(Xs).

?- N^Xs+\(queue(Q), phrase(count([1,2,3]), [0, Q], [N,Xs])).
%@    N = 3, Xs = [1,2,3].

However, there are yet more footguns to be found.

You might be tempted to think, given your new understanding, that the following technique would work:

     a, [N,N] --> [N], double.

     double, [N] --> [N0,N0], { N #= N0+N0 }.

     ?- phrase(a, [2], Result).
     %@    false.

Why doesn't double//0 have access to the two Ns placed on the stack by a?? This is because the semicontext of the head of the rule is not available to the goals of the body!

We can observe this with the following tool:

     dtrace(D0,D0) :- write(dtrace:D0), nl.
     dtrace(Label,D0,D0) :- write(Label:D0), nl.

     as --> [].
     as --> dtrace, [a], as.

     ?- phrase(as, [a,a,a], As).
     %@    As = "aaa"
     %@ ;  dtrace:[a,a,a]
     %@ As = "aa"
     %@ ;  dtrace:[a,a]
     %@ As = "a"
     %@ ;  dtrace:[a]
     %@ As = []
     %@ ;  dtrace:[]
     %@ false.

If we use that in the scenario described:

We see clearly what happened.

This makes it clear that a goal in the body of a rule must have context provided by the return value of a previous rule.

To illustrate this point:

:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).

dtrace(D0,D0) :- write(dtrace:D0), nl.
dtrace(Label,D0,D0) :- write(Label:D0), nl.

push(X), [X] --> []. % +1 (adds 1, consumes 0)

a --> [N], push(N), push(N), double.

double, [N] --> [N0,N0],  { N #= N0+N0 }.

?- phrase(a, [2], Result).
%@    Result = [4].

And if we "instrument" this with dtrace/2:

:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).

dtrace(D0,D0) :- write(dtrace:D0), nl.
dtrace(Label,D0,D0) :- write(Label:D0), nl.

push(X), [X] --> []. % +1 (adds 1, consumes 0)

a --> dtrace(0), [N], dtrace(1), push(N), dtrace(2), push(N), dtrace(3), double, dtrace(end).

double, [N] --> dtrace(a), [N0,N0], dtrace(b), { N #= N0+N0 }, dtrace(c).

?- phrase(a, [2], Result).
%@ 0:[2]        +1 (from 2nd arg)
%@ 1:[]          0  (1 consumed)
%@ 2:[2]        +1 (1 pushed)
%@ 3:[2,2]      +2 (1 pushed)
%@ a:[2,2]      +2 
%@ b:[]          0 (2 consumed in double//0)
%@ c:[]          0 ( bracketed calculation consumes 0)
%@ end:[4]      +1 (1 pushed from the semicontext of double//0)
%@    Result = [4].

(Note: push//1 is very procedural language and not generally idiomatic for declaratively written semantics. This was done purely for an operational demonstration)

At last, we have some general (operational) mental tools for working with semicontext! I'm sure a lot of this was obvious to many of you, but I had to simmer on this for nearly a year before it began to solidify, so hopefully someone finds it helpful!

I also realize that the operational description is very different than the actual list difference semantics happening, but those are still not fully understood to me yet.

There are still many techniques to learn.

[jjtolton]

On a tangential note of very little interest, I find it striking that this usage of DCGs is a strict superset of the semantic functionality of Clojure transducers:

(transduce
 (map identity)                         ;; transducing concept, effectively pass-thru here
 (fn ([[n xs]]   [n       (reverse xs)]) ;; monadic arrity, terminal
   ([[n xs] x] [(inc n) (cons x xs)]))  ;; diadic arrity, step fn
 [0 '()]                                ;; initial value (like 2nd arg of phrase/3)
 [1 2 3])
;;=> [3 (1 2 3)]

In case anyone finds this remotely interesting, I've highlighted the anatomical similarities:

However, as I said, DCGs are a strict superset here because Clojure transducers are not only unimodal, but they can only process sequences (not trees), and they certainly can't be used for parsing. Furthermore, transducers as you've seen are not easily composable -- they are all contained in one block of code. DCGs, ironically, do a better job of respecting the open-closed principle!

[triska]

Interesting write-up, thank you a lot!

One small suggestion I have for everyone from now on: Please add the following to your ~/.emacs:

(setq ediprolog-prefix "")

Since Scryer now supports embedded quads in programs, we can state toplevel interactions verbatim in programs:

?- member(X, "abc").
   X = a
;  X = b
;  X = c.

member(E, [L|Ls]) :-
        member_(Ls, L, E).

member_(_, E, E).
member_([L|Ls], _, E) :-
        member_(Ls, L, E).

[jjtolton]

I ended up writing these because with (setq ediprolog-prefix ""), ediprolog-remove-interactions wipes my whole buffer!

(defun ediprolog-set-prefix-quad ()
  (interactive)
  (setq ediprolog-prefix ""))

(defun ediprolog-set-prefix-regular ()
  (interactive)
  (setq ediprolog-prefix "%@"))

[UWN]

?- num_leaves(T,1).
   T = nil
;  loops.

To fix this, you need to "break up" the otherwise compact recursive rule. So semicontext notation is not that helpful here.

[jjtolton]

?- num_leaves(T,1).
   T = nil
;  loops.

To fix this, you need to "break up" the otherwise compact recursive rule. So semicontext notation is not that helpful here.

Stealing from @triska's prior art, is this more along what you had in mind?

:- use_module(library(dcgs)).
:- use_module(library(lists)).


num_leaves(Tree, N) :-
        length(Ns, N),
        phrase(nodes(Tree), Ns).

nodes(nil) --> [].
nodes(node(Node,L,R)) --> [Node], nodes(L), nodes(R).

?- num_leaves(Tree, N).
   Tree = nil, N = 0
;  Tree = node(_A,nil,nil), N = 1
;  Tree = node(_A,nil,node(_B,nil,nil)), N = 2
;  Tree = node(_A,node(_B,nil,nil),nil), N = 2
;  Tree = node(_A,nil,node(_B,nil,node(_C,nil,nil))), N = 3
;  Tree = node(_A,nil,node(_B,node(_C,nil,nil),nil)), N = 3
;  ... .

?- num_leaves(Tree, 1).
   Tree = node(_A,nil,nil)
;  false.

(side note: at some point I do hope to be capable of original thought, but that day seems quite far off, so I will be content to steal ideas until then 😁 )

[UWN]

is this more along what you had in mind?

Consider the failure slice

num_leaves(Tree, N) :-
        length(Ns, N), false,
        phrase(nodes(Tree), Ns).

?- num_leaves(nil, N), false.
   loops, unexpected.

[hurufu]

You can do quite crazy stuff with semicontex notation, the most obvious is describing natural language rules.

I also find operational explanation to be more understandable, but I'm afraid it is a wrong kind of intuition to build. As a declarative programmers we should strive to develop declarative intuition.