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. An online Logic interpreter is embedded in this lab, which you can use to evaluate logic expressions on this page. You can also use this online Logic interpreter for subsequent homeworks.
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.
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.
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
, and that the list
(1 2)
appended to (3 4)
is equivalent to the list (1 2 3 4)
. 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.
Each code block that contains a logic expression can be evaluated by clicking
into the block and pressing Ctrl-Enter
. You can also edit the code and
evaluate it afterwards by pressing Ctrl-Enter
.
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 following box, the food-chain
facts mentioned above are
already defined. Write Logic queries that answers the following questions:
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:
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:
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:
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:
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:
If it helps you, here's an alternate solution that might be a little easier to read:
Meditate on why this more-verbose solution is equivalent to the first definition for the append fact.
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.
Define a fact (fact (last-element ?lst ?x))
that outputs Success
if
?x
is the last element of the input list ?lst
.
Does your solution work correctly on queries such as (query
(last-element ?x (3)))
? Why or why not?
Write a fact "firsts" that, when input with a list of lists, gives us the first element of each list.
When you finish, the following queries should succeed:
Now, instead of getting us the firsts, let's gather the rests!
When you finish, the following queries should succeed:
Assume we have the two facts insert and anagram as follows
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.
Let's start by defining our grid using our fact dubbed boxes. Fill in the remainder of the fact.
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 rest of the facts in the prompt below:
When you finish, the following queries should return the correct values:
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.
When you finish, the following queries should return the correct values:
Now, let's put all of this together to solve our any 4x4 Sudoku grid. Fill in the fact below to do so.
When you finish, check your solution with the following queries:
Solve the following sudoku puzzle with the new solver that you built!
Tip: it's a good idea to save your code in one place before trying this, since this will take a long time. Also, press Ctrl-Enter only once and be prepared to wait ;)
+-+-+-+-+
|3| | |1|
+-+-+-+-+
|1| | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | |2| |
+-+-+-+-+