Unification and Pattern Matching
Unification is the way variables are bound to a value.
What will be cover ?
- Simple descriptions of Prolog Syntax
- A small example program,
- Unification and Pattern Matching
- Queries and the Searching Mechanisms
- The Computational Model
When are two
terms equals (equivalent)? How does Prolog bind values to a
variable?
- Unification is an attempt by the Prolog
interpreter to match two terms, by instantiating the
variables contained in two terms.
Example: When do two terms rel(X
,b) rel(a, Y) match?
- When X can be instantiated to the value a and Y can be instantiated to the
value b, the two terms are
equal (equivalent).
- So unification will involve assigning
these values to the variables.
The term , rel(a ,b) is called an instance of rel(X ,b)
- Two terms t1and t2 unify
if they have a common instance U.
- Unification Algorithm: (Scott p 595)
"The unification rules for Prolog state that
- A constant unifies only with itself.
- Two
structures unify if and only if they have the same functor and the same
arity, and the corresponding arguments unify recursively.
- A variable unifies with anything.
If the other thing has a value, then the variable is
instantiated. If the other thing is an uninstantiated variable,
then the two variables are associated in such a way that if either is
given a value later, the value will be shared by both."
- Where does unification take place?
1. Explicitly through the use of "=" operator
rel(X ,b) = rel(a, Y)
2. Unification occurs implicitly
when a rule is applied
identity(Z,Z). %clause in file
?- identity(rel(X ,b), rel(a,
Y)) %query
X = a
Y = b
Which of the following unify? What are the
instantiated value of the variables for the successful unification?
1?-
one = one .
2?-
one = two .
3?-
one = X .
4?-r(
a, X ) = r( Y, b).
5?-
r( X ) = f( X ).
6?-
[ a | Tail ] = [ Head | [ x , y ] ] .
7?-
[ a | T ] = [ a ] .
8?-
r( a, f( X ) ) = r( Y , b )
9?-
r( a, f ( X ) ) = r( Y, f( b ) ).
10?-
r( X ) = r( X , Y ).
11?–
f(a) = f( X ,a).
12?–
X = f( X ).
13?–
[A, B | X] = [2, 1].
14?
– p( X , X ) = p(Y, f(Y )).
15?
– f( X , g( X )) = f(a, Y ).
16?
– f( X , b, g( X )) = f(A, A, g(a)).
17? - (X,R) = (a,b,c,d).
18? - [X] = [a,b,c,d].
19? - (X) = (a,b,c,d).
(help(unify_with_occurs_check).
unify_with_occurs_check(+Term1,
+Term2)
[ISO]
As =/2, but using
sound-unification. That is, a variable
only unifies to a term if this term
does not contain the variable itself. To
illustrate this, consider the two goals below:
1 ?- A = f(A).
A = f(f(f(f(f(f(f(f(f(f(...))))))))))
2 ?- unify_with_occurs_check(A, f(A)).
false.
I.e. the first creates a
cyclic-term, which is printed as
an infinitely nested f/1 term
(see the max_depth option of
write_term/2). The second executes logically sound unification
and thus fails. Note that the behaviour of unification
through =/2 as well as implicit unification in the
head can be changed using the Prolog flag
occurs_check.
For more information see Occurs check - Wikipedia, the free encyclopedia
Arithmetic in Prolog
- Prolog defines the usual operators for performing arithmetic.
- Infix notation can be used to specifying expressions
- Like list notation , [ ], an expression can be written in standard form
2 + 3 is short hand (syntactic sugar) for + ( 2, 3)
- We must explicitly ask an expression to be evaluated.
?- X = 2 + 3.
X = 2 + 3
X unifies with the term 2
+ 3
- Use is to evaluate an expression:
?- X is 2 + 3
X = 5
- Check the following:
?- X is 2 + 3, X = 2 + 3.
?- X is +(2,3).
How can we construct loops in Prolog?
Fall, 2016