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.