CS61A Lab 14: Logic Programming

Week 7B, 2012


In Logic Programming, we aim to define rules and 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 rules and facts. It will inform us of what replacements for the variables will make the query true.

The language we will use is called PyGic, and an interpreter is already setup for us on the lab machines, which you can run using python3 -m pygic.interpreter. Let's review the basics.

In PyGic, 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 PyGic are denoted with a ? mark preceding the name. So for example, ?x represents the variable x. We also have lists that look like Python lists, constructed using < >'s. For instance, <1, 2, 3> is the list containing 1, 2, and 3.

The next thing we need to do is begin to define rules and facts about our universe. Rules are defined similarly to how Python functions are defined. We start off with the rule keyword, and structure our rule with a series of hypotheses. The "signature" of the rule, given by its name and arguments, is the conclusion, and all hypotheses must be satisfied for the conclusion to be valid:

P?> rule food_chain(?creature1, ?creature2):
        eats(?creature1, ?creature3)
        eats(?creature3, ?creature2)

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

Facts are essentially condensed versions of rules, where the body of a fact is simply True:

P?> fact eats(shark, big_fish)
P?> fact eats(big_fish, small_fish)
P?> fact eats(domo, kittens)
P?> fact eats(kittens, small_fish)
P?> fact eats(zombie, brains)
P?> 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, 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 look like function calls in Python (though they're different). The interpreter prints the truth value (either Yes or No). If there are variables inside of the query, the interpreter will print one possible mapping. So for example, if the facts above have been defined, we can query them:

P?> eats(zombie, brains)
P?> eats(domo, zombie)
P?> eats(zombie, ?what)
?what = brains

We're first asking PyGic whether a zombie eats brains (the answer is Yes) and if a domo eats zombies (the answer is No). Then we ask whether a zombie can eat something (the answer is Yes), and PyGic 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 we can use the keyword ?more to have PyGic return to us the values one by one, until it finally spits back No, meaning there is no values left that satisfy the query.


1. Within your PyGic interactive session, type in the food_chain rule, and enter in the facts mentioned from above. Issue a PyGic query that answers the following questions:

More complicated rules

Currently, the food_chain rule is a little lacking. A query food_chain(A, B) will only output Yes if A and B are separated by only one animal. For instance, if I added the following facts:

P?> fact eats(shark, big_fish)
P?> fact eats(big_fish, small_fish)
P?> 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 rule doesn't do this:

P?> food_chain(shark, shrimp)

We will define the food_chain_v2 rule that correctly handles arbitrary length hierarchies. We'll use the following logic:

Notice we have two different cases for the food_chain_v2 rule. We can express different cases of a rule simply by entering each case one at a time:

P?> rule food_chain_v2(?a, ?b):
        eats(?a, ?b)
P?> rule food_chain_v2(?a, ?b):
        food_chain_v2(?a, ?c)
        food_chain_v2(?c, ?b)
P?> food_chain_v2(shark, shrimp)

Success! Take a few moments and read through how the above rules 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 PyGic system, multiple 'definitions' of a rule can exist at the same time (as in food_chain_v2) - definitions don't overwrite each other.

Listing and Clear

To view a listing of all rules and facts currently defined, use the listing keyword:

P?> listing()

You can also view a listing of the rules with a particular name:

P?> listing(food_chain)

To clear all currently-defined facts and rules, use the clear keyword. Use with caution!

P?> clear()

You can also clear rules with a particular name:

P?> clear(food_chain)


PyGic has lists as a built-in data type, and they have their own special syntax. To illustrate this syntax, let's examine a few examples. First, let's define the same_car(A, B) rule that outputs Yes if the lists A, B both have the same car (i.e. have the same first element):

P?> same_car(<1, 2, 3>, <1, 2, 3>)
P?> same_car(<hi, there>, <hi>)
P?> same_car(<good, bye>, <moose, pie>)
First, let's define the equal fact that outputs Yes if the two arguments are equal:
P?> fact equal(?x, ?x)
P?> equal(hi, hi)
P?> equal(<1, 2>, <1, 2>)
P?> equal(4, 2)
One definition for the same_car rule could be:
P?> rule same_car(<?car_a | ?cdr_a>, <?car_b | ?cdr_b>):
        equal(?car_a, ?car_b)
Note the special syntax we used here, to split up an input list into its components: the car (i.e. first), and the cdr (i.e. rest). The vertical bar | signifies that the variable afterwards indicates the rest of the list.

We can also easily define the same_first_two rule that outputs Yes if both lists have the same first two elements:

P?> rule same_first_two(<?elem1_a, ?elem2_a | ?cdr_a>, <?elem1_b, ?elem2_b | cdr_b>):
        equal(?elem1_a, ?elem1_b)
        equal(?elem2_a, ?elem2_b)
P?> same_first_two(<1, 2, 3>, <1, 2, 5, 7>)
P?> same_first_two(<4, 5, 6>, <4, moo>)
Finally, we could have omitted the use of isequal by enforcing the equality by setting the variable names equal:
P?> fact same_car(<?car | ?cdr_a>, <?car | ?cdr_b>)
P?> fact same_first_two(<?el1, ?el2 | ?cdr_a>, <?el1, ?el2 | ?cdr_b>)

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:

In Python, this would look like:
def append(a, b):
    if a == []:
        return b
        return [a[0]] + append(a[1:], b)
Thus, we've broken up append into two different cases. Let's start translating this idea into PyGic! The first base case is relatively straightforward:
P?> fact append(<>, ?b, ?b)
P?> append(<>, <1, 2, 3>, ?what)
?what = <1, 2, 3>
So far so good! Now, we have to handle the general (recursive) case:
P?> rule 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 PyGic code corresponds to the recursive case of the Python function definition? As a summary, here is the complete definition for append:
P?> fact append(<>, ?b, ?b)
P?> rule append(<?car | ?cdr>, ?b, <?car | ?partial>):
        append(?cdr, ?b, ?partial)

If it helps you, here's an alternate solution that might be a little easier to read:

P?> fact car(<?car | ?cdr>, ?car)
P?> fact cdr(<?car | ?cdr>, ?cdr)
P?> fact append(<>, ?b, ?b)
P?> rule append(?a, ?b, ?c):
        car(?a, ?car_a)
        cdr(?a, ?cdr_a)
        append(?cdr_a, ?b, ?partial)
        equal(<?car_a | ?partial>, ?c)
Meditate on why this more-verbose solution is equivalent to the first definition for the append rule.


2. Using the append rule, issue the following queries, and ruminate on the outputs. Note that some of these queries might result in multiple possible outputs: use more? to print out the multiple matches:

P?> append(<1, 2, 3>, <4, 5>, <1, 2, 3, 4, 5>)
P?> append(<1, 2>, <5, 8>, ?what)
P?> append(<a, b, c>, ?what, <a, b, c, oh, mai, gawd>)
P?> append(?what, <so, cool>, <this, is, so, cool>)
P?> append(?what1, ?what2, <will, this, really, work>)

3. Define a rule last_pair(?lst, ?x) that outputs Yes if ?x is the last element of the input list ?lst. Check your rules on queries such as:

P?> last_pair(<a, b, c>, c)
P?> last_pair(<3>, ?x)
P?> last_pair(<1, 2, 3>, ?x)
P?> last_pair(<2, ?x>, <3>)
Does your solution work correctly on queries such as last_pair(?x, <3>)? Why or why not?

4. Define the rule contains(?elem, ?lst) that outputs Yes if the ?elem is contained inside of the input ?lst:

P?> contains(42, <1, 2, 42, 5>)
P?> contains(<1, 2>, <a, b, <1>, <1, 2>, bye>)
P?> contains(foo, <bar, baz, garply>)