Due by 11:59pm on Thursday, 12/5
Submission. See the online submission instructions. We have provided a hw11.logic starter file for the questions below.
Readings. Sections 4.3 and 4.4 of Composing Programs.
To complete this homework, you will need to use your Scheme interpreter from project 4. Place the (updated) logic.py interpreter and the hw11.logic starter file in the same directory as your Scheme interpreter. Then, you can evaluate the starter file by: python3 logic.py hw11.logic. You can run the tests in the starter file by: python3 logic.py -t hw11.logic.
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:
(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 possibly 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))
(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)) (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))
(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. In lecture, we defined addition among small positive integers. Extend this system by writing facts for max, which relates two numbers to their maximum:
(fact (increment 1 2)) (fact (increment 2 3)) (fact (increment 3 4)) (fact (increment 4 5)) (fact (increment 5 6)) (fact (increment 6 7)) (fact (increment 7 8)) (fact (increment 8 9)) (query (max 2 4 4) (max 4 2 4) (max 4 4 4)) ; expect Success! (query (max 3 ?x ?x) (max ?x 5 5)) ; expect Success! ; x: 3 ; x: 4 ; x: 5 (query (max 1 2 3)) ; expect Failed.
Q6. Recall that the reduce function in Python combines a sequence of values using a two-argument function. Write facts for reduce-to, which relates the ?value that would be returned by reducing a list of values using an operation such as max or add:
(fact (add 1 ?x ?x+1)
(increment ?x ?x+1))
(fact (add ?x+1 ?y ?z+1)
(increment ?x ?x+1)
(increment ?z ?z+1)
(add ?x ?y ?z))
(query (reduce-to ?value add 1 1 2 3))
; expect Success! ; value: 7
(query (reduce-to ?value max 1 2 4 1 3 1))
; expect Success! ; value: 4
(query (reduce-to 4 add . ?addends))
; expect Success! ; addends: (1 3) ; addends: (2 2) ; addends: (3 1) ; addends: (1 1 2) ; addends: (1 2 1) ; addends: (1 1 1 1) ; addends: (2 1 1)
When you are finished, all tests should pass when you run python logic.py -t hw11.logic.