Learn Prolog Now! DCG Practice Example

Question

I have been progressing through Learn Prolog Now! as self-study and am now learning about Definite Clause Grammars. I am having some difficulty with one of the Practical Session's tasks. The task reads:

The formal language aⁿb^2mc^2mdⁿ consists of all strings of the following form: an unbroken block of as followed by an unbroken block of bs followed by an unbroken block of cs followed by an unbroken block of ds, such that the a and d blocks are exactly the same length, and the c and d blocks are also exactly the same length and furthermore consist of an even number of cs and ds respectively. For example, ε, abbccd, and aaabbbbccccddd all belong to aⁿb^2mc^2mdⁿ. Write a DCG that generates this language.

I am able to write rules that generate aⁿdⁿ, b^2mc^2m, and even aⁿb^2m and c^2mdⁿ... but I can't seem to join all these rules into aⁿb^2mc^2mdⁿ. The following are my rules that can generate aⁿdⁿ and b^2mc^2m.

s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].

s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].

Is aⁿb^2mc^2mdⁿ really a CFG, and is it possible to write a DCG using only what was taught in the lesson (no additional arguments or code, etc)? If so, can anyone offer me some guidance how I can join these so that I can solve the given task?

Mumps

Answer 1

@Timothy, your answer works, but it generates duplicates:

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [a, d] ;            % XXX
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, a, d, d] ;      % XXX

This can be fixed by removing one clause, leaving the DCG:

s --> x.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

% a, b, c, d the same

This generates:

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, b, b, c, c, d] ;
S = [a, a, a, d, d, d] ;
S = [b, b, b, b, c, c, c, c] ;
S = [a, a, b, b, c, c, d, d] ;
S = [a, a, a, a, d, d, d, d] ;

Marylnmarylou

Answer 2

I believe I figured it out...

s --> x.
s --> a,d.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

a --> [a].
b --> [b].
c --> [c].
d --> [d].

?- s([],[]).
Yes

?- s([a,b,c,c,d],[]).
No

?- s([a,a,a,b,b,c,c,d,d,d],[]).
Yes

It's amusing to look at the solution and think, "I racked my brain over that?" But I guess that's half the fun of learning something new, especially when it's something like logic programing coming from an imperative programming background.

Mumps

It's hard, but is pays off. Logic programming (and lazy FP) knowledge esp. served me when learning the iterator concept in C++, Java and Python. – Marylnmarylou

Answer 3

How about something like:

n(L,N) --> n(L,N,0).

n(_,N,N) --> [], !.
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1).

abbccd(N,M) -->
    {M1 is 2*M},
    n("a",N),
    n("b",M1),
    n("c",M1),
    n("d",N).

gen :-
    forall((
           between(1,4,N),
        between(1,4,M),
        phrase(abbccd(N,M),S),
        string_to_atom(S,A)
           ),
           writeln(A)).

executing:

 ?- gen.
abbccd
abbbbccccd
abbbbbbccccccd
abbbbbbbbccccccccd
aabbccdd
aabbbbccccdd
aabbbbbbccccccdd
aabbbbbbbbccccccccdd
aaabbccddd
aaabbbbccccddd
aaabbbbbbccccccddd
aaabbbbbbbbccccccccddd
aaaabbccdddd
aaaabbbbccccdddd
aaaabbbbbbccccccdddd
aaaabbbbbbbbccccccccdddd
true.

Achondroplasia

Thank you, Xonix. That works, but unfortunately it uses concepts not covered until later (code blocks, cuts, etc). I honestly think it's not possible using only simple rules... or if it is, it's not worth the effort because in the "real world" one would take advantage of the other concepts like you did in your sample. – Mumps