prologdcg

Writing a DCG containing same string reversed


I am trying to write a dcg that accepts string of the form l0k, where l and k are strings over the alphabet {1, 2, 3} and l is k in reverse. What I have seems to work in that the first answer of a query is correct, but then it keeps going giving more and more wrong answers, and I am wondering if there is a way to fix this without using cuts. This is what I have at the moment:

s --> a(X), [0], a(X). 
s --> a(X), s, a(X). 
a(X) -->[X].
a --> [1].
a --> [2].
a --> [3].

For

 ?- s([1,2,3,3,2,1,0|L], []).
 

I am getting:

L = [1, 2, 3, 3, 2, 1]
    L = [0, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, 0, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, 0, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, _1376, 0, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
    L = [_1364, _1370, _1376, _1382, 0, _1382, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1] etc.

Solution

  • A possible solution:

    s --> [0].
    s --> a(X), s, a(X).
    
    a(1) --> [1].
    a(2) --> [2].
    a(3) --> [3].
    

    Examples:

    ?- phrase(s, [1,2,3,3,2,1,0|L], []).
    L = [1, 2, 3, 3, 2, 1] ;
    false.
    
    ?- length(L,_), phrase(s,L,[]).
    L = [0] ;
    L = [1, 0, 1] ;
    L = [2, 0, 2] ;
    L = [3, 0, 3] ;
    L = [1, 1, 0, 1, 1] ;
    L = [1, 2, 0, 2, 1] ;
    L = [1, 3, 0, 3, 1] ;
    L = [2, 1, 0, 1, 2] ;
    L = [2, 2, 0, 2, 2] ;
    L = [2, 3, 0, 3, 2] ;
    L = [3, 1, 0, 1, 3] ;
    L = [3, 2, 0, 2, 3] ;
    L = [3, 3, 0, 3, 3] ;
    L = [1, 1, 1, 0, 1, 1, 1] ;
    L = [1, 1, 2, 0, 2, 1, 1] ;
    L = [1, 1, 3, 0, 3, 1, 1] ;
    L = [1, 2, 1, 0, 1, 2, 1] ;
    L = [1, 2, 2, 0, 2, 2, 1] ;
    L = [1, 2, 3, 0, 3, 2, 1] ;
    ...