# CS 61A Lab 11

## Declarative Programming

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, and an interpreter is already setup for us on the lab machines. To copy the folder to your current directory, run:

``````    cp -r ~cs61a/lib/lab/lab11/logic .
``````

Just run `python3 logic.py` after you move your Scheme project files into the folder. Please note that you must have finished up to at least problem 4 on your project in order to do this lab, as this lab depends on your implementation of the `Frame` class.

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.

``````    logic> (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.

``````    logic> (fact (eats shark big-fish))
logic> (fact (eats big-fish small-fish))
logic> (fact (eats domo kittens))
logic> (fact (eats kittens small-fish))
logic> (fact (eats zombie brains))
logic> (fact (append (1 2) (3 4) (1 2 3 4)))
``````

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.

``````    logic> (query (eats zombie brains))
Success!
logic> (query (eats domo zombie))
Failed.
logic> (query (eats zombie ?what))
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.

#### Question

Within your Logic interactive session, type in the `food-chain` fact, and enter in the facts mentioned from above. Issue a Logic query 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?

### More complicated 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:

``````    logic> (fact (eats shark big-fish))
logic> (fact (eats big-fish small-fish))
logic> (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:

``````    logic> (fact (food-chain-v2 ?a ?b) (eats ?a ?b))
logic> (fact (food-chain-v2 ?a ?b) (eats ?a ?c) (food-chain-v2 ?c ?b))
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.

### Recursively-Defined Rules

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:

``````     + 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:

``````    logic> (fact (append () ?b ?b))
logic> (query (append () (1 2 3) ?what))
Success!
what: (1 2 3)
``````

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

``````    ;;                         A        B       C
logic> (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:

``````    logic> (fact (append () ?b ?b ))
logic> (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:

``````    logic> (fact (car (?car . ?cdr) ?car))
logic> (fact (cdr (?car . ?cdr) ?cdr))
logic> (fact (append () ?b ?b))
logic> (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.

### Exercises

1 . 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)))
logic> (query (append (1 2) (5 8) ?what))
logic> (query (append (a b c) ?what (a b c oh mai gawd)))
logic> (query (append ?what (so cool) (this is so cool)))
logic> (query (append ?what1 ?what2 (will this really work)))
``````

2 . Define a fact `(fact (last-element ?lst ?x))` that outputs `Success` if `?x` is the last element of the input list `?lst`. Check your facts on queries such as:

``````    logic> (query (last-element (a b c) c))
logic> (query (last-element (3) ?x))
logic> (query (last-element (1 2 3) ?x))
logic> (query (last-element (2 ?x) (3)))
``````

Does your solution work correctly on queries such as `(query (last-element ?x (3)))`? Why or why not?

3 . Define the fact `(fact (contains ?elem ?lst))` that outputs `Success` if the `?elem` is contained inside of the input `?lst`:

``````    logic> (query (contains 42 (1 2 42 5)))
Success.
logic> (query (contains (1 2) (a b (1) (1 2) bye)))
Success.
logic> (query (contains foo (bar baz garply)))
Failed.
``````

## Challenge Problem!

Implement basic math in logic. The following interactive transcript should work...

``````    logic> (query (2 + 2 = 4))
Success!
logic> (query (2 + 1 = 4))
Failed.
logic> (query (4 - 2 = 2))
Success!
logic> (query (2 * 2 = 4))
Success!
logic> (query (2 * ?x = 4))
Success!
x: 2
logic> (query (2 + ?x = 4))
Success!
x: 2
logic> (query (2 ?op 2 = 4))
Success!
op: +
op: *
logic> (query (?a + ?b = 4))
Success!
a: 1    b: 3
a: 2    b: 2
a: 3    b: 1
a: 4    b: 0
logic> (query (?a ?op ?b = 4))
Success!
a: 1    op: +   b: 3
a: 2    op: +   b: 2
a: 3    op: +   b: 1
a: 4    op: +   b: 0
a: 4    op: -   b: 0
a: 5    op: -   b: 1
a: 6    op: -   b: 2
a: 7    op: -   b: 3
a: 8    op: -   b: 4
a: 9    op: -   b: 5
a: 4    op: *   b: 1
a: 1    op: *   b: 4
a: 2    op: *   b: 2
``````

Here is a skeleton to get you started. Note that we define all the possible numbers in our given universe by a successive sequence; the only numbers Logic knows about are 0 through 9.

``````    (fact (succ 0 1))
(fact (succ 1 2))
(fact (succ 2 3))
(fact (succ 3 4))
(fact (succ 4 5))
(fact (succ 5 6))
(fact (succ 6 7))
(fact (succ 7 8))
(fact (succ 8 9))
(fact (succ 9 10))

(fact (1 + ?x = ?y) YOUR CODE HERE)
(fact (?x + ?y = ?z) YOUR CODE HERE)

(fact (?x - ?y = ?z) YOUR CODE HERE)

(fact (?x * 0 = 0) YOUR CODE HERE)
(fact (1 * ?x = ?x) YOUR CODE HERE)
(fact (?x * 1 = ?x) YOUR CODE HERE)
(fact (?x * ?y = ?z) YOUR CODE HERE)
``````