Set Wednesday Nov 20th, due Thursday Dec 5th
Read the appropriate parts of the course books,
i.e. chapters 17 and 18 of Sterling and Shapiro.
1. Problem 18.2 (ii), page 365 of SS. The following code fixes their bug in 17.20.
/* 17.20 */
?- dynamic monitor/1.
monitor(Goal) :- solve(Goal,Result,[ ]), filter(Result).
monitor(Goal).
?- dynamic filter/1.
filter(yes).
?- dynamic solve/3.
solve(A,yes,Rules) :- fact(A).
solve(A,Result,Rules) :-
rule(A,B,Name), RulesB = [Name|Rules],
solve_body(B,Result,RulesB).
solve(A,no,Rules).
?- dynamic solve_body/3.
solve_body(A&B,Result,Rules) :-
solve_body(A,ResultA,Rules),
solve_and(ResultA,B,Result,Rules).
solve_body(A is_true,Result,Rules) :- solve(A,Result,Rules).
?- dynamic solve_and/4.
solve_and(no,A,no,Rules).
solve_and(yes,B,Result,Rules) :- solve(B,Result,Rules).
% Program 17.20: A two-level rule interpreter carrying rules
2. Plan specialization by partial evaluation.
The idea is that various types of information
can be known or not known at various times. Then the
problem to show how to take advantage of this knowledge
by partially evaluating
the problem solving program to generate different
kinds of specialized programs which are therefore "plans".
This question involves creative thought in that it
expects you to define the problem and to formulate it,
solve it, and give a discussion of the issues.
Use the following shopping example:
(i) Write a general shopping predicate, which makes use of
a generic shopping list and a generic list of shop types.
(ii) Then show how to generate a specialization of this predicate
where you are given a description of a specific mall
where the shopping is to be carried out, e.g. your local mall
(iii) Then show how to specialize the predicate you obtained in
(ii) where you are now given a specific shopping list,
e.g., today's shopping list
This should result in a predicate shop(Shopping_history),
which can be executed using information about
what is discovered to be available in the shops in your local mall
today as you shop. Perhaps this information is in a predicate
available(shop,item).
Some issues for discussion:
(a) dependencies among shopping items, e.g. get a cheese
and then get a wine that goes with the cheese you bought.
(b) optimization of cost of purchases.
(c) optimization of time spent shopping.
(d) can you compute or estimate the saving of computational effort
as a result of using a specialized predicate?
Please set up a web page with your solutions and email the URL
both to me and to our TA Adam at granicz@cs.caltech.edu.