prologprolog-findall

# Why this predicate is written in this way?

I am having a hard time to understand why the second predicate of findall is written as this instead of collect_found([],L) directly.

``````:- dynamic found/1.
findall(X, G, _) :-
asserta(found(mark)),
call(G),
asserta(found(result(X))),
fail.
findall(_, _, L) :- collect_found([], M), !, L = M.

collect_found(S, L) :-
getnext(X),
!,
collect_found([X|S], L).
collect_found(L, L).

getnext(Y) :- retract(found(X)), !, X = result(Y).
``````

Is there any advantage by writing in this way?

Solution

• (This code is from the 5th edition of Programming in Prolog by Clocksin & Mellish. Since it collides with the built-in `findall/3`, I will use the name `cmfindall/3` for their definition)

First, to answer your question: There is in fact no difference between the code in the book and your suggestion. Thus:

``````cmfindall(_, _, L) :- collect_found([], M), !, L = M.
``````

and

``````cmfindall(_, _, L) :- collect_found([], L).

``````

are (in this very context) the same. To see this, let's look at the definition of `collect_found/2`. What is the role of the second argument in it? To better highlight it, I will remove everything that is not related to the second argument:

``````collect_found(_, L) :-
...,
!,
collect_found(_, L).
collect_found(L, L).
``````

From this we see that the second argument has only an influence at the end when it is unified with the first argument. And thus, there is no need to delay that unification after the goal.

Why was the code written like that? It seems the authors wanted to ensure that the removal of `found/1` facts will always be performed, and (maybe in a previous, pre 1981 version) the second argument was sensitive to being instantiated.

Also note that the authors remark (p.168,2nd par):

Any occurrence of `findall` used within the second argument of another `findall` will be treated correctly.

Now they clearly did not consider:

``````?- catch(cmfindall(Y,(Y=2;throw(ex)),_),ex,false).
false.
?- cmfindall(X,(X=1;catch(cmfindall(Y,(Y=2;throw(ex)),_),ex,false)),Xs).
Xs = [2], unexpected.
Xs = [1]. % expected, but not found
``````

Handling such cases correctly is a pretty dirty job since there is still no agreement between systems which primitives to use to handle them cleanly.