61A Homework 13

Due by 11:59pm on TUESDAY, 8/13

Submission. See the online submission instructions. We have provided a starter file for the questions below.

Readings. Section 4.3 and 4.4 of the online lecture notes.

To complete this homework, you will need to use your Scheme interpreter from project 4. Place the Logic interpreter, as well as the starter file, in the same directory as your Scheme interpreter. Then you can load the starter file by: python3 logic.py -load hw13.logic. You can run the tests in the starter file by: python3 logic.py -test hw13.logic.

Note: If your Scheme interpreter prints out None after defining a fact or making a query, change the line if not quiet: in read_eval_print_loop in scheme.py to to if not quiet and result is not None:. (You may turn in project 4 with this change applied, so you don't have to revert it when submitting the project.) Only two things need to be working in your Scheme interpreter for the Logic interpreter to work: dotted lists and Frame.lookup.

Q1. The following are various facts concerning the relationships between characters in the Harry Potter universe:

;;; Facts about the families of the fictional 'Harry Potter' universe.
(fact (married arthur molly))
(fact (married molly arthur))

(fact (father arthur bill))
(fact (father arthur charlie))
(fact (father arthur percy))
(fact (father arthur fred))
(fact (father arthur george))
(fact (father arthur ron))
(fact (father arthur ginny))

(fact (mother molly bill))
(fact (mother molly charlie))
(fact (mother molly percy))
(fact (mother molly fred))
(fact (mother molly george))
(fact (mother molly ron))
(fact (mother molly ginny))

(fact (father james harry))
(fact (mother lily harry))

(fact (married harry ginny))
(fact (married ginny harry))

(fact (father harry james_sirius))
(fact (father harry albus_severus))
(fact (father harry lily_luna))

(fact (mother ginny james_sirius))
(fact (mother ginny albus_severus))
(fact (mother ginny lily_luna))

(fact (married ron hermione))
(fact (married hermione ron))

(fact (father ron rose))
(fact (father ron hugo))

(fact (mother hermione rose))
(fact (mother hermione hugo))

(fact (married bill fleur))
(fact (married fleur bill))

(fact (father bill victoire))
(fact (father bill louis))
(fact (father bill dominique))

(fact (mother fleur victoire))
(fact (mother fleur louis))
(fact (mother fleur Dominique))

(fact (parent ?who ?child)
      (father ?who ?child))

(fact (parent ?who ?child)
      (mother ?who ?child))

Write a query to list all the children of Molly (Weasley):

; YourCodeHere
; expect Success! ; child: bill ; child: charlie ; child: percy ; child: fred ; child: george ; child: ron ; child: ginny

Now write a query to list all the people who are married and their spouses:

; YourCodeHere
; expect Success! ; x: arthur y: molly ; x: molly     y: arthur ; x: harry    y: ginny ; x: ginny     y: harry ; x: ron       y: hermione ; x: hermione       y: ron ; x: bill        y: fleur ; x: fleur     y: bill

Finally, write a fact to determine if a person is a sibling of another person (two people are siblings if they have the same parent):

; YourCodeHere

;;; Q1 tests
(query (sibling ron fred))
; expect Success!
(query (sibling fred ?who))
; expect Success! ; who: bill ; who: charlie ; who: percy ; who: fred ; who: george ; who: ron ; who: ginny ; who: bill ; who: charlie ; who: percy ; who: fred ; who: george ; who: ron ; who: ginny

Why is each child repeated twice? Think about how unification processes this query.

Q2. A molecule of deoxyribonucleic acid, or DNA, consists of two long strands of four nucleotides: adenine (A), thymine (T), cytosine (C), and guanine (G). The two strands are complementary to each other. This means that a nucleotide on one strand is bonded to its complement on the other: adenine will be bound to thymine, and cytosine will be bound to guanine.

The following are some facts about the complements of these nucleotides, as well as some list manipulation facts:

;;; Facts about DNA
(fact (complementary t a))
(fact (complementary a t))
(fact (complementary c g))
(fact (complementary g c))

;;; List manipulation
(fact (equal-lists () ()))
(fact (equal-lists (?e . ?r) (?e . ?s))
      (equal-lists ?r ?s))

(fact (append () ?a ?a))
(fact (append (?x . ?r) ?b (?x . ?c))
      (append ?r ?b ?c))

(fact (member ?x (?x . ?r)))
(fact (member ?x (?y . ?r))
      (member ?x ?r))

(fact (reverse () ()))
(fact (reverse (?x . ?r) ?y)
      (reverse ?r ?s)
      (append ?s (?x) ?y))

Using these facts, write facts for rev_comp_strand, which relates a strand of DNA, represented as an arbitrarily long list of four symbols, with its reverse complement, which is another strand of DNA that has the complementary nucleotides, but in reverse order. See the test below for an example:

; YourCodeHere

;;; Q2 tests
(query (rev-comp-strand (t c t g a) ?what))
; expect Success! ; what: (t c a g a)

Q3. 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. See the test below for examples:

; YourCodeHere

;;; Q3 tests
(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) (b e) (b))))
; expect Success! ; what: b   list: ((c) (e) ())
(query (add-to-all ?what ?list ((b c) (d e) (b))))
; expect Failed.

