|
CSE583 Assignment 3 (Winter 2000) |
|
 CSE Home |
About Us |
Search |
Contact Info |
See the basic page on assignments for program weights, rules for working in pairs, etc.
This assignment is due on Friday, February 25, 2000 at 5PM PST. We will make an announcement later about the specific electronic form for turning in the assignment. Here's the basic information on running CLP(R):
Solution: On the one hand, this would make the programming language much more expressive, encompassing the full range of first-order predicate calculus (FOPC), rather than just Horn clauses. However, since FOPC satisfiability is NP-complete, it would make the language intractable. Furthermore, although it would render the closed-world assumption unnecessary, since negatives can be explicitly represented, this may not be a good thing. Aside from making the logic of Horn clauses complete, the closed-world assumption is rather useful as a programming tool. It's very convenient to be able to not write a bunch of NOT statements for everything in the world which is false. (Of course you could keep the closed-world assumption if you wanted to.)
Solution: von Neumann variables are basically the kind of variables we're
all used to in imperative languages. They represent state which can be
maintained and updated from statement to statement. A straightforward way to
implement this would be to use assert and retract to maintain a mapping of von
Neumann variables to their values. The idea is that you assert a rule
map(Var, Value) to set the value of Var to Value. Then you
retract that rule and assert a new one to change the value. For example, vonneumann.clp contains a simple program which uses
a von Neumann variable 'count' to count the number of times the 'member' rule
has been fired.
While it is possible to maintain von Neumann variables in a logic programming
language, it violates the basic programming principles of logic programming.
Furthermore, it makes the need to understand rule satisfying order (top-down,
left-right) and it's consequences even stronger. Since von Neumann variables
basically "stay alive" through backtracking episodes and the search for
satisfying assignments, its very important to understand the order in which
this search happens. However, there are some things for which von Neumann
variables might be good, if used sparsely and with care. One obvious one is
instrumenting code to see how many times a rule is invoked.
a. Jeremy lives in the red house.
b. Molly owns the dog.
c. Coffee is drunk in the green house.
d. Brian drinks tea.
e. The green house is immediately to the right (your right) of the ivory house.
f. The Snickers eater owns snails.
g. Junior Mints are eaten in the yellow house.
h. Milk is drunk in the middle house.
i. Craig lives in the first house to on the left.
j. The student who eats Skittles lives in the house next to the student with the fox.
k. Junior Mints are eaten in the house next to the house where the horse is kept.
l. The Sweet Tarts eater drinks orange juice.
m. Todd eats M&M's.
n. Craig lives next to the blue house
Who owns the zebra? Who drinks water?
Here are two solutions. Don't try to run zebra1.clp unless you have a lot of cycles on your
hands. The main purpose is to show the basic strategy. (I ran it for two
days on fiji and it never finished.) What's going on is that first the values
in each type are enumerated, (the 'student(todd).', etc. statements). The
first thing 'go' does is force the creation of a list for each type. The list
is required to satisfy the 'all_different' predicate, requiring each element
to be different. This forces all six lists taken together to represent a
one-to-one mapping between students, pets, houses, etc. Then it just remains
to make sure the required constraints hold. To assist in this, a predicate
'match' is defined. 'match' takes two lists and two items. It succeeds if
the position of item1 in list1 is the same as the position of item2 in list2.
For example, match([1,2,3], 3, [a,b,c], c) is true because both 3 and c are in
the 3rd position of their respective lists. 'match' is then used to build
'rightof'. If you strip off the first element of the first list and then call
'match', you're effectively adding 1 to the position of the first item. So
rightof([1,2,3], 2, [a, b, c], a) works by stripping the first element off the
first list and then calling match([2,3], 2, [a,b,c], a). Since 2 and a are
both at the head of their respective lists, so match succeeds and therefore in
the original lists, 2 must have been to the right of a. Finally, 'nextto' is
defined basically by saying either item1 is 'rightof' item2 or item2 is
'rightof' item1. Using these three predicates (match, rightof and nextto),
all the constraints can be expressed. If clpr is able to satisfy all the
constraints, the the lists must represent a solution, and can simply be
printed out. This works fine except that in order to find a solution to
e.g. match(Student, molly, Pet, dog), the system must generate
all possible combinations of students and dog (and, what's worse, all
the other lists). This takes a long time. For purposes of that
constraint, we don't care what's in the other position, just as long as molly
and the dog cohabitate. So what we do instead in zebra2.clp is create lists with variables that are
filled in by the constraints as needed. We don't first generate a list of
assignments and then check them, rather we create a list of variables and try
to make assignments to them one at a time until we either find ourselves in
conflict (in which case the system backtracks) or done with the constraints.
Finally, you can also take a look at Borning's
solution. He uses a different method for constructing the lists. The
nested s subgoals basically force a list of lists to be created. His lists
are also structured differently, each inner list represents a single house
(i.e. the student, pet, drink, etc. associated with that house.) Therefore
his checks are for membership (is the list containing molly in the student
position and dog in the pet position present) or sublists (does the list with
the ivory house immediately precede the list with the green house. Both
solutions are equally valid, I like mine because you get to see the full
solution, not just who has the zebra and who drinks the water.
(20 points) Consider computing grades for a student. There are five assignments, a project, and a final. The assignments are worth 10%, 20%, 5%, 15%, and 10% respectively; the project is worth 25% and the final is worth 15%. Each assignment, the project, and the final is graded on its own scale from 0 to N (that is, N may vary for each). Write a CLP(R) program that computes a weighted final grade for the course on a scale of 0 to 1. In addition, your program should support queries such as, "How much do I have to get on the final to get a 0.85 or better?"
Solution: The solution is in grades.clp. The basic idea is to establish the maximum scores using the maxscores predicate, then compute the grades by first normalizing each score (norm_score_i = score_i/maxscore_i) and then computing the weighted sum (for all i, sum (weight_i * norm_score_i)). (Excuse my lack of math notation, and blame it on HTML.)
Solution: For 3, it doesn't really matter. Only logic (horn clauses) are used, no math. For 4, you could write the same program in prolog, but it would only be able to compute forward (given these assignment grades, what's the total grade), not backwards (given this partial set of assignment grades, what do I need to get on assignment 4 to get an .85 in the class.)
 |
Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to notkin@cs.washington.edu] |