Justin'Chen'C S6 1A 'Sprin g'20 10 '–'notes'c o u rt e sy 'o f 'C h u n g 'Wu' 1'CS61A&Notes&–&Week&14:&Logic&programming&Paradigm&Shift&Again&(Why&Not?)&'With%this%many%paradigm%shifts%in%a%single%semester,%we%expect%you%to%at%least%be%able%to%pronounce%the%word%“paradigm”%correctly%after%this%class.%%To%reiterate,%we%are%now%in%the%realm%of%logic%or%declarative%programming,%at%least%for%a%week.%Here%in%the%magical%world%of%the%non@imperative ,%w e %ca n %sa y %ex ac tly %w h a t%w e %w a n t%–%and%have %t h e %co mputer%figu re %o u t %h o w %t o %g e t%it%f o r%u s .%In s te a d %o f%s a y in g %h o w%to%get%the%solution,%we%describe %–%declare%–%what%the%so lu tio n %lo o k s %like .%'The%mind@boggling%part%of%all%of%this%is%that%it%all%just%works%through%pattern%matching.%That%is,%there%are%no%“procedures”%in%the%way%you’re%used%to;%when%you%write%out%a%parenthesized%statement,%it’s%not%really%a%procedure%ca ll,%a n d %y o u %d o n ’t%r e a lly%get%a%return %va lu e .%Instead,%eit h er%y o u %g e t%e n trie s%fr o m %s o me%databa se ,%o r%n o th in g %a t%a ll.%'Be&Assertive&And&Ask&Questions&(Fitter,&Happier,&More&Productive)&'There'are'two'things'you'can'type'into'our'query'system:'an'assertion'and'a'query. 'A'query'asks'wheth e r 'a'g iv e n 'e xp r es s io n 'matches'some'fact'that’s 'a lre a d y 'in 'th e 'd a ta b a s e. 'If'th e 'q u e ry 'matches,'the n 't h e 'sy st e m'prints'out'all'matches'in'the'database.'If'the'query'doesn’t'match'to'anything,'you'get'no'results. 'An'assertion'states'somet h in g 'tr u e ;'it'a d d s'a n 'e n t ry 'to 't h e'd a t a b as e .'Y o u 'c an'either'asse rt'a 's imple'fact,'or'a 'cla s s'o f 'fa ct s'( sp e c ifie d 'by'a'“rule”). 'So'here’s'an'assertion'that'you’ve'seen:'(assert! (justin likes chocolate)) 'You'can'also'assert'rules.'In'general,'a'rule'lo o k s 'like :'(rule <conclusion> <subconditions>) 'And'it’s'read:'“conclusion'is'true'if'and'only'if'all'the'subconditions'are'true”.'Note'that'you'don’t'have'to'have'subconditions!'Here’s'a'very'simple'rule:'' (rule (same ?x ?x)) 'The'above'says'two'things'satisfy'the'“same”'relation'if'they'can'be'bound'to'the'same'variable.'It’s'deceptively'simple'–'no'subconditions'are'provided'to'check'the'“sameness”'of'the'two'argume nts.'Instead,'either'the'query'system'can'bind'the'two'arguments'to'the'same'variable'?x'–'and'it'can'on ly 'd o 's o 'if'th e 't w o 'a r e'e q u iv a le n t'–'or,'the'que r y's ys te m'can’t. 'And,'of'course,'the'rule'of'love:''(assert! (rule (?person1 loves ?person2) (and (?person1 likes ?something) (?person2 likes ?something) (not (same ?person1 ?person2)))))) 'The'above'rule'means'that'?person1'loves'?person2'if'the'th r ee 'c o n d itio n s 'fo llo wing'can'all'b e 'sa t isfie d ' –'that'is,'?person1'likes'?something'that'?person2'als o 'like s ,'a n d 'th a t'?person1'is 'n o t 'th e 'sa me'person 'as '?person2. 'Note'the'“and”'special'form'enclosing'the'three'conditions'–'an'entry'in 't h e'database'm u s t 'sa tis fy 'A L L't h re e 'co n d it io n s 'to 'b e 'a 'match'for'the'query.'If'you'would'like'a'rule'to'be'satisfied'by'this'or'that'condition,'yo u 'c a n 'e ith e r 'u se 't h e 'or's p e cia l'fo r m'in'the'obvious'way,'or'you'can'make'two'separate'rules.'For'example,'if'one'loves'another'if'they'like'the'same'things'or'if'?person1'is'a'parent'of'?person2,'we'would'add 'th e 'f o llo wing'to'the'd a t abase: ' (assert! (rule (?person1 loves ?person2) (parent ?person1 ?person2))) 'Note'the'new'rule'does'NOT'“overwrite”'the'previous'rule;'this'is'not'the'same'thing'as'redefining'a'procedure'in'Scheme.'Instead,'the'new'rule'comp lem en ts'the 'previo us'rule . '''Justin'Chen'C S6 1A 'Sprin g'20 10 '–'notes'c o u rt e sy 'o f 'C h u n g 'Wu' 2'To'add'to'confusion,'you'can'also'use'the'and'special'form'for'qu e r ies .'F o r'e x a mple, ' (and (justin loves ?someone) (?someone likes chocolate)) is'a'query'th a t'fin d s 'a'p e rs on 'J u stin 'lo v es 'b ec a us e't h at 'p ers o n 'like s'c h o co la te .''There’s'another'special'form'called'lisp-value:'(lisp-value <pred?> <arg1, arg2, ...>) 'The'lispVvalue'condition'is'satisfied'if'the'given'pred?'applied'to'the 'list 'o f'args'r et u rn '#t.'Fo r'e xa m p le,' (lisp-value even? 4)'is'satisfied,'b u t '(lisp-value < 3 4 1)'is'not.'lisp-value'is'u s e fu l'mostly'for'nu merical'comparisons'(things'that'the'logic'system'isn’t'so'great'a t). 'A¬e&on&writing&rules:'it’s'often'tempting 't o 'th in k 'in 'te rms'of'proce d u re s '–'“this'rule'tak es 'in 's o 'a n d 'so ,'a n d 'r et u rn s 's u ch 'a n d 'such”.'This'is'not'the'right'way'to'approach'these'problems'–'re member,'no t h in g 'is'r e tu rn e d ;'a n 'e x p re s sio n 'o r 'q u e ry 'e ith e r'h a s 'a 'match,'or'it'doesn’t.'So'often,'you'need'to'have'both'the'“arguments”'and'the'“return'value”'in'the'expression'of'the'rule,'and'the'rule'is'satisfied'if'“return'value” 'is'wh at'w ou ld 'be'retu rn ed 'if'the'rule'w ere'a 'no rm al'Sc heme'procedure'given 'the'“a rgu m en ts”.'Always'keep'in'mind'that'everything'is'a'Yes'or'No'question,'and'your'rule'can'only'say'if'something'is'a'correct'answer'or'not.'So'when'you'write'a'rule,'instead'of'trying'to'“build”'to'a'solution'like'you’ve'been'doing'in'Scheme,'think'of'it'as'trying'to'check'if'a'given'solution'is'correct'or'not. 'In'fact,'this&is&so&importa nt&I’ll&say&it&again: 'w h e n 'y o u 'd e fin e 'ru le s ,'d o n ’t't h in k'o f 'it'a s'd e fining'proced u re s 'in 'th e 't ra d itio n a l's e nse.'Instead,'th in k 'o f'it'a s,'given%arguments%and%a%proposed%answer,%check%if%the%answer%is%correct.'The'proposed 'a n swer'can'eith er 'b e 'derived'from'the'arguments,'or'it'can’t. 'A'different'approach'for'writing'declarative'rules'is'to'try'to'convert'a'Scheme'program'to'a'rule.'For'example,'let’s'take'a'crack'at'the'popular'append: ' (define (append ls1 ls2) (cond ((null? ls1) ls2) (else (cons (car ls1) (append (cdr ls1) ls2)))) 'The'cond'specifies'an '“ e ith e rVor”'relationship;'either'ls1'is'null'or'it'is'not.'This 'im p lie s'th a t,'fo r 'log ic 'p ro gr amming,'we’d 'n e ed 'two'separate'rules,'each'corresponding'to'each'cond'clause .'T h e 'fir st 'o n e 'is's tr aig h t fo rward: ' (rule (append () ?ls2 ?ls2)) 'The'second'cond'clause'break s'ls1'in t o 'two'parts'–'it
View Full Document