v.Bijan%UCLA-LOCUS@sri-unix.UUCP (10/20/83)
From: Bijan Arbab <v.Bijan@UCLA-LOCUS>
I hope the following will answer some of your questions with respect
to the is_all problem.
1. The is_all function or an equivalent one is a necessary part of
any algorithm that wants to do a breath first search. Therefore
it is only natural to ask whether such a function can be
implemented in pure Prolog or not?
In practice, however, it is O.K. to use other equivalent functions
such as setof or bagof. For that matter it is also O.K. to use the
function is_all that is defined by means of delete-axioms or
add-axioms, here is a definition of such a function:
is_all(A,Y,Q) <- Q & addax(save(Y)) & fail.
is_all(A,Y,Q) <- build-list(A).
build-list(Y.A) <- save(Y) & delax(save(Y)) & build-list(A).
build-list(nil).
2. The reason why abstract data types popped in the discussion is
that: in a paper I was reading about the subject they introduced
the NPO and CPO mechanism, which are a way of introducing
histories into computation. The authors felt that these were
necessary in order to efficiently implement abstract data types
in Prolog, not my claim.
However I felt that the NPO function is exactly what is needed
to solve this problem. With an NPO one can simply ask for the
next solution of a function. Note that NPO is not part of pure
Prolog either, however its use here appears to be more elegant
than add-ax and del-ax.
3. The is_all problem is a hard one, not because all the variables
must be reinitialized each time around the recursion ! In fact
the problem can not be solved "recursivly" in Prolog.
* tentative proof of above statement *
Any recursive definition for is-all would have to be of the form:
is_all(A,Y,Q) <- Q & {SOMETHING} & is-all(...).
where {SOMETHING} and (...) are poperly filled out.
But each new invocation of is_all will be getting evaluated in the
same environment of the father is_all, since the use of delete-axiom
or add-axiom is not allowed. Therefore the solution to Q for `son'
is_all is same as it was for `father' is_all. This implies that only
the first solution to Q is generated by such a function and the others
are not.
The other generation of solutions, will attempt to keep a list of
currently solved goals and make sure that a newly generated solution
is not in that list. This method is not a general one since if a
goal has two identical soultions only one of them will recorded.
All comments are welcome.
-- Bijan