prologenumerationprolog-toplevelprolog-dif

Creating and working with an explicit list vs enumeration through fail


I come up against this all the time, and I'm never sure which way to attack it. Below are two methods for processing some season facts.

What I'm trying to work out is whether to use method 1 or 2, and what are the pros and cons of each, especially large amounts of facts.

methodone seems wasteful since the facts are available, why bother building a list of them (especially a large list). This must have memory implications too if the list is large enough ? And it doesn't take advantage of Prolog's natural backtracking feature.

methodtwo takes advantage of backtracking to do the recursion for me, and I would guess would be much more memory efficient, but is it good programming practice generally to do this? It's arguably uglier to follow, and might there be any other side effects?

One problem I can see is that each time fail is called, we lose the ability to pass anything back to the calling predicate, eg. if it was methodtwo(SeasonResults), since we continually fail the predicate on purpose. So methodtwo would need to assert facts to store state.

Presumably(?) method 2 would be faster as it has no (large) list processing to do?

I could imagine that if I had a list, then methodone would be the way to go.. or is that always true? Might it make sense in any conditions to assert the list to facts using methodone then process them using method two? Complete madness?

But then again, I read that asserting facts is a very 'expensive' business, so list handling might be the way to go, even for large lists?

Any thoughts? Or is it sometimes better to use one and not the other, depending on (what) situation? eg. for memory optimisation, use method 2, including asserting facts and, for speed use method 1?

season(spring).
season(summer).
season(autumn).
season(winter).

 % Season handling
showseason(Season) :-
    atom_length(Season, LenSeason),
    write('Season Length is '), write(LenSeason), nl.

% -------------------------------------------------------------
% Method 1 - Findall facts/iterate through the list and process each
%--------------------------------------------------------------
% Iterate manually through a season list
lenseason([]).
lenseason([Season|MoreSeasons]) :-
    showseason(Season),
    lenseason(MoreSeasons).
    

% Findall to build a list then iterate until all done
methodone :-
    findall(Season, season(Season), AllSeasons),
    lenseason(AllSeasons),
    write('Done').
    
% -------------------------------------------------------------
% Method 2 - Use fail to force recursion
%--------------------------------------------------------------
methodtwo :-
    % Get one season and show it
    season(Season),
    showseason(Season),
    
    % Force prolog to backtrack to find another season
    fail.

% No more seasons, we have finished
methodtwo :-
    write('Done').

Solution

  • method one seems wasteful since the facts are available, why bother building a list of them (especially a large list). This must have memory implications too if the list is large enough ?

    Yes, method 1 takes Θ(n) memory. It's primary benefit is that it is declarative, i.e. it has a straightforward logical meaning.

    Method 2, the "failure-driven loop" as Prolog programmers call it, takes constant memory, is procedural and may be preferred when you're doing procedural (extra-logical) things anyway; i.e., in I/O code it's ok to use it.

    Note that SWI-Prolog has a third way of writing this loop:

    forall(season(S), showseason(S)).
    

    This only works if showseason succeeds for each binding of season(S).