36 1024x768

> (sełq 'database' '(((kwelace ada) 50000.00 1234)

((turing alan) 45000.00 3927)

((sheHoy mary) 35000.00 2850)

((vonNeumann john) 40000.00 7955)

{(Simon horberł) 50000.00 1374)

((mccarthy john) 48000.00 2864)

((rosieli bertrand) 35000.00 2950))

'database*

>    (gct-matchos ((turing alan) 45000.00 3927) 'database')

((turing alan) 45000.00 3927)

>    (get-matches'(? 50000.00 ?) 'databaso')    ; all peoplo who make 50000

(f(lovofaco ada) 50000.00 1234) ((simon herbort) 50000.001374))

>    (get-matches'((? John) ? ?) 'database')    ; all poople named john

(((wnNeumann john) 40000.00 7955) ((mccarthy john) 48000.00 2864))

We impłcmcnf got-matches \viih cdr rccursion to Iook for element* that match with the firs; argument (the patiem). All dcmcnts of the database that match the patiem are conscd together to form the answer for the paltem, get-matches is dclincd:

(defun get-matches (padam databasc)

(cond ((nuH database) ())

((match padam (car database))    : match found. add to rosult

(cons (car database) (get-matches padem (cdr database))))

(t (get-matches padam (cdr database)))))

The henn of the System is the match function. n prcdicatc that determines whether or not two s-cxprcssions containing variablc$ actually match. match is based on the idea that iwo lisis match if and orily if their rcspcctivc pars and cdrs ntatclt, suggesting a car-cdr rccursivc schcmc for the algorithm. The recursion tenninutes when cithcr of the arguments is atomie (this ineludes the cmply list. nil, which is both an atom and a list). If both pjiilems are the same atom or if one of the paticrns is a variablc atom, ?, which can match with anything. then termination is with a succcssful match; othcrwisc. the match will fail. Noticc that if cithcr of the patterns is a wtriable, the other patiem necd not be atomie; variablcs may match with s-exprcssions of arbitrary complcxity.

Bccausc the handling of the terminating conditions is complex, the implemcntation of match uses a function callcd match-atom that takes iwo arguments, one or both of which is an atom. and chccks to sec whether the patterns match. By hiding this complcxity in match-atom the car-cdr rccursivc siructurc of match is morę apparent:

(defun match (padernl pattom2)

(cond (or (atom patternl) (atom pattern2)) ; one of the patterns Is atomie (match-atom padami pattern2)j ; calt match-atom. otherwise (t (and (match (car patternl) (car pełtem2))    : match both car and cdr

(match (cdr patternl) (cdr pattom2))))))

The implemcntation of match-atom makes usc of the fact that when it is callcd a« less one of the arguments is an atom. Becausc of this assumption, a simplc test for

PART VI / LAN6UAGES FOR Al PROBLEM SOLVING

tpatiiy of patterns is all that is nccdcd to test that bo* paltem* are the «me atom («H*iding both bcing a % wriabłe); it will fani eilher if the Mo patem* are (Merem atom* them is nonatomic. If the first tern taili, the only way a match can wcctcd »if corofthe patterns is a vnriablc. This chcck comńutcs the rcmainder of te function dtf> niaoa. Fuuilly. n function variable*p is defined to teu whether or not a pasa ica vari-itk. Trening variablcs as an abstract data lypc non mil wnpłify latcr ntrenoa* to te (unetkm (for csamplc. the exłenston of the function to rnmed wiables a* in PROLOG).

(defun match-atom (patternl pattorn2)

(or (equal patternl patt«m2)    : both patterns «• Im same. or

(variab!e-p patternl)    ;onooithemtsavańaKe.

(varłab!e-p pattem2)))

(defun variable-p (x) (equal x ’?))

15.6 A Recursive Unification Function

b Section 15.5 we implcmcmcd a rccunhe pattcm-marting algorithm that iOowcd the ■donon of unnamed \ariaMes in pattcm>. Now we akod this siraplc paltem nutcher do the fuli unification algorithm prcscMcd in Chaptcr 2. The function. unify. alkws uacd \ari*bies in both of the pattems to bc matchcd, and retums a list of the variaNe biodings rcquircd for the match. This unification function U the basiłoftbc mferenoe Systems devdopcd Inter in this chaptcr.

As in Section 15.5. patterns are cithcr constants, variable$. or IbtttucUKs.InafoU aśfication algorithm. yariabks may bc distinguished front one another by tbcir names. Njmed sariabłes are going to bc represenkd as fors of the form (w <aame>). nfaere <«me> b ttsoaUy an atomie symbol. (var x), (var y), rod (var newsteta) m ewm-ptoof legał variablc$.

The function unify takes as arguments iwo patiem* to bc matchcd and a set of un* iNc snbsritutions (bindings) to be employed in the match. Gcncralł). dus set will be caph (nil) when the function is fitst callcd. On a suę«»firi match, unify wams jfpossi-My empty) set of substitutions rcquircd for a successful match. If no match wa* possiblc. unify retums the symbol failed: nil b used to indicaie an capy mbuimioa »et, Le, a ■Mdi in which no substitutions were rcquircd. An europie of the bełmiotof unify, »nh wmments. appears bclow.

>    (unify '(p a (var x» '(P a b) ())

(((var x), b)j

>    (unify '(p (var y) b) ’(p a (var x)) ()) «(var x). b) ((var y). a))

>    (unify *(p (var x)) *(P (Q a (var y))) ()) (((V8t x) q a (var y)))

>(unify (pa) (pa)())

n«

>(unify (pa)*(qa)()) faited

; retums subsllutflon of b for (var x)

: variabics appear m bolh pauerns

: variabłe bound to more cwnptot patiem

; nil mdłcatrs no subslitution reąuwW ; retums tha atom lalled to MicadUfon

CHAPTBt 1SI MIMTROOUCnDNIOlSP 717