Is there a way I can call non-terminal symbols recursively when working with a DCG in Prolog?

Question

I have been trying to convert a section of Prolog code I created to represent a basic finite automaton into a DCG. Basically it ensures that an acceptable input would be one where the third last element in a string of 0s and 1s is a 1.

E.g. [1,0,0,1,0,1] is acceptable while [1,0,1,0,0,0] is not.

accept(L) :- steps(q0,L,F), final(F).

steps(Q,[],Q).

steps(Q,[H|T],Q2) :- tran(Q,H,Qn), steps(Qn,T,Q2).

final(q1).

tran(Y,0,n0) :- Y = q0; Y = q1; Y = n0.

tran(Y,1,n1) :- Y = q0; Y = q1; Y = n0. 

tran(n1,X,h1):- X = 0 ; X = 1.

tran(h1,X,q1):- X = 0 ; X = 1.

My problem is essentially with the second clause of the steps predicate where the output of "tran(Q,H,Qn)" is used as an input for steps(Qn,T,Q2), in this case being the variable Qn.

The DCG I have come up with is as follows :

accept(L) --> final(F),{F = steps(q,L)}.

steps(Q,[]) --> [Q].


steps(Q,[H|T]) --> steps(E,T), {E = tran(Q,H)}.

final(F)  --> [q1], {F = q1}.

tran(Y,0) --> [n0], {Y = q;Y = q1;Y = n0}.

tran(Y,1) --> [n1], {Y = q;Y = q1;Y = n0}.

tran(n1,X) -->[h1], {X = 0; X = 1}.

tran(h1,X) -->[q1], {X = 0; X = 1}.

I am basically wondering if there is another way of ensuring that the variable E, in the second line of DCG can be used to represent tran(Q,H) instead of defining it as an extra goal which has not been working so far.

Answer 1

DCGs describe lists. Unlike everything else in Prolog, they describe these lists implicitly. Every value you compute in Prolog needs to be passed out of a predicate through an argument -- except for the lists described by DCGs, which you do not represent by an argument. They are instead represented as an implicit DCG state. (There are some uses for having the list as an argument as well, but it's not common.)

What this means is that when you convert a predicate to a DCG, you remove the list argument. But you must keep all other arguments so that you can communicate with the rest of the program.

So, for example, if you have the following predicate:

abc(A, B, C, [A, B, C]).

?- abc(a, b, c, ABC).
ABC = [a, b, c].

To convert it to a DCG that describes the list [A, B, C] you remove the list from the arguments but keep all other arguments:

abc(A, B, C) -->
    [A, B, C].

?- phrase(abc(a, b, c), ABC).
ABC = [a, b, c].

What this means for your program is that your predicate

accept(List) :- ...

will turn into a DCG without arguments:

accept --> ...describe the list somehow...

and your steps predicate:

steps(Q, Steps, Q2) :- ...

will keep the states Q and Q2 as arguments but will remove the list argument:

steps(Q, Q2) --> ...describe the steps somehow...

With this knowledge, the first part of the translation is fairly mechanical:

accept -->
    steps(q0, F),
    { final(F) }.

steps(Q, Q) -->
    [].
steps(Q, Q2) -->
    tran(Q, Qn),
    steps(Qn, Q2).

As for the rest, you had some confusion in your transition DCG because suddenly it looked like you were trying to describe a list of states rather than a list of input symbols. This is partly because you chose bad variable names. This is not entirely your fault; many Prolog texts were written by people with a mathematical background, and written at times when books were printed on paper (which was expensive, so programs had to be more compact than anything else) or stored on tiny, slow storage devices (which again meant they had to be compact above all else) or viewed on tiny computer screens (which again meant that they had to be compact above all else). We don't have these restrictions anymore, so we can free ourselves from the shackles of the past. It is your responsibility to choose good variable names despite what outdated Prolog traditions teach you. By all of which I mean to say: If a variable describes a state, it should be called State instead of Y (or, yes, in automata theory Q can be canonical), and if a variable describes a symbol, it should be called Symbol instead of X.

Anyway. Here is a fixed version:

tran(Q, n0) --> [0], {Q = q0 ; Q = q1 ; Q = n0}.
tran(Q, n1) --> [1], {Q = q0 ; Q = q1 ; Q = n0}.
tran(n1, h1) --> [Symbol], {Symbol = 0 ; Symbol = 1}.
tran(h1, q1) --> [Symbol], {Symbol = 0 ; Symbol = 1}.

The original predicate behaves like this:

?- accept([1, 0, 0, 1, 0, 1]).
true ;
false.

?- accept([1, 0, 1, 0, 0, 0]).
false.

And the fixed DCG version behaves the same:

?- phrase(accept, [1, 0, 0, 1, 0, 1]).
true ;
false.

?- phrase(accept, [1, 0, 1, 0, 0, 0]).
false.

Answer 2

My impression is that you're overengineering... to keep things simple, an abstraction (DCGs, in our case) should be used for its strengths. So, I would suggest to 'invert' your encoding schema: let's predicates be our automaton states, following input in direct way, controlled by DCG normal behaviour, and encode in predicate arguments the state payload, if any (in the example code there is none). For instance

/*  File:    dcg_autom.pl
    Author:  Carlo,,,
    Created: Dec  8 2020
    Purpose: https://stackoverflow.com/q/65191963/874024
*/

:- module(dcg_autom,
          [accept/1
          ]).

accept(S) :- phrase(start, S).

start --> q0.
final --> [].  % overkill, I know...

q0 --> [0], n0.
q0 --> [1], n1.

n0 --> [0], n0.
n0 --> [1], n1.

n1 --> [_], h1.
h1 --> [_], q1.

q1 --> final.
q1 --> [0], n0.
q1 --> [1], n1.

I'm suggesting this architecture change because a finite state automaton it's very easy to implement in basic Prolog, there is really no need to fiddle with DCGs...

Willing to get the list of visited states, the (boring) changes to the code could be

accept(S,L) :- phrase(start(L), S).

start([start|L]) --> q0(L).
final([final]) --> [].  % overkill, I know...

q0([q0|L]) --> [0], n0(L).
q0([q0|L]) --> [1], n1(L).

n0([n0|L]) --> [0], n0(L).
n0([n0|L]) --> [1], n1(L).

n1([n1|L]) --> [_], h1(L).

h1([h1|L]) --> [_], q1(L).

q1([q1|L]) --> final(L).
q1([q1|L]) --> [0], n0(L).
q1([q1|L]) --> [1], n1(L).

and then we have

?- accept([1,0,0,1,0,1],L).
L = [start, q0, n1, h1, q1, n1, h1, q1, final] ;
false.