CS 6795 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