4.10.2 Garbage Collection and Programming Style

The availability of garbage collection can lead to a more natural programming style. Without garbage collection, a procedure that generates global stack garbage may have to be executed in a failure-driven loop. Failure-driven loops minimize global stack usage from iteration to iteration of a loop via SICStus Prolog’s automatic recovery of global stack space on failure. For instance, in the following procedure echo/0 echoes Prolog terms until it reads an end-of-file character. It uses a failure-driven loop to recover inaccessible global stack space.

echo :- repeat, 
        read(Term), 
        echo_term(Term), 
        !.

echo_term(Term) :-
        Term == end_of_file.
echo_term(Term) :-
        writeq(Term), nl, 
        fail.

Any global stack garbage generated by read/1 or write/1 is automatically reclaimed by the failure of each iteration.

Although failure-driven loops are an accepted Prolog idiom, they are not particularly easy to read or understand. So we might choose to write a clearer version of echo/0 using recursion instead, as in

echo :- read(Term), 
        echo_term(Term).

echo_term(Term) :-
        Term == end_of_file, 
        !.
echo_term(Term) :-
        writeq(Term), nl, 
        echo.

Without garbage collection the more natural recursive loop accumulates global stack garbage that cannot be reclaimed automatically. While it is unlikely that this trivial example will run out of global stack space, larger and more practical applications may be unable to use the clearer recursive style without garbage collection. With garbage collection, all inaccessible global stack space will be reclaimed by the garbage collector.

Using recursion rather than failure-driven loops can improve programming style further. We might want to write a predicate that reads terms and collects them in a list. This is naturally done in a recursive loop by accumulating results in a list that is passed from iteration to iteration. For instance,

collect(List) :-
        read(Term), 
        collect_term(Term, List).

collect_term(Term, []) :-
        Term == end_of_file, 
        !.
collect_term(Term, [Term|List0]) :-
        collect(List0).

For more complex applications this sort of construction might prove unusable without garbage collection. Instead, we may be forced to use a failure-driven loop with side-effects to store partial results, as in the following much less readable version of collect/1:

collect(List) :-
        repeat, 
        read(Term), 
        store_term(Term), 
        !, 
        collect_terms(List).

store_term(Term) :-
        Term == end_of_file.

store_term(Term) :-
        assertz(term(Term)), 
        fail.   

collect_terms([M|List]) :-
        retract(term(M)), 
        !, 
        collect_terms(List).
collect_terms([]).

The variable bindings made in one iteration of a failure-driven loop are unbound on failure of the iteration. Thus partial results cannot simply be stored in a data structure that is passed along to the next iteration. We must instead resort to storing partial results via side-effects (here, assertz/1) and collect (and clean up) partial results in a separate pass. The second example is much less clear to most people than the first. It is also much less efficient than the first. However, if there were no garbage collector, then larger examples of the second type might be able to run where those of the first type would run out of memory.



Send feedback on this subject.