[m-users.] Building a serialiser with an additional state

[Peter Wang]

On Sat, 08 May 2021 17:30:11 +0200 Volker Wysk <post at volker-wysk.de> wrote:
> Hi!
> 
> I'm trying to build an example of a serialiser, using DCGs, which has an
> additional state, which needs to be threaded through. This is the code:
> 
> 
> -----
> % Number the elements of a list
> :- pred number(list(string)::in, 
>                int::in, int::out, 
>                list(string)::out, list(string)::in)
>    is det.
> 
> 
> number([], !_St) -->
>     [].
> 
> number([T|Ts], !St) -->
>     num(Nr, !St),
>     [ int_to_string(Nr), T ],
>     count(!St),
>     number(Ts, !St).
> 
> 
> % Get the number inside the state
> :- pred num(int::out, 
>                int::in, int::out, 
>                list(string)::out, list(string)::in)
>    is det.
> 
> num(StIn, StIn, StIn) -->
>     [].
> 
> 
> % Increase the number inside the state by 1
> :- pred count(int::in, int::out, 
>               list(string)::out, list(string)::in)
>    is det.
> 
> count(StIn, StIn+1) -->
>     [].
> -----

Not being a user of DCG syntax, this perplexed me for a bit. Let me
rewrite it with state variable syntax as that's much clearer for me:

    number([], !St, !DCG).
    number([T|Ts], !St, !DCG) :-
	num(Nr, !St, !DCG),
	!:DCG = [int_to_string(Nr), T | !.DCG],
	count(!St, !DCG),
	number(Ts, !St, !DCG).

We can number the variables explicitly as the compiler would:

    number([], St, St, DCG, DCG).
    number([T|Ts], St_0, St, DCG_0, DCG) :-
	num(Nr, St_0, St_1, DCG_0, DCG_1),
	DCG_2 = [int_to_string(Nr), T | DCG_1],
	count(St_1, St_2, DCG_2, DCG_3),
	number(Ts, St_2, St, DCG_3, DCG).

The compiler will need to order the goals such that any variables that
occur as input argument to a call are fully bound (i.e. ground) before
the call.

At the start of the clause, the two variables St_0 and DCG are ground.
We could try to make this call:

	num(Nr, St_0, St_1, DCG_0, DCG_1),

St_0 is ground, but DCG_1 is not yet ground, so that's not possible.

Or we could try to make this call:

	number(Ts, St_2, St, DCG_3, DCG).

DCG is ground, but St_2 is not yet ground, so that's not possible.

There's no possible ordering of the goals here that would satisfy the
mode checker, so the compiler ends up reporting:

> -----
> number.m:033: In clause for `number(in, in, out, out, in)':
> number.m:033:   in argument 5 of call to predicate `number.num'/5:
> number.m:033:   mode error: variable `DCG_1' has instantiatedness `free',
> number.m:033:   expected instantiatedness was `ground'.
> -----

Having said that, the idiomatic way to write the predicate in Mercury
is:

    number([], !St, !Acc).
    number([T|Ts], !St, !Acc) :-
	num(!.St, Nr),
	count(!St),
	number(Ts, !St, !Acc),
	!:Acc = [int_to_string(Nr), T | !.Acc].

This assumes all in-out variable pairs are ordered (in, out),
not (out, in). I've also dropped passing the accumulator to predicates
that do not require it.

I can safely say on behalf of the Mercury developers that we STRONGLY
recommend the use of state variable syntax instead of DCGs. DCG syntax
is only supported because it was inherited from Prolog, before state
variable syntax was invented.

Peter