Lab 12: Logic
Due at 11:59pm on 8/4/2016.
Starter Files
Download lab12.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
- Questions 1 and 2 must be completed in order to receive credit for this lab.
- Questions 3 through 9 are optional. It is recommended that you complete these problems on your own time.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Logic
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 the Logic interpreter here. There is also an online Logic interpreter that you can use to check your code.
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 Success!
(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.
Recursive Facts
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))
Required Questions
Question 1: WWLD: 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 -i lab12.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.
Note that this is not an unlocking question, i.e., there is no OK command to run. Rather, it will be very useful for you to think through what the Logic interpreter would display, and see if your answers are correct.
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: ()
Question 2: 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!
.
; Define the last-element relation here!
(fact (last-element (?x) ?x))
(fact (last-element (?car . ?cdr) ?x)
(last-element ?cdr ?x))
Use OK to test your code:
python3 ok -q last-element
Optional Questions
Question 3: 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?
; Define the firsts relation here!
(fact (firsts () ()))
(fact (firsts ((?x . ?r) . ?ls) (?x . ?xs))
(firsts ?ls ?xs))
Use OK to test your code:
python3 ok -q firsts
Question 4: Rests
Now, instead of getting us the firsts, let's gather the rests!
; Define the rests relation here!
(fact (rests () ()))
(fact (rests ((?_ . ?r) . ?ls) (?r . ?xs))
(rests ?ls ?xs))
Use OK to test your code:
python3 ok -q rests
Solving Sudoku
Assume we have the anagram
relation declared, which relates two lists that
contain exactly the same elements, but potentially in a different order:
logic> (query (anagram (1 2 3 4) (4 2 3 1)))
Success!
logic> (query (anagram (a b c) (b b c a)))
Failed.
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. In addition, if we divide our
4x4 grid into 4 smaller (2 x 2) boxes, each box should also contain
all of the digits from 1 to 4.
Question 5: 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)) )
Use OK to test your code:
python3 ok -q boxes
Question 6: 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) )
Use OK to test your code:
python3 ok -q rows
Question 7: 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)))
Use OK to test your code:
python3 ok -q cols
Question 8: 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))))
Use OK to test your code:
python3 ok -q solve
Question 9
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|
+-+-+-+-+