37 1024x768

We cxp!nin ihc notation. as in «var x) .b). aft er \ve present «he function unify. unify. lik o ihc panem matchcr of Section 15.5. uses a car-cdr recunivc schcmc and u defined by:

(dafun unify (panom 1 patterr>2 substitution-list)

(cond ((equal substitution-list 'failod) *failod)

((varp patternl) (match-var paltom 1 pattorn2 substitution-list)) ; varp tests ((varp pattorn2) (match-var pattorn2 pattoml substitution-list)) : if variaWe ((is-constant-p patiami)

(cond ((equal patternl pattorn2) substitution-list)

(t failed)))

((is-constant-p pattem2) 'failod)

(t (unify (cdr patternl) (cdr pa«ern2)

(unify (car patiami) (car pattem2) substitution-list)))))

On entering unify. the algorithm first chccks whether the substitution list is cqual to failed. This could occur if a prior attempt to unify the cars of iwo pattems had failed. If this condition is met. the function retums failed.

Ncxt. if cithcr panem is a variabłe. the function match-var is callcd to perfonn further chccking and possibły add a ncw binding to the substitution list. If neither paltem is a \-anablc. unify tests whether cithcr is a constant. return i ng the unchangcd substitution list if they arc the same constant. failed othcrwisc.

The last item in the cond statement implcmcms the trec-rccursivc decomposition of the problem: first. the cars of the pattems are unified using the bindings in substitution-list. The rcsult is passed as the third argument to the cali of unify on the Cdr* of both pattems. This allows the \ariablc substitutions madc in matching the cars to be applied to other occurrcnces of those variablcs in the cdrs of both pattems.

match-var. for the casc of matching a variable and a patiem, is dcftncd by:

(defun match-var (var panem substitution-list)

(cond ((equal var patiem) substitution-list)

(t (let ((binding (get-binding var substitution-list)))

(cond (binding (unify (get-binding-valuo binding) pattem substitution-list)) ((occursp var patiom) 'failed)

(t (add-substitution var pattern substitution-list)))))))

match-var lirst chccks whether the variablc and the pattern arc the same; unify i ng a vari-ablc willi itNclfrcquircs no added substitutions. so substitution-list is retumed unchangcd.

If var and pattern are not the same. match-var chccks whether tlić variable is alrcady bound. If a binding cxists. unify is callcd rccursivcly to match the in/ue of the binding with pattern. Notę that this binding vuluc may be a constant. a variable. or a patiem of srbitrary complexity; rcquiring a cali to the fuli unification algorithm to complctc the match.

If no binding currently cxists for var. the function calls occursp to test whether var appears in pattern. The occurs check is nccdcd to prcvcnt attempts to unify a yariabłe with a pattem containing that variablc. leoding to a circular structurc. For cxample. if (var x) was bound to (p (var x)). any attempt to apply those substitutions to a pattem

PART VI f LANOUAGES FOR Al PROBLEM SOLVING

xvouU5 rc»ul« in an infinite loop. If var appcar» in pattem. matcłwar retro failed: oiłierwise. it adds Ihc ncw aut>stiluiion pair to substitution-list u«ir« add-substitution.

unify and match*var arc the hcart of the unifkatkm algortthm. occursp <which pctforms a ircc walk on n patiem to find any occurrcnco of the yąńiblc in that pjucmi, varp. and Is-constant-p (which test whether their argument t* a withle or a comtani. Kipectwely) appear bclow. Functiona for handling subktitutioa wt* arc dikcuMed helów

(etofun occursp (var pattern)

(cond ((equal var pattern) t>

((or (varp pattern) (is-constant-p pattern)) nil)

(t (or (occursp var (car pattem))

(occursp var (cdr pattem))))))

(defun is-constant-p (Itom)

(atom item»

(defun varp (item)

(and (liatp item)

(equal (length item) 2)

(equal (car item) ’var)))

Scts of substitutions arc rcprcscntcd using a built-in I.ISP data type callcd the arsoci-aik>n Ust or </-//-%/. This is the basis for the functions add-substitutlons. get-bir>d:ng. and binding-value. An nssociation list is a list of data rccords, or Atry/daM pairs- The car of cach rccord is a A«rv for its rctricval: the cdr of cach rccord is callcd the derumt. The datura raay bc a list of valucs or a single atom. Rctr*cv»l as implemcnted by the function assoc. which takes as arguments n kcy and an associałion list and returns the first member of the sssociation list that has the kcy as its car. An optional third argument to assoc speetfie* the test to bc uscd in comparing keys. The default test i* the Common Ł.ISP function OQl. a form of equality test rcc]uiring two arguments be the same objcct Ci-c— cithcr the same mentory location or the same numerie valuc>- In impkmenting subsUtutioo scts. wv wtll spccify a less s tri et test, equal. which rcquircs onły that the arguments match syniactically (Lc.. arc designated by idcntical names). An cxamplc of assoes bchavior appears bclow:

>    (assoc 3 ‘((I a) (2 b) (3 c) (4 d»)

(3o)

>    (assoc "d '((a fc» c) (b c d o) (d e f) <c d ©)) :tost » oquai)

(de O

» (assoc "c ’((« - 1) <b . 2) (c . 3) (d . 4)) :test » oqual)

Cc. 3)

Notc that assoc returns the entire rccord matchcd on the kc>" the datura truty bc retricv©d from this list by the cdr function. Also, notice that in the last cali the merabers of Ac a-list arc not lists but a structurc callcd doticrł p**urs, e.g— (• - t).

The dotted pair, or cons pair. is actually the fundamcntal coeistructor in klSP.lt is the rcsull of consing one s-cxpres5ion on to another. the list notation that we have u^ed houghout the chnptcr is Just a notational variant of dotted pairs. For cxample, the s-aluc retumed by (cons 1 nil) is actually (*l - nil) : this is eąuhalcnt to (1). Similarly. the Ust et 2 3) may be written in dotted pair notation as (1 . C2 - ( 3 - nil))), Although the actual

7*13

CHAPTER 15/ANWTROOOCTlONTOUSP