Due by 11:59pm on Friday, 5/2
Homework 10 is in two parts, of which this is the second. The solutions to this part are in logic notation.
Submission. See the online submission instructions. Submit the files for hw10a and hw10b together as hw10. We have provided a hw10b.logic starter file for the questions below.
Readings. Sections 4.3 <http://composingprograms.com/pages/43-declarative-programming.html>`_ and 4.4 of Composing Programs.
To complete this homework, you will need to use the Prolog-in-Python interpreter described in lecture. On the instructional machines, use the command logic hw10b.logic. You can run the tests in the starter file with logic -t hw10b.logic. The bare command logic allows you to use the logic interpreter interactively.
To run these at home, first determine what version of Python you are running (on Unix systems, the command to do so is python3 --version), which can be 3.2 or 3.3. Then download the appropriate ZIP file: either ~cs61a/lib/logic-32.zip or ~cs61a/lib/logic-33.zip. Unzip the downloaded file into the same directory that contains your homework file. You can run the logic interpreter with python3 logic.py hw10b.logic or (to run tests) python3 logic.py -t hw10b.logic. If you have neither of these versions of Python 3, but do have all your changes to scheme_reader.py in Project 4 working, then you should be able to use the Python files from your project together with logic.py and logic_test.py from the ZIP file.
Q1. Write facts for add-to-all, which declares a relation between an item, a list of lists, and a second list whose elements are the elements of the first list with the item added to the front of each:
; YOUR CODE HERE (query (add-to-all a ((b) (c d)) ((a b) (a c d)))) ; expect Success! (query (add-to-all a ((b c) (b) (foo)) ?what)) ; expect Success! ; what: ((a b c) (a b) (a foo)) (query (add-to-all ?what ((c) (d e) ()) ((b c) (b d e) (b)))) ; expect Success! ; what: b (query (add-to-all ?what ?list ((b c) (d e) (b)))) ; expect Failed.
Q2. Write facts for sublists, which relates a list of items to another list that contains every possible sublist of the first. A sublist of a list is a list that contains zero or more items from the original list, in the same order that they appear in the original list:
(fact (append () ?a ?a))
(fact (append (?x . ?r) ?b (?x . ?c))
(append ?r ?b ?c))
; YOUR CODE HERE
(query (sublists (1 2 3) ?subs))
; expect Success! ; subs: (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
Q3. Below is a list of fruits. Write facts for fruits-tail, which relates sublists of fruits starting at a given fruit:
(fact (fruits apple banana cherry date elderberry fig guava)) ; YOUR CODE HERE (query (fruits-tail date elderberry fig guava)) ; expect Success! (query (fruits-tail banana . ?after-banana)) ; expect Success! ; after-banana: (cherry date elderberry fig guava) (query (fruits-tail ?e fig guava)) ; expect Success! ; e: elderberry
Q4. Write facts for fruits-range, which relates a ?before and ?after fruit to a list of the fruits in ?between, which is never empty. You may want to use the prefix fact from discussion section, along with other facts that you create yourself:
(fact (prefix () ?s))
(fact (prefix (?first . ?p) (?first . ?s))
(prefix ?p ?s))
; YOUR CODE HERE
(query (fruit-range cherry guava (date elderberry fig)))
; expect Success!
(query (fruit-range cherry elderberry date))
; expect Failed.
(query (fruit-range cherry elderberry ?between))
; expect Success! ; between: (date)
(query (fruit-range cherry date ()))
; expect Failed.
(query (fruit-range banana fig ?between))
; expect Success! ; between: (cherry date elderberry)
Q5. The Prolog language was originally invented to aid research in natural language processing. Consider a set of grammatical rules such as these:
; sentence : optional-article noun verb optional-article noun ; optional-article : "the" | <empty> ; noun : "boy" | "cat" ; verb : "carries" | "feeds"
(Read the | symbol as "or" and <empty> as an empty sequence of words.) The rule for sentence, for example says "a sentence may be formed from an optional-article, followed by a noun, followed by a verb, another optional-article, and another noun." These rules describe sentences such as "the boy feeds cat".
We can write this same description with logic rules. To do so, we'll translate a term such as noun into a relation (noun ?p ?r), which is intended to mean "?p is a sequence of words that begins with a noun and then continues with the sequence ?r". So, for example:
; logic> (query (noun (boy feeds cat) (feeds cat))) ; Success! ; logic> (query (sentence (the boy feeds the cat and so forth) (and so forth))) ; Success! ; logic> (query (noun (boy cat feeds) ?r)) ; Success! ; r: (cat feeds) ; logic> (query (optional-article (a boy) (boy))) ; Success! ; logic> (query (optional-article (cat feeds boy) (cat feeds boy))) ; Success!
Here are rules that define noun and verb to have the desired meanings. Devise the necessary facts for sentence and optional-article. Hint: the rule for sentence will have to have hypotheses that use the other relations:
(fact (noun (boy . ?r) ?r)) (fact (noun (cat . ?r) ?r)) (fact (verb (carries . ?r) ?r)) (fact (verb (feeds . ?r) ?r)) ; YOUR CODE HERE (query (optional-article (the boy) (boy))) ; expect Success! (query (optional-article (cat feeds boy) (cat feeds boy))) ; expect Success! (query (optional-article (the cat feeds boy) (cat feeds boy))) ; expect Success! (query (optional-article (the cat feeds boy) (the cat feeds boy))) ; expect Success! (query (optional-article (feeds boy) ?x)) ; expect Success! ; x: (feeds boy) (query (optional-article ?x (cat feeds boy))) ; expect Success! ; x: (cat feeds boy) ; x: (the cat feeds boy) (query (sentence (the boy carries cat) ())) ; expect Success! (query (sentence (the ?sub carries the ?obj) ())) ; expect Success! ; sub: boy obj: boy ; sub: boy obj: cat ; sub: cat obj: boy ; sub: cat obj: cat
When you are finished, all tests should pass when you run python logic.py -t hw10b.logic.