7.4 Practical Session

The purpose of this session is to help you get familiar with DCGs, difference lists, and the relation between them, and to give you some experience in writing basic DCGs. As you will learn in the following chapter, there is more to DCGs than the ideas just discussed. Nonetheless, what you have learned so far is certainly the core, and it is important that you are comfortable with the basic ideas before moving on.

First some keyboard exercises:

1. Type in or download the simple append/3 based recognisers discussed in the text, and then run some traces. As you will see, we were not exaggerating when we said that their performance is poor. Even for such simple sentences as The woman shot a man you will see that the traces are long and difficult to follow.
2. Next, type in or download our second recogniser, the one based on difference lists, and run more traces. As you will see, there is a dramatic gain in efficiency. Moreover, you will see that the traces are very simple to understand, especially when compared with the monsters produced by the append/3 based implementations.
3. Next, type in or download the DCG discussed in the text. Type listing so that you can see what Prolog translates the rules to. How does your system translate rules of the form Det  -->  [the] ? That is, does it translate them to rules like det([the|X],X) , or does is make use of rules containing the ’C’ predicate?
4. Now run some traces. Apart from variable names, the traces you observe here should be very similar to the traces you observed when running the difference list recogniser.

And now it’s time to write some DCGs:

1. The formal language Even is very simple: it consists of all strings containing an even number of a s, and nothing else. Note that the empty string ϵ belongs to Even . Write a DCG that generates Even .
2. The formal language a ⁿ b ^{2 m} c ^{2 m} d ⁿ 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 ⁿ b ^{2 m} c ^{2 m} d ⁿ . Write a DCG that generates this language.
3. The language that logicians call “propositional logic over the propositional symbols p , q , and r ” can be defined by the following context free grammar:

   prop  ->  p

   prop  ->  q

   prop  ->  r

   prop  -> ¬  prop

   prop  -> (prop   ∧  prop)

   prop  -> (prop   ∨  prop)

   prop  -> (prop   →  prop)

   Write a DCG that generates this language. Actually, because we don’t know about Prolog operators yet, you will have to make a few rather clumsy looking compromises. For example, instead of getting it to recognise

   ¬ (p   →  q)

   you will have to get it recognise things like

   [not,  ’(’,  p,  implies,  q,  ’)’]

   instead. We will learn in Chapter  9 how to deal with propositional logic somewhat more naturally; in the meantime, write a DCG that accepts a clumsy looking version of this language. Use or for ∨ , and and for ∧ .