Quintus Prolog uses three data areas: program space, local stack space, and global stack space. Each of these areas is automatically expanded if it overflows; if necessary, the other areas are shifted to allow this.
The local stack contains all the control information and variable bindings needed in a Prolog execution. Space on the local stack is reclaimed on determinate success of predicates and by tail recursion optimization, as well as on backtracking.
The global stack space contains the heap (also known as the global
stack) and the trail. The heap contains all the data
structures constructed in an execution of the program, and the trail
contains references to all the variables that need to be reset when
backtracking occurs. Both of these areas grow with forward execution
and shrink on backtracking. These fluctuations can be monitored by
statistics/[0,2].
The program space contains compiled and interpreted code, recorded terms, and atoms. The space occupied by compiled code, interpreted code, and recorded terms is recovered when it is no longer needed; the space occupied by atoms that are no longer in use can be recovered by atom garbage collection described in ref-mgc-ago.
Quintus Prolog uses the heap to construct compound terms, including lists. Heap space is used as Prolog execution moves forward. When Prolog backtracks, it automatically reclaims space on the heap. However, if a program uses a large amount of space before failure and backtracking occur, this type of reclamation may be inadequate.
Without garbage collection, the Prolog system must attempt to expand the heap whenever a heap overflow occurs. To do this, it first requests additional space from the operating system. If no more space is available, the Prolog system attempts to allocate unused space from the other Prolog data areas. If additional space cannot be found, a resource error is raised.
Heap expansion and abnormal termination of execution due to lack of heap space can occur even if there are structures in the heap that are no longer accessible to the computation (these structures are what is meant by "garbage"). The proportion of garbage to non-garbage terms varies during execution and with the Prolog code being executed. The heap may contain no garbage at all, or may be nearly all garbage.
The garbage collector periodically reclaims inaccessible heap space, reducing the need for heap expansion and lessening the likelihood of running out of heap. When the garbage collector is enabled (as it is by default), the system makes fewer requests to the operating system for additional space. The fact that less space is required from the operating system can produce a substantial savings in the time taken to run a program, because paging overhead can be much less.
For example, without garbage collection, compiling a file containing the sequence
p(_) :- p([a]).
:- p(_).
causes the heap to expand until the Prolog process eventually runs out of
space. With garbage collection enabled, the above sequence
continues indefinitely. The list built on the heap by each recursive
call is inaccessible to future calls (since p/1 ignores its argument)
and can be reclaimed by the garbage collector.
Garbage collection does not guarantee freedom from out-of-space errors, however. Compiling a file containing the sequence
p(X) :- p([X]).
:- p(a).
expands the heap until the Prolog process eventually runs out of space. This happens in spite of the garbage collector, because all the terms built on the heap are accessible to future computation and cannot be reclaimed.