CSc 520 — Principles of Programming Languages43 : Logic Programming — Prolog UnificationChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergApril 23, 20081 Unification & Matching• So far, when we’ve gone through examples, I have said simply that when trying to satisfy a goal, Prologsearches for a matching rule or fact.• What does this mean, to match?• Prolog’s matching operator or =. It tries to make its left and right hand sides the same, by assigningvalues to variables.• Also, there’s an implicit = between arguments when we try to match a query?- f(x,y)to a rulef(A,B) :- ....2 Matching ExamplesThe rule:deriv(U ^C, X, C * U ^L * DU) :-number(C), L is C - 1,deriv(U, X, DU).?- deriv(x ˆ3, x, D).D = 1*3*x^2The goal:• x ^3 matches U ^C– x = U, C = 3• x matches X• D matches C * U ^L * DU13 Matching Examples. . .deriv(U+V, X, DU + DV) :-deriv(U, X, DU),deriv(V, X, DV).?- deriv(xˆ3 + xˆ2 + 1, x, D).D = 1*3*x^2+1*2*x^1+0• x ^3 + x^2 + 1 matches U + V– x ^3 + x^2 is bound to U– 1 is bound to V4 Matching AlgorithmCan two terms A and F be “made identical,” by assigning values to their variables?Two terms A and F match if1. they are identical atoms2. one or both are uninstantiated variables3. they are terms A = fA(a1, · · · , an) and F = fF(f1, · · · , fm), and(a) the arities are the same (n = m)(b) the functors are the same (fA= fF)(c) the arguments match (ai≡ fi)5 Matching – ExamplesA F A ≡ F variable subst.a a yesa b nosin(X) sin(a) yes θ = {X=a}sin(a) sin(X) yes θ = {X=a}cos(X) sin(a) nosin(X) sin(cos(a)) yes θ = {X=cos(a)}6 Matching – Examples. . .A F A ≡ F variable subst.likes(c, X) likes(a, X) nolikes(c, X) likes(c, Y) yes θ = {X=Y}likes(X, X) likes(c, Y) yes θ = {X=c, X=Y}likes(X, X) likes(c,) yes θ = {X=c, X= 47}likes(c, a(X)) likes(V, Z) yes θ = {V=c,Z=a(X)}likes(X, a(X)) likes(c, Z) yes θ = {X=c,Z=a(X)}27 Matching ConsequencesConsequences of Prolog Matching:• An uninstantiated variable will match any object.• An integer or atom will match only itself.• When two uninstantiated variables match, they share:– When one is instantiated, so is the other (with the same value).• Backtracking undoes all variable bindings.8 Matching AlgorithmFUNC Unify (A, F: term) : BOOL;IF IsVar(F) THEN Instantiate F to AELSIF Is Var(A) THEN Instantiate A to FELSIF Arity(F)6=Arity(A) THEN RETURN FALSEELSIF Functor(F)6=Functor(A) THEN RETURN FALSEELSEFOR each argument i DOIF NOT Unify(A(i), F(i)) THENRETURN FALSERETURN TRUE;9 Visualizing Matching• From Prolog for Programmers, Kluzniak & Szpakowicz, page 18.• Assume that during the course of a program we attempt to match the goal p(X, b(X, Y)) with aclause C, whose head is p(X, b(X, y)).• First we’ll compare the arity and name of the functors. For both the goal and the clause they are 2and p, respectively.310 Visualizing Matching. . .p(X, b(X, Y))bYXbcAcallercalleeQueryHeadp(A, b(c, A)) :− ...11 Visualizing Matching. . .• The s econd step is to try to unify the first argument of the goal (X) with the first argument of theclause head (A).• They are both variables, so that works OK.• From now on A and X will be treated as identical (they are in the list of variable subs titutions θ).12 Visualizing Matching. . .HeadbYbcXAcallercalleeQueryθ = {A = X}p( A , b(c, A)) :- ...p(X , b(X, Y))13 Visualizing Matching. . .• Next we try to match the second argument of the goal (b(X, Y)) with the second argument of theclause head (b(c, A)).• The arities and the functors are the same, so we go on to to try to match the arguments.4• The first argument in the goal is X, which is matched by the first argument in the clause head (c). I.e.,X and c are now treated as identical.14 Visualizing Matching. . .bYbXcallercalleecAQueryHeadθ = {A = X, X = c}p(X, b(X , Y))p(A, b( c , A)) :- ...15 Visualizing Matching. . .• Finally, we match A and Y. Since A=X and X=c, this means that Y=c as well.16 Visualizing Matching. . .bbcAXYcallercalleeHeadQueryp(X, b(X, Y ))p(A, b(c,A )) :- ...θ = {A = X, X = c, A = Y }17 Readings and References• Read Clocksin-Mellish, Sections 2.4, 2.6.3.18 Prolog So Far. . .• A term is either a– a constant (an atom or integer)5– a variable– a structure• Two terms match if– there exists a variable substitution θ which makes the terms identical.• Once a variable becomes instantiated, it stays instantiated.• Backtracking undoes variable instantiations.• Prolog searches the database sequentially (from top to bottom) until a matching clause is
View Full Document
Unlocking...