There are two sets of exercises here, using the simple Deductive Data Retriever:
- Solving logical representation problems:
- Making the Retriever work better:
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.lisp -- the code for the Deductive Data Retriever
- ddr-tests.lisp -- the test cases for the Deductive Data Retriever
- ddr-exs-tests.lisp -- the test cases for these exercises
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,
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!.
Global variable name:
defparameter to define
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
to see how to represent lists with
(cons x y)
Global variable name:
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)
(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.
defparameter to define
to hold a set of rules to define forward-chaining rules for the predicate
(all-different list), where a list is represented
(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:
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:
Here is a more complicated map that Martin Gardner claimed required 5 colors.
You can encode a map coloring problem in logic with:
- some assertions about what different colors there are, and
- rules (at least one per problem) for a predicate that says whether some map coloring is legal for map; the rules describe the coloring constraints that have to be satisfied.
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.
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.
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
- define a new function, ask-1, to get answers one at a time, and
- redefine ask to get all the answers that ask-1 can generate.
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:
- (ask-1 query form) returns the first of the answers, if any, that the original (ask query form) would return.
- Subsequent calls with no arguments, i.e., (ask-1), return the second, third, ... answers that the original ask would return.
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.
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:
- a variable to hold the form to instantiate on each answer
- a variable to hold the initial generated list for query
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.