| << Prev | - Up - |
A more efficient implementation can be obtained by making use of difference lists. This is a sophisticated (and, once you've understood it, beautiful) Prolog technique that can be used for a variety of purposes. We won't discuss the idea of difference lists in any depth: we'll simply show how they can be used to rewrite our recognizer more efficiently.
The key idea underlying difference lists is to represent the information about grammatical categories not as a single list, but as the difference between two lists. For example, instead of representing a woman shoots a man as [a,woman,shoots,a,man] we might represent it as the pair of lists
[a,woman,shoots,a,man] []. Think of the first list as what needs to be consumed (or if you prefer: the input list), and the second list as what we should leave behind (or: the output list). Viewed from this (rather procedural) perspective the difference list
[a,woman,shoots,a,man] []. represents the sentence a woman shoots a man because it says: If I consume all the symbols on the left, and leave behind the symbols on the right, I have the sentence I am interested in.
That is: the sentence we are interested in is the difference between the contents of these two lists.
Difference representations are not unique. In fact, we could represent a woman shoots a man in infinitely many ways. For example, we could also represent it as
[a,woman,shoots,a,man,ploggle,woggle] [ploggle,woggle].Again the point is: if we consume all the symbols on the left, and leave behind the symbols on the right, we have the sentence we are interested in.
That's all we need to know about difference lists to rewrite our recognizer. If we bear the idea of `consuming something, and leaving something behind' in mind', we obtain the following recognizer:
s(X,Z) :- np(X,Y), vp(Y,Z).
np(X,Z) :- det(X,Y), n(Y,Z).
vp(X,Z) :- v(X,Y), np(Y,Z).
vp(X,Z) :- v(X,Z).
det([the|W],W).
det([a|W],W).
n([woman|W],W).
n([man|W],W).
v([shoots|W],W). The s rule says: I know that the pair of lists X and Z represents a sentence if (1) I can consume X and leave behind a Y, and the pair X and Y represents a noun phrase, and (2) I can then go on to consume Y leaving Z behind, and the pair Y Z represents a verb phrase.
The idea underlying the way we handle the words is similar. The code
n([man|W],W). means we are handling man as the difference between [man|W] and W. Intuitively, the difference between what I consume and what I leave behind is precisely the word man.
Now, at first this is probably harder to grasp than our previous recognizer. But we have gained something important: we haven't used append. In the difference list based recognizer, they simply aren't needed, and as we shall see, this makes a big difference.
How do we use such grammars? Here's how to recognize sentences:
s([a,woman,shoots,a,man],[]).
yes This asks whether we can get an s by consuming the symbols in [a,woman,shoots,a,man], leaving nothing behind.
Similarly, to generate all the sentences in the grammar, we ask
s(X,[]). This asks: what values can you give to X, such that we get an s by consuming the symbols in X, leaving nothing behind?
The queries for other grammatical categories also work the same way. For example, to find out if a woman is a noun phrase we ask:
np([a,woman],[]).And we generate all the noun phrases in the grammar as follows:
np(X,[]).You should trace what happens when this program analyses a sentence such as a woman shoots a man. As you will see, it is a lot more efficient than our append based program. Moreover, as no use is made of append, the trace is a lot easier to grasp. So we have made a big step forward.
On the other hand, it has to be admitted that the second recognizer is not as easy to understand, at least at first, and it's a pain having to keep track of all those difference list variables. If only it were possible to have a recognizer as simple as the first and as efficient as the second. And in fact, it is possible: this is where DCGs come in.
| << Prev | - Up - |