23 1024x768

ooniplo\ da«a stniotures of symbolic and numcric atoms. along willi Hic forms nccded fej manipulaimg thcm. \Vc illusiratc ihc casc willi which USP handlcs symbolic data structure*. to \\vll as ihc naturalncss of dala abslraction tccliniquc$ in USP, with a simplc datahase cuimplć. Our databasc applicalion rcquires ihc mnnipulaiion of crapk)Yt avords coniaining na mc. salnry. and cmploycc numbcr ficlds.

Thcsc rccoids are rcprescnied as lists. wilh ihc namc. salary. and numbcr fickb as thc rirsi. sccwid and third dcmcnts of a lisi. Using nth. il is possiblc lo definc acccss łuneiioos for ihc \arious ficlds of a daia rccord. For cxamplc:

(dcfun namo-fiold (rccord)

(nth 0 rccord))

«i!I ha>c ihc bcłmior.

>    (name-fieW '((Ada LoveIace) 45000.00 38519))

(Ada Lovclace)

SimilarK. thc functions sałary-field and number-field may bc dcfincd lo acccss ihc jpproprutc ficlds of a data rccord. Bccausc a namc is iiself a lisi coniaining iwo clements. a tirsi namc and a łasi namc. il is uscful lo dcfinc functions thai lakc a namo as argument and rerum citbcr thc flrst or list namc as a rcsull.

(defun firsi-name (name)

(nth 0 name))

will have thc bchaiHor.

>    (łirsl-name {name-field '((Ada Uwełaco) 45000.00 338519)))

Ada

ln addman to acccssing indhidual ficlds of a dala rccord. il is also ncccssaiy ta implcmcnt functions to crcaic and modify data rccords. Thcsc ore dcfincd using the buili-in USP (unction: list. list takes any numbcr of urgunicnis. cvnluaics ihcm. and reiurns a lisi containing thosc valuc$ as iis clcmcnis. For cxamplc:

>(Hst1234)

(1234)

>    (list (Ada łamiące) 45000.00 338519)

((Ada Łamiące) 45000.00 338519)

As thc sccond of thcsc cuimplcs suggcsis. list may bc uscd lo dcfinc a consirucior w records in thc databasc:

(defun bulld-record (name talary emp-number)

(list name talary emp-number))

will love ihc bełm tor:

>    (bulld-record (Alan Turtnfl) 50000.00 135772)

((Alan Turing) 50000.00 135772)

Naw, using bulld-record and thc acccss functions. we may constnict functions that Ktum a modiftcd copy of a rccord. For examp!e replace-salary will hchavc:

(cfofun replaco-salary field (record ncw-salary)

(build-racord (name -field record) naw talary

(number-fiold record)))

>    (rcplace-salary-field ((Ada Love!ace) 45000.00 338519) 50000.00)

((Ada Lovelaco) 50000.00 338519)

Notc Ihat this lunction docs not actually updatc thc rccord ttsclf but produccs a moditicd copy of thc record. This updated vcrsion may bc savcd by binding it to a głobal \anabic using setf (Scction 15.1.8). Although LISP providcs forms thal allow a partścular element tn a list to bc modiAcd in thc original structure (i.c. without mafcing a copy). good LISP programming style generałly avoids their usc. and they are not ooicred in this tcxL For LISP applicalions imolving all but extremeły large structure*. modificaiions are generał ł> done by creating a new copy of thc structure.

In thc above e\amplcs. wt crcatcd an abstract data type for cmployec record*. The warious acccss and updatc functions dcfincd in this scction impłement a spccializcd łan-gu*gc appropriatc to thc mcaning of thc records. frccing thc programmer frora. cooccms łbom thc actual list siructurcs bcing uscd to implcmcnt thc records. This simplifics thc derelopmcnt of highcr-lcycl codę. as woli as making that codc much casacr to maintain md tindcistand.

Generally. Al programs manipulatc large amounts of varicd knowlcdgc about problem domains. The data siructurcs uscd to represent this knowlcdgc. such as objeets and semantie nctworks. arc complcx. and humans generał ly find it casicr to relate to this knowlcdgc in lernis of its mcaning rather than thc panicular syntax of its intcmal representation. Thereforc. data abslraction tcchniqucs. always good Computer science, are cncmial tools for thc Al programmer. Heca usc of thc casc with which LISP supports thc dcfimiion of new functions. it is an ideał language for data abslraction.

15.1.6 Lists as Rccursive Struclures

bd»eprevious scction. we uscd nth and list to implcmcnt acccss functions for records ia a sńaplc ~cmplpycc” datahase. Bccausc all cmployec records were of a determmate length (threc clcmcnts). thcsc tw© functions were sufReiem lo acccss thc ficlds of records. Howocr. thcsc functions arc not adcquate lor performing opcratkms on lists of unknown leogth, such as scarching through an unspccificd numbcr of cmployec records. To do this. we musi bc a Mc to scan a list itcratńdy or recursńdy. aerminatmg wben ccrtain caadilions arc met (c.g.. thc desired rccord is found) or thc list is exhausted In this scctioa u iniroducc list operations. along with thc usc of reetnsion to creatc lisi-pioocssmg functions.

691

CHAPTER 15/ANINTROOUCTIONTOUSP