MATCHING Chris Mellish January 1984 -- SEEING WHICH CLAUSES ARE APPROPRIATE ------------------------------------- When Prolog has a goal to be satisfied, it must be able to see which facts and rules may be of use for satisfying that goal. To see this, it attempts to MATCH the goal with the "heads" of the facts and rules for the predicate involved. The "head" of a fact is just the fact itself, whereas the "head" of a rule is the part before the ":-". For instance, if Prolog has the goal: ?- borders(france,P). then both of the rules: borders(france,X) :- european_country(X). borders(X,Y) :- joined_to(X,Y), next_to(X,Y). might be of some use, but the rule: borders(britain,X) :- british_island(X). would not. What exactly are the rules Prolog uses for deciding this?? -- RULES FOR MATCHING ---------------------------------------------------- NB. These rules suffice for most of the programs encountered in the Computers and Thought course, but do not cover all cases. 1. A goal will only match the head of a clause if the goal and the clause are about the same predicate. So, for instance, the clause mother(X,Y) :- female(X), parent(X,Y). will not be relevant to satisfying the goal ?- borders(france,P). The rule is for the 'mother' predicate and the question is for the 'borders' predicate, and so the match fails. 2. For a goal and a clause head to match, EACH argument of the goal must match the CORRESPONDING argument in the clause head. So the first argument in the goal must match the first argument in the head, the second argument in the goal must match the second argument in the head, and so on. This means that the order in which arguments are written is very important. As an example, the goal: ?- mother(fred,mary). will NOT match the fact mother(mary,fred). because 'mary' does not match 'fred' (the first arguments don't match). This is what we would expect, as the fact that Mary is the mother of Fred does not mean that Fred is the mother of Mary. 3. A "constant" object (an object that is not a variable) will match the same constant object, but won't match a different constant object. So 'fred' will match 'fred', but not 'mary' (as the last example assumes). 4. A variable must match against the same object in all the places it occurs in a clause. So if a variable is already instantiated (stands for a particular object), it will match only what that particular object matches. For example, assume that we ask: ?- man(X). and Prolog uses the rule man(M) :- human(M), male(M). then eventually Prolog comes to consider satisfying the SUBGOAL: ?- male(M). Which clauses are appropriate for this subgoal will depend on whether the variable M is yet instantiated. Perhaps satisfying the other subgoal "?- human(M)" has already made M stand for some particular object, 'mary' say. In that case, the subgoal will not match the fact: male(john). because 'mary' does not match 'john'. 5. An uninstantiated variable will match any object, and as a result, the variable will come to stand for that object. For instance, if we ask: ?- man(X). and Prolog decides to try using the fact man(fred) then the match will succeed and X in the question will stand for 'fred'. 6. Two uninstantiated variables match, and the two variables are said to "share" as a result. This means that as soon as one of them becomes instantiated to an object the other one will become instantiated to that object as well. See the next section for an example. -- COMMUNICATING ANSWERS ------------------------------------------------- The way that a clause communicates answers back to the goal it is helping to satisfy is by instantiating the variables in the goal. A common way for this to happen is for a variable in the goal to become instantiated to a constant object in the clause. For instance, when we ask: ?- man(X). if Prolog decides to try using the fact man(fred) then X in the question will come to stand for 'fred'. Sometimes a variable in the goal will come instead to "share" with a variable in the clause. In this case, the goal variable will get its value when the clause variable becomes instantiated. For instance, when we ask: ?- man(X). if Prolog decides to try using the rule man(M) :- human(M), male(M). then the match will succeed and X in the question will come to share with M in this use of the clause. Satisfying the subgoals introduced by the clause will probably cause M to become instantiated to some object. This object will then automatically be the value of X in the question. -- EXAMPLES ----------------------------------------------------------------- For each of the following, see if you can work out for yourself - whether the goal matches the head of the clause - which variables come to stand for which objects - which variables come to share. Then read on to see the answers. You can assume that variables in the goals are all uninstantiated. Goal Clause ---- ------ 1. man(X) man(P) :- human(P), male(P). 2. man(fred) man(P) :- human(P), male(P). 3. man(fred) man(john). 4. borders(X,france) borders(A,B) :- joined(B,A). 5. borders(X,Y) borders(A,B) :- joined(B,A). 6. borders(france,X) borders(uk,G) :- island(G). 7. relation(mary,X) relation(P,P). 8. relation(X,Y) relation(Y,X) :- person(Y). -- ANSWERS --------------------------------------------------------------- 1. Matches. X in goal shares with P in clause. 2. Matches. P in clause stands for 'fred'. 3. Does not match. 4. Matches. X in goal shares with A in clause. B in clause stands for 'france'. 5. Matches. X in goal shares with A in clause. Y in goal shares with B in clause. 6. Does not match. 7. Matches. X in goal shares with P in clause, and both stand for 'mary'. 8. Matches. X in goal shares with Y in clause. Y in goal shares with X in clause. --- File: local/plog/teach/matching --- Distribution: all --- University of Sussex Poplog LOCAL File ------------------------------