There are two sets of exercises here, using the simple Deductive Data Retriever:


Using the Deductive Data Retriever

Anyone should be able to work on the logic rule problems. Watch out for infinite loops!

These exercises require the following files from the EECS 325 library:

ddr-tests.lisp and ddr-exs-tests.lisp define all their tests in the package named ddr-tests. The easiest way to work on these exercises is to write all your code in the ddr-tests package, that is, create a file and start the file with (in-package #:ddr-tests).

When defining rules, put them in the global variables listed in the exercise description, using defparameter. The test cases will automatically load those variables for you. Send those variable definitions to the Critic when done.

Feel free to create new test cases!.

Exercise: member

Global variable name: *member-kb*

Tests: member in ddr-exs-tests.lisp

Use defparameter to define *member-kb* to hold a set of rules to define a deductive (not Lisp!) member predicate. The query (member x l) should be true if and only if x is a member of the list l. Look at the append example in ddr-tests.lisp to see how to represent lists with (cons x y) functional terms.

Exercise: all-different

Global variable name: *all-different-kb*

Tests: all-different in ddr-exs-tests.lisp

We rarely need an "is equal" predicate with a deductive retriever. For example, if you want to say some binary relationship always holds for an object with itself, just say (relation ?x ?x), not (<- (relation ?x ?y) (equal ?x ?y)).

On the other hand, we do often need an "is different" predicate. For example, in the Monkey and Bananas code in ddr-tests.lisp, we want to the monkey to go to the box only if the monkey's current location is different than the box's location.

To make it easier to assert (different x y), the code in the Monkey and Bananas formulation in ddr-tests.lisp defines a forward-chaining rule so that asserting (different x y) automatically asserts (different y x). (Why can't this be a backward-chaining rule?)

That forward-chaining rule cuts the number of assertions needed in half, but we still need to write order(N2) assertions for N objects.

Use defparameter to define *all-different-kb* to hold a set of rules to define forward-chaining rules for the predicate (all-different list), where a list is represented with (cons x y) functional terms. Asserting (all-different list) should cause (different x y) to be asserted for every pair of different items in the list. Assume there are no duplicates in the list.

Exercise: Map Coloring

Global variable name: *map-color-kb*

Tests: color-map1, color-map2, and color-map3in ddr-exs-tests.lisp

The map coloring problem has a long history. The problem is simple: given a map of various countries bordering each other, color the map using the fewest number of colors, such that no countries sharing a border of more than a point have the same color. For many years, it had been proven that 5 colors was sufficient for any flat map, no matter how complex, and that no map was known that needed more than 4. It finally required a computer to generate the complete proof that 4 was enough.

Here are three small maps, one already colored, the others left for you to figure out:

small map coloring problem medium map coloring problem large map coloring problem

Here is a more complicated map that Martin Gardner claimed required 5 colors.

You can encode a map coloring problem in logic with:

Define a KB with the colors red, blue, green and yellow. Then define map coloring rules for the predicate (colors-for map a-region-color b-region-color c-region-color...), so that the test cases below pass. Note that colors-for is given a different number of arguments for each map. This is not a mistake nor anything you have to treat specially. You can have rules for all three maps at the same time. The map argument will keep the rules separate.

Side question: The above maps all have 24 possible solutions. Do all maps have 24 solutions?


Improving the Deductive Data Retriever

These exercises can make the Retriever less prone to infinite loops, though they may also make it run a bit slower.

Do these as "patch files." That is, don't change the code in ddr.lisp, but create a new file, e.g., ddr-patch.lisp. This file should be in the ddr package and contain only the new and changed definitions necessary to change the Retriever. That way I can see your changes in one place and test them, if necessary, by loading the original ddr.lisp and your patches.

Make sure all the old tests in ddr-tests.lisp continue to work as you modify the retriever, unless the modification makes some test inappropriate.

The email rules still apply. Use the Lisp Critic on your code before sending.


Exercise: assert-file

This one's easy, if you've done the I/O chapter.

Define (assert-file pathname) to assert every fact and/or rule in the file named by pathname. It should return a count of how many items were asserted.

movies.lisp is a very large file of movie facts, adapted from a data file for a Prolog course. Test your code on that. It should say that it loaded 2909 items. Make sure you've compiled ddr.lisp before trying to load this file, otherwise Allegro may never finish!


Exercise: DDR Loop Catcher

It's easy to throw the Retriever into an endless loop, e.g.,

> (tell '(<- (married ?x ?y) (married ?y ?x)))
    
    > (tell '(married john mary))
    
    > (ask '(married mary john))

Some common loops can be caught by keeping a stack of current goals, and, when adding to this stack, checking to see if the new query matches (unifies) with a query on the stack already. If so, then you're in trouble, and should quit the search with a failure.

Done correctly, the above example should return an answer for both queries, but should return false for the query (ask '(married brad angeline)).


Exercise: DDR ask-1

The goal of this exercise is to make it possible to get answers one at a time from the Deductive Retriever, somewhat the way the Prolog interpreter works. It should be possible to get one answer and stop, and not pay the cost of looking for other answers. This approach has two advantages. First, if one answer is sufficient, you can get it faster. Second, if a query has an infinite number of answers, a particular application can ask for the first N answers.

More specifically, you need to

The new ask should still pass all the tests in ddr-tests.lisp.

The syntax of ask-1 is like ask, i.e., (ask-1 query [ form ]), except that query is also optional. The semantics of ask-1 is:

Here's an example of how ask-1 should work with one of the test knowledge bases in ddr-tests.lisp:

DDR-TESTS 16 > (make-tiger-kb)
    ...
    DDR-TESTS 17 > (ask '(can-satisfy-hunger ?x))
    ((CAN-SATISFY-HUNGER ANTELOPE) (CAN-SATISFY-HUNGER TIGER))
    
    DDR-TESTS 18 > (ask-1 '(can-satisfy-hunger ?x))
    (CAN-SATISFY-HUNGER ANTELOPE)
    
    DDR-TESTS 19 > (ask-1)
    (CAN-SATISFY-HUNGER TIGER)
    
    DDR-TESTS 20 > (ask-1)
    NIL

As with ask, if form is omitted, it should default to query. If (ask-1) is evaluated and no previous query has been specified, (ask-1) should return false.

Approach

This problem has both a conceptual challenge and a software programming challenge. The conceptual challenge is how to represent the state of the deductive search in a way that supports getting answers one at a time. The programming challenge is how to make as few changes as possible to the existing tested Retriever code.

The current code uses a simple uniform recursive logic: explore all branches and append all results. This automatically takes care of branches that lead to no results or many. But it means that the code has many functions calling other functions recursively, expecting to get lists of all answers back. If now only one answer is returned, how can the basic logic structure be kept?

The answer is generated lists, also known as lazy lists and (in Abelson and Sussman's Structure and Interpretation of Computer Programs) streams. A generated list is a data structure with list-like operations, analogous to car and cdr, but the elements of a generated list may not exist until accessed. That is, the elements may be generate on demand.

The glist package defines some basic functions that create and manipulate generated lists. Most of these functions are analogous to the standard list functions: gcar, gcdr, gappend and so on.

Because generated list functions look like regular list functions, converting list code to generated list code is relatively straightforward. Instead of consing or appending lists of all answers, you gcons or gappend them. You need to do this both in the main code and some of the logic extensions, like match-and. Do not, however, convert all lists to lazy lists. Many lists in the Retriever code, e.g., lists of bindings should remain normal lists. Only lists that involve recursively finding alternatives should be converted.

You'll need two top-level global variables where (ask-1 query form) can save information for subsequent calls:

ask-1 should set these variables when a new query and/or form is passed in. ask-1 should then pop off the next answer from the generated list. ask simply calls ask-1 repeatedly until it returns false, and collects all the answers.

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15

Contents

Important Links