CS 6999 Semantic Web Techniques |
|
Project 6: Goal Reordering in j-DREW BU |
|
|
|
See Project 5
on adding built-ins to j-DREW BU.
Project 5 discusses how to add built-in processing of goals that are
assumed to be ground so they can be evaluated. But suppose they are not ground. This can be handled in two different ways depending on the
built-in. 1. If the built-in is a Boolean function, and the goal
contains a variable, the built in may not be able to be checked at the
moment, but after other goals are processed, the goal in question may become
ground. For example youngAge(X):- $lessThan(X, 20), age(X) where
there is (now or later) a fact age(5) causes the
problem since lessThan is checked before age(X). But if $lessThan
were checked after age(X) were done, X would be set to 5 and the built-in
would not cause a problem. In
this case a strategy for dealing with the built-in that is not ground would
be to move it to the end of the clause, or at least to a point after some
other goal containing this variable. So when adding the clause, youngAge(X):- $lessThan(X, 20),
age(X) the
system would instead add the clause youngAge(X):- age(X), $lessThan(X, 20) 2. In some other cases this might not be a problem, as
the built-in processing, or evaluation, may be used to set the value of some
variable. Consider the clause double(X,Y) :- $plus(X, X, Y). In this clause the
relation $plus(A, B,
C) is
intended to set the value of the third argument to the sum of the other
two. One could imagine adding
all facts such as $plus(1,
1, 2), $plus(2, 2, 4) but this is an
infinite list. For these kinds
of built-ins, have your program analyse the goal, create another goal with
the right answer, unify the two creating a new resolvent and add the
resolvent instead of adding the original rule. For example if the first goal
were $plus(1, 1, R) then you would create
the DefiniteClause $plus(1,
1, 2) and
resolve it against this goal, so that other occurrences of R are also set to 2. Sometimes you will need to defer
these evaluated goals as well, for instance when trying to evaluate $plus(1, S, R). Defer this to when either R or S is bound. If you add $divide and $play to j-DREW you
should be able to deduce the fact go(11) from the
code below. go(X) :- average(c(3,c(12,c(10,c(18,nil)))),
X). average(nil, undefined). average(List, Ave) :- $divide(Total,
Length, Ave), total(List,
Total), count(List,
Length). total(nil, 0). total(c(X, Y), Total) :- $plus(X,
SubTotal, Total), total(Y,
SubTotal). count(nil, 0). count(c(X, Y), Length) :- $plus(1,
SubLength, Length), count(Y,
SubLength). Note the
reordering of goals may not solve all problems of ground/non-ground. Give some examples of this and
possibly some solutions for some cases. Not all cases will have
solutions. Try to include some
of these. Notice that
in principle the reordering could also be done for non-built-ins to achieve better
runtime behaviour. For instance,
attempting cheap goals before expensive goals will give better behaviour if
the cheap goals fail, making the expensive ones unnecessary. |
|
|
|
|
Maintained by Bruce Spencer