6.7 Matching

Introduction

Matching is an important process used while satisfying (sub)goals of rules and queries.

'Matching' refers to the process of comparing terms of (sub)goals with each other, and in the process making variable bindings.

Explanation

When trying to satisfy a (sub)goal of a rule or query, Prolog+CG attems to match the (sub)goal with either:

This is done using all the facts and rule-heads of the program, from the top of the program to the bottom.

There are certain rules when matching:

  1. An atom must be identical to the other atom for them to match.
  2. A structure such as

    graph(cg1, [Animal])
    matches another structure if and only if:

    1. the names of the structure are the same (here, 'graph'), and
    2. the two structures have the same number of terms in their lists of terms, and
    3. each of the terms in the lists match, in the order in which they appear (from left to right).
  3. when matching a variable with a term:

    1. if the variable is bound already, the value of the variable must match the term.
    2. if the variable is free, the matching succeeds, and the value of the variable becomes whatever the term was.

Examples

It is easiest to explain how matching works by using a small example.

Consider the following Prolog+CG program:

// Type-hierarchy
Animate > Animal, Human.

// Graph facts
graph(gr1, [Animal]).
graph(gr2, [Human]).

// Rule
gr(X,Y) :- graph(X,Y).

When asking the following query:

?- gr(X,Y).

the answer is:

{X = gr1, Y = [Animal]}
{X = gr2, Y = [Human]}

This is because:

  • The query was matched against every fact and rule-head in the program. The only thing that matched was the rule-head:
    gr(X,Y)
  • Then the rule-body was called. This had one subgoal,
    graph(X,Y)
    which was then matched against every fact and rule-head in the program.
  • The first thing that matched was the fact
    graph(gr1, [Animal]).
    It matched because:
    • The name of the structures were the same ("graph").
    • The number of terms in the list of terms was the same (2)
    • The variable X was free at the time of matching (since it was free in the query). Thus the variable X acquired whatever value was in the first term of the list of terms. This was "gr1".
    • Similarly, the variable Y was free and so was bound to the graph
      [Animal]
  • Then the first result was printed:
    {X = gr1, Y = [Animal]}
  • Then both variables were made free again (the binding was broken), and the matching went further, starting from the next line after the first fact. This resulted in a match with the second fact:
    graph(gr2, [Human]).
  • This fact matched for the same reasons that the first fact matched.
  • After the second result had been printed:
    {X = gr2, Y = [Human]}
    the variables were made free again, and the matching continued on the next line after the second fact. However, no other facts or rule-heads matched, so these two results were the only ones printed.


PrevLite: 6.6 Clauses and predicates
NextLite: 6.8 Queries

Prev: 6.6 Clauses and predicates
Up: 6 Prolog for CG users
Next: 6.8 Queries