Lab 15: Logic

Due at 11:59pm on No due date.

Starter Files

Download lab15.zip. Inside the archive, you will find starter files for the questions in this lab.

Submission

You do not need to submit anything for this lab.

We've released the solutions so that you can double check your answers and use this lab as a resource for studying. We encourage you to try solving the questions on your own first before consulting the solutions!

Introduction

In Declarative Programming, we aim to define facts about our universe. With these in place, we can make queries in the form of assertions. The system will then check if the query is true, based on a database of facts. It will inform us of what replacements for the variables will make the query true.

The language we will use is called Logic. You can download a version of Logic here. There is also an online Logic interpreter that contains a subset of our version of Logic; it doesn't support arithmetic or the not relation, but it is enough to complete this lab.

In Logic, the primitive data types are called symbols: these include numbers and strings. Unlike other languages we have seen in this course, numbers are not evaluated: they are still symbols, but they do not have their regular numerical meaning. Variables in Logic are denoted with a ? mark preceding the name. So for example, ?x represents the variable x. A relation is a named tuple with a truth value.

The next thing we need to do is define facts about our universe. Facts are defined using a combination that starts with the fact keyword. The first relation that follows is the conclusion, and any remaining relations are hypotheses. All hypotheses must be satisfied for the conclusion to be valid.

(fact (food-chain ?creature1 ?creature2)
      (eats ?creature1 ?creature3)
      (eats ?creature3 ?creature2))

Here we have defined the fact for a food chain: If creature1 eats creature3, and creature3 eats creature2, then creature1 is higher on the food chain than creature2.

Simple facts contain only a conclusion relation, which is always true.

(fact (eats shark big-fish))
(fact (eats big-fish small-fish))
(fact (eats domo kitten))
(fact (eats kitten small-fish))
(fact (eats zombie brain))

Here we have defined a few simple facts: that in our universe, sharks eat big-fish, big-fish eat small-fish, Domos eat kittens, kittens eat small-fish, zombies eat brains. Poor kittens.

Queries are combinations that start with the query keyword. The interpreter prints the truth value (either Success! or Failed.). If there are variables inside of the query, the interpreter will print all possible mappings that satisfy the query.

Try the following queries in your Logic interpreter after you've defined the previous facts:

(query (eats zombie brain))
; expect Succcess!

(query (eats domo zombie))
; expect Failed.

(query (eats zombie ?what))
; expect Success! ; what: brain

(query (?what zombie brain))
; expect Success! ; what: eats

We're first asking Logic whether a zombie eats brains (the answer is Success!) and if a domo eats zombies (the answer is Failed). Then we ask whether a zombie can eat something (the answer is Success!), and Logic will figure out for us, based on predefined facts in our universe, what a zombie eats. If there are more possible values for what a zombie can eat, then Logic will print out all of the possible values. In the end, we ask if there is a relation between zombie and brains (the answer is Success!). Logic will then print out the relation based on predefined facts.

Question 1: Food chain

The food-chain facts mentioned above are already defined in your starter file. You can load a file into your Logic interpreter with the following command:

python3 logic -load filename.logic

In your interpreter, write Logic queries that answers the following questions:

  1. Do sharks eat big-fish?
  2. What animal is higher on the food chain than small-fish?
  3. What animals (if any, or multiple) eat small-fish?
  4. What animals (if any, or multiple) eat sharks?
  5. What animals (if any, or multiple) eat zombies?
  6. What is the relation (if any, or multiple) between shark and small-fish?
(query (eats shark big-fish))
(query (food-chain ?what small-fish))
(query (eats ?what small-fish))
(query (eats ?what shark))
(query (eats ?what zombie))
(query (?what shark small-fish))

Recursive facts

Currently, the food-chain fact is a little lacking. A query (query (food-chain A B)) will only output Success! if A and B are separated by only one animal. For instance, if I added the following facts:

(fact (eats shark big-fish))
(fact (eats big-fish small-fish))
(fact (eats small-fish shrimp))

I'd like the food-chain to output that shark is higher on the food chain than shrimp. Currently, the food-chain fact doesn't do this:

logic> (query (food-chain shark shrimp))
Failed.

We will define the food-chain-v2 fact that correctly handles arbitrary length hierarchies. We'll use the following logic:

  • Given animals A and B, A is on top of the food chain of B if:
  • A eats B, OR
  • There exists an animal C such that A eats C, and C dominates B.