Q4. 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. See the test below for an example:

; YourCodeHere

;;; Q4 tests
(query (sublists (1 2 3) ?what))
; expect Success! ; what: (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Q5. Write facts for unzip, which relates a larger list to two smaller lists, the first of which has all the elements at even positions in the larger list (starting at 0), and the second of which has all the elements at odd positions. You may assume that the larger list has an even number of elements:

; YourCodeHere

;;; Q5 tests
(query (unzip (a b c d e f) ?odds ?evens))
; expect Success! ; odds: (a c e)     evens: (b d f)
(query (unzip ?what (a b c) (d e f)))
; expect Success! ; what: (a d b e c f)

Q6. For this question, we will invent an arithmetic system for Logic. We will use a unary representation of non-negative numbers, where each number is represented as a list (of any item) that is as long as the number is big. (In the examples below, we will represent a number as a list of 1s. Any item can be used instead, as long as the same item is used for all numbers.) For example, the list (1 1 1) represents the number 3, and 0 is represented by the empty list ().

Write facts for +, which relates two numbers and their sum.

Hint: Think about how + is related the facts for list manipulation:

; YourCodeHere

;;; + tests
(query (+ (1 1 1) (1 1) ?what))
; expect Success! ; what: (1 1 1 1 1)
(query (+ (1 1 1) ?what (1 1 1 1 1 1 1)))
; expect Success! ; what: (1 1 1 1)

Write facts for -, which relates a bigger number and a smaller number to their difference.

Hint: Think about how - relates to +:

; YourCodeHere

;;; - tests
(query (- (1 1 1) (1 1) ?what))
; expect Success! ; what: (1)
(query (- (1 1 1 1 1 1 1) ?what (1 1 1)))
; expect Success! ; what: (1 1 1 1)

Write facts for *, which relates to numbers and their product.

Hint: The product of two numbers can be defined recursively using addition:

; YourCodeHere

;;; * tests
(query (* (1 1 1) (1 1) ?what))
; expect Success! ; what: (1 1 1 1 1 1)

Write facts for >, <, >=, and <=, which compare two numbers.

Hint: The < comparison is related to >, and similarly for <= and >=:

; YourCodeHere

;;; <, >, <=, <= tests
(query (> (1 1 1 1) (1 1 1)))
; expect Success!
(query (< (1 1 1 1) (1 1 1)))
; expect Failed.
(query (> (1 1) (1 1 1)))
; expect Failed.
(query (< (1 1) (1 1 1)))
; expect Success!
(query (> (1 1 1) (1 1 1)))
; expect Failed.
(query (< (1 1 1) (1 1 1)))
; expect Failed.
(query (>= (1 1 1 1) (1 1 1)))
; expect Success!
(query (<= (1 1 1 1) (1 1 1)))
; expect Failed.
(query (>= (1 1) (1 1 1)))
; expect Failed.
(query (<= (1 1) (1 1 1)))
; expect Success!
(query (>= (1 1 1) (1 1 1)))
; expect Success!
(query (<= (1 1 1) (1 1 1)))
; expect Success!

Write facts for = and !=, which relate two numbers if they are equal or not equal, respectively.

Hint: You may find - useful here:

; YourCodeHere

;;; =, != tests
(query (= (1 1 1 1) (1 1 1)))
; expect Failed.
(query (!= (1 1 1 1) (1 1 1)))
; expect Success!
(query (= (1 1 1 1) (1 1 1 1)))
; expect Success!
(query (!= (1 1 1 1) (1 1 1 1)))
; expect Failed.
(query (= (1 1 1) (1 1 1 1)))
; expect Failed.
(query (!= (1 1 1) (1 1 1 1)))
; expect Success!

Write facts for /, which relates two numbers with their quotient and remainder.

Hint: If a number \(n\) is divided by divisor \(d\) , then the quotient \(q\) and remainder \(r\) are given by the following: \(n = d * q + r\) , where \(r < d\) :

; YourCodeHere

;;; / tests
(query (/ (1 1 1 1 1 1) (1 1 1) ?quo ?rem))
; expect Success! ; quo: (1 1)        rem: ()
(query (/ (1 1 1 1 1 1) (1 1 1 1) ?quo ?rem))
; expect Success! ; quo: (1)  rem: (1 1)

When you are finished, all tests should pass when you run python logic.py -test hw13.logic.