View Question
 Question
 Subject: Logic Programming Category: Computers > Programming Asked by: sojpetref-ga List Price: \$4.00 Posted: 26 Jan 2005 08:57 PST Expires: 25 Feb 2005 08:57 PST Question ID: 463674
 ```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```
 sojpetref-ga rated this answer: ```Answers are clearly presented. I particularly appreciate the fact that the researcher made an effort to look at an issue from both sides.```