Notice we have two different cases for the food-chain-v2 fact. We can express different cases of a fact simply by entering in each case one at a time:

(fact (food-chain-v2 ?a ?b)
      (eats ?a ?b))
(fact (food-chain-v2 ?a ?b)
      (eats ?a ?c)
      (food-chain-v2 ?c ?b))

Now, if we try the same query as before, we get a Success!:

logic> (query (food-chain-v2 shark shrimp))
Success!

Take a few moments and read through how the above facts work, and how it implements the approach we outlined. In particular, make a few queries to food-chain-v2 — for instance, try retrieving all animals that dominate shrimp!

Note: In the Logic system, multiple 'definitions' of a fact can exist at the same time (as in food-chain-v2) — definitions don't overwrite each other. Instead, they are all checked when you execute a query against that particular fact.

Example: Append

Next, we will define append, Logic style.

As we've done in the past, let's try to explain how append works recursively. For instance, in Scheme, given two lists (1 2 3) and (5 7), the result of (append (1 2 3) (5 7)) is:

(1 2 3 5 7) = (cons 1 (append (2 3) (5 7)))

In Scheme, the full solution would be:

(define (append a b)
        (if (null? a)
            b
            (cons (car a) (append (cdr a) b))))

Thus, we've broken append up into two different cases. Let's start translating this idea into Logic! The first base case is relatively straightforward:

(fact (append () ?b ?b ))

This takes care of cases like

logic> (query (append () (1 2 3) ?what))
(1 2 3)

So far so good! Now, we have to handle the general (recursive) case:

;;                  A        B       C
(fact (append (?car . ?cdr) ?b (?car . ?partial)) (append ?cdr ?b ?partial))

This translates to: the list A appended to B is C if C is the result of sticking the CAR of A to the result of appending the CDR of A to B. Do you see how the Logic code corresponds to the recursive case of the Scheme function definition? As a summary, here is the complete definition for append:

(fact (append () ?b ?b ))
(fact (append (?a . ?r) ?y (?a . ?z))
      (append ?r ?y ?z))

Question 2: Append

The append fact has been defined for you in the starter file. You can load a file into the Logic interpreter with the following command:

python3 logic -load filename.logic

Using the append fact, issue the following queries, and ruminate on the outputs. Note that some of these queries might result in multiple possible outputs.

logic> (query (append (1 2 3) (4 5) (1 2 3 4 5)))

______
Success!

logic> (query (append (1 2) (5 8) ?what))

______
Success!
what: (1 2 5 8)

logic> (query (append (a b c) ?what (a b c oh mai gawd)))

______
Success!
what: (oh mai gawd)

logic> (query (append ?what (so cool) (this is so cool)))

______
Success!
what: (this is)

logic> (query (append ?what1 ?what2 (will this really work)))

______
Success!
what1: ()                        what2: (will this really work)
what1: (will)                    what2: (this really work)
what1: (will this)               what2: (really work)
what1: (will this really)        what2: (work)
what1: (will this really work)   what2: ()

Lists in Logic

Question 3: Last element

Define a set of facts for last-element, which relates an element and a list in the following way: if the element is the last element of the list, last-element will report Success!.

; YOUR CODE HERE

(fact (last-element (?x) ?x))
(fact (last-element (?car . ?cdr) ?x)
      (last-element ?cdr ?x))

(query (last-element (a b c) c))
; expect Success!

(query (last-element (3) ?x))
; expect Success! ; x: 3

(query (last-element (1 2 3) ?x))
; expect Success! ; x: 3

(query (last-element (2 ?x) 3))
; expect Success! ; x: 3

Question 4: Firsts

Write a fact "firsts" that, when input with a list of lists, gives us the first element of each list.

What's your base case? What's your recursive case?

; YOUR CODE HERE

(fact (firsts () ()))
(fact (firsts ((?x . ?r) . ?ls) (?x . ?xs))
      (firsts ?ls ?xs))

(query (firsts ((1 2 3 4) (2 3 4 5) (1 2 3 4) (1 2 3 2)) ?x))
; expect Success! ; x: (1 2 1 1)

(query (firsts ((2 3 4) (3 4 5) (2 3 4) (2 3 2)) ?y))
; expect Success! ; y: (2 3 2 2)

Question 5: Rests

Now, instead of getting us the firsts, let's gather the rests!

; YOUR CODE HERE

(fact (rests () ()))
(fact (rests ((?_ . ?r) . ?ls) (?r . ?xs))
      (rests ?ls ?xs))

