6.3.1 Prolog Representation of Constraint Graphs

Representation of constraint graphs in Prolog.

In the rest of this chapter, we will explain how to implement the constraint solver in Prolog. First of all, let's have a look at how we represent a constraint graph in Prolog. We represent such a graph as a collection usr(Ns,LCs,DCs,BCs) of four lists. These lists contain all ingredients of constraint graphs: nodes (Ns), labeling constraints (solid edges: LCs), dominance constraints (dotted edges: DCs), and binding constraints (dashed arrows: BCs). usr stands for underspecified representation. In other words, we represent the graph by specifying its nodes and its various types of edges. Incidentally, this syntax is extremely similar to the notation as logical formulas (constraints) that we have mentioned above.

Nodes and Labelings

Nodes are simply Prolog atoms: Each node gets a unique name. The labelings are terms which are composed with the Prolog inbuilt operator :. For example, x0:(x2@x1) means that the node x0 is labeled x2@x1. Note that this labeling constraint tells you two things at once, namely that:

x0 has the label @.
x0 has two daughters over solid edges: x1 and x2.

Dominances and Bindings

The Prolog notation for a dominance edge is dom(x0,x1). Finally, a binding edge stating the fact that the variable for which the (var-)node x1 stands for is bound by the (-)node x0 is represented as bind(x1,x0).

Here is a sample constraint for ``John walks'':

usr([x0,x1,x2],[x0:(x2@x1),x1:john,x2:walk],[],[]).

In the more familiar tree representation:

If you experiment with the implementation later, you will notice that the constraint graphs soon become large and somewhat unreadable. For example, here's the representation for ``A woman walks'':

usr([x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17], [x0:(x17@x1),x1:var,x2:(x3@x4),x3:(x6@x16),x4:lambda(x5), x6:lambda(x7),x7:lambda(x8),x8:exists(x9),x9:(x10& x11), x10:(x12@x13),x11:(x14@x15),x12:var,x13:var,x14:var,x15:var, x16:woman,x17:walk], [dom(x5,x0)], [bind(x1,x4),bind(x12,x6),bind(x13,x8),bind(x14,x7),bind(x15,x8)]).

But if you look closely, you'll notice that this long term is really nothing but a representation of the following graph, constructed in a way that allows for better use in a program:

And if you look closely at this constraint graph, you'll notice another thing: We've used the predicate symbol instead of the abbreviation . But didn't we say that abbreviates ? In fact, for all common nouns (that is, also for ``man'', ``siamese cat'', etc.), we will directly use the predicate symbol instead of a -term in our implementation. This will make the semantic macro for common nouns a bit easier. Have a look at the sidetrack in Section 5.2.10 to see why this is possible.