By the end of this lab, you should have submitted the
lab14
assignment using the command submit lab14
.
This lab is due by 11:59pm on 8/12/2014.
We have provided the following starter file: lab14.logic
The language we will using is called Logic. You can download the files necessary for Logic here.
To enter an interactive Logic session, you can use the command:
python3 logic.py
To load a file into an interactive session, include the -load
flag with the
file name after it:
python3 logic.py -load FILENAME
The skeleton files for labs and homeworks also contain tests, which you can run
with -t
flag and the file name and the file name following it:
python3 logic.py -t FILENAME
You can also use this online Logic interpreter for subsequent homeworks, found here.
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.
Let's review the basics. 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 begin to 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 kittens))
(fact (eats kittens small-fish))
(fact (eats zombie brains))
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
, and 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.
(query (eats zombie brains))
; expect Success!
(query (eats domo zombie))
; expect Failed.
(query (eats zombie ?what))
; expect Success! ; ?what: brains
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.
Write Logic queries that answers the following questions:
(query (eats shark big-fish))
(query (food-chain ?what small-fish))
(query (eats ?what small-fish))
(query (eats ?what sharks))
(query (eats ?what zombie))
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 we added the following facts:
(fact (eats shark big-fish))
(fact (eats big-fish small-fish))
(fact (eats small-fish shrimp))
We'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:
(query (food-chain shark shrimp))
; expect Failed.
We will define the food-chain-v2
fact that correctly handles arbitrary length
hierarchies. We'll use the following logic:
A
and B
, A
is on top of the food chain of B
if:A
eats B
, ORC
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))
(query (food-chain-v2 shark shrimp))
; expect Success!
(query (food-chain-v2 shark ?what))
; expect Success! ; what: big-fish ; what: small-fish ; what: shrimp
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.
Next, we will define append in the logic style.
As we've done in the past, let's try to explain how append
recursively. For
instance, given two lists [1, 2, 3], [5, 7
], the result of append([1, 2, 3],
[5, 7])
is:
[1] + append([2, 3], [5, 7]) => [1, 2, 3, 5, 7]
In Scheme, this would look like:
(define (append a b)
(if (null? a)
b
(cons (car a) (append (cdr a) b))))
Thus, we've broken up append into two different cases. Let's start translating this idea into Logic! The first base case is relatively straightforward:
(fact (append () ?b ?b))
(query (append () (1 2 3) ?what))
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))
If it helps you, here's an alternate solution that might be a little easier to read:
(fact (car (?car . ?cdr) ?car))
(fact (cdr (?car . ?cdr) ?cdr))
(fact (append () ?b ?b))
(fact (append ?a ?b (?car-a . ?partial))
(car ?a ?car-a)
(cdr ?a ?cdr-a)
(append ?cdr-a ?b ?partial))
Meditate on why this more-verbose solution is equivalent to the first definition for the append fact.
Define a fact (fact (interleave ?lst1 ?lst2 ?interleaved))
that outputs
Success
if ?interleaved
is the list resulting from interleaving the
elements of ?lst1
and ?lst2
. The base case has been written for you.
; Base Case
(fact (interleave () ?lst2 ()))
; YOUR CODE HERE
(query (interleave (1 2 3 4) (5 6 7 8) ?lst))
; expect Success! ; lst: (1 5 2 6 3 7 4 8)
(query (interleave (1) (2 3 4 5 6 7 8 9) ?lst))
; expect Success! ; lst: (1 2)
(query (interleave (1 3 5 7 9) ?evens (1 2 3 4 5 6 7 8 9)))
; expect Success! ; evens: (2 4 6 8)
(fact (interleave () ?lst2 ()))
(fact (interleave (?first1 . ?rest1) ?lst2 (?first1 . ?rest3))
(interleave ?lst2 ?rest1 ?rest3))
Define a fact (fact (last-element ?lst ?x))
that outputs Success
if
?x
is the last element of the input list ?lst
.
(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
Does your solution work correctly on queries such as (query
(last-element ?x (3)))
? Why or why not?
(fact (last-element (?x) ?x))
(fact (last-element (?car . ?cdr) ?x)
(last-element ?cdr ?x))
Write a fact (fact (firsts lst-of-lsts firsts))
that, will match a list of
lists with a list with the first element of each list.
When you finish, the following queries should succeed:
(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)
(fact (firsts () ()))
(fact (firsts ((?x . ?_) . ?ls) (?x . ?xs))
(firsts ?ls ?xs))
Now, instead of getting us the firsts, let's gather the rests! Write a fact
(fact (rests lst-of-lsts rests))
that will match a list of lists with a list
of the rests of each list.
When you finish, the following queries should succeed:
(query (rests ((1 2 3 4) (2 3 4 5) (1 2 3 4) (1 2 3 2)) ?x))
; expect 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))
; expect Success! ; y: ((3 4) (4 5) (3 4) (3 2))
(fact (rests () ()))
(fact (rests ((?_ . ?r) . ?ls) (?r . ?xs))
(rests ?ls ?xs))