(query (rests ((1 2 3 4) (2 3 4 5) (1 2 3 4) (1 2 3 2)) ?x))
; Success! ; x: ((2 3 4) (3 4 5) (2 3 4) (2 3 2))

(query (rests ((2 3 4) (3 4 5) (2 3 4) (2 3 2)) ?y))
; Success! ; y: ((3 4) (4 5) (3 4) (3 2))

Solving Sudoku

Assume we have the two facts insert and anagram as follows

(fact (insert ?a ?r (?a . ?r)))
(fact (insert ?a (?b . ?r) (?b . ?s)) (insert ?a ?r ?s))

(fact (anagram () ()))
(fact (anagram (?a . ?r) ?b) (insert ?a ?s ?b) (anagram ?r ?s))

With our anagram fact, we can write a few more facts to help us solve a 4 by 4 Sudoku puzzle! In our version of Sudoku, our objective is to fill a 4x4 grid such that each column and each row of our simple grid contain all of the digits from 1 to 4.

Question 6: Boxes

Let's start by defining our grid using our fact called boxes. Fill in the remainder of the fact.

    (fact (boxes ((?a ?b ?c ?d)
                 (?e ?f ?g ?h)
                 (?i ?j ?k ?l)
                 (?m ?n ?o ?p)))
        (anagram (?a ?b ?e ?f) (1 2 3 4))

        ; YOUR CODE HERE

        (anagram (?c ?d ?g ?h) (1 2 3 4))
        (anagram (?i ?j ?m ?n) (1 2 3 4))
        (anagram (?k ?l ?o ?p) (1 2 3 4))
                                        )

Question 7: Rows

Next, let's define a fact of specifying the rules for each row in our grid. The input to rows will be the entire 4x4 grid. Fill in the rest of the facts in the prompt below:

(fact (rows ()))
(fact (rows (?x . ?xs))

      ; YOUR CODE HERE

      (anagram ?x (1 2 3 4))
      (rows ?xs)
      )

(query (rows (( 1  2  4 ?a)
              (?b  3  2  1)
              (?c  4  3  2)
              ( 2  4  3 ?d))))
; expect Success! ; a: 3 ; b: 4 ; c: 1 ; d: 1

Question 8: Columns

Next, let's define the fact specifying the rules for each column in our grid. Again, remember the the entire grid will be the input to our column query.

(fact (cols (() () () ())))

; YOUR CODE HERE

(fact (cols ((?a . ?as) (?b . ?bs) (?c . ?cs) (?d . ?ds)))
      (anagram (?a ?b ?c ?d) (1 2 3 4))
      (cols (?as ?bs ?cs ?ds)))

(query (cols (( 1 ?b  4 ?d)
              ( 3  3  2  1)
              (?a  1 ?c  2)
              ( 2  4  3  4))))
; expect Success! ; a: 4 ; b: 2 ; c: 1 ; d: 3

Question 9: Solve

Now, let's put all of this together to solve our any 4x4 Sudoku grid. Fill in the fact below to do so.

(fact (solve ?grid)

      ; YOUR CODE HERE

      (boxes ?grid)
      (rows ?grid)
      (cols ?grid)
      )

; Template for solving Sudoku, don't run this without
; replacing some variables with numbers!

; (query (solve ((?a ?b ?c ?d)
;                (?e ?f ?g ?h)
;                (?i ?j ?k ?l)
;                (?m ?n ?o ?p))))

(query (solve (( 1 ?b  4 ?d)
               (?e  3 ?g  1)
               (?i  4 ?k  2)
               ( 2 ?n  3 ?p))))
; expect Success! ; b: 2 ; d: 3 ; e: 4 ; g: 2 ; i: 3 ; k: 1 n: 1 ; p: 4

Question 10

Solve the following sudoku puzzle with the new solver that you built!

+-+-+-+-+
|3| | |1|
+-+-+-+-+
|1| | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | |2| |
+-+-+-+-+

Note: The query will take a long time to resolve, but it should eventually work! Can you solve it faster than Logic?

(query (solve ((3  ?b ?c 1 )
               (1  ?f ?g ?h)
               (?i ?j ?k ?l)
               (?m ?n 2  ?p))))
+-+-+-+-+
|3|2|4|1|
+-+-+-+-+
|1|4|3|2|
+-+-+-+-+
|2|3|1|4|
+-+-+-+-+
|4|1|2|3|
+-+-+-+-+