Hi,

I want to bug you on this possibly interesting question that I came across
the other day when I was talking to my friend about a (theoretical) Prolog
research problem.

The question was, given a meta predicate--a predicate such that one of the
arguments of the predicate is actually a conjunction of predicates (e.g.
findall(A,(p(A),q(A,B),s(B)),T)), can we translate the 'findall' into a
conjunction of literals such that the two are logically equivalent (they
produce the same set of answers)?

I'd greatly appreciate it if you would give your opinions on this
puzzle.  Answers with theoretical justification are particularly
invaluable.  Working examples of why or why not would be good as well.

Thanks,
SojPetRef

---

Request for Question Clarification by mathtalk-ga on 27 Jan 2005 19:32 PST

Hi, sojpetref-ga:

I'm not clear in what since you mean to translate "findall" into "a
conjunction of literals".  I'm seeing in this statement an echo of the
prior observation about the example that the "goal" is a conjunction
of predicates, ie. p(A),q(A,B),s(B).

One good question might be how to "implement" a findall in pure
Prolog, withour resorting to side-effects like assert, etc.

But I think you are concerned with a completely different issue... right?

regards, mathtalk-ga

---

Clarification of Question by sojpetref-ga on 28 Jan 2005 07:22 PST

Hi Mathtalk,

Thanks for picking up my question.

You pretty much have asked what I intended to ask, only simplier. :-) 
Yup, that's basically what I am looking for--if we can implement
findall using only conjunction of "simple" literals but not resorting
to side effects (and assert is not a "simple" literal anyway since its
argument could be a predicate; it's actually a "meta-predicate").

Regards,
SojPetRef

Hi, SojPetRef:

With some restrictions/variations that may be crucial to a particular
situation, a "pure" Prolog equivalent to findall is possible, though
not efficient.

With a "goal" like:

findall(A,(p(A),q(A,B),s(B)),L)

the Prolog engine succeeds if L unifies with the list of different
values that A binds to on consecutive backtracking invocations on the
compound goal (p(A),q(A,B),s(B)).

Without side-effects it would be impossible to "remember" all of these
bindings as a consequence of a failure driven backtrack directly into
the given goal.

However we can mostly work around that restriction with a recursive
construction as outlined here:

my_findall_pqs(B,L,M) :-
    p(A),q(A,B),s(B),
    not(member(A,L)),
    !,
    my_findall_pqs(B,[A|L],M).

my_findall_pqs(_,M,M).

Essentially the my_findall_pqs builds a list of the distinct values
for A that make the original goal (p(A),q(A,B),s(B)) succeed, calling
itself recursively with a successively longer list of "old" successes
recorded in L.  When no new successes are possible, the predicate
succeeds by binding the last argument to the middle one.

To use this goal we would start it off with an empty list for the
second argument L, and a free variable M for the third argument:

my_findall_pqs(B,[],M).

Some objections are in order.  First the list M here is returned in
opposite order to what would be produced by findall, a fairly
technical point that could be remedied by a call to a list reversing
predicate.  Potentially more important is the absence of duplicate
entries in our version of M.

Second one might object to the use of not( ), as technically this is a
meta-predicate.  However I used it for clarity above.  The
not(member(A,L)) call can be replaced by a custom predicate:

my_not_member(A,L) :-
    member(A,L),
    !,
    fail.

my_not_member(_,_).

Third one might object to the use of "cuts" ! as not pure Prolog. 
Although this objection is not related to meta-predicates versus
regular predicates, of the two places where cuts are used, the
essential one is actually in the replacement my_not_member above
(which would eventually always succeed through backtracking without
the strategically placed cut).  The use of ! in my_findall_pqs is
something of an efficiency matter, allowing for example the
optimization called tail-recursion elimination.

Continuing briefly with the issue of efficiency, the my_findall_pqs
predicate suffers from a quadratic-time overhead, even with
tail-recursion elimination, due to the necessity of revisiting the
sequence of possible bindings for A again and again.

regards, mathtalk-ga

---

Request for Answer Clarification by sojpetref-ga on 29 Jan 2005 13:58 PST

Hi mathtalk,

Very nice answer.  Thanks.  This is really not an answer
clarification.  I am just curious if it'd be possible to go one step
further: not even using recursion.  My gut feeling is that this
wouldn't be possible.

However, you don't have to spend time on this one if you don't want
to.  I'd greatly appreciate it, though.

Thanks again for your effort.

Regards,
SojpetRef

---

Clarification of Answer by mathtalk-ga on 30 Jan 2005 06:50 PST

Hi, SojPetRef:

The use of recursion in constructing a list of "unknown" length seems
inevitable.  Even checking membership of an arbitrary list for
elements satisfying a predicate requires recursion over the list,
although for the simple "is_member(2)" predicate some Prolog
implementations provide a "built-in" version that is more efficient
than recursion (usually at the expense of allowing backtracking
through the list members).

So, I'll stick my neck out and say that unless the circumstances allow
for the length of the "findall" list to be known in advance, the
translation to a recursion-free equivalent is not possible.

regards, mathtalk-ga

Answers are clearly presented.  I particularly appreciate the fact
that the researcher made an effort to look at an issue from both
sides.