DCGs

[Christopher Howard]

Hi. I'm learning Prolog on my own (not for a class) through the Learn
Prolog Now tutorial. However, I'm a bit stuck on one of the exercises in
the chapter about DCGs:

quote:
--------
The formal language a^n b^2m c^2m d^n consists of all strings of the
following form: an unbroken block of a s followed by an unbroken block
of b s followed by an unbroken block of c s followed by an unbroken
block of d s, such that the a and d blocks are exactly the same length,
and the b and c blocks are also exactly the same length and furthermore
consist of an even number of b s and c s respectively. For example, ϵ ,
abbccd , and aabbbbccccdd all belong to a^n b^2m c^2m d^n. Write a DCG
that generates this language.
--------

One approach that almost works is this:

code:
--------
s --> as,m,ds.

r --> cs,ds.
r --> cs,r,ds.

as --> [a].
as --> [a],as.
m --> [b,b,c,c].
m --> [b,b],m,[c,c].
ds --> [d].
ds --> ds,[d].
--------

This, however, does not provide proper length control. So, the
interpreter will generate a result with 100 d's, while not growing the
other letters proportionately. My first thought was a modification like so:

code:
--------
s --> as,m,ds,length(as,X),length(ds,Y),X =:= Y.
--------

However, this dies with:
"error(existence_error(procedure,length/4),s/2)". Presumably, this is
happening because the interpreter is translating the new statements like
it does the rest of the terms in the DCG statement. So, how do I get the
functionality I need without abandoning the DCG syntax?

-- 
frigidcode.com

signature.asc
Description: OpenPGP digital signature