prologswi-prologlogic-programmingwarren-abstract-machineoccurs-check

Does Prolog need GC when the occurs check is globally enabled?


As far as I can tell, with sound unification, SLD resolution should not create cyclic data structures (Is this correct?)

If so, one could, in theory, implement Prolog in such a way that it wouldn't need garbage collection (GC). But then again, one might not.

Specifically:

:- set_prolog_flag(occurs_check, true).
:- set_prolog_flag(gc, false). /* is this safe? */

Solution

  • The creation of cyclic terms is far from being the only operation that can create garbage (as in garbage collection) in Prolog (also worth noting that not all Prolog systems provide comprehensive support for cyclic terms but most of them support some form of garbage collection).

    As an example, assume that you have in your code the following sequence of calls to go from a number to an atom:

    ...,
    number_codes(Number, Codes),
    atom_codes(Atom, Codes),
    ...
    

    Here, Codes is a temporary list that should be garbage collected. Another example, assume that you're calling setof/3 to get an ordered list of results where you're only interested in the first two:

    ...,
    setof(C, x(X), [X1, X2| _]),
    ...
    

    You just created another temporary list. Or that you forgot about sub_atom/5 and decide to use atom_concat/3 to check the prefix of an atom:

    ...,
    atom_concat(Prefix, _, Atom),
    ...
    

    That second argument, the atom suffix that you don't care about (hence the anonymous variable), is a temporary atom that you just created. But not all Prolog systems provide an atom garbage collector, which can lead to trouble in long running applications.

    But even when you think that you have carefully written your code to avoid the creation of temporary terms, the Prolog system may still be creating garbage when running your code. Prolog systems use different memory areas for different purposes, and operations may need to make temporary copies of segments of memory between different memory areas, depending on the implementation. The Prolog system may be written in a language, e.g. Java, that may eventually take care of that garbage. But most likely it's written in C or C++ and some sort of garbage collection is used internally. Not to mention that the Prolog system may be grabbing a big block of memory to be able to prove a query and then reclaiming that memory after the query terminates.