New version page

Berkeley COMPSCI 61A - Logic programming

Documents in this Course
Lecture 1

Lecture 1

68 pages

Midterm

Midterm

5 pages

Midterm

Midterm

6 pages

Lecture 35

Lecture 35

250 pages

Lecture 14

Lecture 14

125 pages

Lecture 2

Lecture 2

159 pages

Lecture 6

Lecture 6

113 pages

Lecture 3

Lecture 3

162 pages

Homework

Homework

25 pages

Lecture 13

Lecture 13

117 pages

Lecture 29

Lecture 29

104 pages

Lecture 11

Lecture 11

173 pages

Lecture 7

Lecture 7

104 pages

Midterm

Midterm

6 pages

Midterm

Midterm

6 pages

Lecture 8

Lecture 8

108 pages

Lab 4

Lab 4

4 pages

Lecture 7

Lecture 7

52 pages

Lecture 20

Lecture 20

129 pages

Lecture 15

Lecture 15

132 pages

Lecture 9

Lecture 9

95 pages

Lecture 30

Lecture 30

108 pages

Lecture 17

Lecture 17

106 pages

Load more
Upgrade to remove ads

This preview shows page 1-2 out of 6 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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%[email protected] ,%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%[email protected]%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&note&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
Download Logic programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logic programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logic programming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?