These exercises require loading SDDR, the Simple Deductive Data Retriever. 

(ql:quickload "sddr")

The tests for the member and map coloring exercises are in sddr-exs-tests.lisp.

To do the logic problems, define your rules in a Lisp file that begins with (in-package :sddr-tests). Run the tests in that package in the Lisp Listener. 

(in-package :sddr-tests)

For each test, put your rules in the global variable listed in the exercise description, using defparameter. Send those variable definitions to the Critic when they are passing the test cases.

Feel free to create new test cases!.

Exercise: member

Global variable name: *member-kb*

Test name: member

Deductive reriever bundle

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 sddr-tests.lisp to see how to represent lists with (cons x y) functional terms.

Exercise: Map Coloring

Global variable name: *map-color-kb*

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

Deductive retriever bundle

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:

Maps are identified by a map ID, e.g., map1 for the first map. colors-for will have a different number of arguments for each map. This is not a mistake nor anything you have to treat specially. Different rules can use different numbers of arguments for predicates. You can have rules for all three maps at the same time.

Exercise: DDR ask-1

Generated list bundle

Tests: ask-1

Note: you run the tests in sddr-tests, but you define the modified SDDR code in the sddr package.

This exercise is not about defining logic rules. It is about changing the retriever to return answers one at a time. Do this as a "patch file". Don't change the source code but create a new file, e.g., sddr-patch.lisp. This file should define code in the sddr package and contain only the new and changed definitions necessary to change the retriever. Submit only the patches for review.

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.

This does not prevent infinite loops. If you have rules with that can loop forever, you can still get an infinite loop if you ask a query that has no answer.

More specifically, in this exercise you need to

The syntax of ask-1 is like ask. I.e.,

(ask-1 [query rules])

The difference is that the arguments are optional.

Here's an example of how ask-1 should work in SDDR with one of the test cases. 

> (ask-1 '(can-satisfy-hunger ?x) *tiger-kb*)
    (CAN-SATISFY-HUNGER ANTELOPE)

    > (ask-1)
    (CAN-SATISFY-HUNGER TIGER)

    > (ask-1)
    NIL

If (ask-1) is evaluated when 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 work much like regular list functions, converting code using lists to generated lists is much less work than completely redoing the logic of the retriever to keep a queue of answers. Instead of consing or appending lists of all answers, you gcons or gappend them.

Do not generate all the answers and then store the results in a generated list. Only the work needed to find one solution should happen for the first call to ask-1. The work to find the next solution should only happen if you call ask-1 again. You need to look inside the code for where backchaining occurs, both in the main code and some of the logic extensions, like and and not.

Do not convert all lists to lazy lists. Only lists that involve finding alternative solutions should be converted. Other lists, e.g., the list of bindings returned by unification, should remain normal lists.

Hint: you may find it useful to first convert some code using iterative loops to a recursive form first. Change and test first, then introduce generated lists.

You'll need a few top-level global variables to hold the the initial arguments and the generated list of answers. (ask-1 query rules) should set these variables. (ask-1) should then pop off the next answer from the generated list. Note that the original ask can be defined to simply call ask-1 repeatedly until it returns false, and collects all the answers. That way the original tests still work.

Make sure all the still SDDR tests still work as they did before. Note that blocks-world fails one test because of how the rules were written. It should still fail in the revised version.

Use the Lisp Critic on your code before sending.