Unification & MatchingMatching ExamplesMatching Examplesldots Matching AlgorithmMatching -- ExamplesMatching -- Examplesldots Matching ConsequencesMatching AlgorithmVisualizing MatchingVisualizing Matchingldots Visualizing Matchingldots Visualizing Matchingldots Visualizing Matchingldots Visualizing Matchingldots Visualizing Matchingldots Visualizing Matchingldots Readings and ReferencesProlog So Farldots520 —Spring 2008 — 43CSc 520Principles of ProgrammingLanguages43 : Logic Programming — Prolog UnificationChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 43Unification & MatchingSo far, when we’ve gone through examples, I have saidsimply 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 leftand right hand sides the same, by assigning values tovariables.Also, there’s an implicit = between arguments when wetry to match a query?- f(x,y)to a rulef(A,B) :- ....[2]520 —Spring 2008 — 43Matching 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 ˆCx = U, C = 3x matches XD matches C*U ˆL*DU[3]520 —Spring 2008 — 43Matching 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+0x ˆ3 + xˆ2 + 1 matches U + Vx ˆ3 + xˆ2 is bound to U1 is bound to V[4]520 —Spring 2008 — 43Matching AlgorithmCan two terms A and F be “made identical,” byassigning 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) andF = 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]520 —Spring 2008 — 43Matching – 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]520 —Spring 2008 — 43Matching – 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)}[7]520 —Spring 2008 — 43Matching 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 thesame value).Backtracking undoes all variable bindings.[8]520 —Spring 2008 — 43Matching AlgorithmFUNC Unify (A, F: term) : BOOL;IF Is Var(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]520 —Spring 2008 — 43Visualizing MatchingFrom Prolog for Programmers, Kluzniak & Szpakowicz,page 18.Assume that during the course of a program we attemptto match the goal p(X, b(X, Y)) with a clause 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 2 and p,respectively.[10]520 —Spring 2008 — 43Visualizing Matching...p(X, b(X, Y))bYXbcAcallercalleeQueryHeadp(A, b(c, A)) :− ...[11]520 —Spring 2008 — 43Visualizing Matching...The second step is to try to unify the first argument ofthe goal (X) with the first argument of the clause head(A).They are both variables, so that works OK.From now on A and X will be treated as identical (theyare in the list of variable substitutions θ).[12]520 —Spring 2008 — 43Visualizing Matching...HeadbYbcXAcallercalleeQueryθ = {A = X}p( A, b(c, A)) :- ...p( X, b(X, Y))[13]520 —Spring 2008 — 43Visualizing Matching...Next we try to match the second argument of the goal(b(X, Y)) with the second argument of the clausehead (b(c, A)).The arities and the functors are the same, so we go onto to try to match the arguments.The first argument in the goal is X, which is matched bythe first argument in the clause head (c). I.e., X and care now treated as identical.[14]520 —Spring 2008 — 43Visualizing Matching...bYbXcallercalleecAQueryHeadθ = {A = X , X = c}p(X, b( X , Y))p(A, b( c, A)) :- ...[15]520 —Spring 2008 — 43Visualizing Matching...Finally, we match A and Y. Since A=X and X=c, thismeans that Y=c as well.[16]520 —Spring 2008 — 43Visualizing Matching...bbcAXYcallercalleeHeadQueryp(X, b(X, Y ))p(A, b(c, A)) :- ...θ = {A = X , X = c, A = Y }[17]520 —Spring 2008 — 43Readings and ReferencesRead Clocksin-Mellish, Sections 2.4, 2.6.3.[18]520 —Spring 2008 — 43Prolog So Far...A term is either aa constant (an atom or integer)a variablea structureTwo terms match ifthere exists a variable substitution θ which makesthe terms identical.Once a variable becomes instantiated, it staysinstantiated.Backtracking undoes variable instantiations.Prolog searches the database sequentially (from top tobottom) until a matching clause is
View Full Document
Unlocking...