| << Prev | - Up - |
As we've said, matching is a fundamental operation in Prolog. It plays a key role in Prolog proof search (as we shall soon learn), and this alone makes it vital. However, as you get to know Prolog better, it will become clear that matching is interesting and important in its own right. Indeed, sometimes you can write useful programs simply by using complex terms to define interesting concepts. Matching can then be used to pull out the information you want.
Here's a simple example of this, due to Ivan Bratko. The following two line knowledge base defines two predicates, namely vertical/2 and horizontal/2, which specify what it means for a line to be vertical or horizontal respectively.
vertical(line(point(X,Y),point(X,Z))).
horizontal(line(point(X,Y),point(Z,Y))).
Now, at first glance this knowledge base may seem too simple to be interesting: it contains just two facts, and no rules. But wait a minute: the two facts are expressed using complex terms which again have complex terms as arguments. If you look closely, you see that there are three levels of nesting terms into terms. Moreover, the deepest level arguments are all variables, so the concepts are being defined in a general way. Maybe its not quite as simple as it seems. Let's take a closer look.
Right down at the bottom level, we have a complex term with functor point and two arguments. Its two arguments are intended to be instantiated to numbers: point(X,Y) represents the Cartesian coordinates of a point. That is, the X indicates the horizontal distance the point is from some fixed point, while the Y indicates the vertical distance from that same fixed point.
Now, once we've specified two distinct points, we've specified a line, namely the line between them. In effect, the two complex terms representing points are bundled toghether as the two arguments of another complex term with the functor line. So, we represent a line by a complex term which has two arguments which are complex terms as well and represent points. We're using Prolog's ability to build complex terms to work our way up a hierarchy of concepts.
To be vertical or to be horizontal are properties of lines. The predicates vertical and horizontal therefore both take one argument which represents a line. The definition of vertical/1 simply says: a line that goes between two points that have the same x-coordinate is vertical. Note how we capture the effect of `the same x-coordinate' in Prolog: we simply make use of the same variable X as the first argument of the two complex terms representing the points.
Similarly, the definition of horizontal/1 simply says: a line that goes between two points that have the same y-coordinate is horizontal. To capture the effect of `the same y-coordinate', we use the same variable Y as the second argument of the two complex terms representing the points.
What can we do with this knowledge base? Let's look at some examples:
vertical(line(point(1,1),point(1,3))).
yes This should be clear: the query matches with the definition of vertical/1 in our little knowledge base (and in particular, the representations of the two points have the same first argument) so Prolog says `yes'. Similarly we have:
vertical(line(point(1,1),point(3,2))).
no This query does not match the definition of vertical/1 (the representations of the two points have different first arguments) so Prolog says `no'.
But we can ask more general questions:
horizontal(line(point(1,1),point(2,Y))).
Y = 1 ;
no Here our query is: if we want a horizontal line between a point at (1,1), and point whose x-coordinate is 2, what should the y-coordinate of that second point be? Prolog correctly tells us that the y-coordinate should be 2. If we then ask Prolog for a second possibility (note the ;) it tells us that no other possibilities exist.
Now consider the following:
horizontal(line(point(2,3),P)).
P = point(_1972,3) ;
no This query is: if we want a horizontal line between a point at (2,3), and some other point, what other points are permissible? The answer is: any point whose y-coordinate is 3. Note that the _1972 in the first argument of the answer is a variable, which is Prolog's way of telling us that any x-coordinate at all will do.
A general remark: the answer to our last query, point(_1972,3), is structured. That is, the answer is a complex term, representing a sophisticated concept (namely `any point whose y-coordinate is 3'). This structure was built using matching and nothing else: no logical inferences (and in particular, no uses of modus ponens) were used to produce it. Building structure by matching turns out to be a powerful idea in Prolog programming, far more powerful than this rather simple example might suggest. Moreover, when a program is written that makes heavy use of matching, it is likely to be extremely efficient. We will study a beautiful example in a later lecture when we discuss difference lists, which are used to implement Prolog built-in grammar system Definite Clause Grammars (DCGs).
This style of programming is particularly useful in applications where the important concepts have a natural hierarchical structure (as they did in the simple knowledge base above), for we can then use complex terms to represent this structure, and matching to access it. This way of working plays an important role in computational linguistics, because information about language has a natural hierarchical structure (think of the way we divide sentences into noun phrases and verb phrases, and noun phrases into determiners and nouns, and so on).
| << Prev | - Up - |